Algorithmus zur Erzeugung von Zufallswegen

Eine Sache, auf die ich hinweisen möchte, ist, dass Sie den Bereich des Arrays so ändern sollten, dass es bei Null beginnt, oder den Bereich der generierten Anzahl fixieren. Momentan produziert es einen Bereich mit ungültigen Indizes. Da deine Frage nicht darauf ausgerichtet war, habe ich es so gelassen.

Dies erzeugt einen gewundenen Pfad, der abwärts gehen und wieder hochfahren kann, bis entweder gültige Bewegungen ausbleiben oder der untere Bildschirmbereich erreicht wird. Hier ist ein JFIDDLE dafür Ссылка

Ich würde ein Labyrinth mit einer Methode erzeugen, die ein Labyrinth gibt, wo man von jedem Punkt zu jedem anderen kommt. Der rekursive Backtracer ist hierfür gut und einfach zu implementieren.

Nachdem Sie ein Labyrinth auf der Matrix erzeugt haben, müssen Sie einen Weg vom Anfangspunkt zum Endpunkt finden (Es kann jeder Punkt sein. Sie müssen nur daran denken, dass jede Sekunde eine Mauer sein kann). Sie können viele verschiedene Algorithmen im Link am Ende des Beitrags finden. Bei einem Labyrinth, das mit einem rekursiven Backtracer generiert wurde, sind Reihen / Spalten wie gewünscht verbunden (wie gesagt, jeder Punkt ist mit jedem anderen verbunden), aber nicht jede Position kann ein Pfad sein (wegen der Notwendigkeit Wände zu setzen). p>

Ihr gefundener Pfad von Anfang bis Ende erfüllt Ihre Anforderungen, so dass Sie nur alles löschen müssen, was nicht zum Pfad gehört.

Wenn Sie einen eigenen Stapel erstellen, können Sie problemlos Matrizen der Größe ~ 2Kx2K bearbeiten. Vielleicht größer.

Für weiterführende Informationen zu allem, was mit Labyrinthen zu tun hat, empfehle ich diese Seite Ссылка

Sie können einige Änderungen am Labyrinth-Generator vornehmen, so dass es möglich ist, Start / Ende auf jeder möglichen Kachel zu haben, nicht nur auf jeder zweiten. Die einfachste Lösung, die ich mir vorstellen kann, besteht darin, nur für 50% der Fälle ein Labyrinth mit einem Offset von 1 zu erzeugen.

So würde ich dieses Problem angehen.

1) Definieren Sie genau Ihre Regeln für das, was einen gültigen Pfad ausmacht. eine Funktion, die die Matrix auf einen booleschen Wert abbildet. Von deiner Frage aus bin ich nicht klar, was ein gültiger Pfad ist, und ich bin mir auch nicht sicher, ob du es schon bist.

2) Erzeuge wiederholt eine zufällige Anordnung von Kacheln, bis die erzeugte Anordnung die Regeln für einen gültigen Pfad erfüllt. Bei aktuellen Prozessoren wird dies schnell für 6 × 6 funktionieren, dauert aber länger bei größeren Quadraten, z. 100x100.

Eine algorithmische Lösung ist möglich, spart Verarbeitungszeit, aber das ist der schnelle Gewinn in Bezug auf Entwicklungszeit und Code-Einfachheit. Hat auch den Vorteil, Ihnen eine gleichmäßige Verteilung zu geben, d. H. Jeder Pfad wird genauso wahrscheinlich erzeugt wie jeder andere Pfad.

Beispielregelsatz könnte sein:

Ein Pfad ist gültig, wenn und nur wenn die Matrix alle diese Kriterien erfüllt:

1) Jede Kachel in der Matrix (mit Ausnahme von zwei Endkacheln) muss Nachbarn mit genau zwei Kacheln aus den vier möglichen Richtungen N, S, E, W

2) Zwei Kacheln in der Matrix (Endkacheln) müssen Nachbarn mit genau einer Kachel aus den vier möglichen Richtungen N, S, E, W

3) Eine Endkachel muss in der oberen Reihe und die andere in der unteren Reihe sein

Wenn Sie einen Schritt nach dem anderen gehen und der Aufstieg ausgeschlossen wird, scheint es mir, dass Sie nur die letzten beiden Bewegungen im Auge behalten müssen (außer wenn Sie den ersten Schritt bestimmen). Dann könnte der Algorithmus einer Reihe von Regeln folgen und die nächste Kachel zufällig aus den verfügbaren Optionen auswählen.

Zum Beispiel: