階層型状態マシン(HFSM)を実装する

GoFのデザインパターンでStateパターンを階層化した、階層型状態マシン(HFSM:Hierarchical Finite State Machines)を作成してゲーキャラクターの制御を行ったので実装例を紹介したいと思います。

有力なゲームエンジン(UnityやUE4)であればHFSMと同等の機能として「ビヘイビアツリー」がなんとUIエディタ付きで提供されているため、ゲームエンジンI制御に於いては、独自に実装する機会は無いのかと思います。しかし、そういった機能がサポートされていない環境(例えば自作エンジンや、Cocos2d-xなど)でキャラクターのAI制御を行うため実装の必要だったので実装しました。

以下実装した時のキャラクターの動きになります。

実装する状態遷移

今回参考として実装する状態遷移は以下の通りです。

f:id:Takachan:20180909125023p:plain

階層型にしないと戦闘状態に移行する判断を巡回状態の2つが重複して考慮することになる場合があり、コードが重複してしまいます。2つくらいならまだ大丈夫ですが、10個、20個と状態が増えるとかなりツラくなっていきます。従って、HFSMでは共通の判断は上位状態を用いて制御し、子要素は個別の処理に専念するように実装していきます。

使い方

では、早速実装をしていきたいと思います。

元々C++で作成していたのですが、本筋に無関係な、Cocos2d-x固有のコードを除外するために.NET FrameworkのC#で実装していきます。先ず、実装完了後の使い方から説明したいと思います。(今の時点では意味不明だと思いますがこんな風になりますよ的な意味で。

public static void Main(string[] args)
{
    // キャラクターを表すモデルを宣言
    var model = new Model();

    // x-x-x-x 以下、状態遷移を組み立てる x-x-x-x

    // 巡回状態の組み立て
    var patrol = new PatrolState(model);
    patrol.AddChildState(ModelState.Move, new MoveState(model));
    patrol.AddChildState(ModelState.Wait, new WaitState(model));

    // 戦闘状態の組み立て
    var battle = new BattleState(model);
    battle.AddChildState(ModelState.Approach, new ApproachState(model));
    battle.AddChildState(ModelState.Attack, new AttackState(model));

    // モデルに設定して初期状態を指定する
    model.RootState.ChildStateTable[ModelState.Patrol] = patrol;
    model.RootState.ChildStateTable[ModelState.Battle] = battle;
    model.RootState.ChangeChildState(ModelState.Patrol, false); // 初期状態を指定

    // 1フレーム毎のアップデートのつもり
    while (true)
    {
        model.Execute();
        Thread.Sleep(1 / 30/*fps*/ * 1000);
    }
}

状態を組み立て後はExecuteをフレームごとに呼び出せば処理が完了します。

状態を表す基底クラス

全ての状態の元になる抽象クラスの実装です。

ちょっと長いです。デザインパターンのセオリー通り、操作として、状態に入る時、出る時、状態中の動作を抽象メソッドとして定義し、階層型状態マシンなので自分自身の状態の変更と、子要素の状態の変更の2つのメソッドを実行しています。

状態を変更する時に、自分の子要素を全て集めて末端の状態から退場動作を行います。

// 階層型ステートマシンの基底クラス
public abstract class State<S, M>
{
    // -x-x-x- Fields -x-x-x-

    // この状態が制御するモデル
    protected M _model;
    // 現在の子状態を表す識別子
    protected S _current_child_state_id;
    // 現在の子状態
    protected State<S, M> _current_child_state;

    // -x-x-x- Properties -x-x-x-

    // 親の状態を設定または取得する
    public State<S, M> Parent { get; set; }

    // 子状態が取りえる状態を持つテーブル
    public IDictionary<S, State<S, M>> ChildStateTable { get; } = new Dictionary<S, State<S, M>>();

    // 現在の子状態を取得します。
    public State<S, M> ChildState { get { return this._current_child_state; } }

    // -x-x-x- Constructors -x-x-x-

    // 制御対象のモデルを指定してオブジェクトを初期化する
    public State(M model)
    {
        this._model = model;
    }

    // -x-x-x- Methods -x-x-x-

    // 遷移時に一度だけ呼ばれる
    public abstract void Enter();

    // この状態中毎フレーム呼び出される
    public abstract void Execute();

    // この状態を抜ける時に一度だけ呼ばれる
    public abstract void Exit();

    // 子状態を追加する
    public void AddChildState(S state_id, State<S, M> state)
    {
        state.Parent = this.Parent;
        this.ChildStateTable[state_id] = state;
    }

    // 次の状態に自己遷移する
    public void ChangeState(S next_status)
    {
        if (this.Parent == null)
        {
            throw new InvalidOperationException("Not set parent.");
        }

        this.Parent.ChangeChildState(next_status);
    }

    // 子要素の状態を変更する
    public void ChangeChildState(S next_status)
    {
        // 次の遷移が存在するかどうかを確認する
        if (!this.ChildStateTable.ContainsKey(next_status))
        {
            throw new InvalidOperationException("Can not transit state. " + next_status.ToString());
        }

        // 末端までの子状態を集めて末端の子要素から順に退場動作を実行していく
        var childs = new List<State<S, M>>();
        State<S, M> tempState = this._current_child_state;
        while (tempState != null)
        {
            childs.Insert(0, tempState);
            tempState = tempState.ChildState;
        }

        foreach (State<S, M> c in childs)
        {
            c.Exit();
        }

        this._current_child_state_id = next_status;
        this._current_child_state = this.ChildStateTable[next_status];
        this._current_child_state.Enter();

        // 状態を変更したら状態を1回実行する(不要であればコメントアウト)
        this._current_child_state.Execute();
    }
}

