私はグリッドベースのトップダウンゲームのA*パスファインディングに取り組んでいます。私が遭遇した問題は、おそらく下の画像で最も理解しやすいでしょう。アスタリスクはプレイヤー/NPCです。黄色のアスタリスクは、Xへのパスを希望する現在のNPCです。赤いアスタリスクは、この場合は障害物であるNPCです。黄色のセルは壁、白いセルは床です。ゴールへのパス全体は実際には到達できませんが、それでも次善の場所（この場合はスポット番号8）へのパスを取得したいと思っています。
障害物の周りを簡単に通り抜けることができますが、私が説明したとおりに正確に行う方法がわかりません。障害物にぶつかったときに停止すると、3で停止しても正しく機能しません。最終目標からの距離が最も短いクローズドリストのタイルに再パスした場合、最終目標がもう一方にある場合例として壁の側面は、物事をかなりひどく台無しにする可能性があります。
助言がありますか？当たり前のことを見逃しているような気がするので、ここでバカを許してください。
ありがとう、ティム
問題の緩和に基づいたアイデアは次のとおりです。
まず、NPCを持たないグラフのすべての頂点の最短経路問題を解きます。ゴールノードから開始するダイクストラのアルゴリズムの単一のアプリケーションを使用して、各頂点でゴールに出入りする最短経路を取得できます。
次に、問題全体の中で最短経路を見つけようとします。ヒューリスティックとしてダイクストラ法を実行して取得した最短経路情報でA*を使用します。NPCの問題の最短経路は、緩和された問題の最短経路と少なくとも同じ長さであるため、許容されます。これまでの最良のパスを追跡し、検索スペースが使い果たされたときにそれを返します（コメントに投稿したように）。
これが高額だと思われる場合は、ダイクストラを1回だけ実行する必要があることを理解してください。同じグラフでA*の実行ごとに取得した情報を再利用できます。
（警告エンプター：私はこれを試しませんでした。）
1つの方法は、ブロッキングNPCを考慮せずに送信元から宛先へのパスを計算し、パス上に直接ブロッキングNPCがあるかどうかを確認することです。その場合、パス上の最初のブロッキングNPCを考慮に入れてから、パスを再度計算します。すすぎ、目的地に到着できなくなるまで繰り返します。これが起こったとき、あなたは「次善の」目的地として最後に成功したパス上の最新のブロッキングNPCの直前のポイントを取ることができます。
これはあなたの例ではうまくいくはずですが、目的地への入り口が2つブロックされている場合、この方法はさらに遠くの入り口に適用されます。また、最悪の場合、NPCの数だけ最短経路アルゴリズムを実行する必要があります。
ダイクストラとA*を1回だけ実行する必要があるため、larsmansによって提示された方法はこれよりもはるかに優れています。私はこれをあなたがとることができるアプローチの種類のアイデアとしてのみ提示します。