Wie erreicht man eine teilweise Wegfindung?

6

Angenommen, ich habe bereits einen A * -Algorithmus.

Wie kann ich mit den Fällen umgehen, in denen das Ziel nicht erreicht werden kann, und trotzdem versuchen, dorthin zu gelangen?

Zum Beispiel im folgenden Beispiel:

Kachelkarte Beachten Sie die erstaunlichen GIMP-Fähigkeiten!

Die gelbe Einheit muss den grünen Punkt erreichen, befindet sich jedoch auf der Insel und kann ihn nicht erreichen.

Bei einem typischen RTS versucht das Gerät jedoch, so nah wie möglich zu kommen.

Mein Problem ist, dass ich A * nicht sagen kann, dass das dem Ziel am nächsten liegende Plättchen das Quadrat in der Nähe des Meeres ist.

Wie kann ich diese teilweise Wegfindung haben? Ist A * immer noch eine gute Wahl?

path-finding Pierre Arlaud
quelle
Ich denke, RTS findet nur den nächstgelegenen Punkt außerhalb des Geländes und berechnet den Pfad dazu, anstatt eine teilweise Pfadfindung durchzuführen.
API-Beast
@ API-Beast Also 1. machen sie immer noch Pfadfindung, um zu wissen, dass das Ziel nicht erreichbar ist und 2. wie finden Sie den nächsten Punkt?
Pierre Arlaud
Nein, es ist nicht so, dass das Ziel nicht erreichbar ist, es ist so, dass der Punkt, auf den Sie geklickt haben, "solide" ist, z. B. blockiert er die Bewegung der Einheit. RTS haben in der Regel keine nicht erreichbaren Ziele.
API-Beast
Sie müssen nichts ändern. Denken Sie nur an den nächsten Punkt, an dem Sie jemals waren. Das A * versucht, den Pfad zu finden, und schlägt beispielsweise für Sie fehl. Dies bedeutet jedoch nicht, dass nicht zuerst der von Ihnen gezeichnete Pfad festgelegt wird. Sie müssen sich nur an den Pfad zum nächstgelegenen Punkt erinnern, an dem das A * jemals gewesen ist.
Wondra
1
Überprüfen Sie es nie wirklich, teilen Sie es unbedingt mit, wenn es in der Praxis funktioniert. (Dies war nur eine logische Annahme darüber, wie A * funktioniert).
Wondra

Antworten:

3

Theoretisch müssen Sie nichts ändern. Denken Sie nur an den nächsten Punkt, an dem Sie jemals waren. Das A * versucht, den Pfad zu finden, und schlägt beispielsweise für Sie fehl. Dies bedeutet jedoch nicht, dass nicht zuerst der von Ihnen gezeichnete Pfad festgelegt wird. Sie müssen sich nur an den Pfad zum nächstgelegenen Punkt erinnern, an dem das A * jemals gewesen ist.

wondra
quelle
Ein * hat eine schlechte Leistung - der schlimmste Fall in der Tat -, wenn das Ziel nicht erreichbar ist, da es alle zusammenhängenden Knoten besucht. Ich denke, eine Modifikation wird zumindest helfen?
Congusbongus
3
Das Problem ist, dass Sie nicht wissen, dass Ihr Endpunkt nicht erreichbar ist, es sei denn, Sie erschöpfen A * . Wenn Sie Kompromisse bei der Einschränkung der Funktionsweise von A * eingehen, werden Sie viel mehr Zeit damit verbringen, Fälle zu beheben, wenn "Warum ist dieser Pfad einfach fehlgeschlagen?" das passiert.
Patrick Hughes
@PatrickHughes congusbongus könnte einen Punkt haben. RTS-Engines verfügen häufig über einen unvollständigen Pfadfindungsalgorithmus, der den kürzesten Pfad nicht findet (und kaum einer Heuristik folgt), wenn der kürzeste Pfad zu kompliziert ist.
Pierre Arlaud
Lassen Sie den Code einfach funktionieren. Wenn er zu langsam ist, PROFILIEREN Sie ihn. Lass dich nicht von Leuten im Schlamm stecken lassen, weil etwas zu langsam sein könnte. Bringen Sie es einfach zum Laufen und fahren Sie von dort mit dem nächstwichtigsten fort - was die Leistung dieses Algorithmus wahrscheinlich nicht verbessert.
Xaxxon
0

Die Verwendung von A * allein (und das Gehen zum nächsten gesuchten Punkt) ist für kleine Karten in Ordnung, funktioniert jedoch schlecht, wenn die Karte größer ist. Wenn das Ziel nicht erreichbar ist, durchsucht A * den gesamten erreichbaren Bereich, bevor festgestellt wird, dass das Ziel nicht erreichbar ist. Dies kann viele Suchpunkte beinhalten und sehr langsam sein. In dieser Situation hat A * keinen Vorteil gegenüber Algorithmen wie Dijkstra.

Für eine effizientere Lösung benötigen Sie drei Teile:

  • Finden Sie alle Gruppen von Regionen, die nicht erreichbar sind
  • Finden Sie die nächstgelegene erreichbare Position
  • Pfad zu dieser Position finden

Der erste Schritt kann vorberechnet werden, damit Sie kostengünstig feststellen können, ob Ihr Ziel erreichbar ist. Flood-Fill (auch bekannt als BFS) wird ausreichen.

Der zweite ist normalerweise Dijkstra oder ein ähnlich aussehender Algorithmus. Sie können es sogar vorberechnen (suchen Sie für jede nicht erreichbare Position nach der nächstgelegenen erreichbaren Position und speichern Sie sie, bevor das Spiel beginnt).

Sie können dann A * für den dritten Schritt verwenden.

Congusbongus
quelle