私のパスファインディング領域の周りに境界を配置することは受け入れられますか？

Question

現在、A* PathFindingアルゴリズムを使用して、無限のグリッド上のパスを計算します（AP CSのケーススタディでは、GridWorldのバウンドグリッド、AP CSのケーススタディを使用しています）。エンドノードが壁に完全に囲まれているため、有効なパスが存在しない場合を除き、すべてが素晴らしく機能します。予想どおり、アルゴリズムは無限に検索を続け、エンドノードを見つけることはありません。

これに対する可能な解決策は、目に見えないものを配置することです（ユーザーはそれらを表示しませんが、アルゴリズムは実行されます）パスファンディング領域全体の周りの壁は、開始ノード、エンドノード、およびすべての壁ノードがこれらの内にあることを確認します壁、2〜3スペースのパディングなど。何かのようなもの：

_________________________________
|                               |
|              S  |             |
|            _____|   _____     |
|                     | E |     |
|                     |___|     |
|_______________________________|

...最終的にすべてのノードがクローズドリストに追加され、オープンリストが空になり、その時点で有効なパスが存在しないことがわかります。

これは問題に対する合理的な解決策のように思えますか？これが潜在的にうまくいかない可能性のある方法はありますか？別の解決策は、同時に最後から後方にパスファインドすることであることを理解していますが、これは、特にエンドノードがそれほど密接に囲まれていない場合に、潜在的に高価になる可能性があるようです。

Answer 1

エンドノードはどこにあるのか正確にはわかりませんか？そうした場合は、アルゴリズムを実行する前に囲まれているかどうかを確認してください。

Answer 2

あなたの質問に関する私のコメントも参照してください。入力した後、私は素晴らしい解決策であるかもしれないものを思いつきました。これは、エンドノードを知らず、上記のようにエンドノードの位置で何もできない場合です。

あなたは次の線に沿って何かをすることもできます：「私は自分のフィールドに閉じた箱を見つけました、そしてその後の道はありません バツ 一緒に時間 y％ 私はパスがないと言うことができます、そして更新します y％ 時間の経過とともに増加するが、100％に達することはない。

検索エリアに境界を搭載し、何もしていない最中にある素晴らしいソリューションかもしれません。

Answer 3

私は同様の問題を抱えていましたが、これが私がしたことです：

1. のアルゴリズムを実行します n Bの検索から始まる反復
2. のアルゴリズムを実行します n Aを検索するBから始まる反復

どちらかの実行が、どちらか一方が完全に分離された領域にあると判断した場合（これ以上開けたノードはありません）、検索は失敗します。それ以外の場合、検索は通常どおり行われます。

ここでのトリックは、もちろん、のための良い価値を思いつくことです n. 。私は増加して複数のパスをしました n 結果をキャッシュしました（私のグラフはあまり変わりませんでした）。

Answer 4

*を使用しているので、地形ノードにコストで重みを付けることができるはずです。壁のノードに非常に高いコストをかけます。可能なパスの総コストよりも大きくなければなりません。パスの終了コストがその境界コストよりも大きい場合、パスを見つけるために壁を通過する必要があるため、無効です。 A*アルゴリズムは高コストノードを中心にルーティングしているため、必要にならない限り壁を通り抜けることはありません。