ノードやセルのないグリッドレス2D平面にA*アルゴリズムを実装するにはどうすればよいですか？ゴールの邪魔になる比較的多数の静止した障害物や移動する障害物を回避するためのオブジェクトが必要です。私の現在の実装は、オブジェクトの周りに8つのポイントを作成し、それらをオブジェクトの潜在的な位置である可能性のある想像上の隣接する正方形の中心として扱うことです。次に、それぞれのヒューリスティック関数を計算し、最適なものを選択します。始点と移動点の間、および移動点と目標の間の距離は、ピタゴラスの定理を使用して通常の方法で計算します。問題は、この方法では、オブジェクトがすべての障害物を無視することが多く、2つの位置の間を行ったり来たりするときにスタックすることがさらに多いことです。ばかげたmuの質問がどのように見えるかはわかりますが、どんな助けでもありがたいです。
4661 次
5 に答える
5
問題に適した解像度で架空のグリッドを作成します。パフォーマンスを向上させるために可能な限り粗いが、障害物間の（望ましい）ギャップを見つけるのに十分なほど細かい。グリッドは、障害物オブジェクトを持つ四分木にも関連している可能性があります。
グリッド上でA*を実行します。グリッドには、静的な障害物への近さなどの有用な情報が事前に入力されている場合もあります。グリッドの正方形に沿ったパスができたら、パスに変化がある場合は常に、そのパスを一連のウェイポイントに後処理します。次に、ウェイポイント間の線に沿って移動します。
ちなみに、実際の距離は必要ありません（ピタゴラスの定理についての言及を参照）：A *は、距離の推定値で正常に機能します。マンハッタン距離は人気のある選択肢です：|dx| + |dy|。グリッドゲームで斜めの動きが許可されている場合（またはグリッドが「偽物」である場合）、max(|dx|, |dy|)おそらく十分です。
于 2010-10-29T18:38:22.803 に答える
1
ええと 最初に頭に浮かぶのは、各ポイントで勾配またはベクトルを計算して、次のステップに進む方向を見つける必要があるということです。次に、小さなイプシロンで移動してやり直します。
これは基本的にグリッドを作成します。小さなイプシロンを選択することでセルサイズを変えることができます。固定グリッドを使用する代わりにこれを行うことにより、各ステップで小さな角度でも計算できるはずです-8ポイントの例から45°よりも小さいです。
理論的には、数式をシンボリックに解くことができるかもしれません（0に対するeps）。これは、最適な解につながる可能性があります...ただの考えです。
于 2010-10-29T18:28:57.147 に答える
1
障害はどのように表されますか？それらはポリゴンですか？その後、ポリゴンの頂点をノードとして使用できます。障害物がポリゴンとして表されていない場合は、障害物の周りにある種の凸包を生成し、その頂点をナビゲーションに使用できます。編集：私はちょうど気づきました、あなたはあなたが比較的多数の障害物の周りをナビゲートしなければならないと言いました。障害物の頂点を使用することは、多くの障害物では実行不可能な場合があります。
動く障害物についてはわかりません。A*は動く障害物のある最適な経路を見つけられないと思います。
あなたはあなたのオブジェクトが前後に動くと言います-A*はこれをするべきではありません。A*は各移動ポイントを1回だけ訪問します。これは、その場で、または移動する障害物から移動ポイントを生成することによるアーティファクトである可能性があります。
于 2010-10-29T18:38:04.960 に答える
1
大学でこの問題に遭遇したことを覚えていますが、A*検索は使用しませんでした。数学の詳細は思い出せませんが、基本的な考え方はお伝えできます。たぶん、他の誰かがもっと詳しく知ることができます。
オブジェクトがたどることができる潜在的なフィールドをプレイエリアから作成します。
競技場を取り、スタートポイントが最高点になり、ゴールが最低点になるように傾けるか、ワープします。
それが目的地であることを強調するために、可能性を目標に十分に突き刺します。
- すべての障害物に対して、潜在的な丘を作成します。あなたのような非点障害物の場合、潜在的なフィールドは障害物の端で漸近的に増加する可能性があります。
次に、オブジェクトを大理石として想像してください。スタート地点に置くと、障害物の周りで競技場を転がり落ち、ゴールに落ちるはずです。
難しい部分、私が覚えていない数学は、これらのバンプとウェルのそれぞれを表す方程式です。それがわかったら、それらを足し合わせて最終的なフィールドを取得し、ベクトル計算を行って勾配を見つけます（towiが言ったように）。これが、どのステップでも進みたい方向です。うまくいけば、この方法は、障害物が移動するため、すべてのステップで再計算できるほど高速です。
于 2010-10-29T18:39:13.167 に答える
1
NorvigとRusselによる人工知能のA*の議論に基づいたWumpusゲームを実装しているようです：現代的なアプローチ、または非常によく似たものです。
その場合、ヒューリスティック機能の一部として障害物検出を組み込む必要があります（したがって、ここに示すように、障害物の兆候をエージェントに警告するセンサーが必要になります）。
前後の問題を解決するには、移動したパスを保存して、すでにその場所に行ったことがあるかどうかを判断し、ヒューリスティック機能で過去N回の移動（たとえば4回）を調べて、それをタイブレーカー（つまり、ここから北と東に行くことができ、最後の4つの動きが東、西、東、西、今回は北に行く場合）
于 2010-10-29T18:48:12.553 に答える