制御対象のモデルと状態遷移の定義

状態遷移が制御する対象のモデルを表すクラスです。今回は以下の通り定義します。重要なのは、状態遷移時に実際に実行する動作をこのクラスに記述することです。口述の個々の状態クラス内にモデルの具体的なモデルの動作や主要な判断を記述しないように注意します。

現在、ジェネリックを状態クラスで宣言していますが、多様性を確保する方針は、ジェネリックではなくインターフェースのほうが良いかもしれません。

// 状態遷移で制御されるモデルの定義
public class Model
{
    // -x-x-x- Properties -x-x-x-

    // 現在の座標Xの設定または取得する
    public float X { get; set; }

    // 現在の座標Yの設定または取得する
    public float Y { get; set; }

    // ルート状態の設定または取得する
    public State<ModelState, Model> RootState { get; set; }

    // -x-x-x- Methods -x-x-x-

    // 1フレームごとに呼ばれる処理
    public void Execute()
    {
        this.RootState?.Execute(); // 状態を呼び出す。
    }

    // 対象が視界内に居るかどうかを判定する
    public bool IsInsightTarget()
    {
        return true; 
    }

    // 対象が到達可能かどうかを判定する
    public bool IsReachableTarget()
    {
        return true;
    }

    // 適当に移動する
    public void Move() { /* 省略 */ }

    // 対象に接近するために移動する
    public void ApproachTarget() { /* 省略 */ }

    // 攻撃する
    public void Attack() { /* 省略 */ }
}

個別の状態遷移クラスの記述

まず、各状態に対応する列挙子を定義します。これを定義する事で状態を示すことができます。

// 状態を表す列挙子
public enum ModelState
{
    // 巡回状態
    Patrol = 0,
    // 移動状態
    Move,
    // 待機状態
    Wait,

    // 戦闘状態
    Battle,
    // 対象に接近中
    Approach,
    // 対象を攻撃中
    Attack,
}

次に各々の状態クラスの実装になります。物凄い長いので個々の処理をある程度省略しているので全体の流れだけになります。基本的に状態の遷移動作のみを記述し、具体的な動作や判断はModelクラスで行います。

// 巡回状態を表すクラス
public class PatrolState : State<ModelState, Model>
{
    public PatrolState(Model model) : base(model) { }

    // 入場した時は移動を設定
    public override void Enter() { this.ChangeState(ModelState.Move); }

    public override void Execute()
    {
        if (this._model.IsInsightTarget())
        {
            // 視界内に敵が居たら戦闘状態に移行
            this.ChangeState(ModelState.Battle);
        }
        else
        {
            this.ChildState.Execute();
        }
    }

    public override void Exit() { /* nop */ }
}
// 巡回状態を表すクラス
public class MoveState : State<ModelState, Model>
{
    public MoveState(Model model) : base(model) { }

    public override void Enter() { /* nop */ }

    public override void Execute()
    {
        if (/*待機状態に遷移する?*/)
        {
            this.ChangeState(ModelState.Wait);
        }
        else
        {
            // モデルの移動を呼び出す
            this._model.Move();
        }
    }

    public override void Exit() { }
}
// 待機状態を表すクラス
public class WaitState : State<ModelState, Model>
{
    public WaitState(Model model) : base(model) { }

    public override void Enter() { /* nop */ }

    public override void Execute()
    {
        if (/*待機時間が経過した?*/)
        {
            this.ChangeState(ModelState.Move);
        }
    }

    public override void Exit() { /* nop */ }
}
// 戦闘状態を表すクラス
public class BattleState : State<ModelState, Model>
{
    public BattleState(Model model) : base(model)
    {
        // 戦闘は先ずは対象に接近から始める
        this.ChangeChildState(ModelState.Approach);
    }

    public override void Enter() { /* nop */ }

    public override void Execute()
    {
        if (this._model.IsInsightTarget() && this._model.IsReachableTarget())
        {
            this.ChildState.Execute();
        }
        else
        {
            // 対象が居ない場合巡回状態に戻る
            this.ChangeState(ModelState.Patrol);
        }
    }

    public override void Exit() { /* nop */ }
}
// 対象に接近中を表すクラス
public class ApproachState : State<ModelState, Model>
{
    public ApproachState(Model model) : base(model) { }

    public override void Enter() { /* nop */ }

    public override void Execute()
    {
        // 対象に接近する
        this._model.ApproachTarget();
    }

    public override void Exit() { /* nop */ }
}
// 対象に接近中を表すクラス
public class AttackState : State<ModelState, Model>
{
    public AttackState(Model model) : base(model) { }

    public override void Enter() { /* nop */ }

    public override void Execute()
    {
        // 対象を攻撃
        this._model.Attack();
    }

    public override void Exit() { /* nop */ }
}

実際の実装時はかなり複雑になると思いますが、基本的な流れはこんな感じになります。