Optimieren von AStar, um den nächstgelegenen Standort zum nicht erreichbaren Ziel zu finden

11

Ich habe AStar in Java implementiert und es funktioniert in einem Bereich mit Hindernissen, in dem das ausgewählte Ziel erreichbar ist.

Wenn das Ziel jedoch nicht erreichbar ist, befindet sich der berechnete "Pfad" in keiner Weise zum nächstgelegenen Ort (zum nicht erreichbaren Ort), sondern ist ein zufälliger Pfad.

Gibt es eine praktikable Möglichkeit, AStar so zu optimieren, dass der Pfad zum nächstgelegenen Ort zu einem nicht erreichbaren Ziel gefunden wird?

path-finding Shivan Drache
quelle

Antworten:

20

Verfolgen Sie den Knoten mit dem niedrigsten EstimatedDistanceToEnd(dh dem niedrigsten h(x)). Wenn kein Endknoten zum Zurückverfolgen erreichbar ist, ziehen Sie stattdessen von diesem Knoten zurück.

BlueRaja - Danny Pflughoeft
quelle
Einfach. Ich liebe es!
John McDonald
Ich habe mir nur auf den Kopf geschlagen und bin "doh" gegangen, als ich deine Antwort gelesen habe. Vielen Dank!
Shivan Dragon
1

Dies ist nicht wirklich eine A * -Frage. Bei A * geht es darum, einen Pfad von Punkt A zu Punkt B zu finden. Auch wenn er erweitert werden kann, können die Ergebnisse leicht unübersichtlich und unvorhersehbar sein. Was Sie stattdessen benötigen, ist ein Algorithmus, der das am nächsten erreichbare Ziel auswählt.

Hier ist eine Möglichkeit, dies zu tun: Wenn A * einen gültigen Pfad zurückgibt (Start- / Endknoten in Pfad stimmen mit Eingabeknoten überein), geben Sie den Pfad zurück. Andernfalls...

  • Beginnen Sie mit der Suche ab dem Anfangsknoten
  • Durchqueren Sie alle verknüpften Knoten (denken Sie daran, die besuchten zu markieren, um eine unendliche Rekursion zu vermeiden).
  • Vergleichen Sie die Entfernungen zum Ziel, um den nächstgelegenen Knoten zu finden
Schlange5
quelle
So etwas wie Flood Fill scheint angemessen zu sein. En.wikipedia.org/wiki/Flood_fill Beachten Sie, dass Sie immer noch A * vom Startknoten zum Knoten mit dem geringsten Abstand benötigen. Beachten Sie auch, dass dies immer die Überprüfung aller verbundenen Knoten umfasst und daher extrem langsam sein kann.
Roy T.
Ja, es könnte langsam sein. Aber die Langsamkeit würde höchstwahrscheinlich davon herrühren, dass die Knoten im Speicher verstreut sind. das kann leicht behoben werden. Es ist auch möglich, es zu beschleunigen, indem Sie auf Genauigkeit verzichten - überspringen Sie einfach zu weit entfernte Links oder zeigen Sie in die falsche Richtung.
Schlange5
1
@Roy: A *, BFS, und all ähnliche Wegfindung Algorithmen genau das , so langsam wie Hochwasser-fill, weil sie alle brauchen alle angeschlossenen Knoten zu überprüfen , um sicherzustellen , es ist kein Weg bis zum Ende. Es gibt jedoch Möglichkeiten, dieses Problem zu lösen. siehe hier .
BlueRaja - Danny Pflughoeft