Рекурсивный генератор лабиринтов с обратным отслеживанием

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

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

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

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

Несмотря на название, рекурсия не обязательно должна быть реализована с использованием рекурсии. Часто она реализуется итеративным методом с использованием очереди LIFO (то есть стека). Для очень больших лабиринтов использование рекурсии с большей вероятностью приведет к переполнению стека вызовов, в зависимости от языка программирования и доступной памяти. Очередь LIFO легче адаптировать для обработки больших объемов данных, даже храня очередь на диске или в базе данных, если доступной памяти недостаточно.

Как это работает

Алгоритм работает с использованием подхода поиска в глубину на основе стека. Вот пошаговое описание:

1. Выберите начальную ячейку и отметьте её как посещённую.
2. Пока есть непосещенные ячейки: Посмотрите на соседние ячейки, которые еще не были посещены. Если существует хотя бы один непосещенный сосед: Случайно выберите одного из непосещенных соседей. Уберите стену между текущей ячейкой и выбранным соседом. Переместитесь к выбранному соседу и отметьте его как посещенный. Поместите текущую ячейку в стек. Если непосещенных соседей нет: Вернитесь назад, удалив последнюю ячейку из стека.
3. Продолжайте этот процесс, пока стек не опустеет.

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

На самом деле, на этом сайте у меня используются две версии этого алгоритма: одна основана на алгоритме LIFO (последний вошел — первый вышел) для генерации лабиринтов на этой странице, а другая — на рекурсии для решения лабиринтов, в том числе и тех, которые генерируются другими алгоритмами (так создаются карты с решениями). Наличие двух разных версий — это просто развлечение, потому что я — зануда, которому это интересно, хотя любая из них могла бы подойти для обоих случаев ;-)

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

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

• Генератор лабиринта алгоритма Эллера
• Генератор лабиринтов с алгоритмом растущего дерева
• Генератор лабиринтов по алгоритму Крускала