2D RTSでの作業を計画して、Astarがどのように機能するかを学ぼうとしました。実際、Astarをバイナリヒープと組み合わせて最適化する方法や、 JumpPoinSearchアルゴリズムなどのパス対称性を利用するアルゴリズムを説明する記事を見つけました。ジャンプポイント検索を実装しようとしましたが、正常に実行されます。私はMovingAIのマップを使っていくつかのベンチマークテストを行いました。
しかし、問題があります。斜めの動きが許可されている場合、すべてが正常に実行されます。無効にされている場合、パスは返されません。
それは私がそれを実装した方法に関連しているかもしれません、そして私はすべて尋ねています...一般的に、あなたは目標に到達するために（斜めの動きではなく）まっすぐな動きだけを含むパスを検索するようにアルゴリズム（JPS）にどのように義務付けますか？
ジャンプポイント検索には、対角線が機能する必要があります。状態アルゴリズムが入っている場合、これはその制限の1つです。また、対称性が失われるため、地形を区別できるようにすることはできません（泥=動きに対するペナルティなど）。A *に固執し、地形表示（メッシュ、ウェイポイント）によってパフォーマンスを向上させることをお勧めします。または、HPA*を確認してください。
元の方向に垂直な方向に沿ってサブ検索を送信する場合（斜めの動きの場合と同様）、基本的な方向のみを使用するバージョンのJPSを作成できるはずです。そうすることで、特定の場所にあるノードがさらに先のノードを見つけるタイミングを見つけることができます。
まあ、技術的に言えば、斜めの動きが許可されていない場合、最適なヒューリスティックはマンハッタン距離です。つまり、A*は最小限の動きで答えを見つけることができます。クローズドリストを使用するのではなく、各ノードがonOpenおよびonClosedブール値を持つグリッドでマップを表すことは、非常に最適化されます。さらに、std make heap、push_heap、およびpop heapを使用すると、コストlog n（1からpop +lognからsort=O（logn））で最も安価なノードを取得できます。これは、ベクトルを使用するよりもはるかに優れたスケーリングです。