マルチプルターゲットのためのA *経路探索を最適化する

Question

ある場所から別の場所にいくつかのユニットを移動したい。 2〜3ユニットは問題ありませんが、20〜30に移動しようとすると多くの時間がかかります...一般に、ユニットはほぼ同じ方向に移動するので、20回カウントする必要はありません...私は最初のユニットから道を辿り、残りのユニットのパスを "追加する"と考えました（私は、最初のユニットのパスPを呼び出すと、ユニットn→Pスタート）+ユニットnのP +（P end - > Unit n target）...素晴らしいですが、場合によっては2番目のユニットがターゲットのすぐ近くにある場合のExpamleのために、それは1番目に行く必要がありますユニットを起動してからターゲットに戻ってください...どうすれば最適化できますか？多分ユニットをグループに分けてグループを移動するのは良い考えですか？私は私の...英語と申し訳ありません長いため、テキストが読みにくい悪い

Answer 1

いくつかの考えのための任意の助け

ありがとう、申し訳ありません...より良いアイデアAY持っていけない：

1. スタートすべての検索の共通点：ターゲット位置を検索します。
2. すべてのユニットの最小距離をA *ヒューリスティックとして使用します。これは、最適パスをもたらす許容ヒューリスティックです。これは、ユニットのたくさんの計算が多少遅くなるかもしれない、あなたは最初のユニットを見つけた後、検索を再起動しないでくださいここではいくつかのトリック
3. をしなければならないかもしれませんが、あなたがそれらのすべて

あなたを見つけるまでちょうど検索を続けますこれは後方検索であるため、すべての「許可された移動」チェックの方向を反転する必要がありますが、それ以外の場合はおそらくうまく動作します。ただし、移動するユニットの開始時に正確なパスを計画することは、パスが恐ろしく愚かに見えない限り、まだ必要でないときにはあまりにも多くの作業を行います。そして、あなたが他のユニットがパスをブロックしていると考えると、それらの正確なパスはしばしば無効になります。

Answer 2

有望な解決策は、パスキャッシングです。

特に、ノードX_0からX_nの順序付けられたシーケンスからなる最短経路Pは、多くの有益な情報を有する。

最も重要なのは、どのI> = 0と私< J < = nに、X - jがへX_Iからの最短パスは、パス内のノードのサブシーケンスである、P.

これはあなたに非常に多くを与えます潜在的に再利用できるデータ（実際にはn^2個のデータ）があります。

マップが変更されていない場合は、all-pairs shortest pathを事前計算する方が現実的かもしれません。これは実装が簡単なアルゴリズムですが、O（n^3）時間がかかります。

これまで述べてきたように、A *の実装では最近のパスのハッシュテーブルを単純に維持するほうが意味があります。

Answer 3

私は次のことがわかりました。

1. 前述のようにパスキャッシングを使用します。マップが動的であり、キャッシュを頻繁にクリアする必要がある場合、これはうまくいかないかもしれません。

2. グループを使用します。ユニットのグループを1つとして扱い、リーダーをリーダーとして指定し、そのパスを見つけます。他のユニットは、リーダの足音にちょうど従うことができ、それらの足音を見つけるためのマイナーな道があります（したがって、ユニットはメインパスにも障害物を避けるように見えます）。これが機能するためには、互いに隣り合っているユニットを選んで、部下から指揮官までの道のりは本当に小さくすべきです。

3. 対話性のトレードオフ精度。一度にすべてのパスを計算せず、時間をかけてそれらを広げてください。パスを必要とするユニットに優先キューを使用し、いくつかポップしてパスを計算します。あなたは、あなたのパスにもコードを見つける時間を与えることさえできます。私はグループ化とパスキャッシングを組み合わせてこれを行いましたが、私の実装におけるこの変更は私にとって最大の利益でした。