Wegfindung mit Trägheit

Ich arbeite derzeit an der Wegfindung für ein Spiel, in dem sich Einheiten bewegen, aber Trägheit haben. Die meisten typischen Pfadfindungsalgorithmen (A *, Djikastra usw.) dienen lediglich dazu, die Länge des Pfades zu minimieren.

Diese Techniken gelten jedoch meines Wissens nicht für Fälle, in denen die Einheit Trägheit aufweist. Wenn die Einheit Trägheit hat, gibt es einen signifikanten Unterschied in den Kosten, um eine Fliese in einer bestimmten Richtung zu belassen, basierend auf der Richtung, in die Sie gehen möchten.

Zum Beispiel sind die Kosten für das Verlassen eines Plättchens in Richtung Norden erheblich höher, wenn Sie das Plättchen aus dem Osten betreten haben, als wenn Sie aus dem Süden gekommen sind. (Im ersten Beispiel müssten Sie langsamer fahren, um die Ost-West-Geschwindigkeit zu stoppen, während Sie im zweiten Beispiel direkt durchfahren könnten.)

Die Tatsache, dass das System Trägheit hat, bedeutet, dass Sie, um eine Kurve zu fahren, möglicherweise lange vor der Kurve langsamer fahren müssen. Mein bisher bester Gedanke ist, dass Sie die zusätzliche Zeit berechnen, die zum Verlangsamen benötigt wird, und diese dann zu den heuristischen Umzugskosten addieren. Dies scheint jedoch zu implizieren, dass Sie der geschlossenen Liste niemals eine Kachel hinzufügen könnten, da die Eingabe aus einer anderen Richtung die Kosten für den Umzug grundlegend verändern könnte.

Darüber hinaus ist das Konzept der Verwendung eines Gitters ohnehin eine Abstraktion, da sowohl Position als auch Geschwindigkeit Gleitkommakonzepte sind. Gibt es einen Algorithmus, der die Pfadfindung auf einer offenen Ebene mit Trägheit besser als A * handhaben kann, oder welche Änderungen könnte ich an einem bereits vorhandenen Algorithmus vornehmen, um ihn für diese Art von Bewegung geeignet zu machen?

Die einzige neue Einschränkung, die die Trägheit der Wegfindung auferlegt , ist die Kontinuität , dh keine plötzlichen Geschwindigkeitsbrüche. Beginnen Sie mit der Generierung eines A * -Pfads, jedoch mit einer großen Wendung. Der Grund, warum A * an sich nicht angemessen ist, liegt darin, dass es die Kontinuität verletzt. Erstellen wir also ein neues.

A * wählt den besten Weg als kürzesten Weg, aber mit Trägheit ist der kürzeste Weg nicht mehr der schnellste Weg. Der schnellste Weg wird derjenige sein, der den kürzesten Weg gibt, ohne die Kontinuität zu unterbrechen .

Mit normalem A * kann jede Iteration zu einem benachbarten Plättchen "springen", beginnend mit den niedrigsten Kosten. Anstatt nur benachbarte Kacheln zuzulassen, lassen wir für die nächste Runde alle Kacheln zu, die sich in unserem Bewegungsbereich befinden. Dies bedeutet, dass die einzigen Kacheln, die wir als nächstes auswählen können, die Kacheln sind, bei denen wir den Impuls um einen Betrag ändern müssten, den das Objekt physisch kann.

TLDR: Wir verschieben die Auswahl von A * durch unsere Dynamik und fügen Sie, dass in unseren Schwung.

Pfadfindungsalgorithmen wie A * können mit Trägheit (oder jeder anderen Dimension, die Sie darauf werfen können) gut umgehen. Der Schlüssel besteht darin, sie als zusätzliche Dimension zu behandeln und ein höherdimensionales Suchdiagramm für die Suche zu erstellen.

Nehmen wir zur Vereinfachung an, wir haben nur zwei Geschwindigkeiten: langsam und schnell und diesen Pfad:

A --(sharp turn)-- B ----------- C --(ravine)-- D

Um die scharfe Kurve auszuführen AB, müssen wir langsam sein. Um die Schlucht zu überspringen, müssen wir schnell sein und können die Geschwindigkeit nur auf Pfaden ändern. Hier ist das resultierende Suchdiagramm:

(fast): A       B ----> C -----> D
                  \   ^
                    X
                  /   v
(slow): A ----> B ----> C        D

Sie sehen also, der einzige Weg von A nach D besteht in diesem Fall darin, Azu Blangsam, zu schnell und zu schnell Bzu Cbeschleunigen .CD

Die Pfadkosten sind ebenfalls einfach: Sie hängen von der Geschwindigkeit ab. Wenn wir also willkürlich entscheiden, dass die Kosten für schnell-schnell 1, schnell-langsam oder langsam-schnell als 2 und langsam-langsam als 3 sind, betragen die Kosten für A->D3 + 2 + 1 = 6.

Wie Sie vielleicht vermutet haben, besteht das Problem darin, dass A * mit Diagrammen arbeitet und nicht mit kontinuierlichen Bereichen arbeitet. Das heißt, Sie müssen diskrete Geschwindigkeiten wie bei langsam / schnell festlegen, und jede zusätzliche Geschwindigkeitsstufe multipliziert die Größe Ihres Suchdiagramms. Je körperlich anstrengender Ihr Spiel ist, desto mehr Geschwindigkeitsstufen benötigen Sie und desto teurer wird die Wegfindung. Im schlimmsten Fall ist es für Spiele zu teuer. Wenn ja, haben Sie einige andere Möglichkeiten:

• Lassen Sie Ihre KI betrügen, damit sie einige Pfade durcheinander bringt, z. B. wenn Sie eine Kurve machen können, auch wenn sie etwas zu schnell ist. Dies bedeutet, dass Sie mit weniger Geschwindigkeitsstufen in Ihrem A * -Suchdiagramm davonkommen können
• Berechnen Sie ähnlich wie bei Rennspielen die idealen Pfadkurven vorab, und Ihre KI navigiert einfach zum besten Knoten auf dieser Kurve und fährt damit fort