あるたおるた - 敵の移動ルーチン

| トラックバック(0)

どうも あ〜る です。

前回、障害物を配置したことにより
敵がただ直線的に動くと障害物に引っかかって
進めなくなってしまうので
今回はそれを解消するための移動ルーチンを考えます。

基本的な考え方は、マップがチップ単位になっているので
チップの中央を通過しながら、障害物のない上下左右隣のチップに
移動していけば障害物にぶつからずにすむというものでしょう。

でもただ闇雲にランダムに進む先を決めていると
目標地点までたどり着くのに時間がかかりすぎます。

なので、現在地チップから目的地チップまでの
最短経路を求めて、それに沿って進むということを考えました。

そこで、前回の再起呼び出しのルーチンを応用して、
現在地からの距離マップを作ればいいかと思ったのですが
これだとどうも具合が悪そうです。

例えば、こんな再帰処理にすると...

enemy_routine_1.png

どこまで繰り返してもまだ短いルートの検索が
残っているかもしれないので、
全てのケースを処理しなければなりません。
これはさすがに馬鹿っぽいですね...。
この説明だけだと分かりにくそうなので、例えば
下の図のようなケースを考えれば分かるでしょう。

enemy_routine_2.png

開始地が緑で目的地がオレンジとすると、
再帰呼び出しの順序により、上ルート、下ルート、左ルート
の順序で左隣のチップのチェックが行われます。
(説明のために他のルートをはしょっています。)
そうすると、この下ルートでたどり着いた時は
すでに埋められている距離よりも長く、
左ルートでたどり着いた時は短くなります。
どのタイミングで調べたルートが最短かは
その時点では分からないので、
全ルート探索が必要になってしまうということになります。

ということで、再帰呼び出しでの処理はせず
こんな風に考えました。

enemy_routine_3.png

目的地はオレンジのチップであるとします。
まず、調べなければならない先端部分(図の赤いチップ)を配列に登録します。
登録されたチップについて、
・距離マップに距離を登録
・上下左右のチップが進入可能かつすでに距離が登録されていないなら
 次の先端部分として配列に登録
という処理をします。
そしてこれを目的チップに到達するまで繰り返します。
最後に目的地から距離が1ずつ小さくなる隣接チップを
たどって戻ればルートが完成します。

最後の図で距離が埋められていないところは
目的地までの距離が確定しており、
もう調べる必要はないので打ち切りです。
目的地への最短ルートは2通りありますが
どっちでもいいので、目的地から最初に見つかった
距離4のチップへのルートをたどっていきます。
これであれば無駄なくルートが調べられそうですね。

ということで、コーディングしてきますー。

トラックバック(0)

トラックバックURL: http://kei-prj.com/mt/mt-tb.cgi/45