3

2D グリッドがあるとしましょう。パスファインディングは、私の問題の二次的なステップです。

私のことは、グリッドの真ん中にユニットがあるとしましょう。ユーザーに「これらはすべて利用可能な宛先です。」と伝えたい。

ユニットが歩けるマスの数に基づいて、ユーザーに「到達できるマスはこれだけです」と表示したいと思います。次に、ユーザーが選択した目的地をパス検索します。

到達可能な目的地を表示するために最初の検索を行う最良の方法は何ですか?

地形には、地形に応じてボーナスの制限もある場合があります。

これが何と呼ばれているのかわからないので、どこを見ればいいのか、何をググるべきなのかを教えていただければ幸いです。

乾杯！:)

/E

4

3 に答える 3

4

最善の方法は、おそらく深さ優先検索 (http://en.wikipedia.org/wiki/Depth_first_search) で、どこまで行けるかを制限することです。

于 2011-02-04T21:49:39.043 に答える
2

グリッド内の各ポイントについて、以下を保存します。

  • ユニットからこのポイントまでの最小距離。
  • 最短経路でユニットへの次のステップ。

これを計算するには、幅優先検索を実行します。

  • ユニットのポイント距離コストを 0 に設定し、その「パス ポインター」は重要ではありません/null です。
  • キューを作成し、その中に開始点を入れます。
  • キューが空でない間:
    • 次のポイントを取り、それを伝播します (すべての隣人を見てください。現在のポイントを介してそれらに行くことが有益な場合は、それらの距離/パスを設定し、それらをキューの最後に追加します)

制限がある場合は、正しいステップ数の後に検索を停止するように注意してください。

これを正しく行うと、到達可能なすべてのポイントを見つけることができ、それらの距離の長さを見つけて、利用可能な最短経路も取得できます (ただし、「後方」に保存されます)。

最短経路問題に対して深さ優先探索を行わないでください! 多くの繰り返し計算を何度も何度も行う可能性があります。(A* などのより高度なヒューリスティック アルゴリズムを使用している場合を除きますが、とにかく自分が何をしているのかを既に知っている必要があります)

于 2011-02-05T02:11:38.737 に答える
0

接続されたセルを同じ番号でマークし、異なる番号で接続されていないことをマークします。http://en.wikipedia.org/wiki/Connected_Component_Labelingで、セルをマークするための 2 パス アルゴリズムを見つけることができます。セルの数が異なる場合、プレイヤーはその場所に到達できません。

于 2011-02-04T21:52:48.060 に答える