Генератор лабиринтов «Охота и убийство»

Алгоритм «Охота и уничтожение» — это, по сути, модифицированная версия рекурсивного алгоритма с возвратом. Модификация заключается в систематическом сканировании (или «охоте») за новой ячейкой, с которой можно продолжить, когда дальнейшее движение невозможно, в отличие от истинного рекурсивного поиска, который всегда возвращается к предыдущей ячейке в стеке.

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

Идеальный лабиринт - это лабиринт, в котором есть ровно один путь из любой точки лабиринта в любую другую точку. Это значит, что вы не сможете ходить по кругу, но часто будете сталкиваться с тупиками, вынужденными разворачиваться и идти обратно.

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

Об алгоритме охоты и убийства

Алгоритм «Охота и убийство» — это простой, но эффективный метод генерации лабиринтов. Он чем-то похож на поиск в глубину (т.е. на алгоритм рекурсивного возврата), за исключением того, что когда он не может продвинуться дальше от текущей позиции, он систематически сканирует (или «охотится») по лабиринту, чтобы найти новую ячейку для дальнейшего продвижения. Алгоритм состоит из двух основных фаз: ходьбы и охоты.

Как работает алгоритм «Охота и убийство» для генерации лабиринтов

Шаг 1: Начните с произвольной ячейки.

• Найдите случайную ячейку в сетке и отметьте её как посещённую.

Шаг 2: Этап ходьбы (случайное блуждание)

• Выберите случайного соседа, которого вы еще не посещали.
• Переместитесь к соседней ячейке, отметьте её как посещённую и проложите путь между предыдущей и новой ячейками.
• Повторяйте этот процесс, пока не останется ни одного непосещенного соседа.

Шаг 3: Этап поиска (возвращение назад путем сканирования)

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

Дополнительное чтение

Если вам понравился этот пост, вам также могут понравиться эти предложения:

• Генератор лабиринтов по алгоритму Крускала
• Рекурсивный генератор лабиринтов с обратным отслеживанием
• Генератор лабиринтов на основе алгоритма Уилсона