Генерація лабіринтів: DFS, Прим, Круксаль та Вілсон

Лабіринт – це розгалужена структура, що покриває сітку.

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

DFS Backtracker: довгі, вигнуті коридори

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

стек = [початковий клітинний блок]; позначити початковий клітинний блок як відвіданий поки стек не порожній: поточна = стек.верхній() сусіди = невідвідані сусіди поточного якщо сусідів немає: стек.видалити(); продовжити наступний = випадковий(сусідів) видалити стінку(поточний, наступний); позначити наступний як відвіданий стек.додати(наступний) Оскільки він завжди зобов’язується глибині перед тим, як відступити, DFS схильний генерувати лабіринти з довгих, вигнутих, низькорозгалужених коридорів і порівняно небагато тупиків біля входу — візуально найбільш «лабіринтоподібний» із чотирьох за людським поглядом.

stack = [startCell]; mark startCell visited
while stack not empty:
  current = stack.top
  neighbours = unvisited neighbours of current
  if neighbours empty: stack.pop(); continue
  next = random(neighbours)
  removeWall(current, next); mark next visited
  stack.push(next)

Prim's і Kruskal's: мінімальні спільні дерева з випадковими вагами

Звичайний Prim починається з однієї клітинки, підтримує набір межуючих стін у фронтиері та повторно вибирає випадкову стіну з цього набору, вирізаючи її, якщо вона з’єднує відвідану клітинку з невідвіданою — структурно ідентична класичній алгоритму мінімального спільних дерева Прима з випадково призначеними вагами замість фактичної відстані. Звичайний Randomised Kruskal замість цього перемішує кожну стіну в сітці у випадковому порядку та обробляє їх одну за одною, вирізаючи стіну, коли дві клітинки, які вона розділяє, належать до різних вже-з’єднаних компонентів (відстежується за допомогою структури union-find / disjoint-set), інакше пропускає її. Обидва гарантують дійсне дерево з’єднання завдяки конструкції; їхня візуальна сигнатура коротша, більш рівномірно розподілені тупики та частіші розгалуження, ніж DFS, оскільки ні один алгоритм не зобов'язується продовжувати один шлях наскільки це можливо перед відступом.

Kruskal (randomised):
  edges = shuffle(all possible walls)
  dsu = new DisjointSet(allCells)
  for wall in edges:
    if dsu.find(wall.cellA) != dsu.find(wall.cellB):
      removeWall(wall); dsu.union(wall.cellA, wall.cellB)

Wilson: рівномірні розмашисті дерева через петлі, що були стерті

DFS, Prim і Kruskal усі виробляють дійсне розмашисте дерево, але не з однаковою ймовірністю для кожного можливого розмашистого дерева сітки — деякі форми дерев виникають частіше, ніж інші. Алгоритм Wilson (1996) є єдиним винятком на цій сторінці: він генерує розмашисте дерево рівномірно випадково з множини всіх можливих розмашистих дерев, використовуючи петлі, що були стерті випадкові ходи. Починаючи з невідвіданого клітинки, він виконує випадкову прогулянку до тих пір, поки не зустрінеся з ростучим лабіринтом, потім видаляє будь-яку петлю, яку прогулянка повернула назад, і додає отриманий безпетльовий шлях у лабіринт; повторюючи це для всіх інших невідвіданих клітинок, цей метод виробляє справді рівномірну вибірку — математично сильніше гарантія, ніж у трьох інших алгоритмах, але за рахунок значно менш передбачуваного часу виконання, оскільки випадкова прогулянка може довго блукати, перш ніж вона випадково зустрінеться з лабіринтом.

Розв’язання миттєво з використанням BFS

Оскільки ідеальний лабіринт є деревом, існує рівно один шлях між входом та виходом, а алгоритм пошуку в ширину (BFS) знаходить його за час O(cells), розширюючися від стартової точки по колу відстаней, що збільшується, і записуючи батьківський елемент кожного клітинки під час її першого зустрічі. Потім шлях відновлюється шляхом переходу назад через ці батьківські посилання від виходу.

BFS є правильним вибором тут, оскільки дерево не має циклів для турбування та немає ваг ребер для порівняння, що відповідає ситуації, в якій побудовані алгоритми Дейкстри та A*. Додаткові витрати на ці алгоритми не приносять користі у випадку лабіринтів.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Maze Generator і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.