Algorytmy generacji labiryntu: drzewa rozpinające i teoria grafów

Labirynt jest drzewem rozpinającym w ukryciu

Zastanów się nad siatką komórek, gdzie każda para sasiednich komórek reprezentuje potencjalne krawędź, a domknięte mury są domyślne między nimi. Idealny labirynt — dokładnie jedna ścieżka między każdymi dwiema komorami, bez pętli, nic nie jest niewykorzystane — to dokładnie to, co teoretycy grafów nazywają drzewem rozpinającym siatki grafowej: podzbiorem krawędzi (waliny usunięte), który łączy każdą komórkę za pomocą dokładnie n − 1 krawędzi, bez pętli. Każdy algorytm generujący labirynt na tej symulacji jest w podstawie algebrą tworzenia losowego drzewa rozpinającego; różnią się tylko tym drzewem rozpinającym, które tendują do wygenerowania.

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

Takie samo cel, bardzo różne tekstury

Algorytm backtrackingowy rekurencyjny (losowy poszukiwanie w głębokości) rysuje korytarz dalej, aż natrafia na zatokę, następnie cofa się i próbuje innej nieosiągniętej kierunku. Dlatego, że zasługuje na długie sekcje przed cofnięciem się, tworzy labirynty z długimi, skręcającymi się korytarzami i stosownie rzadziej gałęzi — teksturę „rzeki”. Algorytm Prim’s losowy z kolei rosnie labirynt od granic kandydatów na ściany, wybierając jedną losowo na każdym kroku; ponieważ nie jest zasłoniony przez żaden konkretny kierunek, tworzy krótsze zatoki i gęstsze, bardziej równomiernie gałęziste tekstury. Oba algorytmy są poprawne — oba zawsze kończą się prawidłowym drzewem rozpinającym — ale losują z bardzo różnych, strukturalnie nieco uciętych podzbiorów wszystkich możliwych drzew rozpinających.

Algorytm Wilsona: losowanie bez obciążenia

Algorytm Wilsona przyjmuje inny, wyższy podejście, aby usunąć to obciążenie. Wykonuje szlak oczyszczone z pętli: zaczyna losowy szlak od nieodwiedzonego pola i co//= kiedy ten szlak odwiedza już odwiedzony komórkę, usuwa powstającą pętlę przed kontynuacją. Powtarzane wielokrotnie aż do momentu, gdy każda komórka dołączy do drzewa, ten procedurę matematycznie udowodniono, że produkuje drzewo rozpinające jednorodne — każdy możliwy drzewo rozpinające siatki ma tą samą prawdopodobieństwo wyniknięcia, czego ani algorytm odwrotnej ścieżki, ani algorytm Prim nie mogą wyróżnić. Kosztem jest wariancja czasu wykonania: wcześniejsze losowe szlaki oczyszczone z pętli na prawie pustej siatce mogą chodzić długą drogę przed rozwinięciem się.

Algorytm Kruskala i struktura danych union-find

Algorytm Kruskala losowo permutuje każdą kandydatę na ścianę, a następnie przetwarza ją jeden po drugim: zrzuca tylko ścianę, jeśli dwie komórki, które ją oddziela, nie są już połączone przez jakiś inny ścieżkę w labiryncie. Sprawdzanie „już połączone” jest dokładnie zadaniem struktury danych union-find (struktura zbiorów rozłącznych), która śledzi komponenty spójne i może je łączyć lub zapytywać prawie w czasie stałym — taka sama struktura danych używana jest przez algorytm Kruskala dla drzewa rozpinającego o minimalnej długości w grafie ogólnym.

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

Rozwiązywanie jest prawie zbyt proste

Bo idealny labirynt jest drzewem, więc między wejściem a wyjściem istnieje dokładnie jedna ścieżka — nie ma tutaj problemu z najkrótszą ścieżką do rozwiązania, tylko jedna ścieżka do znalezienia. Wyszukiwanie w szerokości od początku nadal robi to jasno: eksploruje poziom za poziomem i podczas osiągnięcia celu, przeprowadzając się z powrotem poprzez wskaźniki rodziców, odtwarza tę jedyną prawdziwą ścieżkę. Wyszukiwanie w szerokości zarabia sobie prawo do istnienia głównie na nieidealnych labiryncach zawierających pętle, gdzie wielu ścieżek rzeczywiście konkurencja i tylko BFS (lub Dijkstra dla zmiennych wagi) jest zagwarantowane znalezienie najkrótszej.

Często zadawane pytania

Wypróbuj na żywo

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