記事の目的と前提（流し読みでOK）
今回の記事では、条件分岐を排除したAIコードを作ることが可能なのか。
もしそれが実現するとして、有用性があるのかを考察したいと考えています。
また、この記事で言うゲームAIや条件分岐に関する前提は以下の通りです。
ゲームAI
今回の記事のゲームAIは、正確にはゲームAIのベースコードをイメージしています。
つまり敵一体、キャラ一体、に合わせてゲームAIを一つずつ作るような環境は想定していません。
ベースコードとは文字通りAIのベースです。
大きなAIクラスを用意し、クラスが持つ設定を変えることで挙動が違うAIを量産できるようなコードです。
上手く想像ができないと言う場合は、次の前提の説明で例を用意したのでそちらを見てください。
私が考えるこの設計のメリットは以下の通りです。
- コードの管理がしやすい
- 新しいAIを作る際のコストが減る（異なる設定を作るだけ）
- 共通化できる
- AI間での連携や情報のやり取りがやりやすい
ですが問題もあります。
それは以下の通りです。
- コードが長くなりがち
- 条件分岐が増える
- 個々のキャラの挙動の拡張性が損なわれる（上手く作れないと、このゲームのキャラは似たような動きばかりするな……って感想に）
今回はこの問題点の内、コードが長くなりがちと、条件分岐が増えるについて考えていきます。
ちなみになぜ条件分岐が増えるのかは次の項目で説明します。
条件分岐
今回の記事における条件分岐とは、一言で言うとAIのコードのぜい肉です。
つまり判断→行動というAIの基本的な動作には関係がない、先述のベースコードが大きすぎるせいで生まれてしまう条件分岐です。
その例として以下のコードを作成しました。（フレームワークはUnity、言語はC#です）
using UnityEngine;
public class BigAISamp : MonoBehaviour
{
#region 定義
/// <summary>
/// 攻撃する際の条件判断の基準となる設定の列挙型。
/// </summary>
enum JudgeConditions
{
一定距離内にいるかで判定 = 0,// 一定以内の距離にいる敵を攻撃
HP量で判定 = 1,// HPが一定以上か
MP量で判定 = 2,// MPが一定以上か
攻撃力で判定 = 3 // 攻撃力が一定以上か
}
/// <summary>
/// 位置やHPなど、敵のデータを格納するクラス。<br></br>
/// 今回は中身がないダミー。
/// </summary>
public class TargetData
{
}
#endregion 定義
#region インスタンス変数
/// <summary>
/// このAIがどんな条件で攻撃を行うか、という設定。<br></br>
/// インスペクタから入れる想定。<br></br>
/// たとえばこの変数の値が 一定距離内にいるかで判定 であれば距離が一定以内のものを攻撃する。
/// </summary>
[SerializeField]
JudgeConditions useCondition;
#endregion インスタンス変数
#region 処理
/// <summary>
/// メインループ
/// </summary>
void Update()
{
// 敵の中からターゲットを決定。
// 引数となる敵の候補配列はシングルトンから持ってくる想定。(自分はそうしている）
TargetData target = Judge(GManager.instance.EnemyArray);
// 判断後に攻撃対象がいれば攻撃する。
if ( target != null )
{
Attack();
}
}
/// <summary>
/// 攻撃条件に当てはまったターゲットのデータを返す処理。
/// </summary>
/// <param name="tData">ターゲット候補のリスト</param>
/// <returns>今回の判断の結果、攻撃対象になったターゲット。対象がいなければ null</returns>
TargetData Judge(TargetData[] tData)
{
for ( int i = 0; i < tData.Length; i++ )
{
if ( useCondition == JudgeConditions.一定距離内にいるかで判定 )
{
// 距離の判定を書いて、もし一定内の距離ならそいつをターゲットに。
return tData[i];
}
else if ( useCondition == JudgeConditions.HP量で判定 )
{
// HPの判定を書いて、もし一定以上ならそいつをターゲットに。
return tData[i];
}
else if ( useCondition == JudgeConditions.MP量で判定 )
{
// MPの判定を書いて、もし一定以上ならそいつをターゲットに。
return tData[i];
}
else
{
// 攻撃力の判定を書いて、もし一定以上ならそいつをターゲットに。
return tData[i];
}
}
// いなければ null。
return null;
}
/// <summary>
/// 攻撃する処理。
/// </summary>
/// <param name="target">攻撃ターゲット</param>
void Attack(TargetData target)
{
// 殴れ！
}
#endregion 処理
}
このコードはAIのベースコードのサンプルとして作成しました。
useCondition変数の中身を変えることで、敵との距離に応じて攻撃するAI、敵の現在のHPに応じて攻撃するAIなどが作れるはずです。
これが設定で振る舞いが変わるAI、という言葉の真意です。
そしてこのコードの問題、ぜい肉はJudge()メソッドの以下の部分です。
if ( useCondition == JudgeConditions.一定距離内にいるかで判定 )
{
// 距離の判定を書いて、もし一定内の距離ならそいつをターゲットに。
return tData[i];
}
else if ( useCondition == JudgeConditions.HP量で判定 )
{
// HPの判定を書いて、もし一定以上ならそいつをターゲットに。
return tData[i];
}
else if ( useCondition == JudgeConditions.MP量で判定 )
{
// MPの判定を書いて、もし一定以上ならそいつをターゲットに。
return tData[i];
}
else
{
// 攻撃力の判定を書いて、もし一定以上ならそいつをターゲットに。
return tData[i];
}
おわかりでしょう。
AIの判断とは関係がない、設定を判別するための条件分岐があります。
つまりある設定のAIで特定の判断をする、という挙動を実装するために、自分の設定をAIが解釈しなければならなくなっているということです。
そしてAIを作りこむほど、こうした分岐は無尽蔵に増えていきます。
- 状態（おこってるなど）に応じた分岐処理
- キャラの特性（空を飛ぶキャラの場合など）に応じた分岐処理
- 今いるマップの設定に応じた分岐処理
- 装備している武器に応じた分岐処理
本当に無限です。
心底無限です。
自分の設計が悪いだけかもしれませんが……。
でもとにかく、判断のたびに馬鹿みたいに無駄な条件分岐をしているのは許せない。
ループの外に条件判断を追い出す、などの改善は可能でしょうがそれは根本的な解決ではありません。
今回の目的はこういったコードを懲らしめてやることです！
泣いても許さん！！
長くなりましたが前提と目的は以上です。
また、#1 がタイトルについているのは可能ならゆるく連載として続けたいと考えているためです。
次回のテーマと検証内容は決まっているためとりあえず第二回は作れそうです。
そして連載としての目的は汎用性とパフォーマンスを両立したAIのベースコード（ある程度）を考察すること。
同じことを考えている人たちからアイデアをもらうこと。
以上の二つになる予定です。
次回については記事の最後に触れるので、もし気になったら見てください。
また、連載の検証などは基本的にUnity、あるいはC#に主眼を置いて行う予定です。
よろしくお願いいたします。
ぜい肉たる分岐の消滅方針
パッと考えついたのは継承による多態性の利用でした。
これはベースコードを継承したコードを作り、距離で判断するキャラクターであればオーバーライドしたJudge()メソッド内に距離の判定処理を書く、というようなものです。
しかしこれは却下です。
結局継承先でコードを書かなくてはいけないため、コードに設定を注入して振る舞いを変える、という目標に反します。
ですから考え直した結果、自分は次の方法にたどり着きました。
判定メソッドでデリゲートの配列を作り、設定の列挙子をint変換して判断処理を呼び出せるようにする。
この場合、コードは次のような感じになります。
using System;
using UnityEngine;
public class DelegateAISamp : MonoBehaviour
{
#region 定義
/// <summary>
/// 攻撃する際の条件判断の基準となる設定の列挙型。
/// </summary>
enum JudgeConditions
{
一定距離内にいるかで判定 = 0,// 一定以内の距離にいる敵を攻撃
HP量で判定 = 1,// HPが一定以上か
MP量で判定 = 2,// MPが一定以上か
攻撃力で判定 = 3 // 攻撃力が一定以上か
}
/// <summary>
/// 位置やHPなど、敵のデータを格納するクラス。<br></br>
/// 今回は中身がないダミー。
/// </summary>
public class TargetData
{
}
#endregion 定義
#region インスタンス変数
/// <summary>
/// このAIがどんな条件で攻撃を行うか、という設定。<br></br>
/// インスペクタから入れる想定。<br></br>
/// たとえばこの変数の値が 一定距離内にいるかで判定 であれば距離が一定以内のものを攻撃する。
/// </summary>
[SerializeField]
JudgeConditions useCondition;
/// <summary>
/// デリゲートの配列。<br></br>
/// ここに判断処理を格納し、JudgeConditions列挙子の値でアクセスできるようにする。
/// </summary>
Func<TargetData[], TargetData>[] judgeArray = new Func<TargetData[], TargetData>[4];
#endregion インスタンス変数
#region 処理
/// <summary>
/// 初期化処理<br></br>
/// デリゲート配列を作成。
/// </summary>
private void Start()
{
// 各条件に対応するローカルメソッドを作成し、デリゲート配列に格納する。
// 距離判定用のローカルメソッド。
// JudgeConditions.一定距離内にいるかで判定 に対応（処理内容はダミー）
TargetData distanceJudge(TargetData[] tData)
{ return tData[0]; }
// HP判定用のローカルメソッド。
// JudgeConditions.HP量で判定 に対応（処理内容はダミー）
TargetData hpJudge(TargetData[] tData)
{ return tData[0]; }
// MP判定用のローカルメソッド。
// JudgeConditions.MP量で判定 に対応（処理内容はダミー）
TargetData mpJudge(TargetData[] tData)
{ return tData[0]; }
// 攻撃力判定用のローカルメソッド。
// JudgeConditions.攻撃力で判定 に対応（処理内容はダミー）
TargetData atkJudge(TargetData[] tData)
{ return tData[0]; }
// 各判断処理を対応する配列要素に格納。
judgeArray[(int)JudgeConditions.一定距離内にいるかで判定] = distanceJudge;
judgeArray[(int)JudgeConditions.HP量で判定] = hpJudge;
judgeArray[(int)JudgeConditions.MP量で判定] = mpJudge;
judgeArray[(int)JudgeConditions.攻撃力で判定] = atkJudge;
}
/// <summary>
/// メインループ
/// </summary>
void Update()
{
// 使用する設定（useCondition）で配列のどの判断処理にアクセスするか、が決定される。
TargetData target = judgeArray[(int)useCondition](GManager.instance.EnemyArray);
// 判断後に攻撃対象がいれば攻撃する。
if ( target != null )
{
Attack();
}
}
/// <summary>
/// 攻撃する処理。
/// </summary>
/// <param name="target">攻撃ターゲット</param>
void Attack(TargetData target)
{
// 殴れ！！！
}
#endregion 処理
}
おわかりでしょうか。
Judge()メソッドのうっとうしい条件分岐が消え、デリゲート配列にアクセスするだけで設定の解釈が完了します。
必要なのはjudgeArray[(int)useCondition](GManager.instance.EnemyArray)というスリムな一文だけです。
この仕組みであれば、たとえ判断条件が千種類あったとしても一定の計算量、つまり配列アクセスの計算量O(1)で設定を解釈できることになります。
ベースコードという仕様上、デリゲート配列をシングルトンに一つだけ作って共有する、というような運用であればさらに無駄なく使用できるはずです。
なにより簡潔なコードはかっこいい（気がしますね）。
もちろんもっといい方法があるのかもしれませんが、今の私が考えつく最善はこれでした。
しかしデリゲートには呼び出しのオーバーヘッドがあるといいます。
今の私が思う最善ではありますが、そもそも本当にこの方法で上手いこと高速化できるのか、ということは検証しなければなりません。
ということで実際に比較と検証を行ってみようと思います。
検証の前説明
検証にあたって、ちょうどいい題材がありましたので利用しましょう。
以下は2025-01-18(土) 21:00 のAtCorderのコンテスト（トヨタ自動車プログラミングコンテスト2025）のC問題のリンクです。
私はクソザコなのでACできませんでした。
解答見てようやく区間和の問題だったのだと気づけました。
そしてこの問題を検証に利用します。
競技プログラミングをやらない人向けに簡単に説明すると、こちらはConsole.ReadLine()などで読み取った情報に従い処理を分岐させる必要がある問題です。
読み取った入力が1ならAの操作、2ならBの操作、といった感じです。
コードの例を出すと、一般には以下のような分岐をします。
// 与えられるクエリの個数。
// 簡単に言うと処理をループで繰り返す回数。
int qCount = int.Parse(Console.ReadLine());
for ( int i = 0; i < qCount; i++ )
{
// n回目のクエリの種別。
// ほんとはこんな風には読み取らないですが簡略化します。
int qType = int.Parse(Console.ReadLine());
// タイプ1のクエリの処理。
if ( qType == 1 )
{
}
// タイプ2のクエリの処理。
else if ( qType ==2 )
{
}
}
つまり、この入力が1の場合の操作、入力が2の場合の操作、といった分岐をそのまま配列のデリゲートに置き換えることができるんですね。
そして今回の検証の前提を以下に記します。
- クエリの個数、つまり処理の繰り返し回数は1000000回（問題の入力例3を繰り返すだけ）
- 各検証コードを四回実行し処理時間の平均を見る
ではさっそく検証に使うコードを紹介……したいのですが、その前にコードで使用しているライブラリについて触れておきます。
kzrnm様が作成したCompetitive.IOという入出力用ライブラリです。
https://github.com/kzrnm/Competitive.IO
あわせて提出コードには同氏のSorceExpanderも利用しています。
https://github.com/kzrnm/SourceExpander
そして今回の例では使用していませんが、これまた同氏のac-library-csharpというライブラリにもお世話になっております。
https://github.com/kzrnm/ac-library-csharp
この記事の検証コードはコンテストで提出したコードの流用です。
そして当たり前のように上記のライブラリをコンテストで利用しているため、検証が終わるまでコードに他人様のライブラリが紛れ込んでいることに気が付きませんでした。
本来ならコードを修正して検証しなおすべきなのでしょうが、ここは紹介させていただいて、著作権表示をすることでお許しいただければと思います。
申し訳ありません。（次回からは気を付けます）
以下は本日使用する検証コードの すべて に含まれている、Competitive.Libraryのライセンス表示です。
Competitive.Library
MIT License
Copyright (c) 2020 naminodarie
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
検証してみた
最初の検証コードは以下の二つです。
1.普通にif文で分岐したコード
2.デリゲート配列を利用してクエリの種類を解釈したコード
ゲームAIとは正直色々前提が違うのですが、まずはこのままやってみましょう。
1.普通にif文で分岐したコードの結果
for ( int i = 0; i < q; i++ )
{
int query = reader;
if ( query == 1 )
{
h.Add(lastScale);
lastScale += reader;
}
else if ( query == 2 )
{
h.RemoveAt(1);
h[0] += h[1] - h[0];
}
else
{
int num = reader;
writer.WriteLine(h[num] - h[0]);
}
}
こちらを四回実行した結果が以下です。
| 回 数 | 処理時間 |
|---|---|
| 一回目 | 63803ms |
| 二回目 | 62652ms |
| 三回目 | 66440ms |
| 四回目 | 68309ms |
| 平均 | 65301ms |
2.デリゲート配列を利用してクエリの種類を解釈したコードの結果
// 配列に格納するローカルメソッド。
// 1番目の検証コードのif 分岐の中身そのまま。
void Query1()
{
h.Add(lastScale);
lastScale += reader;
}
void Query2()
{
h.RemoveAt(1);
h[0] += h[1] - h[0];
}
void Query3()
{
int num = reader;
writer.WriteLine(h[num] - h[0]);
}
// デリゲート配列の作成。
Action[] que = new Action[3];
que[0] = Query1;
que[1] = Query2;
que[2] = Query3;
for ( int i = 0; i < q; i++ )
{
// 読んだクエリのタイプから1引いてそのままインデックスとして使えるように。
int query = reader - 1;
que[query]();
}
こちらを四回実行した結果が以下です。
| 回 数 | 処理時間 |
|---|---|
| 一回目 | 65545ms |
| 二回目 | 61870ms |
| 三回目 | 66602ms |
| 四回目 | 67687ms |
| 平均 | 65426ms |
A.結論？
- 1.普通にif文で分岐したコードの結果平均
- 65301ms
- 2.デリゲート配列を利用してクエリの種類を解釈したコードの結果平均
- 65426ms
デリゲート配列でちょっと遅くなってますね。
じゃあ終わります……とはなりません。
以下をご覧ください。
これは使用している入力情報です。（正確にはこれを100000回繰り返している）
10
1 15
1 10
1 5
2
1 5
1 10
1 15
2
3 4
3 2
この入力情報では、二行目以降がループ一回ごとで使うデータです。
そしてその最初の文字は使用する処理のタイプを示しています。
つまり二行目の
1 15
の場合、ループで使うクエリのタイプは1になります。
するとすぐに気づきますが、全体的にタイプ1のクエリが多いです。
10個の内の6個がタイプ1です。
これは今回の検証の1000000回の繰り返しの内、600000回はタイプ1のクエリになるということです。
そうなるとif分岐にあまりに有利です。
何故なら分岐の最初がif ( query == 1 )になっているので、一回目の分岐でヒットしまくります！！
if ( query == 1 )
{
h.Add(lastScale);
lastScale += reader;
}
else if ( query == 2 )
{
h.RemoveAt(1);
h[0] += h[1] - h[0];
}
else
{
int num = reader;
writer.WriteLine(h[num] - h[0]);
}
ゲームAIの設定解釈だとこうはいかないでしょう。
ですからもう少し条件分岐に不利な設定で再試行します。
3.分岐を逆にしたコードの結果
for ( int i = 0; i < q; i++ )
{
int query = reader;
if ( query == 3 )
{
int num = reader;
writer.WriteLine(h[num] - h[0]);
}
else if ( query == 2 )
{
h.RemoveAt(1);
h[0] += h[1] - h[0];
}
else if ( query == 1 )
{
h.Add(lastScale);
lastScale += reader;
}
}
はい、分岐を見ての通り逆からにしました。
3のクエリから1のクエリに分岐が流れます。
これで最初の条件判断をほぼtrue判定できなくなりました。
結果は以下です。
| 回 数 | 処理時間 |
|---|---|
| 一回目 | 63636ms |
| 二回目 | 69144ms |
| 三回目 | 68653ms |
| 四回目 | 69385ms |
| 平均 | 67704.5ms |
どうです、劇的に遅くなりました。
たった三つの条件分岐でもこれです。
これが現実でしょう！（都合のいい結果に狂喜する図）
それではもっと 不利な条件を追求 実際の環境に近いシビアさを徹底しましょう！
4.分岐を増加し、検査順をめちゃくちゃにしたコードの結果
for ( int i = 0; i < q; i++ )
{
int query = reader;
if ( query == 4 )
{
continue;
}
else if ( query == 3 )
{
int num = reader;
writer.WriteLine(h[num] - h[0]);
}
else if ( query == 1 )
{
h.Add(lastScale);
lastScale += reader;
}
else if ( query == 5 )
{
continue;
}
else if ( query == 2 )
{
h.RemoveAt(1);
h[0] += h[1] - h[0];
}
}
以上のようにダミーの分岐を加えてみました。
これで条件分岐は五つ、検査順もめちゃくちゃです。
結果は以下。
| 回 数 | 処理時間 |
|---|---|
| 一回目 | 69757ms |
| 二回目 | 69204ms |
| 三回目 | 69567ms |
| 四回目 | 69106ms |
| 平均 | 69408.5ms |
遅すぎますね。
遅すぎる。
あまりにも。
私のゲームのAIの設定なんてモノによっては十五種類くらいあったりするので、それを一個一個解釈してたとしたら恐ろしいくらい遅いはず。
でもちょっとデリゲート配列ばかりひいきしすぎなので、今度はそっちも不利にしてみましょう。
5.配列要素を千個にしたデリゲート配列コードの結果
// デリゲート配列の作成。
// 千個の内三つだけ要素を入れる。
Action[] que = new Action[1000];
que[0] = Query1;
que[1] = Query2;
que[2] = Query3;
for ( int i = 0; i < q; i++ )
{
// 読んだクエリのタイプから1引いてそのままインデックスとして使えるように。
int query = reader - 1;
que[query]();
}
以上の通り、空の要素を増やして配列長を千にしました。
いや、結局配列のアクセスのオーダーはO(1)なのでなにも不利になってないよねと思った方は流石でございます。
そうです、いくら要素を増やしてもデリゲート配列で設定を解釈した場合、結果はほぼ変わらないのです。
不利にするならせめて配列へのアクセス位置をランダムにする工夫を入れるべきだと思うかもしれません。
しかし、そもそもよくアクセスするデリゲートはメモリにキャッシュされるはずです。
であればアクセス頻度に応じた最適化が行われるのは当然、というかそれもこの実装の特徴だと考えます。
もしそうならわざとアクセスにばらつきを作る意味は薄いかなと私は考えました。（素人考えですので、もし何か違う意見があれば教えていただけると助かります）
結果は以下の通りです。
| 回 数 | 処理時間 |
|---|---|
| 一回目 | 67291ms |
| 二回目 | 67371ms |
| 三回目 | 66831ms |
| 四回目 | 66367ms |
| 平均 | 66965ms |
若干遅くなっていますが、それでも逆条件分岐（2番目のコード)の結果、平均67704.5msよりも速いですね。
千個のデリゲートがあったとしてもこれなら十分です。
終わりに
以上で検証を終わります。
デリゲート配列を利用することで、ゲームAIが設定の解釈に要するオーバーヘッドを大幅に削減できることが分かりました。
これで速くて短い、かっこいいコードが書けますね。
とはいえ、やはり最速を追い求めるなら、AIをキャラクターごとに作り、しっかりと最適化してやるのが一番だと思います。
共通の抽象クラスなりインターフェイスなりを実装してやればオブジェクト指向っぽい運用は十分にできるはずです。
しかし私はあくまでもベースコードを作り、設定を流し込むタイプのAIに惹かれてしまいます。
その実装の利点は最初に語った通りですが、単純にそういうスーパーAIを作るのが楽しくて仕方がないんですね。
また、こういうスーパーAIを応用したゲーム性というか……簡単に言うと味方NPCのAIのロジックをプレイヤーがいじれるようなゲームをずっと作っていますので。
AIの設定を解釈する、という部分と向き合うのはもう必須なんですね。
だから今後も汎用ゲームAIの可能性を突き詰めていけたらなと思います。
あとは、いつか自分で作ってるゲームの内容にも触れてみたいですね。
次回予告
そして次回の内容についてお話します。
次回のテーマは非同期処理です。
n秒に一回判断するAIがあるとして、メインループに時間待ち処理を乗せる実装と、非同期で時間を待つ実装ではどちらが速いのかを試してやろうと思います。
今回はUnityを動かしませんでしたが、次回はUnityで検証するつもりです。
あと非同期処理はUnitaskのDelayを使う予定ですが、もっといい方法があったら教えてください。
もちろん今回の検証に関する意見や、デリゲート配列以外にいい実装があるとか、そういうコメントも大歓迎です。
自分は独学でやっているので、きちんとした技術がある人のお話を聞ける機会が喉から手が出るほど欲しいです。
それではまた、次回の記事でお会いしましょう。