9

AからBへのパスを見つける必要がある2Dグリッド内のエンティティを制御するAIに使用するパスファインディングアルゴリズムを探しています。最短パスである必要はありませんが、非常に高速に計算する必要があります。グリッドは静的であり（変更されることはありません）、一部のグリッドセルは障害物で占められています。

現在A*を使用していますが、常に最速のパスを計算しようとするため、目的には遅すぎます。主なパフォーマンスの問題は、パスが存在しない場合に発生します。その場合、A*はあまりにも多くのセルを探索しようとします。

パスが最短パスである必要がない場合に、A *よりも高速にパスを見つけることができる別のアルゴリズムを使用できますか？

ありがとう、

ルミナル

4

7 に答える 7

9

グリッドが静的で変化しないと仮定します。グリッドを構築した後、グラフの連結成分を一度計算できます。

次に、ソース頂点とターゲット頂点がコンポーネント内にあるかどうかを簡単に確認できます。はいの場合はA*を実行し、そうでない場合はコンポーネント間にパスがないため実行しないでください。

BFSまたはDFSを使用して、グラフの連結成分を取得できます。

于 2013-03-19T19:19:50.643 に答える
4

最短パスの代わりにパスを見つけるには、グラフ走査を使用します（たとえば、深さ優先または最良優先）。必ずしも高速であるとは限りません。実際、一部のグラフではA *よりもはるかに多くのノードをチェックする可能性があるため、データによって異なります。ただし、実装は簡単で、定数係数は大幅に低くなります。

パスがないときにパスが検索されないようにするには、（グラフを作成した後で）互いに素なセットを作成して、指定された2つのポイントが接続されているかどうかをすばやく確認できます。これには線形空間と線形時間が必要であり、ルックアップには実質的に一定の時間がかかりますが、パスがあるかどうかだけがわかり、そのパスがどこに行くかはわからないため、完全なアルゴリズムを実行する必要があります。

事前にデータ構造を構築していて、実行時に瞬時の最短経路と交換するための時間とスペースがもう少しある場合は、ケーキを持って食べることもできます。Floyd-Warshallアルゴリズムは、すべての最短経路を提供します。 O(|V|^3)| V |²（開始、宛先）のペアがあることを考えると、これは比較的控えめな時間です。少し大きい可能性のある行列を計算し|V| * |V|ますが、これは整数行列であり、必要なのは|V| * |V| * log_2 |V|ビットのみであると考えてください（たとえば、1024個の頂点に対して1.25 MiBです）。

于 2013-03-19T19:37:02.350 に答える
2

2つの頂点が接続されているかどうかを知りたいだけなので、DFSまたはBFSのいずれかを使用できます。両方のアルゴリズムは、グラフ内のすべての頂点のセットであるO(|V|)場所で実行されます。V

ヒューリスティックが計算されるのに取るに足らない時間がかかる場合は、この2つのアルゴリズムのいずれかを使用してください。そうでない場合、A *はDFSまたはBFSと同様に、またはより適切に実行されるはずです。

別のオプションとして、Floyd-Warshallアルゴリズム（O(V^3)）を使用して、グリッドを作成した後、頂点の各ペア間の最短距離パスを計算できます。これにより、シミュレーションの開始時にすべての重労働を実行し、すべての最短を保存します。ハッシュ内のO（1）アクセスのパス、またはこれがメモリ爆発的すぎることが判明した場合は、頂点から頂点に移動するために必要な頂点を格納するような行列を保持できnextます。したがって、からへのパスを構築できます。next[i][j]ijij(i, k1=next[i][j]), (k1, k2=next[k1][j]) ... (kr, j)

于 2013-03-19T19:15:42.007 に答える
1

グラフが十分に小さい場合は、Floyd-Warshallアルゴリズムを使用してすべての最短経路を事前計算できます。これにはO(|V|²)、パスを保存するためのメモリとO(|V|³)、事前計算のための時間が必要です。

