2D Pfadfindung mit mehreren möglichen Endpunkten?

Question

I currently have another question mit Wegfindung in Java zu tun. Ich denke jedoch, dass dies eine separate Frage ist.

Ich mache ein Spiel. Die Pfadfindung muss in der Lage sein, mit mehreren möglichen Endpunkten umzugehen. Alle gefundenen Algorithmen und Tutorials haben nur einen Endpunkt.

Wäre es leicht, diese Änderung in ein bereits existierendes Stück Code zu ändern, oder sollte ich besser versuchen, mein eigenes von Grund auf neu zu schreiben?

Answer 1

Wenn Sie A* verwenden, aber mehrere Eckpunkte in Ihrem Diagramm haben, die als Ziele betrachtet werden können, können Sie die Entfernung zu jedem Ziel schätzen und das Minimum verwenden. A* funktioniert so lange, wie Sie die tatsächliche Entfernung zum Ziel nicht überbewerten.

Dieses spezielle Verhalten kann jedoch dazu führen, dass Sie Ihre eigene A* Implementierung schreiben. Es ist nicht viel Code; vielleicht ein oder zwei Tage Hausaufgaben für einen College-Studenten, IIRC.

Answer 2

Ich weiß nicht viel über Spiele, aber Floyd-Warshall ist ein Multiple-Endpunkt-Kürzester-Pfad-Algorithmus.