Генератор лабіринтів алгоритму Вільсона

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

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

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

Про алгоритм Вільсона

Алгоритм Вілсона для генерації рівномірних остовних дерев з використанням випадкової стіни зі стиранням циклів був створений Девідом Брюсом Вілсоном.

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

Як працює алгоритм Вілсона для генерації лабіринтів

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

Крок 1: Ініціалізація

• Почніть із сітки, заповненої стінами.
• Визначте список усіх можливих комірок уривку.

Крок 2: Виберіть випадкову початкову комірку

• Виберіть будь-яку випадкову клітинку та позначте її як відвідану. Це слугуватиме відправною точкою лабіринту під час генерації.

Крок 3: Випадкове блукання зі стиранням циклів

• Виберіть невідвідану клітинку та почніть випадкову прогулянку (рух у випадкових напрямках).
• Якщо шлях досягає вже відвіданої комірки, видаліть будь-які петлі на шляху.
• Як тільки маршрут з'єднається з відвіданою областю, позначте всі клітинки на шляху як відвідані.

Крок 4: Повторюйте, доки не будуть відвідані всі комірки:

• Продовжуйте вибирати невідвідані клітинки та виконувати випадкові блукання, доки кожна клітинка не стане частиною лабіринту.

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

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

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