Rekursiver Backtracker-Labyrinthgenerator

Der rekursive Backtracker-Algorithmus ist im Grunde eine allgemeine Tiefensuche. Bei der Labyrinthgenerierung wird er leicht modifiziert, um den Pfad zufällig zu wählen. Für die eigentliche Suche hingegen durchsucht man typischerweise die einzelnen Ebenen linear. Dadurch entstehen Labyrinthe mit langen, gewundenen Gängen und einem sehr langen, verschlungenen Lösungsweg.

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.

Der rekursive Backtracker-Algorithmus ist eine Tiefensuche zur Erzeugung perfekter Labyrinthe (Labyrinthe ohne Schleifen und mit genau einem Pfad zwischen je zwei Punkten). Er ist einfach, effizient und erzeugt optisch ansprechende Labyrinthe mit langen, gewundenen Gängen.

Trotz ihres Namens muss die Implementierung nicht zwangsläufig rekursiv erfolgen. Häufig wird sie iterativ mithilfe einer LIFO-Warteschlange (d. h. eines Stacks) umgesetzt. Bei sehr großen Labyrinthen kann die Verwendung von Rekursion, abhängig von der Programmiersprache und dem verfügbaren Speicher, eher zu einem Stack-Überlauf führen. Eine LIFO-Warteschlange lässt sich leichter an die Verarbeitung großer Datenmengen anpassen und kann bei unzureichendem Speicherplatz sogar auf der Festplatte oder in einer Datenbank gespeichert werden.

So funktioniert es

Der Algorithmus arbeitet mit einer stapelbasierten Tiefensuche. Hier die schrittweise Aufschlüsselung:

1. Wählen Sie eine Startzelle und markieren Sie diese als besucht.
2. Solange unbesuchte Zellen vorhanden sind: Betrachte die benachbarten, noch nicht besuchten Zellen. Falls mindestens eine unbesuchte Nachbarzelle existiert: Wähle zufällig eine der unbesuchten Nachbarzellen aus. Entferne die Wand zwischen der aktuellen Zelle und der gewählten Nachbarzelle. Bewege dich zur gewählten Nachbarzelle und markiere sie als besucht. Lege die aktuelle Zelle auf den Stapel. Falls keine unbesuchten Nachbarzellen vorhanden sind: Gehe zurück, indem du die letzte Zelle vom Stapel entfernst.
3. Setzen Sie diesen Vorgang fort, bis der Stapel leer ist.

Eine interessante Eigenschaft dieses Algorithmus ist, dass er sowohl als Labyrinthgenerator als auch als Labyrinthlöser fungiert. Wendet man ihn auf ein bereits generiertes Labyrinth an und stoppt beim Erreichen des festgelegten Endpunkts, enthält der Stack die Lösung des Labyrinths.

Ich verwende auf dieser Seite tatsächlich zwei Versionen dieses Algorithmus: eine LIFO-Warteschlangen-basierte Version zur Generierung von Labyrinthen und eine rekursive Version zur Lösung von Labyrinthen, auch solcher, die von anderen Algorithmen generiert wurden (so entstehen die Karten mit den Lösungen). Die zwei verschiedenen Versionen sind nur ein kleines Spiel, weil ich ein Technikfreak bin und es interessant finde; beide hätten für beide Zwecke funktioniert.

Weitere Informationen

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

• Labyrinthgenerator mit wachsendem Baumalgorithmus
• Jagen und Töten Labyrinth Generator
• Wilsons Algorithmus-Labyrinth-Generator