Teilweise beobachtbare Spielkarte - ist A * angemessen?

16

Ich weiß sehr wenig über Spieleentwicklung und versuche, mich mit den Algorithmen zur Pfadfindung zu beschäftigen.

Berücksichtigen Sie dieses Setup: Ein Agent befindet sich auf einer 2D-Karte und muss den kürzesten Weg zu einem global bekannten Objekt finden, verfügt jedoch nur über Informationen zu Hindernissen in seinem lokalen Sichtbereich (dh, es sind nur unmittelbare Hindernisse bekannt, der allgemeine Aufbau der Karte ist unbekannt ).

Außerdem ist jede Bewegung zu einem benachbarten Feld teuer und der Pfadfindungsalgorithmus sollte die Anzahl der Bewegungen minimieren.

Rechenleistung ist auch von größter Wichtigkeit und wichtiger als Genauigkeit.

Ist A * für diesen Anwendungsfall geeignet?

algorithm path-finding maps David Chouinard
quelle

Antworten:

19

Sie sollten den D * -Algorithmus verwenden, der genau für dieses Szenario entwickelt wurde. Insbesondere ist die D * Lite-Implementierung die effizienteste und einfachste Variante.

jmegaffin
quelle
2
Sehr relevant . Das Verständnis von D * -lite ist einfach, sobald Sie LPA * (den Algorithmus, auf dem D * -lite basiert) verstanden haben , aber LPA * selbst ist ziemlich komplex. Wenn Sie also vorhaben, D * -lite tatsächlich zu implementieren, ist das Papier zu LPA * der Startpunkt (vorausgesetzt, Sie verstehen bereits A *, das heißt)
BlueRaja - Danny Pflughoeft
3

Viele Spiel-KI-Implementierungen in dieser Situation entscheiden sich dafür, zu schummeln und sich selbst ein umfassendes Wissen über die Karte zu verschaffen, über die ihr menschlicher Gegner nicht verfügt. Sie können dann einfach A * auf die gesamte Karte anwenden.

Wie sinnvoll dies für computergesteuerte Einheiten ist, hängt davon ab, wie verwirrend die Karten sind und ob der Spieler mit der Zeit wahrscheinlich die Kartenlayouts lernt.

Wenn dies für vom Spieler kontrollierte Einheiten ist, können Sie auch verhindern, dass der Spieler ein Ziel auswählt, das er noch nicht erkundet hat, um ihn zu zwingen, es manuell zu erkunden.

Adam
quelle
2
Gute Vorschläge, die für meinen Anwendungsfall nicht geeignet sind, aber für andere nützlich sein könnten. (Ich entwickle eine KI, um an einer Spielsimulation teilzunehmen)
David Chouinard
Es gibt auch Spiele, bei denen die Implementierung der Wegfindung davon ausgeht, dass unerforschte Gebiete überquert werden können, während Gebiete, die zuvor besucht wurden, seit dem letzten Besuch keine Änderung der Überquerbarkeit aufwiesen (dh es würde nicht bekannt sein, dass eine Mauer zerstört oder gebaut wurde, bis sie das Gebiet besucht nochmal).
Lie Ryan