java - グラフでのパスファインディング？（GPS）？

Question

私のゲームの都市は、基本的に道路と交差点のグラフです。

各道路には、始点と終点の交差点への参照があります。

各交差点には、上、左、下、右の道路への参照があるか、3方向、2方向の交差点などの場合はnullがあります。

道路は長方形です。

これを考えると、道路Aから道路Bに到達するためのパスを生成する方法はありますか？（A *と言うよりも簡単なことはありますか？

ありがとう

Answer 1

グラフは重み付けされていないため、 BFSを試すことができます-情報がなく、おそらくA *アルゴリズムよりも遅くなります（A *の妥当なヒューリスティック関数を使用）。

双方向BFSを実行することで、少し高速化できます。これは、重み付けされていないグラフでも最適であり、標準のBFSよりもはるかに高速である必要があります。
双方向BFSの考え方は単純です。最初から最後まで（次々に）BFSステップ（深さ1、深さ2、...）を実行し、見つけたら2つの検索の前面が交差していること-あなたはあなたの道を持っています。 通常の
BFSO(2 * B^(d/2)) = O(B^(d/2))がdBO(B^d)

Answer 2

すべてのパスファインディングアルゴリズムを自分で実装したくない場合は、JGraphTを強くお勧めします。これは、すべてのグラフ作成のニーズに対応する優れたライブラリです。エッジのリストを返すことにより、最短パスを見つけることができます。

ただし、確かに学習曲線があります。私はWeightDirectedGraphsを使いたいと思っていましたが、それを使用する適切な方法を見つけるために少しグーグルが必要でした。

編集：あなたがあなたの投稿にJavaとC ++の両方のタグを付けていることに気づきましたが、JGraphTはJavaライブラリです（名前のJが示すように）。

Answer 3

ダイクストラのアルゴリズムは非常に簡単です。