Генератори Лабіринтів: Алгоритми Розгалуження та Графічна Теорія

Лабіринт — це макет дерева у прихованому вигляді

Візьміть сітку клітин і розглядайте кожен попарний сусідній зв’язок між клітинами як потенційний край, з муром між ними за замовчуванням. Ідеальний лабіринт — тобто рівно один шлях між будь-якими двома клітинами, без циклів, нічого нездійсненного — це те, що графічні теоретики називають макетом дерева для цієї сітки графа: підмножина країв (мури, зруйновані), яка з’єднує кожну клітину, використовуючи рівно n − 1 ребер, без циклів. Кожна алгоритм генерації лабіринту в цій симуляції насправді є алгоритмом побудови випадкового макету дерева; вони відрізняються лише тим, яке макет дерева вони схильні генерувати.

grid graph:   n cells, up to 2n edges (shared walls)
perfect maze: a spanning tree — exactly n−1 edges kept, zero cycles, fully connected

Однакова мета, зовсім різні текстури

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

Алгоритм Wilsona: семплювання без упередження

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

Алгоритм Краскала и структура union-find

Алгоритм Краскала переставляет всех кандидатов стен в случайном порядке, затем обрабатывает их по одному: разрушайте стену только если две клетки, которые она разделяет, еще не соединены каким-либо путем через лабиринт до сих пор. Эффективная проверка «соединен» — это работа структуры union-find (disjoint-set), которая отслеживает компоненты связности и может объединять или запрашивать их почти за постоянное время — ту же структуру, используемую в алгоритме Краскала для поиска минимального остовного дерева в общем графе.

shuffle(walls)
for (a, b) in walls:
  if find(a) != find(b):     // not already connected
    remove_wall(a, b)
    union(a, b)               // merge their components

Розв’язання майже надто легке

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

Frequently asked questions

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

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