概要
本シリーズでは，2Dシューティングの敵NPCを動かすための意思決定アルゴリズムについて考えています．
Part 2においては，Part 1で紹介したBehavior Treeというアルゴリズムの実装を進めていきます．Behavior Treeには制御ノード，末端ノード，修飾ノードがありますが，このプロジェクトでは，制御ノードとして，SequnceNodeとSelectorNode，末端ノードとしてActionNodeとConditionNode，修飾ノードとして，InverterNode，RepeaterNode，RetryUntilSuccessfulNode，KeepRunningUntilFailureNodeをそれぞれ実装しています．
開発環境にはProcessingを用いています．
前回までのあらすじ
前回のパートでは，敵NPCを動かすための，キャラクタAIのアルゴリズムとして，Behavior Treeを選択しました．また，Behavior Treeのアルゴリズムの概要についても示しました．
今回のパートでは，実際にBehavior Treeの実装を進めていきます．
開発環境
開発環境としては今回もProcessingを使います．ProcessingはVisual Artのためのプログラミング環境です．図形描画や画面のアップデート，キー入力の処理などが簡単に利用できて，デモ用コードを書くのに適しています．
将来的にはUnityへの移植を念頭に置いているため，Processing内での開発言語としてはJavaを選択します．
参考実装
参考実装としては，前回に引き続き，上記のリンクの実装を据えることにします．
ただし，本記事の内容は，参考実装を100%カバーするものではありませんので，注意してください．
Behavior Treeの実装
全体のベースとなる実装
NodeStatus
enum NodeStatus{ SUCCESS, FAILURE, RUNNING; }
Behavior Treeでは，全てのノードは3種類の結果のいずれかを返します．これを列挙型としてまとめておき，コード中で使っていくことにします．ノードがSUCCESSを返す場合は，ノードが正常状態で終了したことを意味します．FAILUREの場合は失敗して終了した場合を指します．RUNNINGはノードがまだ実行状態であることを意味します．
BehaviorTreeNode
class BehaviorTreeNode{
String name;
NodeStatus status;
BehaviorTreeNode(String nodeName) {
this.name = nodeName;
}
/* must override this method */
NodeStatus evalNode() {
return null;
}
/* debug function */
void printName() {
println("the name of this node is ", name);
}
}
全てノードの基本となるBehaviorNodeは以上のように書きました．BehaviorNodeはノードの名前と，ノードの実行状態の2つのフィールドを持ちます．ノードの評価はevalNode()の中に実装していきます．printName()は無くても機能上問題ないですが，ノードが自身の名前を名乗れるようにしておくと，デバッグの時に便利なので一応書いています．
制御ノードの実装
Behavior Treeの処理の流れを制御するのが制御ノードですが，今回はSequenceNodeとSelectorNodeの2つを実装します．
制御コードは配下に複数のノードを持ちますので，子ノードの追加と，それらの評価のメソッドを持つベースクラスを作るところから実装を始めたいと思います．
class ControlNode extends BehaviorTreeNode{
ArrayList children;
ControlNode(String nodeName) {
super(nodeName);
this.children = new ArrayList();
}
void addChild(BehaviorTreeNode new_node) {
children.add(new_node);
}
void printAllChildren() {
int len = children.size();
for (int i=0; i<len; i++) {
children.get(i).printName();
}
}
}
BehaviorTreeNodeを継承して，ControlNodeを以上のように書きました．ControlNodeは子ノードを管理するための配列を持っており，addChild()で引数として渡されたノードをこの配列に追加します．
printAllChildren()は無くても機能上は問題ありませんが，デバッグ用途で書いています．
SequenceNode
Sequence Nodeの動作を上図に示しました．Sequnce Nodeでは，配下に持っている全てのノードを順番に実行していきます．この際，配下のノードは処理結果を返してきますが，これは気にせずに，次々に実行します．配下のノードを全て実行し終えたら，SUCCESSを上位ノードに返します．処理を実行している間は常にRUNNINGを返します．
class SequenceNode extends ControlNode {
int numberChildren = 0;
int numberExecutedChildren = 0;
SequenceNode(String nodeName) {
super(nodeName);
}
NodeStatus executeAllChildren() {
BehaviorTreeNode processNode;
NodeStatus sequenceStatus = null;
NodeStatus processResult;
numberChildren = this.children.size();
if (numberExecutedChildren == numberChildren) {
return NodeStatus.SUCCESS;
}
// check the child node currently being processed
processNode = children.get(numberExecutedChildren);
// decide sequence status depend on the result of the current node.
processResult = processNode.evalNode();
switch (processResult) {
case SUCCESS:
numberExecutedChildren++;
sequenceStatus = NodeStatus.RUNNING;
break;
case FAILURE:
numberExecutedChildren++;
sequenceStatus = NodeStatus.RUNNING;
break;
case RUNNING:
sequenceStatus = NodeStatus.RUNNING;
break;
}
return sequenceStatus;
}
@Override
NodeStatus evalNode() {
NodeStatus result;
result = this.executeAllChildren();
return result;
}
}
ContolNodeを継承し，以上のようにして，SequenceNodeをつくりました．evalNode()をoverrideして，executeAllChildren()の実行結果をこのノードの処理結果として返すようにしています．executeAllChildrenでは，childrenに追加された子ノードを順番に実行していきます．
Part1でも紹介したように，Behavior Treeにおいては，Tick()によって何度もツリーを辿ることによって処理が進んでいきます．SequenceNodeはその中で，配下のどのノードを実行しているのかを管理する必要があります．そのために，numberExecutedChildrenという実行されたノードの個数を保持するフィールドを持っています．この値を使って，executeAllChildren()の中で，その回で実行すべき子ノードをchildrenから引っ張り出します．子ノードの個数はnumberChildrenというフィールドに保持されており，numberExecutedChildrenとnumberChildrenが同じ値であれば，配下のノードは全て実行されたということですので，SUCESSを返します．そうでないなら，引っ張り出した子ノードを実際に実行して，その結果に応じた処理をします．
子ノードの実行結果についてですが，SequenceNodeでは，子ノードの結果は気にしませんので，処理中は常にRUNNINGを返すようにしています．
SelectorNode
SelectorNodeの動作を上図に示しました．SelectorNodeは，適当なアクションが取れるところまで処理を続ける制御ノードです．配下のノードを順に処理していく部分についてはSequenceNodeと同様ですが，配下のノードの処理結果を加味して動作します．
配下のノードがSUCCESSを返してきた場合には，何らかの意味のある動作がとれたということですので，上位ノードにSUCCESSを返して処理を終了します．このとき，SUCCESSを返したノード以降のノードは実行されないということに注意してください．SUCCESSを返すようなノードがないときは，次々とノードが実行されていきますが，全てのノードにおいてFAILUREが返された場合には，意味のある行動をとることに失敗したということですので，Selector Node自体も上位ノードにFAILUREを返して終了します．
class SelectorNode extends ControlNode {
int numberChildren = 0;
int numberExecutedChildren = 0;
SelectorNode (String nodeName) {
super(nodeName);
}
NodeStatus executeChildren() {
BehaviorTreeNode processNode;
NodeStatus selectorStatus = null;
NodeStatus processResult;
numberChildren = this.children.size();
if (numberExecutedChildren == numberChildren) {
return NodeStatus.FAILURE;
}
// check the child node currently being processed
processNode = children.get(numberExecutedChildren);
// decide selector status depend on the result of the current node.
processResult = processNode.evalNode();
switch (processResult) {
case SUCCESS:
selectorStatus = NodeStatus.SUCCESS;
break;
case FAILURE:
numberExecutedChildren++;
selectorStatus = NodeStatus.RUNNING;
break;
case RUNNING:
selectorStatus = NodeStatus.RUNNING;
break;
}
return selectorStatus;
}
@Override
NodeStatus evalNode() {
NodeStatus result;
result = executeChildren();
return result;
}
}
ControlNodeを継承して，上のようにSelectorNodeを書きました．evalNode()をoverrideして，executeChildre()で配下のノードを実行した結果をSelectorNodeの結果として返すようにしています．
executeChildren()では，SequenceNodeと同じ要領で，配下の子ノードを順番に実行しています．違っているのはノードを全て実行し終えた時の処理と，子ノードの結果の扱いです．
SelectorNodeでは，子ノードを全て実行し終えるということは，適切なアクションが取れなかったということを意味します．このため，numberChildrenとnumberExecutedChildrenの値が一致した場合では，SequenceNodeとは反対にFAILUREを返すようにしています．
また，子ノードの処理結果の扱いに関しては，SequenceNodeでは子ノードの処理結果がSUCCESSであってもFAILUREであってもnumberExecutedChildrenをインクリメントして，次のノードに処理を進めていましたが，SelectorNodeではFAILUREの時だけ処理を次ノードに進めます．これによって，SUCESSを返す子ノードがあった場合にはそのノードに留まるので，以降のノードが実行されなくなります．SUCCESSを示すノードがあったときは，SelectorNode自体もSUCCESSを返すことになります．
末端ノードの実装
末端ノードは，ゲーム中でのキャラクタの挙動に対応するノードです．大まかには行動に対応するActionNodeと意思決定に対応するConditionNodeがあります．
ここで，末端ノードはキャラクタのアクションを作るわけですが，ゲーム上でのキャラクタのアクションというのは，ゲームやそのキャラクタに対して固有のものです．つまり，それ専用のコードがBehavior Treeのコードとは別にあるわけです．そのため，Behavior Tree上で実際に使う末端ノードは，Behavior Treeに関する処理と，キャラクタの挙動を作るコードを合わせたものということになります．
こういうわけで，どこでも使える一般的な末端ノードを作ることは難しいです．そこで，アクションに与えられた残り時間の管理や，上位ノードへの結果の応答といった，Behavior Tree上での末端ノードの挙動だけを実装したActionNodeクラスを実装し，これを継承する形で，ゲームで使う末端ノード作ることにします．
なお，図上ではActionNodeのみ記載していますが，ConditionNodeについても同じ要領です．
Part2 (本パート)では，ベースとなるActionNodeとConditionNodeをそれぞれ実装します．これらをPart4で，ゲームで使う末端ノードに仕立てる予定です．
LeafNode
/* This is a base class for leaf nodes. */ class LeafNode extends BehaviorTreeNode{ NodeStatus status; LeafNode(String nodeName){ super(nodeName); } }
末端ノードのベースとなるクラスを上のように書きました．中身は非常にシンプルで，持っているフィールドは処理結果を示すstatusだけです．
このクラスを作らずに，直接BehaviorTreeNodeを継承させることもできるのですが，末端ノードは末端ノードで，それ用のベースクラスから作った方が理解しやすい気がしたので使っています．
ActionNode
ActionNodeは，キャラクタの行動を作る末端ノードのベースとなるクラスです．Behavior Treeにキャラクタの動作のスクリプトを紐づける役割をしています．このクラスが達成すべきことは次の2つです．
1つ目は，キャラクタの行動に与えられた残り時間を管理することです．キャラクタが行動に使える時間は限られているのが普通ですので，残り時間を常に管理する必要があります．これによって，時間切れとなった時に，失敗とみなして次のタスクに移ったり，想定した時間よりも早く動作が完了した時に動作を繰り返したりすることが可能になります．
2つ目は，上位ノードに対して行動の結果を通知することです．ActionNodeはキャラクタの行動に紐づくものですから，そのキャラクタがとった行動が成功だったのか，失敗だったのか，あるいはまさに今取り組んでいる途中なのか，を上位ノードに知らせなければなりません．
class ActionNode extends LeafNode{
boolean isFinished = false;
boolean enableRepeat = false; // by default, repeating is disabled.
int requiredTotalFrames = 0;
int remainedFrames = 0; // it's decremented every Action() calls
ActionNode(String nodeName, int requiredTotalFrames){
super(nodeName);
this.requiredTotalFrames = requiredTotalFrames;
this.remainedFrames = requiredTotalFrames;
}
NodeStatus Action(){
if(0 < remainedFrames){
remainedFrames--;
return NodeStatus.RUNNING;
/* execute process to finite the action if remaindFrames reaches 0 */
}else{
/* reset */
if(enableRepeat){
isFinished = false;
remainedFrames = requiredTotalFrames;
}
return NodeStatus.SUCCESS;
}
}
@Override
NodeStatus evalNode(){
NodeStatus result;
result = this.Action();
return result;
}
}
Action Nodeを上記のように実装しました．overrideしたevalNode()が呼ばれることで，Action()が実行された結果が返されます．
Action()は前述した時間管理と，処理結果の決定に対応しているメソッドです．時間管理にはrequiredTotalFramesとremaindFramesの二つのフィールドを使います．requiredTotalFramesはこのクラスが作られる時に設定される値で，このアクションに対して割り当てられた時間（フレーム数）を表します．それに対して，remaindFramesは今残っている時間（フレーム数）を表します．remaindFramesは始めはrequiredTotalFramesで初期化されますが，実行されるたびに1ずつ減っていき，やがて0になります．remaindFramesの値が残っている間は，処理結果としてRUNNINGを返し続けて，0を下回ったときは処理が終了したということですのでSUCCESSを返します．
また，このAction Nodeは処理の繰り返しができるようになっており，そのためにenableRepeatというフィールドを持っています．このフィールドをtrueに設定しておくと，remaindFramesが0になって処理が終わった時に，remaindFramesがリセットされます．これによって処理が繰り返されます．
処理が終了したかどうかの判定にisFinishというフィールドを定義しています．これは後々，このクラスを拡張してキャラクタの専用の末端ノードを作る時に使っていくことになります．
ConditionNode
ConditionNodeはキャラクタの意思決定に対応するノードです．ゲーム上であれば，目標との距離が規定の距離よりも近いか，必殺技が使用可能か，HPが規定以上残っているか，鍵が空いているか，など，キャラクタを取り巻く状況を評価して，その後の行動の決定に使います．
ターン制のRPGやボードゲームは別として，アクションゲームではキャラクタの思考のために特別に時間を割くことはないので，ConditionNodeでは１回のTick()で処理結果を返します．このため，処理結果はSUCCESSかFAILUREのどちらかで，RUNNINGを返すことはありません．
class ConditionNode extends LeafNode{
boolean isMet = false;
NodeStatus status;
ConditionNode(String nodeName){
super(nodeName);
}
void checkCondition(){
if(isMet){
status = NodeStatus.SUCCESS;
}else{
status = NodeStatus.FAILURE;
}
}
@Override
NodeStatus evalNode(){
checkCondition();
return this.status;
}
}
ConditionNodeを上のように実装しました．overrideしたevalNode()でcheckConditionが呼び出されて，これによって処理結果がセットされ，これが応答されます．非常にシンプルです．
checkCondition()は，条件が満たされているかどうかを判定するisMetというフィールドを元に処理結果をセットします．
条件が満たされているのかの判定については，ゲーム固有，キャラクタ固有のコードになりますので，ConditionNodeを継承してキャラクタ固有の条件判定用ノードを作る際に記述していきます．
修飾ノードの実装
修飾ノードは配下のノードの動作に変更を加えるためのノードです．指定回数の繰り返しや，処理結果の反転などが代表的です．
様々な種類の修飾ノードが考えられますが，このプロジェクトでは，InverterNode，RepeaterNode，RetryUntilSuccessfulNode，KeepRunningUntilFailureNodeを実装します．
なお，配下のノードの個数についてですが，修飾ノードでは基本的に1つしか子ノードを持たないということに注意してください．複数のノードを修飾の対象としたいときは，制御ノードを間に噛ませると良いです．
DecoratorNode
制御ノードや末端ノードの場合と同様に，ベースクラスを作るところから始めていきます．
/* This is a base class for decorator nodes. */
class DecoratorNode extends BehaviorTreeNode {
BehaviorTreeNode child;
DecoratorNode(String nodeName) {
super(nodeName);
}
void setChild(BehaviorTreeNode new_node) {
this.child = new_node;
}
}
修飾ノードのベースクラスであるDecoratorNodeを上のように実装しました．DecoratorNodeは子ノードchildを持ち，これを修飾の対象とします．childを設定するために，setChild()というメソッドを定義しました．これによって，外部から引数として渡されたノード子ノードに設定できます．
InverterNode
InverterNodeは，配下のノードの処理結果を反転する修飾ノードです．
/* InverterNode is a node to invert the result of child node and return it */
class InverterNode extends DecoratorNode {
InverterNode(String nodeName) {
super(nodeName);
}
@Override
NodeStatus evalNode() {
NodeStatus result;
result = child.evalNode();
switch(result) {
case SUCCESS:
result = NodeStatus.FAILURE;
break;
case FAILURE:
result = NodeStatus.SUCCESS;
break;
case RUNNING:
result = NodeStatus.RUNNING;
break;
}
return result;
}
}
InverterNodeを上のように実装しました．overrideしたevalNode()で，結果の反転をしています．配下ノードのevalNode()を呼び出して得た結果がSUCCESSであった場合にはFAILUREを返し，FAILUREであった場合にはSUCCESSを返します．
RUNNINGの場合は，まだ配下のノードが実行中ですのでRUNNINGを返します．
RepeaterNode
RepaterNodeは，配下のノードを指定の回数だけ繰り返し実行する修飾ノードです．
/* RepeaterNode is a node to execute the specific child node repeatedly */
class RepeaterNode extends DecoratorNode {
int repeatCount = 0;
RepeaterNode(String nodeName, int repeatCount) {
super(nodeName);
this.repeatCount = repeatCount;
}
@Override
NodeStatus evalNode() {
NodeStatus result = child.evalNode();
// it's termination condition of this node.
if (repeatCount == 0) {
return NodeStatus.SUCCESS;
}
switch (result) {
case SUCCESS:
result = NodeStatus.RUNNING;
repeatCount--;
break;
case FAILURE:
result = NodeStatus.FAILURE;
break;
case RUNNING:
result = NodeStatus.RUNNING;
break;
}
return result;
}
}
RepeaterNodeを上のように実装しました．繰り返し回数を示すrepeatCountというフィールドを持っています．evalNodeでは，配下のノードが成功するたびにこのカウンタをデクリメントしていき，最終的に0になった時にSUCCESSを上位ノードに返します．
現状の実装では配下ノードがFAILUREとなった時に，ループから抜けられなくなるという問題があります．僕のデモでは特に問題にならなかったので，放置されているのですが，デモ以外の用途でこうしたコードを使うときは，もうすこし防衛的に書くべきです．
RetryUntilSuccessfulNode
RetryUntilSucessfulNodeは，配下のノードが成功するまで繰り返し実行する修飾ノードです．数回は失敗する前提のアクションを取るときなどに使用します．ただ，試行回数の上限は決めておく必要があって，そうしないと，成功の見込みがない状態で試行を始めた時に，そのアクションから抜け出せなくなってしまいます．
class RetryUntilSuccessfulNode extends DecoratorNode {
int numberAttempt;
RetryUntilSuccessfulNode(String nodeName, int numberAttempt) {
super(nodeName);
this.numberAttempt = numberAttempt;
}
@Override
NodeStatus evalNode() {
NodeStatus result;
result = child.evalNode();
switch (result) {
case SUCCESS:
result = NodeStatus.SUCCESS;
break;
case FAILURE:
result = NodeStatus.RUNNING;
numberAttempt--;
break;
case RUNNING:
result = NodeStatus.RUNNING;
break;
}
if (numberAttempt == 0) {
result = NodeStatus.FAILURE;
}
return result;
}
}
上のようなコードでRetryUntilSuccessfulNodeを実装しました．試行できる残り回数をnumberAttemptというフィールドに保持していて，下位ノードの結果がFAILUREであると，これがデクリメントされて，再度試行されます．numberAttemptが0になってしまったら，もうこれ以上は試行できないので，上位ノードにFAILUREを返します．
numberAttepmtが0になるまでは，失敗でも試行を続けますので，下位ノードがFAILUREを返した場合でも上位ノードにはRUNNINGを返します．
KeepRunningUntilFailureNode
KeepRunningUntilFailureNodeは，配下のノードが失敗するまで繰り返す修飾ノードです．RetryUntilSuccessfulNodeを反対にしたようなノードなのですが，回数の上限を特に設けていないという部分が異なります．下位ノードがSUCCESSを返している状態は望ましい状態であると言えるので，名前にKeepと入っていることから分かるように，できる限りその状況を維持しようとします．
ゲームの文脈では，炭鉱夫がひたすら金脈を掘り続けるみたいな状況で使い道があるかと思います．
class KeepRunningUntilFailureNode extends DecoratorNode{
KeepRunningUntilFailureNode(String nodeName) {
super(nodeName);
}
@Override
NodeStatus evalNode() {
NodeStatus result;
result = child.evalNode();
switch (result) {
case SUCCESS:
result = NodeStatus.RUNNING;
break;
case FAILURE:
result = NodeStatus.FAILURE;
break;
case RUNNING:
result = NodeStatus.RUNNING;
break;
}
return result;
}
}
KeepRunningUntilFailureNodeを上のように実装しました．非常にシンプルで，下位ノードがFAILUREを返した場合以外では，上位ノードにRUNNINGを返し続けます．
クラスの継承関係の確認
このパートでは，Behevior Treeを実装するために様々なクラスを作成しましたので，ここで一旦，クラス同士の関係を整理しておきたいと思います．
クラスの継承関係を上図に示しました．全てのベースになっているのはBehaviorTreeNodeです．これを継承して，LeafNode，ControlNode，DecoratorNodeが作られました．それぞれが末端ノード，制御ノード，修飾ノードに対応しています．
LeafNodeを継承して，キャラクタの行動に対応するActionNodeと，意思決定に対応するConditionNodeが作られました．
ControlNodeを継承して，処理の順次実行をするSequenceNodeと，選択的な実行をするSelectorNodeが作られました．
DecoratorNodeを継承して，処理の反転をするInverterNode，指定回数を繰り返すRepeaterNode，成功まで繰り返すRetryUntilSucessfulNode，失敗するまで繰り返すKeepRunningUntilFailureNodeが作られました．
まとめ
Processingをつかって，Behavior Treeで必要なノード群を実装しました．
制御ノードとして，SequnceNodeとSelectorNodeをそれぞれ実装しました．
末端ノードとしてActionNodeとConditionNodeをそれぞれ実装しました．
修飾ノードとして，InverterNode，RepeaterNode，RetryUntilSuccessfulNode，KeepRunningUntilFailureNodeをそれぞれ実装しました．
次回やること
このシリーズではゲーム上の敵NPCをBehavior Treeを使って動かすことを目的としています．Part 1，Part 2ではBehavior Treeの実装を進めてきましたが，このアルゴリズムを適用するためのデモ用ゲームがまだ準備されていません．
そこで，次回のPart 3では，デモ用として，簡単な2Dシューティグゲームを実装します．以前の弾幕シューティングの記事でも似たようなことを実はしているのですが，今回は，HPとダメージ計算も導入して，きちんと勝敗がつくようにします．
別パートへのリンク
Part 1 :
Part 2 :
現在地点．この記事です．
Part 3 :
工事中
Part 4 :
工事中
コード全体
今回紹介したコードの全体は以下で確認できます．
