シミュレーションゲームにおける移動範囲を求めるアルゴリズム

「グレンジ Advent Calendar 2017」19日目を担当するy244です。
株式会社グレンジにてクライアントエンジニアをしております。

#概要
今回の記事の内容はシミュレーションゲームにおけるユニットの移動範囲を求めるアルゴリズムを書いてみたという内容になります。
ソースコードはページ下部にあります。

#要件定義
(10x10)マスのフィールドを用意
ユニットの初期位置は(x:6, y:6)の位置
ユニットの移動力は「3」の移動可能範囲を出す。

#実装の内容
■マップデータを作成
10×10の配列を作成、初期値として「-1」を設定する

■ユニットに初期位置と移動データを持たせる
ユニットの初期位置と移動力を設定
初期位置(x:6, y:6) 移動力「3」

##移動範囲を求める
初期処理で初期位置（移動開始位置）に移動力を代入します。

■2つの関数を用意する
・現時点の位置から４方向を（上, 下, 左, 右）を探索する関数 「Search4」
・移動先が移動可能な場所か判定する関数「Search」

「Search4」は各方向毎に探索する地点のさ座標と移動力を「Search」に渡す
「Search」は現在の移動力から移動先の値分引きます、移動力が残っていれば「Search4」を再帰呼び出しを行う。

上に向かって探索を始めます。一つ上に上がって移動力が減りましたが、まだ移動力が残っているので（移動力：2）あるので上に上がります。それを続けていくとやがて移動力が0になります。

　→　　→　

移動力が0になったので下側に一つ戻り(6, 4)の位置へ戻る。そして探索方向を左に変え探索、また移動力が0になったので「0」を設定し右に一つ戻る(6, 4)の位置へ戻る。そして探索方向を右に変え探索、移動力が0になったので「0」を設定。

　→　

今までのようなことを繰り返すと下記のような結果となり移動範囲を求めることができます。

# 探索のポイント
・まず探索の進み方にルールがあり、上／下／左／右の順で探索するようなっています。
・進むたびに移動力が減っていき移動力がある内は同じ方向にに移動と探索を続けます。
・移動力がなくなった際に進んでいた方向から一つ戻り次の移動方向に向きを変え探索をする。
・すでに探索した場所なのかは判定、(現在の移動力 -1) と 「進もうとしているマップの値」 を比較して判断している

すでに探索した場所かの判定

// 進もうとしているマップの値が大きいもしくは等しければ すでに探索済み
if((現在の移動力-1) <= 進もうとしているマップの値 return;

その繰り返しでマスを埋めていっている形です。まず行けるとこまで行きそこから徐々に周りを埋めながら戻ってくるようなコースで探索しています。
そこらへんのイメージを持ちつつ、下記のコードを見てもらえれば理解しやすいかと思います。コード量もさほどないので。

# コード

移動範囲を演算

public class CalcMoveRange : MonoBehaviour {
    // オリジナルマップデータ
    List<List<int>> _originalMapList;
    // 移動計算結果のデータ格納用
    List<List<int>> _resultMoveRangeList;
    
    // マップ上のx,z位置
    int _x;
    int _z;
    // 移動力
    int _m;

    // マップの大きさ
    int _xLength = 10;
    int _zLength = 10;

    void Awake()
    {
        // マップデータを作成 (本来はここでは作成せず外部から渡す)
        for(int i=0; i<_zLength; i++) 
        {
            List<int> moveXList = new List<int> ();

            for(int k=0; k<_xLength; k++)
            {
                moveXList[k] = -1;
            }
            _originalMapList.Add(moveXList);
        }
    }

    /// <summary>
    /// 探索開始
    /// 計算結果のマップデータを返す
    /// </summary>
    public List<List<int>> StartSearch( int currentX,  int currentZ, int movePower)
    {
        // _originalMapListのコピー作成
        _resultMoveRangeList = new List<List<int>>(_originalMapList);

       _xLength = _resultMoveRangeList[0].Count;
       _zLength = _resultMoveRangeList.Count;

        _x = currentX;
        _z = currentZ;
        _m = movePower;
        
        // 現在位置に現在の移動力を代入
        _resultMoveRangeList[_z][_x] = _m;
        Search4(_x, _z, _m);

        return _resultMoveRangeList;
   }

    /// <summary>
    /// 移動可能な範囲の4方向を調べる
    /// </summary>
    void Search4(int x, int z, int m) 
    {

        if(0<x && x<_xLength && 0<z && z<_zLength)
        {
            // 上方向
            Search(x, z-1, m);
            // 下方向
            Search(x, z+1, m);
            // 左方向
            Search(x-1, z, m);
            // 右方向
            Search(x+1, z, m);
        }
    }

    /// <summary>
    /// 移動先のセルの調査
    /// </summary>
    void Search(int x, int z, int m) 
    {
        // 探索方向のCellがマップエリア領域内かチェック
        if(x<0 || _xLength <= x) return;
        if(z<0 || _zLength <= z) return;

        // すでに計算済みのCellかチェック
        if((m-1) <= _resultMoveRangeList[z][x]) return;

        m = m + _originalMapList[z][x];

        if(m>0)
        {
            // 進んだ位置に現在の移動力を代入
            _resultMoveRangeList[z][x] = m;
            // 移動量があるのでSearch4を再帰呼びだし
            Search4(x,z,m);
        } 
        else
        {
            m = 0;
        }
    }

}

Usage

CalcMoveRange calcMoveRange = new CalcMoveRange();

// 引数にX座標とZ座標と行動力を渡す
// 行動範囲のマップデータが戻り値として返ってくる
List<List<int>> moveRangeList = calcMoveRange.StartSearch(6, 6, 3);

#まとめ
かなり少ないコード量で済んだかと思います。
ただ今回は基本的な機能を作成したのみなので色々な要件には対応できていません。
・マップの形状が多角形になった場合のマップ領域外の判定ができない
これをベースにもう少し汎用で的に拡張できればと思います。

#その他
「グレンジ Advent Calendar 2017」 12日目のMiyaAtsuの「タイルマップ使ってみた」の記事を読んで組み合わせればシミュレーションゲームのマップは作れるかと思います。