Генератор лабіринтів полювання та вбивств

Алгоритм «Полювання та знищення» насправді є модифікованою версією рекурсивного зворотного відстеження. Модифікація полягає в систематичному скануванні (або «пошуку») нової комірки, з якої можна продовжити пошук, на відміну від справжнього рекурсивного пошуку, який завжди повертається до попередньої комірки в стеку.

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

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

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

Про алгоритм полювання та вбивства

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

Як працює алгоритм «Полювання та вбивство» для створення лабіринту

Крок 1: Почніть з випадкової комірки

• Знайдіть випадкову клітинку в сітці та позначте її як відвідану.

Крок 2: Фаза ходьби (випадкова ходьба)

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

Крок 3: Фаза полювання (повернення через сканування)

• Скануйте сітку рядок за рядком (або стовпець за стовпцем).
• Знайдіть першу невідвідану комірку, яка має хоча б одного відвіданого сусіда.
• Підключіть цю комірку до сусіда, якого відвідали, щоб відновити фазу ходьби.
• Повторюйте, доки не будуть відвідані всі клітини.

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

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

• Генератор лабіринтів алгоритму Крускала
• Генератор рекурсивних лабіринтів Backtracker
• Генератор лабіринтів алгоритму Еллера