4

AS3 に A* アルゴリズムを実装しましたが、1 つのことを除いてうまく機能します。多くの場合、結果のパスは、ターゲットへの最も「自然な」またはスムーズなルートをたどりません。私の環境では、オブジェクトは、水平または垂直に移動できるのと同じくらい安価に斜めに移動できます。これは非常に簡単な例です。開始点は S でマークされ、終了 (または終了) 点は F でマークされます。

 | | | | | | | | | |
 |S| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

ご覧のとおり、最初の検索ラウンドでは、ノード [0,2]、[1,2]、[2,2] がすべて N のスコアを持つため、可能なノードのリストにすべて追加されます。私が抱えている問題は、続行するノードを決定しようとしている次の時点で発生します。上記の例では、次のノードを選択するために possibleNodes[0] を使用しています。これを possibleNodes[possibleNodes.length-1] に変更すると、次のパスが得られます。

 | | | | | | | | | |
 |S| | | | | | | | |
 | |x| | | | | | | |
 | | |x| | | | | | |
 | | | |x| | | | | |
 | | |x| | | | | | |
 | |x| | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

そして、 possibleNextNodes[Math.round(possibleNextNodes.length / 2)-1] で

 | | | | | | | | | |
 |S| | | | | | | | |
 |x| | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
x| | | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

これらのパスはすべて同じ数のステップを含むため、コストは同じですが、この状況では、最も賢明なパスは次のようになります...

 | | | | | | | | | |
 |S| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |x| | | | | | | | |
 |F| | | | | | | | |
 | | | | | | | | | |
 | | | | | | | | | |

数学的に正しいだけでなく、パスをより賢明に見せるための正式に受け入れられた方法はありますか?

4

5 に答える 5

10

ヒューリスティック関数にタイブレーカーを追加する必要があります。ここでの問題は、同じコストのパスが多数あることです。

直接ルートを優先する単純なタイブレーカーの場合は、クロス積を使用できます。つまり、S が開始点で E が終了点で、X がアルゴリズムの現在の位置である場合、SE と XE の外積を計算し、0 からさらに逸脱するほどヒューリスティックにペナルティを追加できます (= 直接ルート）。

コード内:

 dx1 = current.x - goal.x
 dy1 = current.y - goal.y
 dx2 = start.x - goal.x
 dy2 = start.y - goal.y
 cross = abs(dx1*dy2 - dx2*dy1)
 heuristic += cross*0.001

A* 全般に関する優れたチュートリアルであるhttp://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S12も参照してください。

于 2009-05-10T16:44:21.440 に答える
4

自然に見えるパスが必要な場合は、コストがデカルト座標系の長さに対応していることを確認する必要があります。つまり、斜めに移動するコストは、垂直または水平に移動するコストの sqrt(2) 倍になるはずです。

于 2009-05-10T16:46:48.927 に答える
2

各正方形のコスト計算に「制御努力」を追加できます。アクターは、パスにコストが追加されるため、向きを変えたり方向を変えたりしすぎないようにします。

http://angryee.blogspot.com/2009/03/better-pathfinding.html

于 2009-05-27T13:16:40.023 に答える
1

私の記憶が正しければ、これの秘訣は、コスト関数に追加のパラメーターを追加することです (隣接するノード間のすべてのステップ、またはあなたの場合は四角形に対して)。sqrt(2)斜めの動きよりも）。さて、パスを滑らかにすることと実際にルートの最適性を低下させる (延長する) ことの間にはおそらく微妙な境界線がありますが、これを回避することはできません. 独自のアプリケーションに固有のものを発見する必要がある特定のトレードオフがあり、これはテストによってのみ実際に達成できます。

ゲーム開発サイトに、これを行う方法を正確に詳述した記事があったと思いますが、現時点では見つけられないようです. とにかくコスト関数を試してみて、どのような結果が得られるかを確認してください。それが正しい方法だと確信しています。

于 2009-05-10T16:51:16.800 に答える
0

より「賢明」とは何ですか？もっとまっすぐ？アルゴリズムがそれについて何かをしようとしている場合は、それを適切に定量化する必要があります.

斜めに移動することは、水平/垂直に移動するのと同じくらい安価であるため、すべてのパスは、A* で使用できるすべての基準に従って同等です。より「賢明な」パスが必要な場合は、一部のパスが他のパスよりも望ましいことをアルゴリズムに伝え、水平/垂直を対角線よりも「良い」ものとして効果的に重み付けする必要があります。私が見る限り、それはあなたの環境のパラメータを変更することです.

于 2009-05-10T16:47:26.587 に答える