Jagen und Töten Labyrinth Generator

Der Hunt-and-Kill-Algorithmus ist im Grunde eine modifizierte Version des rekursiven Backtrackers. Die Modifikation besteht darin, systematisch nach einer neuen Zelle zu suchen (oder „zu suchen“), von der aus die Suche fortgesetzt werden kann, wenn kein weiterer Fortschritt möglich ist. Dies steht im Gegensatz zu einer echten rekursiven Suche, die immer zur vorherigen Zelle im Stack zurückkehrt.

Daher lässt sich dieser Algorithmus leicht anpassen, um Labyrinthe mit unterschiedlichem Erscheinungsbild zu generieren, indem man einfach häufiger oder nach bestimmten Regeln in den „Jagdmodus“ wechselt. 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 Jagd- und Tötungsalgorithmus

Der Hunt-and-Kill-Algorithmus ist eine einfache, aber effektive Methode zur Generierung von Labyrinthen. Er ähnelt der Tiefensuche (z. B. dem rekursiven Backtracker-Algorithmus), mit dem Unterschied, dass er, sobald er sich nicht weiter von der aktuellen Position entfernen kann, das Labyrinth systematisch durchsucht (oder „jagt“), um eine neue Zelle für den weiteren Weg zu finden. Der Algorithmus besteht aus zwei Hauptphasen: dem Durchlaufen und der Suche.

Wie der Jagd- und Tötungsalgorithmus bei der Labyrinthgenerierung funktioniert

Schritt 1: Beginnen Sie mit einer zufälligen Zelle

• Wähle eine zufällige Zelle im Raster aus und markiere sie als besucht.

Schritt 2: Gehphase (Zufallsgang)

• Wähle einen zufälligen, noch nicht besuchten Nachbarn.
• Gehe zu diesem Nachbarn, markiere ihn als besucht und zeichne einen Pfad zwischen der vorherigen und der neuen Zelle.
• Wiederholen Sie den Vorgang, bis keine unbesuchten Nachbarn mehr übrig sind.

Schritt 3: Suchphase (Zurückverfolgen durch Scannen)

• Durchforsten Sie das Raster Zeile für Zeile (oder Spalte für Spalte).
• Finde die erste unbesuchte Zelle, die mindestens einen besuchten Nachbarn hat.
• Verbinde diese Zelle mit einer bereits besuchten Nachbarzelle, um die Gehphase fortzusetzen.
• Wiederholen Sie den Vorgang, bis alle Zellen besucht wurden.

Weitere Informationen

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

• Kruskals Algorithmus-Labyrinth-Generator
• Ellers Algorithmus-Labyrinthgenerator
• Wilsons Algorithmus-Labyrinth-Generator