Labyrinthgenerator mit wachsendem Baumalgorithmus

Der Growing-Tree-Algorithmus ist interessant, da er das Verhalten verschiedener anderer Algorithmen nachahmen kann, je nachdem, wie die nächste Zelle während der Generierung ausgewählt wird. Die Implementierung auf dieser Seite verwendet einen breitensuchenden, warteschlangenähnlichen Ansatz.

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 Wachstumsbaum-Algorithmus

Der Growing-Tree-Algorithmus ist eine flexible und leistungsstarke Methode zur Erzeugung perfekter Labyrinthe. Er ist deshalb interessant, weil er das Verhalten verschiedener anderer Labyrinthgenerierungsalgorithmen, wie beispielsweise des Prim-Algorithmus, des rekursiven Backtrackings und der rekursiven Division, nachahmen kann, je nachdem, wie die nächste zu verarbeitende Zelle ausgewählt wird.

Wie der Wachstumsbaum-Algorithmus funktioniert

Schritt 1: Initialisierung

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

Schritt 2: Labyrinthgenerierungsschleife

• Solange die Zellenliste nicht leer ist: Wähle eine Zelle anhand einer bestimmten Strategie (siehe unten) aus. Erschaffe einen Durchgang von der ausgewählten Zelle zu einem ihrer unbesuchten Nachbarn (zufällig ausgewählt). Füge den Nachbarn der Liste hinzu, da er nun Teil des Labyrinths ist. Hat die ausgewählte Zelle keine unbesuchten Nachbarn, entferne 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 erstellt wurde.

Zellselektionsstrategien (Flexibilität des Algorithmus)

Das entscheidende Merkmal des Growing-Tree-Algorithmus ist die Auswahl der jeweils nächsten zu verarbeitenden Zelle. Diese Wahl beeinflusst das Erscheinungsbild des Labyrinths maßgeblich:

Neueste Zelle (stapelartiges Verhalten) – Rekursiver Backtracker:

• Wählen Sie immer die zuletzt hinzugefügte Zelle aus.
• Es entstehen lange, gewundene Gänge mit vielen Sackgassen (ähnlich einem Tiefensuchlabyrinth).
• Labyrinthe haben in der Regel lange Gänge und sind leicht zu lösen.

Zufallszelle (Randomisierter Prim-Algorithmus):

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

Älteste Zelle (warteschlangenähnliches Verhalten):

• Wähle immer die älteste Zelle in der Liste.
• Erzeugt Labyrinthe mit einer gleichmäßigeren Verteilung, ähnlich einem Breitensuche-Muster.
• Kurze, buschige Gänge mit dichten Verbindungen.
• (Dies ist die hier implementierte Version)

Hybride Ansätze:

Strategien für unterschiedliche Labyrintheigenschaften kombinieren. Zum Beispiel:

• 90 % neueste Einträge, 10 % zufällige Einträge: Sieht größtenteils aus wie ein rekursives Backtracker-Labyrinth, jedoch mit gelegentlichen Abzweigungen, die lange Gänge unterbrechen.
• 50 % neueste, 50 % älteste Pflanzen: Schafft ein Gleichgewicht zwischen langen Korridoren und buschigem Bewuchs.

Weitere Informationen

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

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