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

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

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

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

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

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

Як це працює

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

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

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

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

Додаткова література

Якщо вам сподобався цей пост, вам також можуть сподобатися ці пропозиції:

• Генератор лабіринтів алгоритму Еллера
• Алгоритм вирощування дерева Генератор лабіринтів
• Генератор лабіринтів алгоритму Вільсона