Применение «Волнового алгоритма» для игры «Сапер»06.11.2024 16:16

class MapOpener final
{
public:
    MapOpener(const mtlt::matrix &map,
              mtlt::matrix &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 &m_map;
    mtlt::matrix &m_opened;

    std::vector m_old_wave;
    std::vector 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);
    }
}