Генератор рекурсивних лабіринтів Backtracker

Алгоритм рекурсивного зворотного трекера насправді є пошуком загальної мети за глибину. Коли використовується для генерації лабіринту, він дещо змінений для випадкового вибору шляху, тоді як якщо використовується для реальних цілей пошуку, зазвичай просто шукають кожен рівень у лінійному порядку. Він має тенденцію виробляти лабіринти з довгими, звивистими коридорами і дуже довгим, звивистим рішенням.

Ідеальний лабіринт - це лабіринт, в якому існує рівно один шлях з будь-якої точки лабіринту в будь-яку іншу точку. Це означає, що ви не можете ходити по колу, але часто будете стикатися з глухими кутами, що змусить вас розвернутися і повернутися назад.

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

Алгоритм рекурсивного зворотного трекера — це метод пошуку на глибині для створення ідеальних лабіринтів (лабіринтів без петель і одного шляху між будь-якими двома точками). Він простий, ефективний і створює візуально привабливі лабіринти з довгими звивистими коридорами.

Незважаючи на свою назву, вона не обов'язково повинна бути реалізована за допомогою рекурсії. Це часто реалізується в ітераційному підході з використанням черги LIFO (тобто стека). Для дуже великих лабіринтів використання рекурсії з більшою ймовірністю призведе до переповнення стека викликів, залежно від мови програмування та доступної пам'яті. Чергу LIFO можна легше адаптувати для обробки великих обсягів даних, навіть зберігаючи чергу на диску або в базі даних, якщо доступної пам'яті недостатньо.

Як це працює

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

1. Виберіть початкову клітинку та позначте її як відвідану.
2. Поки є невідвідані клітини:
   • Подивіться на сусідні клітини, які ще не відвідали.
   • Якщо існує хоча б один невідвіданий сусід:
     • Випадковим чином виберіть одного з невідвіданих сусідів.
     • Видаліть стінку між поточною кліткою і обраним сусідом.
     • Перейдіть до обраного сусіда і позначте його як відвіданий.
     • Перемістіть поточну клітинку в стек.
   • Якщо невідвіданих сусідів немає:
     • Виконайте зворотний шлях, витягнувши останню клітинку зі стосу.
3. Продовжуйте цей процес, поки стопка не спорожніє.

Цікавим фактом про цей алгоритм є те, що він працює і як генератор лабіринту, і як розв'язувач лабіринтів. Якщо ви запустите його по вже згенерованому лабіринту і просто зупинитеся, коли потрапите у визначену кінцеву точку, стек міститиме розгадку лабіринту.

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