Генератор лабиринтов на основе алгоритма Уилсона

Алгоритм Уилсона — это метод случайного блуждания со стиранием циклов, который генерирует однородные остовные деревья для создания лабиринтов. Это означает, что все возможные лабиринты заданного размера с одинаковой вероятностью будут сгенерированы, что делает его беспристрастным методом генерации лабиринтов. Алгоритм Уилсона можно считать улучшенной версией алгоритма Олдоса-Бродера, поскольку он генерирует лабиринты с идентичными характеристиками, но он работает намного быстрее, поэтому я не стал реализовывать здесь алгоритм Олдоса-Бродера.

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

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

Об алгоритме Уилсона

Алгоритм Уилсона для генерации однородных остовных деревьев с использованием случайной стены со стиранием циклов был создан Дэвидом Брюсом Уилсоном.

Первоначально Уилсон представил этот алгоритм в 1996 году, исследуя случайные остовные деревья и цепи Маркова в теории вероятностей. Хотя его работа была в основном в области математики и статистической физики, с тех пор алгоритм широко использовался для генерации лабиринтов из-за его способности создавать идеально однородные лабиринты.

Как работает алгоритм Уилсона для генерации лабиринтов

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

Шаг 1: Инициализация

• Начните с сетки, заполненной стенами.
• Определите список всех возможных ячеек прохода.

Шаг 2: Выберите случайную начальную ячейку

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

Шаг 3: Случайный обход со стиранием цикла

• Выберите не посещенную ячейку и начните случайное блуждание (перемещение в случайных направлениях).
• Если путь достигает уже посещенной ячейки, сотрите все петли на пути.
• Как только маршрут приведет вас к посещенному региону, отметьте все ячейки на пути как посещенные.

Шаг 4: Повторяйте, пока не будут посещены все ячейки :

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

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

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

• Генератор лабиринтов «Охота и убийство»
• Генератор лабиринта алгоритма Эллера
• Генератор лабиринтов с алгоритмом растущего дерева