java - 複数の可能なエンドポイントを持つ2dパス検索?

Question

現在、Javaでのパス検索に関する別の質問があります。しかし、これは別の質問だと思います。

ゲームを作っています。経路探索では、複数のエンド ポイントを処理できる必要があります。私が見つけたすべてのパス検索アルゴリズムとチュートリアルには、1 つのエンドポイントしかありません。

この変更は、既存のコードに簡単に変更できるのでしょうか?それとも、自分でゼロから作成するほうがよいでしょうか?

Answer 1

を使用しているA*が、ゴールと見なすことができる複数の頂点がグラフにある場合、各ゴールまでの距離を推定し、最小値を使用できます。A*目標までの実際の距離を過大評価しない限り、機能します。

ただし、この特殊な動作により、独自のA*実装を作成する必要が生じる場合があります。コードはそれほど多くありません。大学生の IIRC の宿題は 1 日か 2 日かもしれません。

Answer 2

ゲームについてはよくわかりませんが、Floyd-Warshallは複数のエンドポイントの最短パス アルゴリズムです。