概要
2Dシューティングゲーム上で敵NPCを動かすための，意思決定アルゴリズムについて考えます．本シリーズでは意思決定アルゴリズムとしてBehavior Treeを採用することとし，全４回に渡って，その実装について考えます．最終的にはProcessingによって，簡単な対戦デモを実装する予定です．
Part1では，Behavior Treeのアルゴリズムの概要を見ていくことにします．
経緯
友人(@Ririn_main)と一緒に，2Dシューティングゲームの開発を進めています．当ブログでは以前，シューティングゲームで用いる弾幕要素について考えました．
見映えがして，かつ，避けにくい弾幕を作ることによって，プレイヤは回避行動に手応えを感じて，ゲームを楽しむことができます．
しかし，プログラムをゲームとして成立させるためにはこれだけでは不十分です．アクションゲームはあくまでも敵キャラクタと戦うものですから，敵キャラクタのふるまいの実装が欠かせません．
ベタ書きで実装を書いていくことも可能ではありますが，ゲームには複数のキャラクタが登場するため，複数キャラ間で共通して使いまわせて，かつ高い柔軟性が達成できる枠組みを準備するべきです．
そこで，一般的な商業ゲームで用いられている，キャラクターAIのアルゴリズムについて調べて，取り入れることにしました．
キャラクタAIのアルゴリズムの比較
キャラクタAIについては，以下の資料の「Chapter3：意思決定アルゴリズム」が詳しいです．
三宅陽一郎. "ディジタルゲームにおける人工知能技術の応用の現在 (< 特集> エンターテイメントにおける AI)." 人工知能 30.1 (2015): 45-64.
この特集によると，キャラクタAIを作る代表的な意思決定アルゴリズムとして次のようなものが知られています．
Rule-base
条件と命令をペアにしたルールを登録しておき，これを基に意思決定をする手法です．
State-base
複数の状態を定義しておき，その間を遷移させていくことで行動を変化させていく手法です．
Behavior-base (Behavior Tree)
キャラクタの取るべき振る舞いをツリー構造で持っておく手法です．ゲーム業界やロボット分野で幅広く使われている標準的な手法です．作成するユーティリティが揃っていればプログラマ以外も設計をすることができます．
Goal-base
長期的な目標を見据えたタスク設計をする手法です．ゴールを決めて，そこから逆算していくことで，取るべき行動を決定します．
Utility-base
評価関数を持っておき，その値を最大化するような行動を選択することで，キャラクタの行動を作る手法です．
Task-base
ゴールに対応するタスクを分解して階層化することで，キャラクタの実行すべき仕事を決定する手法です．
Simulation-base
簡易化した世界の中でランダム要素を組み合わせながらシミュレーションして，最良の結果になるものを選択することで，キャラクタの次の行動を決定する手法です．
デバッグの容易性という部分も重要ですが，我々のゲームにおいてはもう1人の開発者（非プログラマ）もキャラクタの行動を作成するため，開発者間で簡単に振る舞いについて情報を共有できることが重要です．こうした背景からBehavior Treeを今回は選択することにします．
Behavior Treeの参考実装
Behavior Treeについては，さまざまな実装例が存在すると思いますが，今回は，以下を参考実装とします．
このサイトでは，Behavior Treeの詳細な説明とともに，C++での実装が紹介されています．
Behavior Treeについて
Behavior Treeは，あるエージェント（ゲームのNPCなど）の行動を，あらかじめ準備しておいたツリーをもとに決定する手法です．エージェントは一定時間ごとにツリーをたどり，次にやるべき行動をトリガーします．ゲームのNPCなどによく使われる手法ですが，ロボティクスなどの文脈でも広く用いられています．
上図に，Behavior Treeの構造を示しました．Behaviro Treeを構成するノードを大まかに分類すると，末端ノード，制御ノード，修飾ノードの３種類があります．
末端ノード
末端ノードはキャラクタの具体的な動作に対応しているノードです．キャラクタの具体的な動作として，「走る」「攻撃する」「回復する」などの行動のほか，「敵が近いかどうかを判定する」「回復をすべきかどうかを判定する」という状況判断があります．
制御ノード
制御ノードは，処理の流れを制御するためのノードです．自身の配下にあるノードを，一定の方法で順番に実行していきます．
制御ノードの種類によって処理方法が異なりますが，代表的なものとしてはSequenceNodeがあり，上図に示しているように配下のノードを左端から順番に全て実行していきます．
修飾ノード
修飾ノードは他のノードの処理を変化させるノードです．配下のノードに対して有効で，処理結果を反転させたり，規定の回数だけ同じ処理を繰り返したりと言ったことができます．
上図では，末端ノードに対して修飾ノードを適用する例を示していますが，制御ノードに対しても適用できます．
各ノードの処理結果について
Behavior Treeが大まかには３種類のノードによって構成させることがわかりました．ここで，もう一つ重要な話題があり，それがノードの処理結果です．
BehaviroTreeでは各ノードは処理結果を自身の上位ノードに通知することになっています．処理結果としては，SUCCESS，FAILURE，RUNNNINGの３種類があります．
SUCCESSは処理が終了し，かつ，結果が成功であったことを示します．
FAILUREは処理が終了したけれども，結果が失敗であったことを示します．
RUNNINGは処理を実行している途中であることを示します．
ゲーム上の処理の具体例として，例えば，目的地への移動タスクを考えます．このタスクにおいての処理結果を上図に示しました．キャラクタが無事に目的地へ到着した時，このタスクは終了となり，かつ結果が成功であるので，SUCCESSが返されます．反対になんらかのエラーによって目的地への移動が困難になった場合もこのタスクは終了しますが，目的は果たせていないので，FAILUREが返されます．タスクを遂行している途中では，この処理に対応するノードはRUNNNINGを返し続けます．
Tick()について
ここまでで，Behavior Treeがおおまかに３種類のノードで構成され，それぞれのノードがSUCCESS, FAILURE, RUNNINGのいずれかの処理結果を返すということがわかりました．最後に，これらを使って，どのようにキャラクタの振る舞いが作られるのかを説明します．
Behavior Treeでは，一定のタイミングごとにTreeを辿ることによって，処理が進んでいきます．Treeを一回辿る処理をTick()と呼んでいて，Tick()では最上位のrootノードから，再帰的にBehavior Treeを辿っていきます．
Tick()の動作を上図に示しました．Treeを辿って行くと最終的には末端ノードに辿り着き，これによって，それに紐づくアクションが実行されます．前述の通り，全てのノードは処理結果を上位ノードに通知しますので，末端ノードの処理結果が上位ノードに順番に伝播されていって，最終的にrootノードの処理結果が定まることになります．
TreeのrootがSUCCESSを返したら，一連の行動が全て終了したということになりますので，また最初からTreeを辿り直して，次の行動を決定します．ゲーム上では，これをひたすらに繰り返していくことになります．
なお，ここで，末端ノードの特にアクションに関連するノードは，ゲーム世界や現実世界の具体的動作に紐づいています．このため，末端ノードは，関連する動作にかかる時間の分だけRUNNINGを返し続けなければなりません．それを実現するためには，末端ノードに待ち時間を値として持たせておき，ツリーでこのノードに辿り着くたびにそれを減じておけば良いでしょう．そして，行動が終わった時，あるいは持ち時間が0になった時にSUCCESSかFAILUREを返すようにします．
Tick()を呼び出すタイミングに関しては，様々な実装があると思います．例えば，毎秒ごとにTick()を呼び出すという実装や，毎フレームごとにTick()を呼び出すという実装が考えられます．ゲームの場合はフレームを基準に時間を考えることが多いので，毎フレームとまではいかなくても，固定のフレームごとにTick()を呼び出すという実装が一般的だろうと考えます．あるいは，ターン制で進むゲームシステムの場合であれば，ターンごとに辿るという実装も考えられます．
まとめ
敵NPCの意思決定アルゴリズムとしてBehavior Treeを採用しました．
Behavior Treeでは主に３種類のノードを組み合わせてツリーを構築し，それを一定時間ごとに辿ることによってキャラクタを動かします．
次回やること
次のパートではPart1で紹介したBehaviorTreeのノードをさらに詳細に説明し，Processingを用いて各ノードを実装していく予定です．
他パートへのリンク
Part 1 : 現在地点．この記事です．
Part 2:
Part 3: 工事中
Part 4: 工事中
