Rekursiver Backtracker-Labyrinthgenerator

Der rekursive Backtracker-Algorithmus ist eigentlich eine allgemeine Tiefensuche. Wenn er zur Labyrinthgenerierung verwendet wird, wird er leicht modifiziert, um den Pfad nach dem Zufallsprinzip auszuwählen, während man bei tatsächlichen Suchzwecken normalerweise einfach jede Ebene in linearer Reihenfolge durchsucht. Er neigt dazu, Labyrinthe mit langen, gewundenen Korridoren und einer sehr langen, verwinkelten Lösung zu erzeugen.

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 zum Generieren perfekter Labyrinthe (Labyrinthe ohne Schleifen und mit einem einzigen Pfad zwischen zwei beliebigen Punkten). Er ist einfach, effizient und erzeugt optisch ansprechende Labyrinthe mit langen, gewundenen Korridoren.

Trotz seines Namens muss es nicht unbedingt rekursiv implementiert werden. Es wird oft in einem iterativen Ansatz mithilfe einer LIFO-Warteschlange (also eines Stapels) implementiert. Bei sehr großen Labyrinthen führt die Verwendung von Rekursion je nach Programmiersprache und verfügbarem Speicher eher zu einem Überlauf des Aufrufstapels. Eine LIFO-Warteschlange kann leichter an die Verarbeitung großer Datenmengen angepasst werden und sogar auf der Festplatte oder in einer Datenbank gespeichert werden, wenn der verfügbare Speicher nicht ausreicht.

Wie es funktioniert

Der Algorithmus arbeitet mit einem stapelbasierten Tiefensuche-Ansatz. Hier ist die schrittweise Aufschlüsselung:

1. Wählen Sie eine Startzelle und markieren Sie sie als besucht.
2. Solange es unbesuchte Zellen gibt:
   • Schauen Sie sich die benachbarten Zellen an, die noch nicht besucht wurden.
   • Wenn mindestens ein unbesuchter Nachbar existiert:
     • Wählen Sie nach dem Zufallsprinzip einen der nicht besuchten Nachbarn aus.
     • Entfernen Sie die Wand zwischen der aktuellen Zelle und dem ausgewählten Nachbarn.
     • Gehen Sie zum ausgewählten Nachbarn und markieren Sie ihn als besucht.
     • Schieben Sie die aktuelle Zelle auf den Stapel.
   • Wenn keine unbesuchten Nachbarn vorhanden sind:
     • Gehen Sie zurück, indem Sie die letzte Zelle aus dem Stapel nehmen.
3. Setzen Sie diesen Vorgang fort, bis der Stapel leer ist.

Interessant an diesem Algorithmus ist, dass er sowohl als Labyrinthgenerator als auch als Labyrinthlöser funktioniert. Wenn Sie ihn auf einem bereits generierten Labyrinth ausführen und einfach anhalten, wenn Sie den festgelegten Endpunkt erreichen, enthält der Stapel die Lösung für das Labyrinth.

Ich habe auf dieser Site tatsächlich zwei Versionen dieses Algorithmus im Einsatz: eine auf LIFO-Warteschlangen basierende zum Generieren von Labyrinthen auf dieser Seite und eine auf Rekursion basierende zum Lösen von Labyrinthen, auch von Labyrinthen, die von anderen Algorithmen generiert wurden (so werden die Karten mit den Lösungen erstellt). Dass es zwei verschiedene Versionen gibt, ist nur zum Spaß, weil ich ein Nerd bin, der es interessant findet; jede hätte für beides funktionieren können ;-)