path-finding - A* パスファインディング - 歩けない目的地に最も近い

Question

私はすでに動作する A* 実装を持っています。問題は、歩くことができない目的地を選択すると、パスが返されないことです。私は、私が得ることができる「最も近い」ものを手に入れたいと思っています。

望ましいオプションは完全に動的です (目的地の周りの 8 つのタイルをチェックして 1 つを見つけようとするだけではありません)。そうすれば、歩行不能なタイルの巨大な正方形に囲まれた歩行不能なタイルをクリックしても、可能な限り接近します。

Answer 1

ここで提供される簡単な答えで十分かもしれませんが、それはゲームの種類と何を達成しようとしているかによって異なると思います。

たとえば、このプレイ フィールドを見てみましょう (申し訳ありませんが、戦争の霧を示すために使用したのと同じソフトウェアを再利用しています :)) :

ご覧のとおり、Angry Chicken が左側と右側の間の通路を塞いでいます。怒っている鶏は何でもかまいません...それが静的な障害物である場合は、最も低いh nodeもので十分かもしれませんが、動的なオブジェクト (ロックされたドア、橋を描くなど...) の場合は、次の例が役立ちます。問題をどのように解決したいかを見つけます。

ヒーローの目的地を反対側に設定すると

明らかに到達できないため、パスをどうしたいかを考える必要があります。manhattan距離や距離などの標準的なヒューリスティックを使用するeuclidianと、次の結果が得られます。

これで十分かもしれませんが、私たちの小さなヒーローがニワトリとやり取りして通過できる方法があるとしたら、それはまったく意味がありません。あなたが望むのはこれです

どうすればこれを行うことができますか？これを行う簡単な方法は、 でパス検索を行うことですhierarchical graphs。これは複雑に聞こえますが、そうではありません。まず、複数のグリッド ノードを含む高レベルのノードとエッジの新しいセットを構築できるようにする必要があります (または他の表現では何も変わりません)。

ご覧のとおり、 rightblue nodeと left がありred nodeます。矢印は、2 つのノード間のエッジを表します。あなたが尋ねるこのグラフを作成する方法は？簡単です。開いているノードから開始し、すべての隣接ノードを展開して高レベル ノードに追加します。完了したら、グラフの別の部分につながる可能性のある動的ノードを開き、同じことを行います。

さて、私たちのヒーローから赤への道を尋ねるときX、あなたは最初に高レベルで経路探索を行います... からblue nodeへの道はありred nodeますか? はい！チキンを通して。

edgeニワトリである横断を可能にする に行くことで、青い側をナビゲートする方法を簡単に知ることができます。

それが単純な壁である場合、単一のノードにアクセスすることで、反対側に到達する方法がないことを非常に迅速に判断して、希望どおりに処理し、おそらく A* を実行して最低値を返すことができます。hノード。

Answer 2

最小の h 値を持つタイルを保持するポインターを保持できます。パスが返されない場合は、代わりに保持しているタイルへのパスを生成するだけです。