Генератор лабиринтов на основе алгоритма Уилсона
Опубликовано: 16 февраля 2025 г. в 19:33:27 UTC
Генератор лабиринтов, использующий алгоритм Уилсона для создания идеального лабиринта. Этот алгоритм генерирует все возможные лабиринты заданного размера с одинаковой вероятностью, поэтому теоретически он может генерировать лабиринты многих смешанных макетов, но поскольку возможных лабиринтов с более короткими коридорами больше, чем с более длинными, вы будете чаще их видеть.Wilson's Algorithm Maze Generator
Алгоритм Уилсона — это метод случайного блуждания со стиранием циклов, который генерирует однородные остовные деревья для создания лабиринтов. Это означает, что все возможные лабиринты заданного размера с одинаковой вероятностью будут сгенерированы, что делает его беспристрастным методом генерации лабиринтов. Алгоритм Уилсона можно считать улучшенной версией алгоритма Олдоса-Бродера, поскольку он генерирует лабиринты с идентичными характеристиками, но он работает намного быстрее, поэтому я не стал реализовывать здесь алгоритм Олдоса-Бродера.
Идеальный лабиринт - это лабиринт, в котором есть ровно один путь из любой точки лабиринта в любую другую точку. Это значит, что вы не сможете ходить по кругу, но часто будете сталкиваться с тупиками, вынужденными разворачиваться и идти обратно.
Созданные здесь карты лабиринтов включают в себя версию по умолчанию без стартовых и финишных позиций, так что вы можете решить их сами: из любой точки лабиринта в любую другую найдется решение. Если вам нужно вдохновение, вы можете включить предлагаемые стартовую и финишную позиции - и даже увидеть решение между ними.
Об алгоритме Уилсона
Алгоритм Уилсона для генерации однородных остовных деревьев с использованием случайной стены со стиранием циклов был создан Дэвидом Брюсом Уилсоном.
Первоначально Уилсон представил этот алгоритм в 1996 году, исследуя случайные остовные деревья и цепи Маркова в теории вероятностей. Хотя его работа была в основном в области математики и статистической физики, с тех пор алгоритм широко использовался для генерации лабиринтов из-за его способности создавать идеально однородные лабиринты.
Как работает алгоритм Уилсона для генерации лабиринтов
Алгоритм Уилсона гарантирует, что конечный лабиринт будет полностью связным и не будет содержать петель, путем итеративного вырезания путей из непосещенных ячеек с использованием случайных блужданий.
Шаг 1: Инициализация
- Начните с сетки, заполненной стенами.
- Определите список всех возможных ячеек прохода.
Шаг 2: Выберите случайную начальную ячейку
- Выберите любую случайную ячейку и отметьте ее как посещенную. Это служит отправной точкой лабиринта во время генерации.
Шаг 3: Случайный обход со стиранием цикла
- Выберите не посещенную ячейку и начните случайное блуждание (перемещение в случайных направлениях).
- Если путь достигает уже посещенной ячейки, сотрите все петли на пути.
- Как только маршрут приведет вас к посещенному региону, отметьте все ячейки на пути как посещенные.
Шаг 4: Повторяйте, пока не будут посещены все ячейки :
- Продолжайте выбирать непосещенные ячейки и выполнять случайные обходы, пока каждая ячейка не станет частью лабиринта.