Jagen und Töten Labyrinth Generator
Veröffentlicht: 16. Februar 2025 um 20:52:24 UTC
Labyrinthgenerator, der den Hunt-and-Kill-Algorithmus verwendet, um ein perfektes Labyrinth zu erstellen. Dieser Algorithmus ähnelt dem Recursive Backtracker, neigt jedoch dazu, Labyrinthe mit etwas weniger langen, gewundenen Korridoren zu generieren.Hunt and Kill Maze Generator
Der Hunt and Kill-Algorithmus ist eigentlich eine modifizierte Version des Recursive Backtracker. Die Modifikation besteht darin, systematisch nach einer neuen Zelle zu suchen (oder zu „jagen“), von der aus man weitermachen kann, wenn es nicht weitergeht, im Gegensatz zu einer echten rekursiven Suche, die immer zur vorherigen Zelle im Stapel zurückgeht.
Aus diesem Grund kann dieser Algorithmus leicht angepasst werden, um Labyrinthe mit unterschiedlichem Erscheinungsbild zu erzeugen, indem man einfach wählt, den „Jagdmodus“ häufiger oder nach bestimmten Regeln zu aktivieren. Die hier implementierte Version wechselt nur dann in den „Jagdmodus“, wenn sie sich nicht weiter von der aktuellen Zelle entfernen kann.
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 Hunt and Kill Algorithmus
Der Hunt and Kill-Algorithmus ist eine einfache, aber effektive Methode zum Generieren von Labyrinthen. Er ähnelt einer Tiefensuche (also dem Recursive Backtracker-Algorithmus), mit dem Unterschied, dass er, wenn er sich von der aktuellen Position nicht weiter bewegen kann, das Labyrinth systematisch absucht (oder „jagt“), um eine neue Zelle zu finden, von der aus er weitergehen kann. Der Algorithmus besteht aus zwei Hauptphasen: Gehen und Jagen.
So funktioniert der Hunt-and-Kill-Algorithmus zur Labyrinthgenerierung
Schritt 1: Beginnen Sie bei einer zufälligen Zelle
- Suchen Sie eine zufällige Zelle im Raster und markieren Sie sie als besucht.
Schritt 2: Gehphase (Random Walk)
- Wählen Sie einen zufälligen, nicht besuchten Nachbarn aus.
- Gehen Sie zu diesem Nachbarn, markieren Sie ihn als besucht und erstellen Sie einen Pfad zwischen der vorherigen und der neuen Zelle.
- Wiederholen Sie den Vorgang, bis keine unbesuchten Nachbarn mehr übrig sind.
Schritt 3: Jagdphase (Rückverfolgung durch Scannen)
- Durchsuchen Sie das Raster zeilenweise (oder spaltenweise).
- Suchen Sie die erste nicht besuchte Zelle, die mindestens einen besuchten Nachbarn hat.
- Verbinden Sie diese Zelle mit einem besuchten Nachbarn, um die Gehphase fortzusetzen.
- Wiederholen Sie den Vorgang, bis alle Zellen besucht wurden.