🧩 Labyrinth-Generator — Recursive Backtracker, Prim, Wilsons Algorithmus

Ein gleichverteilter Spannbaum (Uniform Spanning Tree, UST) ist ein Spannbaum, der gleichverteilt zufällig aus allen möglichen Spannbäumen eines Graphen ausgewählt wird. Für ein N×N-Raster gibt es astronomisch viele Spannbäume (für große N etwa e^(πN²/3)). Wilsons Algorithmus erzeugt USTs effizient in erwarteter O(N² log N)-Zeit mithilfe schleifenfreier Zufallsbewegungen. USTs haben Verbindungen zur statistischen Physik (das kritische Ising-Modell) und werden in der strengen Untersuchung zufälliger Labyrintheigenschaften verwendet.

Der Recursive Backtracker (DFS) läuft in O(N²)-Zeit und benötigt O(N²) Stapelspeicher (für ein N×N-Raster). Prims Algorithmus mit einer zufälligen Prioritätswarteschlange ist ebenfalls O(N² log N), aber aufgrund cache-freundlichen Zugriffs meist schneller in der tatsächlichen Laufzeit. Kruskals Algorithmus mit einer Union-Find-Struktur läuft in O(N² α(N²)), wobei α die inverse Ackermann-Funktion ist (nahezu linear). Wilsons Algorithmus hat eine erwartete Laufzeit von O(N² log N), aber hohe Varianz durch die Länge der Zufallsbewegungen.

DFS ist von Natur aus sequenziell. Kruskals Algorithmus ist am besten parallelisierbar: Die Kanten können parallel gemischt werden, und Union-Find unterstützt bei sorgfältiger Synchronisierung nebenläufige Operationen. Parallele Labyrinth-Erzeugung teilt das Raster meist in rechteckige Regionen auf, erzeugt Labyrinthe innerhalb jeder Region unabhängig voneinander und entfernt dann Wände zwischen den Regionen, um sie zu verbinden — dies erzeugt ein gültiges, aber kein gleichverteiltes Labyrinth. GPU-basierte Labyrinth-Erzeugung nutzt zellularautomatenbasierte Ansätze für maximale Parallelität.

Eine BFS vom Eingang garantiert den kürzesten Weg in einem ungewichteten Rasterlabyrinth, indem sie Zellen Ebene für Ebene besucht, bis der Ausgang gefunden ist. DFS findet einen Weg (nicht notwendigerweise den kürzesten) in O(N²)-Zeit. A* mit euklidischer oder Manhattan-Distanz als Heuristik ist in der Praxis bei großen Labyrinthen schneller. Dijkstras Algorithmus behandelt gewichtete Labyrinthe (z. B. wenn verschiedene Zellen unterschiedliche Durchquerungskosten haben, was Gelände simuliert). Alle drei sind im schlimmsten Fall O(N²) für perfekte Labyrinthe.

„Fluss" (auch „Geradeaus-Verzerrung" genannt) misst, wie oft der Gang geradeaus weiterläuft statt abzubiegen. DFS-Labyrinthe haben eine hohe Flussqualität (lange gerade Gänge), da das Zurückverfolgen dazu neigt, in einer Richtung fortzufahren, bis es blockiert ist. Prims Labyrinthe haben eine niedrige Flussqualität (viele Abbiegungen und kurze Läufe). Wilsons UST-Labyrinthe haben eine Flussqualität, die gegen die theoretische Erwartung für zufällige planare Bäume konvergiert, zwischen DFS und Prim liegend.

Ja. Der Growing-Tree-Algorithmus verallgemeinert DFS und Prims: Er führt eine Liste aktiver Zellen und wählt die nächste zu erweiternde Zelle aus dieser Liste (neueste = DFS, zufällig = Prim-artig, älteste = BFS). Ellers Algorithmus erzeugt Labyrinthe zeilenweise mit O(N) Speicher, unabhängig von der Labyrinthhöhe, geeignet für Streaming oder unendliche Labyrinthe. Sigma-Labyrinthe (hexagonale Raster) und Theta-Labyrinthe (kreisförmige Raster) verwenden dasselbe Spannbaum-Konzept, angepasst an nicht rechteckige Zellgraphen.

Jedes perfekte Labyrinth ist ein Spannbaum des Rastergraphen. Kruskals Labyrinth-Algorithmus ist buchstäblich Kruskals MST-Algorithmus mit zufälligen Kantengewichten (jeder Wand wird eine Zufallszahl zugewiesen). Prims Labyrinth-Algorithmus ist Prims MST mit zufälliger Kantenwahl. Da die Gewichte zufällig sind, erzeugen beide zufällige Spannbäume, jedoch nicht gleichverteilt zufällig — sie haben eine Verzerrung zu kurzen Kanten (Wände neben bereits besuchten Zellen). Wilsons Algorithmus korrigiert diese Verzerrung, um echte USTs zu erzeugen.