Pfadfindung mit mehreren zufälligen Pfaden in einem Tower Defense-Spiel

Ich dachte über zufällige Wegfindung für mein Tower Defense-Spiel nach. Ein * würde für meine Schüler nicht funktionieren, da ich speziell eine zufällige Pfadfindung benötige .

Stellen Sie sich eine Karte mit Routen, einem Startpunkt und einem Ziel vor. Ich habe mehrere Routen, die alle vom Startpunkt zum Ziel führen, auf die eine oder andere Weise. Es könnte so aussehen:

Farbbeschreibung: rot - Ausgangspunkt; schwarz - Bestimmungsort; grau - Route; Leerraum
(Die Zahlen werden im Text als Referenz für einige Kacheln verwendet)

Ich dachte zuerst daran, den nächsten Wegpunkt zufällig zu berechnen, wenn eine Entität eine Kachel passiert. Das würde aber nicht funktionieren. Wenn eine Entität Kachel 1 passiert, kann sie entweder nach oben oder nach unten gehen. Wenn es um 2 geht, kann es entweder nach unten / oben (relativ zu seiner Position) oder nach rechts gehen.
Wenn es runter / rauf geht, geht es zu Kachel 1, was bedeutet, dass es rückwärts geht. Schlecht...

Ich würde es wirklich gerne dynamisch machen , aber ich kann nicht herausfinden, was ich jetzt tun kann. Jemand mit Ideen oder Erfahrungen darin?

Anstatt alle benachbarten Quadrate als mögliche nächste Wegpunkte zu haben, schließen Sie nur Quadrate ein, die nicht zum Anfang zurückführen, und wählen Sie diese zufällig aus. Wenn Sie dies tun würden, wäre es unmöglich, rückwärts zu gehen, da ein Zurückgehen keine Option ist.

Dies ist ein gerichtetes Diagrammproblem mit jedem Wegpunkt als Scheitelpunkt und jedem Pfad als Kante. Sie müssen nur die Anzahl der Zyklen begrenzen und sie möglicherweise vollständig entfernen.

Du sagst zufällig, aber wie viel Zufälligkeit willst du? Ist es in Ordnung, wenn die Feinde einen Pfad wählen, der zehnmal so lang ist wie der kürzeste? Ist es in Ordnung, wenn die Feinde in eine Sackgasse geraten und zurückgehen müssen? Das heißt, zufällig über welche Pfade und mit welcher Wahrscheinlichkeitsverteilung?

Angenommen, Sie möchten, dass die Feinde kurze Wege bevorzugen, könnten Sie A * verwenden, aber die zugeführten Kantengewichte zufällig variieren. Dann wählen die Feinde immer einen zufälligen Pfad, der jeden Knoten höchstens einmal besucht, mit einer Tendenz zu kürzeren Pfaden. Insbesondere wenn es ohne Randomisierung mehrere Pfade gleicher Länge geben würde, würde jeder dieser Pfade mit gleicher Wahrscheinlichkeit ausgewählt.

Alternativ können Sie in A * Nachbarn in zufälliger Reihenfolge durchlaufen. Wenn in Ihrem Beispiel die Pfadfindung den Knoten 1 erreicht, wird zufällig die Oberseite des unteren Nachbarn zuerst in die Warteschlange gestellt, wodurch der obere oder untere Pfad zuerst berücksichtigt wird. Diese Lösung würde dazu führen, dass Feinde zufällig zwischen allen kürzesten Pfaden wählen. In Ihrem einfachen Beispiel wären beide kürzesten Wege gleich wahrscheinlich, aber in einer Situation wie:

start -+--------+
       |        |
       +--------+
       |        |
       +--------+- end

Der obere Pfad würde mit einer Wahrscheinlichkeit von 1/2 gewählt, während die unteren mit einer Wahrscheinlichkeit von jeweils 1/4 gewählt würden.

Nur ein Proof of Concept:

1. Wähle eine zufällige Richtung.
2. Wenn dies dazu führen würde, dass wir irgendwohin gehen, wo wir bereits waren, wählen Sie eine andere Richtung.
3. Wenn wir keine Richtung mehr haben, kehren Sie mit einer unerforschten Richtung zum letzten Feld zurück.