Генератор лабіринтів алгоритму Вільсона
Опубліковано: 16 лютого 2025 р. о 19:34:45 UTC
Генератор лабіринтів використовує алгоритм Вілсона для створення ідеального лабіринту. Цей алгоритм генерує всі можливі лабіринти заданого розміру з однаковою ймовірністю, тому теоретично він може генерувати лабіринти багатьох змішаних планувань, але оскільки можливих лабіринтів з коротшими коридорами більше, ніж довгих, ви будете частіше їх бачити.Wilson's Algorithm Maze Generator
Алгоритм Вілсона — це метод випадкового прогулянки, стертого з петлею, який генерує однорідні охоплюючі дерева для створення лабіринту. Це означає, що всі можливі лабіринти заданого розміру з однаковою ймовірністю будуть згенеровані, що робить це неупередженою технікою генерації лабіринтів. Алгоритм Вілсона можна вважати вдосконаленою версією алгоритму Олдоса-Бродера, так як він генерує лабіринти з ідентичними характеристиками, але при цьому працює набагато швидше, тому я не спромігся реалізувати тут алгоритм Олдоса-Бродера.
Ідеальний лабіринт - це лабіринт, в якому існує рівно один шлях з будь-якої точки лабіринту в будь-яку іншу точку. Це означає, що ви не можете ходити по колу, але часто будете стикатися з глухими кутами, що змусить вас розвернутися і повернутися назад.
Карти лабіринту, згенеровані тут, включають версію за замовчуванням без стартових і фінішних позицій, тому ви можете визначити їх самостійно: з будь-якої точки лабіринту в будь-яку іншу точку буде знайдено шлях. Якщо вам потрібне натхнення, ви можете ввімкнути запропоновані позиції старту і фінішу - і навіть побачити рішення між ними.
Про алгоритм Вільсона
Алгоритм Вілсона для генерації однорідних охоплюючих дерев з використанням випадкової стіни, стертої петлею, був створений Девідом Брюсом Вілсоном.
Вілсон вперше представив цей алгоритм у 1996 році під час дослідження випадкових охоплюючих дерев та ланцюгів Маркова в теорії ймовірності. Хоча його роботи були в основному пов'язані з математикою та статистичною фізикою, з тих пір алгоритм став широко використовуватися для генерації лабіринтів завдяки своїй здатності створювати ідеально однорідні лабіринти.
Як працює алгоритм Вілсона для генерації лабіринтів
Алгоритм Вілсона гарантує, що кінцевий лабіринт повністю з'єднаний без будь-яких петель шляхом ітеративного вирізання шляхів з невідвіданих клітин за допомогою випадкових прогулянок.
Крок 1: Ініціалізація
- Почніть з сітки, якою заповнюють стінки.
- Визначте список всіх можливих комірок проходу.
Крок 2: Виберіть випадкову початкову клітинку
- Виберіть будь-яку випадкову клітинку і позначте її як відвідану. Це служить відправною точкою лабіринту під час генерації.
Крок 3: Випадкова прогулянка з циклічним стиранням
- Виберіть невідвідану клітинку і почніть випадкову прогулянку (рухаючись у випадкових напрямках).
- Якщо прогулянка доходить до вже відвіданої клітинки, зітріть усі петлі на шляху.
- Як тільки прогулянка з'єднається з відвіданою областю, позначте всі клітинки на шляху як відвідані.
Крок 4: Повторюйте, поки не будуть відвідані всі клітини:
- Продовжуйте вибирати невідвідані клітини та виконувати випадкові прогулянки, доки кожна клітинка не стане частиною лабіринту.