“Сапёр”. Алгоритм поиска соседних клеток, не содержащих мин или цифр

#javascript #алгоритм

Стандартный "сапер". Поле 16 на 16 клеток. 20 мин на поле.

При первом нажатии игрок заведомо не попадает на клетку с миной. Он попадает либо
на пустую клетку, либо на клетку, содержащую информацию о количестве мин вокруг. Назовем
ее клеткой с цифрой. 

Если игрок кликнул на клетку с цифрой - открываем только ее. Если игрок кликнул на
полностью пустую клетку, то кроме этой самой клетки требуется открыть все (related,
не могу перевод подобрать. Соединенные что ли) клетки включая те, которые содержат
в себе цифру, но не дальше их. Что-то типа такого:



Игрок кликнул на зеленую точку. В красных содержатся мины. Желтые содержат в себе
цифры. Фиолетовые отображают те клетки, которые должны быть открыты вместе с зеленой.
(Да, на некоторых из желтых фиолетовые отметки неслучайны, те тоже должны быть открыты).

Собственно, интересует алгоритм поиска этих самых фиолетовых клеток.
Также, если есть какие-то тонкости реализации именно относительно JavaScript, то
тоже буду рад выслушать.
    

Ответы

Ответ 1

Самый простой алгоритм:

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

Если не пустая - ничего не делать.

Псевдокод

функция Проверить ячейку (ячейка)
    если ячейка проверерена -> выход
    если ячейка не пустая -> выход

    Отметить, что ячейка проверена, чтобы не проверять дважды.

    Проверить ячейку сверху если есть
    Проверить ячейку снизу если есть
    Проверить ячейку слева если есть
    Проверить ячейку справа если есть
конец функции


Вариант без рекурсии:

функция Проверить ячейку (ячейку)
    если ячейка не пустая -> выход

    получить ячейки для проверки <- [
        ячейка сверху если есть
        ячейка снизу если есть
        ячейка слева если есть
        ячейка справа если есть
    ] // смежные

    Пока есть ячейки для проверки:

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

конец функции


Ответ 2

допустим есть nums(point) - возвращает 0 на фиолетовых и >0 на остальных.
допустим есть dist(pointA, pointB) - (float) возвращает расстояние между клеточками.
допустим есть closedPoints - это массив ещё не открытых клеточек

// для волн сбора фиолетовых клеток до кучи
function nearestPinc(pointA, openList) {
   function okDist(pointB) {
        return dist(pointA, pointB) == 1;
   }
   // клетка пустая(фиолетовая) и она близка к pointA
   if (nums(pointA) == 0 && openList.find(okDist)) {
      openList.push(pointA);
   }
   return openList;
}

// для последней волны сбора жёлтых клеток
function nearestYellow(pointA, openList) {
   function okDist(pointB) {
        return dist(pointA, pointB) < 2;
   }
   // клетка близка к pointA
   if (openList.find(okDist)) {
      openList.push(pointA);
   }
   return openList;
}

function getOpenList(point) {
   let openList = [point];
   if (nums(point) > 0) // ткнули в жёлтую
      return openList;
   // собираем все повязанные фиолетовые клеточки
   let L = openList.length;
   // пока находим фиолетовые клетки достаточно близкие к уже найденным
   while (L < (openList = closedPoints.reduce(nearestPinc, openList)).length) {
      L = openList.length;
   }
   return closedPoints.reduce(nearestYellow, openList)
}