Генератор лабіринтів полювання та вбивств
Опубліковано: 16 лютого 2025 р. о 20:57:28 UTC
Генератор лабіринтів використовує алгоритм Hunt and Kill для створення ідеального лабіринту. Цей алгоритм схожий на рекурсивний відстежувач, але має тенденцію генерувати лабіринти з дещо менш довгими, звивистими коридорами.Hunt and Kill Maze Generator
Алгоритм Hunt and Kill насправді є модифікованою версією Recursive Backtracker. Модифікація полягає в систематичному скануванні (або «полюванні») на предмет нової комірки, щоб продовжити з моменту, коли вона не може пройти далі, на відміну від справжнього рекурсивного пошуку, який завжди повертатиметься до попередньої комірки в стеку.
Завдяки цьому цей алгоритм можна легко адаптувати для створення лабіринтів з різним виглядом і відчуттям, просто вибираючи частіше входити в режим «полювання» або за певними правилами. Версія, реалізована тут, переходить у режим «полювання» лише тоді, коли вона не може піти далі від поточної комірки.
Ідеальний лабіринт - це лабіринт, в якому існує рівно один шлях з будь-якої точки лабіринту в будь-яку іншу точку. Це означає, що ви не можете ходити по колу, але часто будете стикатися з глухими кутами, що змусить вас розвернутися і повернутися назад.
Карти лабіринту, згенеровані тут, включають версію за замовчуванням без стартових і фінішних позицій, тому ви можете визначити їх самостійно: з будь-якої точки лабіринту в будь-яку іншу точку буде знайдено шлях. Якщо вам потрібне натхнення, ви можете ввімкнути запропоновані позиції старту і фінішу - і навіть побачити рішення між ними.
Про алгоритм «Полювання та вбивство»
Алгоритм «Полювання та вбивство» — це простий, але ефективний метод створення лабіринтів. Він дещо схожий на пошук з урахуванням глибини (тобто алгоритм рекурсивного зворотного трекера), за винятком того, що коли він не може просунутися далі від поточної позиції, він систематично сканує (або «полює») по лабіринту, щоб знайти нову клітинку для продовження. Алгоритм складається з двох основних фаз: прогулянки і полювання.
Як працює алгоритм полювання та вбивства для генерації лабіринтів
Крок 1: Почніть з випадкової клітинки
- Знайдіть випадкову клітинку в сітці та позначте її як відвідану.
Крок 2: Фаза ходьби (випадкова прогулянка)
- Виберіть випадкового невідвіданого сусіда.
- Перемістіться до цього сусіда, позначте його як відвіданий і проріжте шлях між попередньою і новою клітинкою.
- Повторюйте до тих пір, поки не залишиться невідвіданих сусідів.
Крок 3: Фаза полювання (зворотне відстеження за допомогою сканування)
- Скануйте сітку рядок за рядком (або стовпець за стовпцем).
- Знайдіть першу невідвідану клітку, в якій є хоча б один відвіданий сусід.
- Підключіть цю клітку до відвіданого сусіда, щоб відновити фазу прогулянки.
- Повторюйте до тих пір, поки всі клітини не будуть відвідані.