14

A* ヒューリスティックと Bresenham アルゴリズムの仕組みについて私が理解していることから、現在の状態と目標の状態のみがヒューリスティック関数に渡されるため、これは不可能な場合があります。しかし、誰かがこの問題に対する賢い解決策を持っているかもしれません。

A* を使用してグリッド上のパスを計画しています。現在の状態と目標または障害物を回避する次のターンの間に空きスペースがある場合に、最適なパスがブレゼンハムの線をたどるヒューリスティックが必要です。

問題を説明するためのいくつかの画像を次に示します。

マンハッタン距離:

ワールド内の動きがグリッド上のチェッカーのように機能する場合、これはまったく問題ありませんが、最終的には A* パスを連続平面上のモーションに変換するので、これは非常にうまく機能します。

マンハッタン距離ヒューリスティックを使用した赤から緑への最短経路

ユークリッド距離:

改善されましたが、まだ完全ではありません。端の直線に注目してください。対角線は、私が望んでいるものと同じくらい簡単に対角線のままにすることができました。

ユークリッド距離ヒューリスティックを使用した赤から緑への最短経路

私が欲しいもの:

Bresenham のラインは、次のターンまたはゴールに引き寄せられます。

ブレゼンハムのラインを使ってゴールに到達する、私が実際に望んでいる最良のパス

ここで良いリソースを見つけましたhttp://theory.stanford.edu/~amitp/GameProgramming/Heuristics.htmlは、私が探しているものに触れていますが、最初からゴールまでブレゼンハムの線を引くためにしか機能しないようです。私が欲しいのは、ブレゼンハムの線が障害物を迂回して次のターンに引き寄せられることです。

この問題への良いアプローチのアイデアはありますか?

4

4 に答える 4

3

コスト関数をオンザフライで変更して、前に進むコストが累積されたエラーで増加するようにすることはできますか?

アイデアは、アルゴリズムの開始時に、標準の Bresenham のように DX と DY を計算することです。(この例の残りの部分では、DX > DY > 0 と仮定します。他の方向に合わせて変更してください。)

次に、訪問したすべての隣接ノードについて、Bresnaham エラーを追跡します。

if (neighbor.X > this.X) 
   neighbor.err=this.err+DY 
else if (neighbor.Y > this.Y) 
   neighbor.err=this.err-DX

次に、コスト関数を変更して X の増加を優先しますが、追加しif (err >= DX/2) then cost=cost+FACTORます。他のすべてのコストが等しいマップでは、これは正しい線をたどるはずです。

あなたが必要とするかもしれない他のことは、パスが障害物を回避するときの特別な処理です。隣接ノードが +X または +Y 方向にない場合はいつでも DX と DY を再計算することで、その状況を処理できる可能性があります。(残念ながら、これにはノードごとに個別の DX、DY、およびエラーを追跡する必要があり、オーバーヘッドが大きすぎる可能性があります)

免責事項、私は A *または Bresneham アルゴリズムを何年も実装していません。このアイデア全体が機能しない可能性があります

于 2011-04-24T16:14:55.103 に答える
1

すべての移動手段を現在の位置 (またはゴールが表示されている場合はゴール) から見えるコーナーに配置し、最短経路を見つけたら、すべてのストップ間にブレゼンハム ラインを引きます。

于 2011-04-24T17:29:55.370 に答える
0

Bresenham アルゴリズム、おそらく適応 Bresenham、たとえば空間充填曲線で衝突検出を使用できますか?

于 2011-04-24T16:40:16.537 に答える
0

リンク先の記事の同点の解消セクションで説明したように、このノードがその親と目標の間の線上にどれだけ近いかというヒューリスティックに要因を追加できます。そうすれば、可能な限り直線パスにとどまることが優先されます。

于 2011-04-24T21:10:30.053 に答える