Демонстрация работы алгоритма.
Демонстрация работы алгоритма.

Волновой алгоритм — это алгоритм поиска пути, который использует волновое распространение для определения кратчайшего пути от начальной вершины до целевой вершины.

В этой статье мы не будем рассматривать основной принцип данного алгоритма (поиск кратчайшего пути), а лишь обратимся к идее волнового алгоритма. Название алгоритма происходит от способа распространения, напоминающего распространение волн.


Идея

Состояние карты для игры «Сапер» будем хранить в виде матрицы. Матрица может содержать следующие значения:

  1. Может принимать значения от 0 до 8, если эта клетка не содержит бомбу.

  2. Может принимать заранее определённое значение для бомбы.

Вот несколько понятий, которые будут использоваться в этой статье:

  1. Пустая ячейка — это ячейка, значение которой равно нулю.

  2. Непустая ячейка — это ячейка, в которой содержится число от 1 до 8 или знак бомбы.

Мы не будем рассматривать этапы генерации бомб и подсчета их вокруг каждой клетки, поскольку это не является основной темой данной статьи.

Идея использования волнового алгоритма в этой задаче заключается в последовательном открытии ячеек (волна за волной), пока это возможно.

Рассмотрим поведение случайного «Сапера» из интернета
Поведение раскрытия клеток при попадании в пустую ячейку.
Поведение раскрытия клеток при попадании в пустую ячейку.

Если требуется открыть ячейку, а под ней находится пустая ячейка, то текущая и все остальные пустые ячейки, до которых можно добраться из исходной, будут открыты. Также будут открыты все соседние ячейки, которые не являются пустыми.

Поведение раскрытия клеток при попадании в непустую ячейку.
Поведение раскрытия клеток при попадании в непустую ячейку.

Если необходимо было открыть ячейку, а под ней оказалась непустая ячейка, то единственное, что нужно сделать — это открыть её и завершить алгоритм.

В игре «Сапер» используется окрестность Мура.

Окрестность Мура

В двумерном случае — совокупность восьми клеток на квадратном паркете, имеющих общую вершину с данной клеткой. Окрестность получила своё название в честь одного из пионеров теории клеточных автоматов Эдварда Мура.

Окрестность Мура
Окрестность Мура


Алгоритм

Волновой алгоритм работает следующим образом:

  1. Распространение начинается с заданной точки или группы точек.

  2. От исходной точки происходит распространение на глубину в одну ячейку.

  3. Все новые ячейки, которые попадают в зону распространения, становятся частью «новой» волны.

  4. В конце процесса значения из «новой» волны присваиваются «старой», и от неё начинается новый цикл распространения.

В классическом «Волновом алгоритме» при каждом распространении вычислялось значение, которое представляло собой кратчайшее расстояние от начальной точки до текущей. В данной задаче в этом нет необходимости, так как мы не стремимся найти кратчайший путь. Вместо этого, каждая ячейка, попавшая под распространение, будет открываться. Это делается для того, чтобы алгоритм не зацикливался и посещенные ячейки больше не попадали под распространение.

В целом, как и в классическом «Волновом алгоритме», в нашем случае в процесс распространения будут вовлечены только пустые ячейки, а препятствия, то есть непустые ячейки, останутся без внимания.

Пример последовательной работы алгоритма раскрытия ячеек
Пример последовательной работы алгоритма раскрытия ячеек

На иллюстрации выше приведены следующие условные обозначения:

  1. Символ точки представляет собой пустую ячейку.

  2. Символ белого квадрата — это закрытая ячейка.

  3. Символы собачки и чисел от 1 до 8 обозначают непустые ячейки.

  4. Точка внутри красного квадрата — это волна, от которой будет происходить распространение.

  5. Белый квадрат внутри зелёного квадрата указывает на возможные ячейки, которые могут попасть под воздействие волны. Это соседние клетки с ячейками, участвующими в распространении.

В качестве соседей для каждой ячейки распространения рассматриваются только закрытые ячейки. (см. Условные обозначения п.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

Комментарии (2)


  1. Ingulf
    07.11.2024 18:53

    я так понимаю задача чисто применить алгоритм? как обход препятствий в виде бомб
    сейчас при обходе известно очень много информации о клетках (особенно это верно о непосещенных клетках)
    было бы интересно усложнить задачу до решателя игры сапёр волновым алгоритмом


    1. tonitaga Автор
      07.11.2024 18:53

      Данная статья рассматривается со стороны "разработчика" игры. Поэтому конечно все данные известны.

      А так да, было бы интересно рассмотреть со стороны "игрока"