私はかなり単純なトップダウンの 2D ゲームを書いています。すべての衝突データに対して、タイルの等間隔の 2D グリッドを使用します。グリッド内の各タイルは、塗りつぶされているか空です。
経路探索のために、私は A* (A Star) を使用しており、Manhattan と Diagonal (別名 Chebyshev 距離) ヒューリスティックの両方を試しました。
これはほとんどの場合うまく機能しますが、凹状の形状 (例: U 形状) のくぼみに位置するターゲットへのパス検索を試みると、非常にコストがかかります。
たとえば、下の図では、右側の人物が左側の人物へのパス検索を行います。草 (緑、濃い緑、黄色) はすべて空きスペースです。固体タイルは、茶色の「木」タイルと灰色の「石」タイルのみで、横向きの「U」の形をしています。
これがパス検索の結果です (この場合は Manhattan Heuristics を使用した A*)。
赤と緑のデバッグ ドロー スクエアは、A* 検索中にアクセスされたタイルを示します。赤は「クローズド」リストにあり、緑は「オープン」リストにあります (A* 仕様による)。選択された最終パスの青い線 (正しい)。
ご覧のとおり、検索はかなり徹底的で、多くのタイルを訪問し、ほぼ完全な円を作成しています。
A* アルゴリズムと、私が選択したヒューリスティックに基づいて、なぜこれが起こっているのかを理解しています (壁に沿ってターゲットを通過すると、遠くにあるタイルの F 値が高くなり始め、正しい値に戻る前にそれらを調査する必要があります)。道）。私が知らないのは、これをより良くする方法です:)
可能な改善に関する提案はありますか？おそらく別のヒューリスティック？たぶん、すべて一緒に別のパス検索アルゴリズムですか？
ありがとう！
いくつかの提案に基づいて、A* 実装を更新してHPA*で見つかった改善を含めることに傾いています。いくつかの最初の読み取りに基づいて、階層の適切な粒度を考えると、上記のようなケースに非常にうまく対処できるようです. これを調べ終わったら更新します。
