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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 3: Случайное блуждание с удалением циклов

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

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

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

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

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

• Генератор лабиринта алгоритма Эллера
• Рекурсивный генератор лабиринтов с обратным отслеживанием
• Генератор лабиринтов «Охота и убийство»