Волновой алгоритм — это алгоритм поиска пути, который использует волновое распространение для определения кратчайшего пути от начальной вершины до целевой вершины.
В этой статье мы не будем рассматривать основной принцип данного алгоритма (поиск кратчайшего пути), а лишь обратимся к идее волнового алгоритма. Название алгоритма происходит от способа распространения, напоминающего распространение волн.
Идея
Состояние карты для игры «Сапер» будем хранить в виде матрицы. Матрица может содержать следующие значения:
Может принимать значения от 0 до 8, если эта клетка не содержит бомбу.
Может принимать заранее определённое значение для бомбы.
Вот несколько понятий, которые будут использоваться в этой статье:
Пустая ячейка — это ячейка, значение которой равно нулю.
Непустая ячейка — это ячейка, в которой содержится число от 1 до 8 или знак бомбы.
Мы не будем рассматривать этапы генерации бомб и подсчета их вокруг каждой клетки, поскольку это не является основной темой данной статьи.
Идея использования волнового алгоритма в этой задаче заключается в последовательном открытии ячеек (волна за волной), пока это возможно.
Рассмотрим поведение случайного «Сапера» из интернета
Если требуется открыть ячейку, а под ней находится пустая ячейка, то текущая и все остальные пустые ячейки, до которых можно добраться из исходной, будут открыты. Также будут открыты все соседние ячейки, которые не являются пустыми.
Если необходимо было открыть ячейку, а под ней оказалась непустая ячейка, то единственное, что нужно сделать — это открыть её и завершить алгоритм.
В игре «Сапер» используется окрестность Мура.
Окрестность Мура
В двумерном случае — совокупность восьми клеток на квадратном паркете, имеющих общую вершину с данной клеткой. Окрестность получила своё название в честь одного из пионеров теории клеточных автоматов Эдварда Мура.
Алгоритм
Волновой алгоритм работает следующим образом:
Распространение начинается с заданной точки или группы точек.
От исходной точки происходит распространение на глубину в одну ячейку.
Все новые ячейки, которые попадают в зону распространения, становятся частью «новой» волны.
В конце процесса значения из «новой» волны присваиваются «старой», и от неё начинается новый цикл распространения.
В классическом «Волновом алгоритме» при каждом распространении вычислялось значение, которое представляло собой кратчайшее расстояние от начальной точки до текущей. В данной задаче в этом нет необходимости, так как мы не стремимся найти кратчайший путь. Вместо этого, каждая ячейка, попавшая под распространение, будет открываться. Это делается для того, чтобы алгоритм не зацикливался и посещенные ячейки больше не попадали под распространение.
В целом, как и в классическом «Волновом алгоритме», в нашем случае в процесс распространения будут вовлечены только пустые ячейки, а препятствия, то есть непустые ячейки, останутся без внимания.
На иллюстрации выше приведены следующие условные обозначения:
Символ точки представляет собой пустую ячейку.
Символ белого квадрата — это закрытая ячейка.
Символы собачки и чисел от 1 до 8 обозначают непустые ячейки.
Точка внутри красного квадрата — это волна, от которой будет происходить распространение.
Белый квадрат внутри зелёного квадрата указывает на возможные ячейки, которые могут попасть под воздействие волны. Это соседние клетки с ячейками, участвующими в распространении.
В качестве соседей для каждой ячейки распространения рассматриваются только закрытые ячейки. (см. Условные обозначения п.2). Это нужно для того чтобы алгоритм не зациклился.
Реализация
С++
class MapOpener final
{
public:
MapOpener(const mtlt::matrix<std::size_t> &map,
mtlt::matrix<bool> &opened)
: m_map(map)
, m_opened(opened)
{};
public:
std::size_t Open(const Point tap_point);
private:
void HandleCell(std::size_t row, std::size_t col);
void HandleNeighbors(std::size_t row, std::size_t col);
private:
const mtlt::matrix<std::size_t> &m_map;
mtlt::matrix<bool> &m_opened;
std::vector<Point> m_old_wave;
std::vector<Point> m_new_wave;
std::size_t m_opened_cells;
};
} // namespace minesweeper
Класс MapOpener содержит ссылки на матрицу игры «Сапер» и на матрицу, описывающую состояние каждой ячейки. Это позволяет создать объект данного класса один раз и использовать его на протяжении всего времени работы программы.
namespace minesweeper
{
std::size_t MapOpener::Open(const Point tap_point)
{
m_opened(tap_point.row, tap_point.col) = true;
m_opened_cells = 1;
const std::size_t kTapValue = m_map(tap_point.row, tap_point.col);
/**
* Если это непустая ячейка то просто открываем ячейку и выходим
*/
if (kTapValue == values::g_Bomb || kTapValue != values::g_Empty)
return m_opened_cells;
m_old_wave.clear();
m_old_wave.push_back(tap_point);
while (!m_old_wave.empty())
{
/**
* Обрабатываем последовательно ячейки распространения
*/
for (const auto [row, col] : m_old_wave)
HandleNeighbors(row, col);
/**
* После обработки распространения,
* новое распространения перемещается в старое
*/
m_old_wave = std::move(m_new_wave);
}
return m_opened_cells;
}
void MapOpener::HandleCell(std::size_t row, std::size_t col)
{
/**
* Открытая ячейка не попадает в распространение
*/
if (m_opened(row, col))
return;
/**
* Закрытая ячейка открывается.
* Это необходимо для исключения попадания уже посещенных ячеек
*/
m_opened(row, col) = true;
m_opened_cells++;
/**
* В распространение попадают только пустые ячейки
*/
if (m_map(row, col) == values::g_Empty)
m_new_wave.emplace_back(row, col);
}
void MapOpener::HandleNeighbors(std::size_t row, std::size_t col)
{
const std::size_t kRows = m_map.rows();
const std::size_t kCols = m_map.cols();
if (row > 0 && col > 0) /* Ячейка сверху-слева */
HandleCell(row - 1, col - 1);
if (row > 0) /* Ячейка сверху */
HandleCell(row - 1, col);
if (row > 0 && col + 1 < kCols) /* Ячейка сверху-справа */
HandleCell(row - 1, col + 1);
if (col + 1 < kCols) /* Ячейка справа */
HandleCell(row, col + 1);
if (row + 1 < kRows && col + 1 < kCols) /* Ячейка снизу-справа */
HandleCell(row + 1, col + 1);
if (row + 1 < kRows) /* Ячейка снизу */
HandleCell(row + 1, col);
if (row + 1 < kRows && col > 0) /* Ячейка снизу-слева */
HandleCell(row + 1, col - 1);
if (col > 0) /* Ячейка слева */
HandleCell(row, col - 1);
}
} // namespace minesweeper
Пример использования
int main()
{
// ...
MapOpener map_opener(map, opened);
// ...
while (true)
{
// ...
std::size_t opened_count = map_opener.Open(current_tap_point);
// ...
Draw(map, opened);
}
}
Подробнее прочитать про "Волновой алгоритм" можно прочитать здесь и здесь
Для матриц использовалась данная библиотека