Labyrinthgenerator mit wachsendem Baumalgorithmus

Der Growing Tree-Algorithmus ist interessant, weil er das Verhalten mehrerer anderer Algorithmen emulieren kann, je nachdem, wie die nächste Zelle während der Generierung ausgewählt wird. Die Implementierung auf dieser Seite verwendet einen Breitensuche-Ansatz, der einer Warteschlange ähnelt.

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 den Growing Tree-Algorithmus

Der Growing Tree-Algorithmus ist eine flexible und leistungsstarke Methode zum Generieren perfekter Labyrinthe. Der Algorithmus ist interessant, weil er das Verhalten mehrerer anderer Algorithmen zur Labyrinthgenerierung emulieren kann, wie etwa Prims Algorithmus, rekursives Backtracking und rekursive Division, je nachdem, wie Sie die nächste zu verarbeitende Zelle auswählen.

So funktioniert der Growing Tree-Algorithmus

Schritt 1: Initialisierung

• Beginnen Sie mit einem Raster aus unbesuchten Zellen.
• Wählen Sie eine zufällige Startzelle und fügen Sie sie einer Liste hinzu.

Schritt 2: Labyrinth-Generierungsschleife

• Solange die Zellenliste nicht leer ist:
  • Wählen Sie eine Zelle aus der Liste basierend auf einer bestimmten Strategie (siehe unten).
  • Schneiden Sie einen Durchgang von der ausgewählten Zelle zu einer ihrer unbesuchten Nachbarzellen (zufällig ausgewählt).
  • Fügen Sie den Nachbarn der Liste hinzu, da er jetzt Teil des Labyrinths ist.
  • Wenn die ausgewählte Zelle keine unbesuchte Nachbarn, entfernen Sie sie aus der Liste.

Schritt 3: Beendigung

• Der Algorithmus ist beendet, wenn keine Zellen mehr in der Liste vorhanden sind, was bedeutet, dass das gesamte Labyrinth ausgehöhlt wurde.

Strategien zur Zellauswahl (Flexibilität des Algorithmus)

Das entscheidende Merkmal des Growing Tree-Algorithmus ist die Art und Weise, wie Sie auswählen, welche Zelle als nächstes verarbeitet werden soll. Diese Auswahl beeinflusst das Aussehen des Labyrinths erheblich:

Neueste Zelle (stapelähnliches Verhalten) – Rekursiver Backtracker:

• Wählen Sie immer die zuletzt hinzugefügte Zelle aus.
• Erzeugt lange, verwinkelte Korridore mit vielen Sackgassen (wie ein Labyrinth mit Tiefensuche).
• Labyrinthe haben in der Regel lange Passagen und sind leicht zu lösen.

Zufällige Zelle (Algorithmus des randomisierten Prims):

• Wählen Sie jedes Mal eine zufällige Zelle aus der Liste aus.
• Erzeugt ein gleichmäßiger verteiltes Labyrinth mit komplexen, verworrenen Pfaden.
• Weniger lange Korridore und mehr Verzweigungen.

Älteste Zelle (warteschlangenähnliches Verhalten):

• Wählen Sie immer die älteste Zelle in der Liste aus.
• Erzeugt Labyrinthe mit einer gleichmäßigeren verteilt, wie ein Breitensuchemuster.
• Kurze, buschige Durchgänge mit dichten Verbindungen.
• (Dies ist die hier implementierte Version)

Hybridansätze:

Kombinieren Sie Strategien für unterschiedliche Labyrintheigenschaften. Beispiel:

• 90 % neuste, 10 % zufällig: Sieht größtenteils wie ein rekursives Backtracker-Labyrinth aus, aber mit gelegentlichen Abzweigungen, die lange Korridore unterbrechen.
• 50 % neuste, 50 % älteste: Gleicht lange Korridore mit buschigem Wachstum aus.