Was ist ein guter Algorithmus, um ein Labyrinth zu erzeugen?

https://stackoverflow.com/questions/38502

09-06-2019
|

Frage

Angenommen, Sie möchten ein einfaches Labyrinth auf einem N-mal-M-Raster mit einem Durchgang und vielen Sackgassen, aber das sieht „richtig“ aus (d. h.als ob jemand es von Hand gemacht hätte, ohne allzu viele kleine Sackgassen und so weiter).Gibt es eine bekannte Möglichkeit, dies zu tun?

Lösung

Aus http://www.astrolog.org/labyrnth/algrithm.htm

Rekursiver Backtracker:Dies hängt in gewisser Weise mit der unten beschriebenen rekursiven Backtracker-Lösungsmethode zusammen und erfordert einen Stapel bis zur Größe des Labyrinths.Seien Sie beim Schnitzen so gierig wie möglich und schnitzen Sie immer in einen unbearbeiteten Abschnitt, wenn dieser sich neben der aktuellen Zelle befindet.Jedes Mal, wenn Sie in eine neue Zelle wechseln, schieben Sie die vorherige Zelle auf den Stapel.Wenn neben der aktuellen Position keine nicht erstellten Zellen vorhanden sind, verschieben Sie den Stapel an die vorherige Position.Das Labyrinth ist fertig, wenn Sie alles vom Stapel nehmen.Dieser Algorithmus führt zu Labyrinthen mit einem möglichst hohen „Fluss“-Faktor, mit weniger, aber längeren Sackgassen und normalerweise einer sehr langen und kurvenreichen Lösung.Es läuft ziemlich schnell, obwohl Prims Algorithmus etwas schneller ist.Rekursives Backtracking funktioniert nicht als Wandaddierer, da dies dazu neigt, zu einem Lösungspfad zu führen, der der Außenkante folgt, wobei das gesamte Innere des Labyrinths durch einen einzigen Stamm mit der Grenze verbunden ist.

Sie erzeugen nur 10 % Sackgassen

ist ein Beispiel für ein Labyrinth, das mit dieser Methode erstellt wurde.

Andere Tipps

Es stellt sich heraus, dass es 12 klassische Algorithmen gibt, um „perfekte“ Labyrinthe zu erzeugen.Ein Labyrinth ist perfekt, wenn es nur eine Lösung hat.Hier sind einige Links zu jedem Algorithmus, grob nach meiner Präferenz geordnet.

Weitere Informationen finden Sie unter Mazelib auf GitHub, einer Python-Bibliothek, die alle Standardalgorithmen zum Erzeugen/Lösen von Labyrinthen implementiert.

Eine ziemlich einfache Lösung könnte darin bestehen, den Diagrammkanten zufällige Gewichte zuzuweisen und diese anzuwenden Kruskals Algorithmus um einen minimalen Spannbaum zu finden.

Beste Diskussion aller Zeiten über Algorithmen zur Labyrinthgenerierung: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (war vor ein paar Tagen auf HN).

Seltsamerweise wurde durch eine leichte Änderung der „kanonischen“ Regeln und ausgehend von einer zufälligen Konfiguration Conways Spiel des Lebens scheint ziemlich schöne Labyrinthe zu erzeugen!

(Ich erinnere mich nicht an die genaue Regel, aber es ist eine sehr einfache Modifikation, die dazu führt, dass die Zellpopulation „verdichtet“ wird ...)

Am liebsten nutze ich den Kruskal-Algorithmus, aber wenn ich zufällig eine zu entfernende Kante auswähle, gewichte die Auswahl basierend auf den Kantentypen, mit denen sie verbunden ist.

Indem Sie die Gewichte für verschiedene Kantentypen variieren, können Sie Labyrinthe mit vielen unterschiedlichen Eigenschaften oder „Persönlichkeiten“ erstellen.Sehen Sie hier mein Beispiel:

https://mtimmerm.github.io/webStuff/maze.html

Eine der Methoden zur Erzeugung eines Labyrinths ist die randomisierte Version des Prim-Algorithmus.

Beginnen Sie mit einem Gitter voller Wände.Wählen Sie eine Zelle aus und markieren Sie sie als Teil des Labyrinths.Fügen Sie die Wände der Zelle zur Wandliste hinzu.Die Liste enthält zwar Wände:

Wählen Sie eine beliebige Wand aus der Liste aus.Wenn die Zelle auf der gegenüberliegenden Seite noch nicht im Labyrinth ist:

(i) Machen Sie die Wand zu einem Durchgang und markieren Sie die Zelle auf der gegenüberliegenden Seite als Teil des Labyrinths.

(ii) Fügen Sie die benachbarten Wände der Zelle zur Wandliste hinzu.

Wenn sich die Zelle auf der gegenüberliegenden Seite bereits im Labyrinth befand, entfernen Sie die Wand aus der Liste.

Für mehr Verständnis klicken Sie Hier

Hier ist der als Pseudocode geschriebene DFS-Algorithmus:

Erstellen Sie einen CellStack (LIFO), um eine Liste der Zellstandorte zu speichern
set TotalCells = Anzahl der Zellen im Raster
Wählen Sie zufällig eine Zelle aus und nennen Sie sie CurrentCell
setze VisitedCells = 1

Während besuchtezells <Totalcells finden alle Nachbarn von CurrentCell, wobei alle Wände intakt sind
Wenn einer oder mehrere gefundene gefunden werden, wählen Sie zufällig eine
Reißen Sie die Wand zwischen ihm und CurrentCell nieder
Push CurrentCell-Position auf dem CellStack
Machen Sie die neue Zelle zu CurrentCell
Fügen Sie 1 zu besuchten Zellen hinzu, sonst stecken Sie den neuesten Zelleintrag aus dem Zellstack
Machen Sie es den aktuellen Endif -Endif

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow