移動可能範囲計算

[PR]横浜で超魅力価格の記念写真を:記念写真が大人気､結婚写真､成人式写真

移動可能範囲計算

　このページは、シミュレーションゲームでよく使用されている移動可能範囲計算のアルゴリズムについて説明します。
　このアルゴリズムを用いることにより、自作のゲームにファイアーエンブレムなどの戦略的な要素を組み込むことができます。
　ただし、このアルゴリズムは私が学生時代のときに考えたものであり、実用性については、業界人ではないので良くわかりません。
　メモリを無駄に使いますので、メモリの厳しい環境には利用できないかもしれません。

参考文献（いきなり）

　このアルゴリズムには、再起呼び出しについての理解が必要です。
　再起呼び出しの説明については、「あゆしゃのC言語プログラミング(Vol.006) 関数」（1999/12/01 発行）をご覧ください。
　再起呼び出しについての説明、およびこのページに書かれている内容の原文がここにあります。

はじめに（基礎）

　あゆしゃが再起呼び出しを勉強したのは、フラクタルグラフィックでした。
　そこで再起呼び出しによって、フラクタルグラフィックがかけるようになりましたし、再起呼び出しとは何者かという事についても知ることができました。

　しかし。
　ほかに使い方ってないのかなぁ？

　という疑問を抱いていたとき、あゆしゃはファイアーエンブレム聖戦の系譜にはまっていました。

　ユニットを選択すると、
　移動可能な範囲が緑で表示されて、
　移動先を選択すると、
　パカランパカラン・・・

　ほう。。。

　でも、移動可能な範囲って、どうやって計算するのだろう？

　っていうか、移動って何だろう？

　移動とは、上か下か右か左に１歩動く動作の繰り返し。

　じゃあ、

　上下左右に移動できるかどうかの判定をおこない、
　移動できるのであれば再起呼び出しを行い、
　移動できなければ移動元へ戻る

　ということを再起で繰り返していれば・・・

サンプルプログラム

void calcMove( int x, int y, int m )
{
    if( data[ y ][ x ] >= m ) return;
    data[ y ][ x ] = m;
    if( y > Y_MIN ) calcMove( x, y - 1, m-wait[y-1][x] );
    if( y < Y_MAX ) calcMove( x, y + 1, m-wait[y+1][x] );
    if( x > X_MIN ) calcMove( x - 1, y, m-wait[y][x-1] );
    if( x < X_MAX ) calcMove( x + 1, y, m-wait[y][x+1] );
}

　これで、移動可能範囲が計算できます。

void calcMove( int x, int y, int m )

　引数の x と y は、キャラクターのマップ上の座標を、m はその移動力を示しています。

　data配列は、処理の前に 0 で埋めておきます。

    if( data[ y ][ x ] >= m ) return;

　data配列にすでに現在よりも大きな移動力がセットされている場合、もうすでに最良の移動経路を計算済みであるため、なにもせずにリターンします。
　この処理は、再起構造の終了もかねています。１行で２度おいしいです。

    data[ y ][ x ] = m;

　そして、このマップパーツにいるときの残りの移動力はこれだけですよ、ということをdata配列にセットしておきます。

　ZOC（敵ユニットに囲まれたマスを通過することはできない、というルール）を実現したい場合は、あらかじめ敵ユニットに挟まれている領域を判断できるマップを用意し、これがその場所である場合（各ユニットに隣接するマスを＋１させておき、ここのそれが２以上である場合、など）、ここでリータンすればよいでしょう。

    if( y > Y_MIN ) calcMove( x, y - 1, m-wait[y-1][x] );
    if( y < Y_MAX ) calcMove( x, y + 1, m-wait[y+1][x] );
    if( x > X_MIN ) calcMove( x - 1, y, m-wait[y][x-1] );
    if( x < X_MAX ) calcMove( x + 1, y, m-wait[y][x+1] );

　最後に、再起呼び出しを実行します。
　実行するとき、上下左右に移動するように x と y を少し編集し、現在の移動力から移動先のマップパーツの進入ロスを減算します。
　ただし、マップ領域をはみ出さないことを確認し、はみ出すようならば実行しません。
　wait配列は、いわゆる進入ロスで、そのマップパーツに移動するにはどれだけの移動力を消費するかということを定義しておきます。

　このプログラムがすべての処理を終えたとき、data配列には、キャラクターが移動できる範囲に１以上最大移動力以下の値がセットされているはずです。

　この１以上の範囲を、緑で表示すれば、
移動可能範囲の完成です。

　移動先を指定されたら、その移動先のdata配列を調べ、１以上であれば移動できますよ、と判定できます。

最短経路の検索

　また、計算後のdata配列は、図にあるように、キャラクターの現在位置を頂点として、周囲に行くにしたがって値が下がっていくピラミッド型のような構造をしています。

　ですから、指定された移動先からdata配列に格納されている値を大きいほう、大きいほうへとたどっていくと、その軌跡は最短経路の道筋となります。

　もちろん、障害物をよけて移動する最短経路を取得できます。

　これでシミュレーションゲームはばっちりですね。

一つ前に戻る

メインページへ戻る

[PR]何かを探す前に無料占い:当たる！無料占い『ｽﾋﾟﾘﾁｭｱﾙの館』