Vista Minesweeper Gameover раскрывает алгоритм

Question

Я пытаюсь сделать перспективного клона тральщика. Прямо сейчас мой алгоритм раскрытия - это каскадный алгоритм. Это выглядит как квадрат, который становится все больше и больше. В vista mnesweeper я заметил, что когда игра заканчивается, она циклически перебирает игру, чтобы раскрыть мины. Кто-нибудь знает, как называется этот алгоритм? Спасибо

Answer 1

Ближайшее официальное название, которое я мог найти для описываемого вами алгоритма, - "Прямоугольный спиральный поиск" , который представляет собой алгоритм, который выводит путь, по которому следует полностью сканировать сетку по спирали. 1003 *

Простой алгоритм сканирования по часовой стрелке квадратной сетки размером (2N + 1) ^ 2, N> 0 будет выглядеть так:

(Предполагая, что координата (0,0) сетки находится в нижнем левом углу сетки)

1. Начало в центральной ячейке сетки (N, N)
2. Переместиться влево (-1,0) для следующей ячейки
3. Установить направление движения вверх (0, + 1)
4. Хотя текущая ячейка (X, Y) не является углом (то есть (X-N) ^ 2 == (Y-N) ^ 2), двигайтесь в заданном направлении
5. Если текущая ячейка не в (0,0)
   6. Поверните направление по часовой стрелке
      • (0, + 1) становится (+1,0)
      • (+ 1,0) -> (0, -1)
      • (0, -1) -> (-1,0)
      • (- 1,0) -> (0, + 1))
   7. Один раз двигаться в новом направлении
   8. Перейти к шагу 4
6. Если текущая ячейка (0,0), все готово

Для сеток (2N) ^ 2 и неквадратных необходимо настроить первые 3 шага.

Реализация для квадратных сеток доступна для Perl в объекте Spiral модуля Array-Tour.