Generowanie Labiryntów: DFS, Prim, Kruskal i Wilson

Labirint jest drzewem rozpinającym dla grafu siatki

Traktuj każdy element siatki jako węzeł, a każdą możliwą ścianę między sąsiadującymi komórkami jako potencjalny krawędź. Idealny labirynt – dokładnie jeden ścieżka między dowolnymi dwoma komórkami, bez pętli, bez obszarów odizolowanych – to w zasadzie drzewo rozpinające dla tej siatki: zbiór krawędzi łączący każdy węzeł bez cykli. Każdy klasyczny algorytm generowania labiryntów jest, pod różnym tytułem, algorytmem drzewa rozpinającego zastosowanym do siatki, dlatego też mogą wyglądać bardzo inaczej wizualnie, a jednocześnie gwarantują tę samą właściwość strukturalną.

DFS Backtracker: długie, wijące się korytarze

Algorytm przeszukiwania w głąb (DFS) backtracker rozpoczyna się od losowej komórki i wielokrotnie przesuwa do losowego, nieodwiedzonego sąsiada, niszcząc ścianę między nimi i przesuwając stary cell na stos. Gdy komórka nie ma nieodwiedzonych sąsiadów, wyjmuje ją z stosu i kontynuuje od niej.

stos = [startCell]; oznacz startCell jako odwiedzoną while stos nie jest pusty: aktualny = stos.top sąsiedzi = nieodwiedzona sąsiadów aktualnego if sąsiedzi jest pusta: stos.pop(); kontynuuj następny = losuj(sąsiedzi) usuńŚcianę(aktualny, następny); oznacz następny jako odwiedzoną stos.push(następny) Ponieważ zawsze komituje się na głębokość przed cofaniem, DFS tendencyjnie generuje labirynty z długimi, wijącymi się, mało rozgałęziającymi się korytarzami i stosunkowo niewiele ślepych przejść w pobliżu wejścia — wizualnie najbardziej "labiryntowy" spośród czterech algorytmów dla ludzkiego oka.

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 i Kruskal: minimalne drzewa rozgałęziające z losowymi wagami

Algorytm Uproszczonego Przyma rozpoczyna się od jednej komórki, utrzymuje zbiór granic murów przyległych do rosnącego labiryntu i w sposób powtarzalny wybiera losowy mur z tego zbioru, jeśli łączy odwiedzoną komorę z niezakreszoną – co jest strukturalnie identyczne z klasycznym algorytmem minimalnego drzewa rozgałęziającego z przyznawanymi losowymi zamiast rzeczywistymi odległościami wagami. Algorytm Uproszczonego Kruskala natomiast losuje każdy mur na planszy do losowej kolejności i przetwarza go jeden po drugim, wycinając mur, gdy dwie komórki, które on oddziela, należą do różnych już połączonych komponentów (śledzone za pomocą struktury union-find / disjoint-set), pomijając go w przeciwnym razie. Oba gwarantują poprawną strukturę drzewa rozgałęziającego dzięki konstrukcji; ich sygnatura wizualna charakteryzuje się krótszymi, bardziej równomiernie rozłożonymi ślepymi końcami i częstszymi gałęzieniami niż DFS, ponieważ żaden z algorytmów nie zobowiązuje się do przedłużania jednego ciągu tak daleko, jak to możliwe, zanim nie cofnie się w tył.

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: drzewa rozpostawne o zmiennym przebiegu w pętli usunięte (loop-erased walks)

Algorytm Wilsona (1996) jest jedynym wyjątkiem z tej strony: generuje drzewo rozpostawne losowo ze zbioru wszystkich możliwych drzew rozpostawnych, wykorzystując w pętlach usunięte losowe wędrówki. Rozpoczynając od niewidzialnej komórki, wykonuje wędrówkę losową aż do momentu, gdy natrafi na rosnący labirynt, następnie usuwa każdy pierścień, który wędrówka prześledziła z powrotem przez siebie i dodaje wynikający z tego ścieżkę bez pierścieni do labiryntu; powtarzając to dla wszystkich pozostałych niewidzialnych komórek, generuje uczciwy próbnik - matematycznie silniejszą gwarancję niż w przypadku trzech innych algorytmów, kosztem znacznie mniej przewidywalnego czasu wykonania, ponieważ losowa wędrówka może długo się rozpowiadać zanim przypadkowo natrafi na labirynt.

Rozwiązanie natychmiastowe z użyciem BFS

Ponieważ idealny labirynt jest drzewem, istnieje dokładnie jeden ścieżka między wejściem a wyjściem, a algorytm bfs (Breadth-First Search) ją znajduje w czasie O(komórki), rozszerzając się krok po kroku od punktu początkowego, tworząc pierścienie oddalenia, i zapisując rodzica każdej komórki przy pierwszym jej dotknięciu. Następnie, przechodząc wstecz przez te wskazówki rodziców, rekonstruuje drogę do wyjścia. BFS jest tutaj najbardziej odpowiedni, ponieważ drzewo nie zawiera cykli, które trzeba monitorować, ani wag krawędzi, które należy porównywać – sytuacja, w której algorytmy Dijkstry i A* wymagają dodatkowych kosztów, które niczego nie przynoszą w labiryncie.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Maze Generator i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.