Miklix

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.

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:

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.


Neues Labyrinth generieren








Ü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.

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.