- 180 名前：デフォルトの名無しさん mailto:sage [2009/05/23(土) 20:48:53 ]
- >>173
最短経路が必要な場合は、２DRPGの最短移動アルゴリズムを使えばいいよ。
12x12の配列Aをワークとして用意する。型はintでいいや。
Aはすべて-1で初期化しておく。
まずスタート地点の決定。これは総当たりだから省略。
現在の探索深度を示すワーク int depth を用意して0に初期化する。
さて探索だけど、
1.スタート地点を現在値nowPositionに設定して、それに対応するAに０を代入する。
2.Aを全探索して、値がdepthになっているものがあれば、
その上下左右(斜めも移動できるなら斜めも）に移動可能かどうかを
調べる。移動可能で、かつその位置に対応するAが-1なら、その位置に
depth+1を書き込む。
移動可能な位置がゴールなら終了。４へ。
3.A全体を操作し終わるまで調べて、ひとつもdepthがなければ終了。ゴールには到達できない。
１つでもdepthがあれば、++depthして、２を繰り返す。
4.ここからが最短経路探索。
まずゴールには到達しているから、ゴールのdepthは分かってる。
そこから 上下左右のAの値が depth-1 になっている位置が最短経路。
複数ある場合の処理は好きなようにすればいいが、今回は単純に最初に
みつかった場所へ移動すればいいだろう。
5.これを繰り返してスタートに到達するまで続ける。なおスタートには必ず到達できる。
|
 |
