Волновой алгоритм — это алгоритм поиска пути, который использует волновое распространение для определения кратчайшего пути от начальной вершины до целевой вершины.
В этой статье мы не будем рассматривать основной принцип данного алгоритма (поиск кратчайшего пути), а лишь обратимся к идее волнового алгоритма. Название алгоритма происходит от способа распространения, напоминающего распространение волн.
Идея
Состояние карты для игры «Сапер» будем хранить в виде матрицы. Матрица может содержать следующие значения:
-
Может принимать значения от 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); } }Подробнее прочитать про «Волновой алгоритм» можно прочитать здесь и здесь
Для матриц использовалась данная библиотека
Нурислам Губайдуллин (tonitaga) School21
ссылка на оригинал статьи https://habr.com/ru/articles/856546/
Добавить комментарий