Генератор лабиринтов «Охота и убийство»
Опубликовано: 16 февраля 2025 г. в 20:56:28 UTC
Генератор лабиринтов, использующий алгоритм Hunt and Kill для создания идеального лабиринта. Этот алгоритм похож на Recursive Backtracker, но имеет тенденцию генерировать лабиринты с несколько менее длинными, извилистыми коридорами.Hunt and Kill Maze Generator
Алгоритм Hunt and Kill на самом деле является модифицированной версией Recursive Backtracker. Модификация заключается в систематическом сканировании (или «охоте») на новую ячейку для продолжения, когда она не может двигаться дальше, в отличие от настоящего рекурсивного поиска, который всегда возвращается к предыдущей ячейке в стеке.
Из-за этого этот алгоритм можно легко адаптировать для создания лабиринтов с другим внешним видом и ощущением, просто выбрав входить в режим «охоты» чаще или в соответствии с определенными правилами. Версия, реализованная здесь, входит в режим «охоты» только тогда, когда она не может двигаться дальше от текущей ячейки.
Идеальный лабиринт - это лабиринт, в котором есть ровно один путь из любой точки лабиринта в любую другую точку. Это значит, что вы не сможете ходить по кругу, но часто будете сталкиваться с тупиками, вынужденными разворачиваться и идти обратно.
Созданные здесь карты лабиринтов включают в себя версию по умолчанию без стартовых и финишных позиций, так что вы можете решить их сами: из любой точки лабиринта в любую другую найдется решение. Если вам нужно вдохновение, вы можете включить предлагаемые стартовую и финишную позиции - и даже увидеть решение между ними.
Об алгоритме «охоты и убийства»
Алгоритм Hunt and Kill — это простой, но эффективный метод генерации лабиринтов. Он чем-то похож на поиск в глубину (т. е. алгоритм Recursive Backtracker), за исключением того, что когда он не может продвинуться дальше от текущей позиции, он систематически сканирует (или «охотится») лабиринт, чтобы найти новую ячейку, с которой можно продолжить. Алгоритм состоит из двух основных фаз: ходьба и охота.
Как работает алгоритм «охоты и убийства» для генерации лабиринтов
Шаг 1: Начните со случайной ячейки.
- Найдите случайную ячейку в сетке и отметьте ее как посещенную.
Шаг 2: Фаза ходьбы (случайная прогулка)
- Выберите случайного соседа, к которому вы еще не заходили.
- Перейдите к этому соседу, отметьте его как посещенный и проложите путь между предыдущей и новой ячейкой.
- Повторяйте до тех пор, пока не останется ни одного не посещенного соседа.
Шаг 3: Фаза поиска (возврат с помощью сканирования)
- Просматривайте сетку строка за строкой (или столбец за столбцом).
- Найдите первую непосещенную ячейку, у которой есть хотя бы один посещенный сосед.
- Подключите эту ячейку к посещенному соседу, чтобы возобновить фазу ходьбы.
- Повторяйте, пока не будут посещены все ячейки.