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

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

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

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

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

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

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

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

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

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

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