明らかに、これは非常に大きなグラフのオプションではありません。それらの場合、最も高価なA *検索を回避するために、Thomasの回答を使用し、連結成分を事前計算する必要があります（線形時間とメモリを使用します）。

于 2013-03-19T19:34:40.073 に答える
0

A *、BFS、DFS、およびその他すべての検索アルゴリズムは、パスがない場合にまったく同じ数のノードをチェックする必要があるため、「最初にDFSを使用する」は適切な答えではありません。また、Floyd-Warshallを使用する必要はまったくありません。

静的グラフの場合、解決策は単純です。@Thomasの回答を参照してください。非静的グラフの場合、問題はより複雑です。優れたアルゴリズムについては、この回答を参照してください。

于 2013-03-19T23:33:35.890 に答える
0

迷路が決して変わらず、存在するパスが永遠に存在する場合、迷路の「領域」を見つけてそれらを何らかの形式で保存するマッピングアルゴリズムを使用できませんか？メモリ使用量はノードまたはセルの量に比例し、速度は配列の2つの要素にアクセスして比較する速度です。

コンピューティング（リージョンへのスプライティング）はおそらくもっと時間がかかりますが、最初に一度実行されます。たぶん、この目的のためにいくつかのフラッドフィルアルゴリズムを適応させることができますか？

上記から明らかかどうかはわかりませんが、例は常に役立つと思います。PHP構文を使用してご容赦ください。

例（迷路5x5）（[]障害物をマークします）：

    0 1 2 3 4
  +----------+
0 |[][]   2  |
1 |  [][]    |
2 |    []  []|
3 |  1 []    |
4 |    []    |
  +----------+

インデックス付き領域（「x：y」の代わりに数値ハッシュを使用する方が良い場合があります）：

$regions=array(
    '0:1'=>1,'0:2'=>1,'0:3'=>1,'0:4'=>1,'1:2'=>1,'1:3'=>1,'1:4'=>1,
    '2:0'=>2,'3:0'=>2,'3:1'=>2,'3:2'=>2,'3:3'=>2,'3:4'=>2,'4:0'=>2,
    '4:1'=>2,'4:3'=>2,'4:4'=>2
);

その場合、タスクは、開始点と終了点が両方とも同じ領域にあるかどうかを確認することだけです。

if ( $regions[$startPoint] == $regions[$endPoint] )
    pathExists();



誤解しない限り、A *の複雑さ（速度）は開始点と終了点の間の距離（または解の長さ）に依存します。これはおそらく検索を高速化するために使用される可能性があります。

迷路の中にいくつかの「ジャンクションノード」（JN ）を作成しようとします。それらは関数上に配置でき（最も近いJNがどこにあるかをすばやく知るため）、隣接するすべてのJN間のパスが事前に計算されます。

したがって、開始点から最も近いJNまで、および終点から最も近いJNまで（すべてが同じ領域（上記）にある場合）、ソリューションを検索するだけで済みます。これで、いくつかの領域があり、その一部にJNがまったくないか、すべてのJNが迷路の障害物に落ちるシナリオ（迷路の複雑さに関して関数が適切に選択されていない場合）を見ることができます。 ..したがって、可能であればこれらのJNを手動で定義するか、このJN配置機能を重要なものにする（各領域の面積を考慮して）方がよい場合があります。

JNに到達すると、それらの間のパスにインデックスを付けるか（開始JNと終了JNの間の事前定義されたパスを高速に取得するため）、または別のA *パスファインディングを実行できます。ただし、今回は「ジャンクションノード」のセットのみです。それらのうち、 JN間のこのパス検索はより高速になります。

于 2013-03-21T11:10:26.887 に答える
0

Anytime A *アルゴリズム（ANA *またはその他のバリアント）の使用を検討できます。

これらは、最初のパスを見つけるために貪欲な最良優先探索を実行することから始まります。

次に、ヒューリスティック関数を使用して実行することにより、重みがますます少なくなり、段階的に改善されます。

いつでも検索を中止して、これまでに見つかった最適なパスを取得できます。

于 2013-04-14T00:40:23.610 に答える