Wilsons Algorithmus-Labyrinth-Generator
Veröffentlicht: 16. Februar 2025 um 19:31:33 UTC
Labyrinthgenerator, der Wilsons Algorithmus verwendet, um ein perfektes Labyrinth zu erstellen. Dieser Algorithmus generiert alle möglichen Labyrinthe einer bestimmten Größe mit der gleichen Wahrscheinlichkeit, sodass er theoretisch Labyrinthe mit vielen gemischten Layouts generieren kann. Da es jedoch mehr mögliche Labyrinthe mit kürzeren als mit längeren Korridoren gibt, werden Sie diese häufiger sehen.Wilson's Algorithm Maze Generator
Wilsons Algorithmus ist eine Methode mit schleifenlos gelöschtem Zufallsgang, die gleichmäßige Spannbäume für die Erstellung von Labyrinthen generiert. Dies bedeutet, dass alle möglichen Labyrinthe einer bestimmten Größe mit gleicher Wahrscheinlichkeit generiert werden, was ihn zu einer unvoreingenommenen Technik zur Labyrinthgenerierung macht. Wilsons Algorithmus kann als verbesserte Version des Aldous-Broder-Algorithmus betrachtet werden, da er Labyrinthe mit identischen Eigenschaften generiert, aber viel schneller läuft, sodass ich mich nicht darum gekümmert habe, den Aldous-Broder-Algorithmus hier zu implementieren.
Ein perfektes Labyrinth ist ein Labyrinth, in dem es genau einen Weg von jedem Punkt des Labyrinths zu jedem anderen Punkt gibt. Das bedeutet, dass man sich nicht im Kreis drehen kann, sondern oft auf Sackgassen stößt, die einen zwingen, umzudrehen und zurückzugehen.
Die hier generierten Labyrinthkarten enthalten eine Standardversion ohne Start- und Zielpositionen, so dass Sie diese selbst bestimmen können: Es gibt eine Lösung von jedem Punkt des Labyrinths zu jedem anderen Punkt. Wenn Sie sich inspirieren lassen möchten, können Sie eine vorgeschlagene Start- und Zielposition aktivieren - und sogar die Lösung zwischen den beiden Punkten sehen.
Über Wilsons Algorithmus
Wilsons Algorithmus zum Erzeugen gleichmäßiger Spannbäume unter Verwendung einer schleifengelöschten Zufallswand wurde von David Bruce Wilson entwickelt.
Wilson stellte diesen Algorithmus ursprünglich 1996 vor, als er in der Wahrscheinlichkeitstheorie an zufälligen Spannbäumen und Markow-Ketten forschte. Obwohl seine Arbeit hauptsächlich in Mathematik und statistischer Physik lag, wurde der Algorithmus seitdem aufgrund seiner Fähigkeit, perfekt einheitliche Labyrinthe zu erzeugen, häufig zur Labyrinthgenerierung eingesetzt.
Wie Wilsons Algorithmus zur Labyrinthgenerierung funktioniert
Der Wilson-Algorithmus stellt sicher, dass das fertige Labyrinth vollständig verbunden ist und keine Schleifen aufweist, indem er mithilfe von Zufallswegen iterativ Pfade aus nicht besuchten Zellen erstellt.
Schritt 1: Initialisieren
- Beginnen Sie mit einem Raster voller Wände.
- Definieren Sie eine Liste aller möglichen Passagezellen.
Schritt 2: Wählen Sie eine zufällige Startzelle
- Wählen Sie eine beliebige Zelle aus und markieren Sie sie als besucht. Dies dient während der Generierung als Ausgangspunkt des Labyrinths.
Schritt 3: Random Walk mit Schleifenlöschung
- Wählen Sie eine unbesuchte Zelle aus und beginnen Sie einen Zufallsgang (Bewegung in zufällige Richtungen).
- Wenn der Weg eine bereits besuchte Zelle erreicht, löschen Sie alle Schleifen im Pfad.
- Sobald der Spaziergang mit der besuchten Region verbunden ist, markieren Sie alle Zellen im Pfad als besucht.
Schritt 4: Wiederholen, bis alle Zellen besucht sind :
- Wählen Sie weiterhin nicht besuchte Zellen aus und führen Sie Zufallswanderungen durch, bis jede Zelle Teil des Labyrinths ist.