Miklix

Rekursiver Backtracker-Labyrinthgenerator

Veröffentlicht: 16. Februar 2025 um 18:16:00 UTC

Labyrinthgenerator, der den rekursiven Backtracker-Algorithmus verwendet, um ein perfektes Labyrinth zu erstellen. Dieser Algorithmus neigt dazu, Labyrinthe mit langen, gewundenen Korridoren und einer sehr langen, verwinkelten Lösung zu erstellen.

Diese Seite wurde maschinell aus dem Englischen übersetzt, um sie so vielen Menschen wie möglich zugänglich zu machen. Leider ist die maschinelle Übersetzung noch keine ausgereifte Technologie, so dass Fehler auftreten können. Wenn Sie es vorziehen, können Sie sich die englische Originalversion hier ansehen:

Recursive Backtracker Maze Generator

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.


Neues Labyrinth generieren








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 ;-)

Teilen auf BlueskyAuf Facebook teilenAuf LinkedIn teilenAuf Tumblr teilenTeilen auf XAuf LinkedIn teilenPin auf Pinterest

Mikkel Bang Christensen

Über den Autor

Mikkel Bang Christensen
Mikkel ist der Schöpfer und Eigentümer von miklix.com. Er verfügt über mehr als 20 Jahre Erfahrung als professioneller Computerprogrammierer/Softwareentwickler und ist derzeit in Vollzeit für ein großes europäisches IT-Unternehmen tätig. Wenn er nicht gerade bloggt, verbringt er seine Freizeit mit einer Vielzahl von Interessen, Hobbys und Aktivitäten, was sich bis zu einem gewissen Grad in der Vielfalt der auf dieser Website behandelten Themen widerspiegelt.