Wilsons Algorithmus-Labyrinth-Generator

Wilsons Algorithmus ist ein schleifenbereinigtes Random-Walk-Verfahren, das gleichmäßige Spannbäume zur Labyrinthgenerierung erzeugt. Das bedeutet, dass alle möglichen Labyrinthe einer gegebenen Größe mit gleicher Wahrscheinlichkeit generiert werden, wodurch es sich um eine unvoreingenommene Labyrinthgenerierungsmethode handelt. Wilsons Algorithmus kann als verbesserte Version des Aldous-Broder-Algorithmus betrachtet werden, da er Labyrinthe mit identischen Eigenschaften erzeugt, aber deutlich schneller ist. Daher habe ich auf die Implementierung des Aldous-Broder-Algorithmus hier verzichtet.

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

Der Wilson-Algorithmus zur Erzeugung gleichmäßiger Spannbäume unter Verwendung einer schleifenbereinigten Zufallswand wurde von David Bruce Wilson entwickelt.

Wilson stellte diesen Algorithmus ursprünglich 1996 im Rahmen seiner Forschung zu zufälligen Spannbäumen und Markov-Ketten in der Wahrscheinlichkeitstheorie vor. Obwohl seine Arbeit primär der Mathematik und der statistischen Physik galt, wird der Algorithmus aufgrund seiner Fähigkeit, perfekt gleichmäßige Labyrinthe zu erzeugen, seither häufig zur Labyrinthgenerierung eingesetzt.

Wie Wilsons Algorithmus zur Labyrinthgenerierung funktioniert

Wilsons Algorithmus stellt sicher, dass das endgültige Labyrinth vollständig verbunden ist und keine Schleifen enthält, indem er iterativ Pfade von unbesuchten Zellen aus mittels Zufallspfaden erzeugt.

Schritt 1: Initialisieren

• Beginnen Sie mit einem Raster, das mit Wänden gefüllt ist.
• Definiere eine Liste aller möglichen Durchgangszellen.

Schritt 2: Wähle eine zufällige Startzelle

• Wähle eine beliebige Zelle aus und markiere sie als besucht. Diese dient bei der Generierung als Startpunkt des Labyrinths.

Schritt 3: Zufallspfad mit Schleifenlöschung

• Wähle eine unbesuchte Zelle und beginne einen Zufallspfad (Bewegung in zufälligen Richtungen).
• Falls der Pfad eine bereits besuchte Zelle erreicht, werden alle Schleifen im Pfad gelöscht.
• Sobald der Weg mit der besuchten Region verbunden ist, markieren Sie alle Zellen auf dem Pfad als besucht.

Schritt 4: Wiederholen Sie den Vorgang, bis alle Zellen besucht wurden:

• Wähle weiterhin unbesuchte Zellen aus und führe Zufallswanderungen durch, bis jede Zelle Teil des Labyrinths ist.

Weitere Informationen

Wenn Ihnen dieser Beitrag gefallen hat, könnten Ihnen auch diese Vorschläge gefallen:

• Jagen und Töten Labyrinth Generator
• Ellers Algorithmus-Labyrinthgenerator
• Kruskals Algorithmus-Labyrinth-Generator