Wie man die folgende Situation am besten darstellt - agent ( @) muss zum Ziel gelangen ( $). Der Weg ist durch einen Wassergraben blockiert ( ~~~). Ein Rechen (oder ein anderes Gerät wie Wasserlaufstiefel) ist verfügbar, mit dem das Hindernis überquert werden kann.
.....~~~... . ground
...=.~~~... = rake
.....~~~.$. ~ water
.@...~~~... @ agent
.....~~~... $ goalWie kann man den Pfad richtig finden @, $vorausgesetzt, es gibt keinen sofort verfügbaren Pfad? Sollte mein Weg nicht nur Kosten, sondern auch Voraussetzungen haben?
UPD : Das Problem ist, dass das Ziel nicht zugänglich ist und Rake nur eines von vielen möglichen Objekten auf der Karte ist. Die Frage ist dann: "Wie kann der Agent verstehen, dass er den Rechen benötigt?"
ai
path-finding
zzandy
quelle
quelle
Antworten:
Ich denke über einen Stapel von Zielen nach, die Wegfindung muss kommentiert werden :
get $$Pfad zu finden, der mit der erforderlichen Wasserlauffähigkeit vorhanden ist.get waterwalking.get waterwalking, get $get $.$- jetzt haben wir die Fähigkeit und können das Ziel erreichen.quelle
Das gesamte Pfadfindungsmaterial ist nur eine Suche nach dem kürzesten Pfad über einem Diagramm. Um Ihr Problem zu lösen, müssen Sie nur einige zusätzliche Kanten hinzufügen (die den Pfad darstellen, den das Boot nehmen kann) und einen einfachen Pfadfindungsalgorithmus ausführen. Es spielt keine Rolle, ob Sie BFS, Dijkstra oder A * verwenden. Implementieren Sie einfach einen normalen Pfadfindungsalgorithmus mit einigen zusätzlichen Kanten. Weitere Informationen zum Finden von Pfaden in einer Grafik finden Sie auf der Wiki-Seite
quelle
no path from @ to $zugoto rake, bring it to water, place it, goto $.Ich würde dies mit einer Art Verhaltensbaumlösung tun - Sie gehen zum Ziel und nehmen alle Hindernisse zur Kenntnis, die Ihr A * blockiert haben. Wenn Sie versagen, überprüfen Sie, ob es Objekte gibt, die helfen können, diese Hindernisse zu überwinden. In diesem Fall den Pfad zu diesem Objekt. Wiederholen. Dies bedeutet, dass der Agent versuchen muss, zum Ziel zu gelangen, und scheitern muss, bevor er auf die Idee kommt, Tools zu verwenden. Dies kann einige Zeit dauern, insbesondere wenn es eine riesige Welt von Kacheln gibt, die alle überprüft werden müssen. Könnte nicht zu fehl am Platz aussehen, dass der Agent einige Zeit braucht, um darüber nachzudenken, wie das Problem gelöst werden kann.
Ich kann mir jedoch eine echte Hardcore-Lösung vorstellen. Fügen Sie Ihrem Pfadfindungsraster eine weitere Dimension hinzu. Im Fall einer 2D-Karte erstellen Sie das Pfadfindungsgitter in 3D. In diesem einfachen Beispiel hätte diese neue Dimension nur eine Tiefe von zwei, aber in einem echten Spiel würde sie schnell groß werden.
Bei z = 0 kartieren Sie das Gelände unter normalen Umständen, was bedeutet, dass Wasserfliesen als unpassierbar gelten.
Bei z = 1 kartieren Sie das Gelände so, wie es ist, während Sie den Rechen haben, was bedeutet, dass Wasserfliesen als begehbar gelten (aber wenn Sie beispielsweise Wandfliesen haben, können diese fest bleiben).
Die Pfadfindung ist ein gewöhnliches A * in den x- und y-Dimensionen, was bedeutet, dass jede Gitterzelle Zugriff auf ihre Nachbarn hat. In der z-Dimension darf sich das A * jedoch NICHT ausbreiten.
Außer wo der Rechen ist. Das Rechenobjekt wirkt als Öffnung zwischen z = 0 und z = 1 im Pfadfindungsgitter.
Dies bedeutet, dass das A * in z = 0 nach außen flutet, auf das Wasser trifft und keine Optionen mehr hat - dann breitet es sich durch das Rechenplättchen auf z = 1 aus und bei z = 1 (wo Wasser begehbar ist) finde den Weg zum Ziel. Der Effekt ist, dass sich der NPC ohne zu zögern zum Rechen bewegt und dann den kürzesten Weg zum Ziel bewegt.
quelle