概要
今回は、AIの中でも比較的スタンダードな、「Behavior Tree」について書きたいと思います。
（内容は、いろいろな記事を拾い読みしながら、自分の解釈で実装したものになるので、多少の誤解や間違いがあるかもしれません）
実装したサンプルはGithubで公開しています。
GitHub - edom18/SimpleBehaviorTree
スクエニの以下の記事にも、
と記載があるので、それなりに大きな比率を占めているものだと思います。
ちなみに、Unityのアセットストアにも、GUIで簡単に実装が行えるアセットが売られています。
Behavior Treeとは
Behavior Treeとは、ビヘイビア、つまり振る舞いをツリー構造状に定義し、それを逐一実行してく形のものです。
AIに対して、なにかしらの判断と、一連の流れを記述した行動をとらせたい場合に重宝する手法です。
Behavior Treeを構成するのは「ノード」です。
いくつかの基本ノードを様々に組み合わせながら、AIとしての処理を作っていきます。
ノードの種類
- ActionNode
- Decorator
- ConditionNode
- Sequencer
- Selector
- Repeater
などがあります。
特に、ActionNodeとConditionalNodeについてはリーフノードになっていて、分岐処理や、実際のアクションを実行するノードとなります。
それ以外のSequencer、Selectorは、いわゆるコンポジットパターンによる、子ノードを持てるノードになっています。
名前からなんとなく分かるかと思いますが、Sequencerは一連の流れを処理し、Selectorは、子ノードのうちのどれかを選択します。
以下で少し細かく見ていきます。
ActionNode
アクションノード。一番末端にあるノードで、ゲームオブジェクトの実際の振る舞い（アニメータを起動してアクションさせたり、1フレーム分移動させたり、など具体的な行動）を記述します。
Decorator
デコレータ。アクションノードなどの結果をデコレート、つまり装飾して返します。
例えば、アクション自体は成功しているけど、強制的に失敗にする、など用途は様々です。
ConditionNode
条件分岐用のノード。
プレイヤーが近くにいあるか、HPは足りているか、など様々な分岐を行うのに利用されるノードです。
以下で説明するシーケンサの中のひとつのノードに指定することで、例えば「プレイヤーが近くにいたら攻撃する」などの分岐が可能になります。
また、条件分岐ノードは「条件が更新された」場合に、それまで実行していた処理を中断して分岐がtrueになったあとの処理を再度実行するかを評価することができます。（詳細は後述します）
Sequencer
シーケンサ。つまり一連の流れを処理するノードです。
Selectorとの大きな違いは、登録された子ノードすべてを実行し、もし途中のノードで「失敗」が返された場合は、その時点でシーケンサの処理自体を「失敗」として親に戻します。
いわゆる「AND」的な振る舞いをするのがシーケンサの役割です。
主な利用シーンとしては、プレイヤーの位置を特定し(1)、その場所まで移動(2)、そして一定距離まで近づいたら攻撃(3)というような一連の流れを実行します。
もし仮に、途中の「プレイヤーの位置まで移動」が困難になった場合、（高台に逃げられた、とか）この処理は「失敗」扱いとなり、結果として「近づいて攻撃する」という一連の流れ自体が失敗になるわけです。
Selector
セレクタ。どれかひとつを選択します。イメージ的には「OR」ですね。
そしてこれは、「どんな行動をすべきか」を選択する場合に一番用いられるノードでしょう。
前述のシーケンサと組み合わせることで、「一定の体力がある場合は、近づいて攻撃」のパターンと、「体力が少なくなったから離れて攻撃」の選択肢があった場合に、ふたつのパターン自体はシーケンサにより一連の流れとして実装し、その「どちらかを選択する」ことを、セレクタが行う、という感じになります。
Repeater
設定されたノードを「リピート」するノードです。
ルートノードの下において処理をループすることで、常に思考を繰り返すAIが作れたりします。
ノードの状態
ノードにはいくつかの状態があります。
- 非アクティブ（Inactive）
- 成功（Success）
- 失敗（failure）
- 実行中（Running）
- 完了（Completed）
該当の処理が成功した場合は「成功」、失敗した場合は「失敗」、そして移動処理中など、まだ処理結果が分からず、処理中を表す状態が「実行中」となります。
また、まだタスクの実行が開始されていない状態を「非アクティブ」とし、非アクティブ状態で活性化された場合にOnStartなどの処理を実行します。
そして最終的に、全タスクが完了状態になった場合に、Behavior Tree全体が完了状態となるようになっています。
ノードのサイクル
各ノードはサイクルを持っていて、OnAwake、OnStart、OnUpdate、OnEndなどがあります。
今回実装したのはこの4つの状態です。
これを見てピンと来る方もいるかもしれませんが、いわゆるステートパターンにある状態遷移に近いイメージですね。
各ノードが活性化され、アクティブなノードが常にOnUpdateが呼ばれる形で実装しています。
冒頭のスクエニの記事でも触れられていますが、ステートパターンとは相性がよく、スクエニのFF15の各キャラクターは全体の大きな状態はステートパターンで実装され、各状態ごとの細かい処理はBehavior Treeで実装されているようです。
Conditionalノードの場合は、必要に応じて再評価する
Conditionalノードについてはやや特殊で、条件分岐を行う関係上、「再評価する必要がある場合」があります。
例えば、敵が近くにきた場合は攻撃する、というAIを作るとしましょう。
当然、最初は敵は近くにいません。
そしてその分岐は「失敗」に終わります。敵が近くにいないからですね。
その後、時間が経過して、敵が近づいてきたとしましょう。
しかし、再評価する仕組みがない場合、すでにその分岐は評価が終わってしまっているため、敵が近くにいる、という分岐処理は二度と実行されません。
つまり、敵が近づいてきたにもかかわらず、「敵が近づいてきたら攻撃する」という項目が一切実行されなくなってしまいます。
AIとしてこれでは困りますね。
そのため、再評価が必要な分岐の場合は、親ノード側でそれを知る必要があるわけです。
UnityのアセットであるBehavior Designerを見てみたところ、どうやら再評価がある分岐ノードについては常にOnUpdateを呼び続け、仮に状態が変化した場合にそれを検知するような仕組みになっていました。
実装方法は様々でしょうが、（オブザーバパターンなど）とにかく、分岐ノードの再評価が必要な場合は、常にチェックするように実装する必要がある、というわけです。
（じゃないと状態変化に気づけませんからね）
直感的にも再評価してくれるほうがいいと思うので、今回自分で自作してみた実装には再評価の仕組みを入れてあります。
実装方針
今回の実装は、比較的シンプルな形で、「ちょっとした分岐と再評価、そして行動」ができるAIが作れるレベルのものを目指しました。
（あくまでビヘイビアツリーの内容把握が目的なので）
まず、全体を管理するためのクラスとしてSimpleBehaviorTreeクラスを用意します。
このクラスがマネージャとして振る舞い、全体のタスクの更新と現在の状況の把握を行います。
ノードはNodeクラスがベースクラス
各ノードに関しては、Nodeクラスをベースクラスとして、前述したノードを実装しました。
これをそれぞれツリー構造になるように親子構造を構築し、それのルートノードをSimpleBehaviorTreeの実行する最初のノードとして設定します。
using UnityEngine; namespace BehaviorTreeSample { /// <summary> /// Simple Behavior Treeのノードベースクラス /// </summary> public abstract class Node { protected GameObject _owner; public GameObject Owner { get { return _owner; } set { _owner = value; } } private int _index = -1; public int Index { get { return _index; } set { _index = value; } } protected Node _parentNode; public Node ParentNode { get { return _parentNode; } set { _parentNode = value; } } protected string _name; public string Name { get { return _name; } set { _name = value; } } // 現在のステータス protected BehaviorStatus _status = BehaviorStatus.Inactive; public BehaviorStatus Status { get { return _status; } } public Node() { _name = GetType().ToString(); } /// <summary> /// Behavior Tree起動時に一度だけ呼ばれる /// </summary> public virtual void OnAwake() { // do nothing. } /// <summary> /// ノードが実行されたら呼ばれる /// </summary> public virtual void OnStart() { Debug.Log("[OnStart] " + Name); _status = BehaviorStatus.Running; } /// <summary> /// ノード実行中（Running）に毎フレーム呼ばれる /// </summary> public virtual BehaviorStatus OnUpdate() { if (_status == BehaviorStatus.Completed) { Debug.Log("This task already has been completed."); return _status; } if (_status == BehaviorStatus.Inactive) { OnStart(); } return _status; } /// <summary> /// ノードの実行が終了したら呼ばれる /// </summary> public virtual void OnEnd() { if (_status == BehaviorStatus.Completed) { return; } _status = BehaviorStatus.Inactive; } /// <summary> /// ノードが中断された際に呼び出される /// </summary> public virtual void OnAbort() { OnEnd(); } /// <summary> /// 子ノードを追加する /// </summary> /// <param name="child">追加する子ノード</param> public virtual void AddNode(Node child) { // do nothing. } /// <summary> /// 子ノードを複数追加する /// </summary> /// <param name="nodes">追加する子ノード郡</param> public virtual void AddNodes(params Node[] nodes) { // do nothing. } } }
見てもらうと分かるように、OnStart、OnUpdate、OnEndメソッドをvirtualで定義し、派生クラス側でそれをoverrideして利用する想定です。
OnAwakeだけは少し特殊で、SimpleBehaviorTreeクラスが起動された際に、ツリー全体を走査して、すべてのノードを「起こし」ます。そのときに実行されるのがOnAwakeです。
なので、このメソッドは実行後一度だけ呼ばれるメソッドとなります。初期化処理などをここで記述する想定です。
SimpleBehaviorTreeクラスは全体を管理
前述したように、SimpleBehaviorTreeクラスが全体を管理するマネージャクラスとなります。
そして管理方法としてはシンプルに、ツリー構造を持ったタスクすべてにユニークなインデックスを割り振り、インデックス番号からすぐに該当タスクを取り出せるようにします。
インデックス割り振りは、起動時に全タスクを起こすOnAwakeを呼び出すタイミングで行います。その際に、順にツリーを辿ってインデックスを割り振ります。
処理としては以下のようになります。
/// <summary> /// 対象ノードを起動（Awake）する /// </summary> /// <param name="node">起動するノード</param> private void CallOnAwake(Node node) { // ノードに全体のグラフの通し番号を設定する node.Index = _nodeList.Count; _nodeList.Add(node); // 対象ノードにオーナーを設定する node.Owner = _owner; // ノード起動 node.OnAwake(); // CompositeNodeの場合は再帰的に起動させる CompositeNode cnode = node as CompositeNode; if (cnode != null) { foreach (var child in cnode.Children) { CallOnAwake(child); } } }
そして、全体が管理できるようになったら、ルートノードから処理を開始します。
実行はツリー構造を辿り、シーケンサ、セレクターなどから構成された部分ごとに実行を繰り返します。
最終的には必ずどれかのリーフノードにたどり着くので、それを実行し、それが「成功」か「失敗」か、あるいは「実行中」かを判断し、「実行中」だった場合は処理をいったんそこで停止します。
※ 今回の実装では、全タスクの走査は1フレーム内で行います。そのため、どこかに無限ループがあったり、実行内容が多すぎる場合はゲームが停止します。
Conditionalノードの監視
前述したように、条件分岐を行うノードに関しては必要に応じて「再評価」する仕組みを導入します。
具体的には、再評価するべきとフラグが立てられたノードに関しては再評価リストにノードを登録し、他のタスク実行中も常に条件分岐処理（OnUpdate内でそれを行う）を実行し、もし条件分岐の状態が変化した場合にそれを通知します。
再評価対象などの情報を保持する専用クラスを設ける
今回の設計方針では、全タスクに対してインデックスが割り振られているので、そのインデックスを保持して、どのタスクが再評価必要かを把握するにはインデックスだけがあれば十分です。
ただ、それに紐づく親のタスクインデックスや、前回のタスクの終了状態などを一緒に保持しておくことで、評価が切り替わったことを検知することができるようになっています。
/// <summary> /// 再評価する際の諸々の情報を格納する /// </summary> public class ConditionalReevaluate { public int Index { get; set; } public BehaviorStatus Status { get; set; } public int CompositeIndex { get; set; } public int StackIndex { get; set; } public void Initialize(int i, BehaviorStatus status, int stack, int composite) { Index = i; Status = status; StackIndex = stack; CompositeIndex = composite; } }
Indexはタスクのインデックス、Statusは判断されたときの状態、StackIndexはスタック中どこにあるかのインデックス、CompositeIndexは親のインデックスを参照しています。
この「再評価情報」をリスト化し、再評価が必要なタスクを毎フレームチェックし、変化があった場合にそれを検知します。
そのために、毎フレームのUpdateごとに再評価リストをすべて評価します。
/// <summary> /// 再評価が必要なノードを再評価する /// </summary> /// <returns>再評価して変化のあったノードのIndex</returns> private int ReevaluateConditionalTasks() { for (int i = 0; i < _reevaluateList.Count; i++) { ConditionalReevaluate cr = _reevaluateList[i]; BehaviorStatus status = _nodeList[cr.Index].OnUpdate(); // 前回の状態と変化していたら、祖先まで遡って処理を停止する if (cr.Status != status) { CompositeNode cnode = _nodeList[cr.CompositeIndex] as CompositeNode; if (cnode != null) { cnode.OnConditionalAbort(cr.Index); } _reevaluateList.Remove(cr); return cr.Index; } } return -1; }
再評価に変化があったら、同じ祖先ノードまで遡って停止を伝える
もし仮に、どこかの再評価が変化した場合は、それまで実行していたタスクを終了させ、変化した分岐からやり直します。
例えば、シーケンサの最初のタスクに「敵が近くにいたら」というタスクがあった場合、大体の場合においては敵が近くにいないため「失敗」に終わります。
失敗した場合は「パトロール」などの別のタスクが実行されることになります。
そしてしばらくして敵が近づいてきた場合は分岐の結果が変わります。
このタイミングで、先に進んでいたタスクの「パトロール」を停止し、分岐結果が変わったところまでやり直し、以後の処理を継続します。
つまり、敵が近づいてきたら攻撃、などの「分岐が成功したあと」のタスクが実行される、というわけです。
↑最初の分岐が失敗になり、次のシーケンスが実行されている状態
↑最初の分岐状態が変更されたため、それまで実行されていたタスクを終了し、変化した分岐先の処理が開始される
以上のように、タスクを順次実行しながら、分岐が変化した際にそこまで戻って処理を行うことで、状況を把握し、適切に行動を起こすAIの仕組みを構築することができます。
実装してみて
SequencerとSelectorが重要な要素になります。
これらが連携しながらAIとしてキャラクターを操作していきます。
なので、アクションノードなどは実際の実行処理を記述するのみです。
今回は簡単のため、インスタンス生成時にラムダ式を渡してそれを実行するようにしています。
よく使われるようなアクションは個別に新規で作成してもいいと思います。（例えば一定時間待つアクションとか）
今回実装したアクションノードクラス↓
/// <summary> /// 実際のアクションを行うノード /// </summary> public class ActionNode : Node { private Func<GameObject, BehaviorStatus> _action; public ActionNode(Func<GameObject, BehaviorStatus> action) { _action = action; } public override BehaviorStatus OnUpdate() { base.OnUpdate(); _status = _action.Invoke(Owner); return _status; } }
実装してみて思ったのは、こうしたグラフを持つものはやはり、GUIベースのツールがないと実装するのは困難だな、ということ。
仕組み自体はできたものの、これを、高度に入り組んだAIを実際に組むとなるとコードが膨大になり、かつ管理も困難になるので、実際のところは、上で紹介したようなアセットを使うなどしたほうがよさそうです。
が、仕組みや動作原理などを把握したかったので今回のサンプルを作成しました。
冒頭でも書きましたが、いろんな記事を拾い読みして想像で実装したので、若干勘違いや他で使われているものと異なっている部分があるかもしれません。
また、「Behavior Designer」を実際に使ってその使用感や、カスタムタスクを実際に作成して動作確認したりしながら内部を想像して実装したので、だいぶ「Behavior Designer」よりの実装になっていると思います。
ちなみに、（タイトル同じですが）GREEのEngineerブログで、PHPによる実装例が記載されていました。
こちらもだいぶシンプルな例になっているので、合わせて見てみるとより分かりやすいかもしれません。
シンプルなBehaviour Treeを実装してみる - GREE Engineers' Blog
その他のAI実装パターン
ちなみに、以前にこれとは別のAI作成パターンとして、「ゴール駆動型エージェント」の記事も書いているので、AI関連に興味がある方は読んでみてください。
