【Unity】再帰的呼び出し

再帰的呼び出しとは？

再帰的呼び出しとは、ある関数が自分自身を呼び出すことを指します。適切に使用することで、複雑な問題を簡潔に解決できる場合があります。

この概念はUnityやC#に限定されず、プログラミング全般において重要な手法の一つです。

再帰的呼び出しの構造

再帰的に呼べるメソッドを作成する場合、メソッド内に二つの要素が必要です。

終了条件
- 終了条件がないと無限にメソッドが呼ばれ続けることになります
- 必ず終了する条件を設定します
再帰的呼び出し
- 自分自身を再帰的に呼び出す部分です
- そのまま呼び出すと終了条件にも引っかからず無限に呼ばれるため渡す引数を変化させます

簡単な例

以下の例では、1〜引数nまでの値の和を返します。

public int Sum(int n)
{
    if (n == 1)
    {
        // 終了条件
        return 1;
    }

    // 再帰呼び出し
    return n + Sum(n - 1);
}

Sum(4) として呼び出すと、Sum(4),Sum(3),Sum(2),Sum(1)と再帰的に呼ばれて、終了条件をとして1を返します。

その後、1+2+3+4として合計値を返すことになります。

以下は階乗(n!)を求める例です。

public int Factorial(int n)
{
    if (n <= 1)
    {
        // 終了条件
        return 1;
    }
    
    // 再帰呼び出し
    return n * Factorial(n - 1);
}

こちらも引数nを1ずつ減らしながら再帰的に呼び出し、全てを掛け合わせた値を返します。

Unityで使えそうな例

Unityで使えそうな例として、指定したTransformを起点に、

その子階層を再帰的に辿りながら、すべてのオブジェクトのlayerを変更する処理を紹介します。

再帰処理では、子オブジェクトがいない場合にループが呼ばれないため、それが事実上の終了条件となります。

Unityで使えそうな例を挙げてみます。

以下は指定したTransformから下の階層を辿っていき、全てのlayerを変更する例です。

子がいない場合はforeachが呼ばれないのでそれが終了条件となります。

public void SetLayer(Transform transform, int layer)
{
    transform.gameObject.layer = layer;
    foreach (Transform child in transform)
    {
        SetLayer(child, layer);
    }
}

エディタ拡張を書く際に、指定したフォルダ以下のファイル一覧を調べたい場合があるかもしれません。

以下の例では、フォルダ内のファイルをコンソールに出力し、フォルダが存在する場合はそのパスを用いて再帰的に呼び出すことで、

下層フォルダ内のファイルまで調べることができます。

public void GetFiles(string path)
{
    // ファイル一覧を取得
    var files = System.IO.Directory.GetFiles(path);
    foreach (var file in files)
    {
        Debug.Log(file);
    }

    // ディレクトリ一覧を取得
    var dirs = System.IO.Directory.GetDirectories(path);
    foreach (var dir in dirs)
    {
        GetFiles(dir);
    }
}

これらの例のように階層構造になっている場合、forなどでループさせるのは面倒ですが、

再帰的呼び出しを活用すると簡潔に記述できます。

ゲーム開発に活かすには？

再帰的呼び出しはゲームにも使われています。

シミュレーションゲームで移動可能な範囲を調べる

マス目状の平面マップ上で、ユニットを移動させて隣接するユニットと戦わせるようなシミュレーションゲームを考えてみます。

このゲームでは以下の要素があるとします：

マス目を表す2次元の配列
各マス目の地形情報に応じた移動コスト
ユニットの移動力
ユニットの現在位置を表すXY座標

これらの情報をもとに、ユニットが移動できる範囲を求めるアルゴリズムを考えます。

具体的には、最初の移動力を基準として、各マスの地形コストを差し引きながら、隣接するマスに再帰的に移動を試みます。

再帰処理では、XY座標を±1ずつ変化させ、移動力が残っている限り次のマスを探索します。

以下は、移動コストがすべて1の場合の例です。

public void FindMovableRange(int[,] grid, int x, int y, int remainingMove, bool[,] visited)
{
    // 配列の範囲外、移動力が0未満、またはすでに訪問済みの場合は終了
    if (x < 0 || y < 0 || x >= grid.GetLength(0) || y >= grid.GetLength(1) || remainingMove < 0 || visited[x, y])
    {
        return;
    }

    // 現在のセルを訪問済みに設定
    visited[x, y] = true;

    // 上下左右に移動（再帰呼び出し）
    FindMovableRange(grid, x + 1, y, remainingMove - 1, visited); // 右
    FindMovableRange(grid, x - 1, y, remainingMove - 1, visited); // 左
    FindMovableRange(grid, x, y + 1, remainingMove - 1, visited); // 下
    FindMovableRange(grid, x, y - 1, remainingMove - 1, visited); // 上
}

このように再帰を用いることで、マップ上の移動可能な範囲を効率的に計算することができます。

地形コストが異なる場合でも、このアルゴリズムを拡張して適用可能です。

ゲーム開発の場面では、この仕組みを活用して戦略性を持たせることができます。

ぷよぷよのようなゲームで隣接している色を調べる

「ぷよぷよ」というゲームがありますが、そのルールでは、同じ色のぷよが4つ以上並ぶと消える仕組みになっています。さらに、見た目の仕様として、同じ色のぷよが隣り合っている場合、それらはくっついて見えるようになります。

この処理では、指定した座標を起点に、その位置のぷよの色と同じ色がどこまで連なっているかを再帰的に調べます。その結果をもとに、見た目を変化させたり、消える条件を満たしているかどうかを判定しています。

再帰を用いることで、隣接するぷよを効率的に探索でき、ゲームのルールに基づいた処理を実現しています。

塗りつぶしの処理

ゲームではありませんが、昔ながらのペイントツールでも、再帰的呼び出しが使われる例があります。例えば、同じ色の範囲を新しい色で塗りつぶす処理です。

この処理では、指定した座標を起点に、隣接する座標へ移動しながら再帰的に呼び出しを行います。もし隣接するピクセルの色が異なれば、そこで処理を終了します。このような仕組みにより、連続した同じ色の範囲を効率的に塗りつぶすことが可能になります。

シミュレーションゲームの例と同様に、再帰を活用して座標を変えながら探索を進めるアルゴリズムが重要な役割を果たしています。

注意する点

スタックオーバーフロー

終了条件を適切設定せずに再帰的呼び出しを行うと、スタックオーバーフローが発生する可能性があります。

適切に終了条件を設定し、無限に再帰的呼び出しされないように注意が必要です。

パフォーマンス

再帰的に呼び出すメソッドの中で複雑な処理を行うと、処理落ちなどの負荷に繋がる可能性があります。

同じ計算を何度も行わないような工夫が必要です。

まとめ

今回は、再帰的呼び出しについて解説しました。「自分自身を呼び出すメソッド」という概念は、一見すると少しイメージしづらいかもしれませんが、うまく活用することで、ゲームやアプリ開発において非常に役立つ手法です。

再帰を使えば、コードを簡潔に記述できるというメリットがあります。ただし、その一方で、スタックオーバーフローなどの問題が発生する可能性があるため、適切な終了条件を設けるなどの注意が必要です。

ぜひ、ご自身のプロジェクトでも再帰的呼び出しを活用してみてください！