Nehmen wir an, Sie wollen ein einfaches Labyrinth auf einem N x M-Raster, mit einem Weg durch, und eine gute Anzahl von Sackgassen, aber das sieht "richtig" (d.h. wie jemand es von Hand ohne zu viele kleine winzige Sackgassen und all das gemacht). Gibt es eine bekannte Methode, dies zu tun?
Es stellt sich heraus, dass es 11 klassische Algorithmen gibt, um "perfekte" Labyrinthe zu erzeugen. Ein Labyrinth ist perfekt, wenn es eine, und nur eine, Lösung hat. Hier sind einige Links zu jedem Algorithmus, in der groben Reihenfolge meiner Vorlieben.
Weitere Informationen finden Sie unter mazelib auf GitHub, eine Python-Bibliothek, die alle Standard-Algorithmen zum Erzeugen und Lösen von Labyrinthen implementiert.
Sie sagen, dass der zelluläre Automat hier perfekte Labyrinthe erzeugt, aber Ihre Bibliothek sagt etwas anderes. Wie kommt das? github.com/theJollySin/mazelib/blob/master/docs/
@JeroSquartini Sie haben völlig recht. Am Ende habe ich wohl einfach nur realmente wollen, dass es sogar 12 klassische Algorithmen zur Erstellung von Labyrinthen gibt. Und während Cellular Automaton est wirklich beliebt ist, ist sie definitiv nicht "perfekt".
Desde http://www.astrolog.org/labyrnth/algrithm.htm
Rekursiver Backtracker: Diese Methode ist in gewisser Weise mit der weiter unten beschriebenen rekursiven Backtracker-Methode verwandt 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 nicht gebauten Abschnitt, wenn sich einer neben der aktuellen Zelle befindet. Jedes Mal, wenn du dich zu einer neuen Zelle bewegst, schiebe die vorherige Zelle auf den Stapel. Wenn sich neben der aktuellen Position keine ungemachten Zellen befinden, schiebe den Stapel auf die vorherige Position. Das Labyrinth ist fertig, wenn alles vom Stapel verschwunden ist. 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 verwinkelten Lösung. Er läuft recht schnell, obwohl der Algorithmus von Prim noch etwas schneller ist. Rekursives Backtracking funktioniert nicht als Wandaddierer, da dies zu einem Lösungsweg führt, der der Außenkante folgt, wobei das gesamte Innere des Labyrinths durch einen einzigen Stiel mit dem Rand verbunden ist.
Sie produzieren nur 10 % Sackgassen
ist ein Beispiel für ein mit dieser Methode erzeugtes Labyrinth.
Der rekursive Backtracker erzeugt, wie erwähnt, eine ziemlich flussartige Lösung. Interessanter ist vielleicht der Eller-Algorithmus, der ähnliche Eigenschaften wie die Zufallsalgorithmen hat (die einen guten Prozentsatz an Flusslösungen und Sackgassen liefern), aber viel schneller läuft.
Eine ziemlich einfache Lösung könnte darin bestehen, den Graphenkanten zufällige Gewichte zuzuweisen und die Kruskals Algorithmus um einen minimalen spannenden Baum zu finden.
Die beste Diskussion aller Zeiten über Algorithmen zur Erzeugung von Labyrinthen: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (war vor ein paar Tagen auf HN).
Das ist nicht nur eine großartige Diskussion über die Erzeugung von Labyrinthen. Es ist ein großartiges Beispiel für eine technische Präsentation, die perfekt .
Wow, das ist die beste Diskussion über die Entstehung von Labyrinthen, die ich je gesehen habe. Was für eine fantastische Präsentation!
Am liebsten verwende ich den Algorithmus von Kruskal, aber wenn ich eine Kante zufällig auswähle, gewichte ich die Auswahl nach den Arten von Kanten, mit denen sie verbunden ist.
Indem Sie die Gewichte für verschiedene Kantentypen variieren, können Sie Labyrinthe mit vielen verschiedenen Eigenschaften oder "Persönlichkeiten" erzeugen. Siehe mein Beispiel hier:
Seltsamerweise, indem man die "kanonischen" Regeln leicht verändert und von einer zufälligen Konfiguration ausgeht, Conway's Spiel des Lebens scheint ziemlich schöne Labyrinthe zu erzeugen!
(Ich erinnere mich nicht mehr an die genaue Regel, aber es ist eine sehr einfache Modifikation, die dazu führt, dass die Zellpopulation "verdichtet" wird...)
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
