HSM/階層型状態遷移機械

ゲームプログラミングでは FSM (有限状態遷移機械, Finite State Machine) を多用する。保守性に優れ、また記述が容易な FSM を作成するためのフレームワークとして HsmBase クラステンプレートを用意した。本文書では HsmBase テンプレートに関して背景、チュートリアル、リファレンスを提供する。

ソースコード

• source:GameLib/Hsm.h
• source:GameLib/Hsm.inl

背景

目的は FSM (Finite State Machine; 有限状態遷移機械) を実装するための簡潔かつ十分に高機能なクラスライブラリを提供すること。ライブラリの実装に際しては様々なトレードオフが発生するが、特にゲームや組み込み用途での使用を視野に入れ、下記の点を重視した。

• 状態と実行コンテクストのモノリシック化
• UML ステートチャートで取り入れられている主要要素への対応
  • ステートチャート図を直感的にコードに変換できること。
  • 入れ子状態のサポート。
  • 入退場動作のサポート。
  • デフォルト状態遷移のサポート。
  • ガードのサポート
  • ジャンクションポイントのサポート。
• ポータビリティ
  • C++ 言語処理系の枠内で実装でき、別途トランスレータや環境依存の API 等を必要としないこと。
  • 実行時に巨大な外部ライブラリを必要としないこと。
  • 十分高速に動作すること。
  • 実行時に巨大なメモリを必要としないこと。
• 高い開発効率
  • コーディングが容易であること。
  • 型安全であること。
  • 拡張性があること。
  • 十分な実行時エラーチェックを提供すること。
  • 実行時エラーチェックは、コンパイルオプションで無効化できること。

機能面では、特に入れ子状態のサポートが目玉。ライブラリの HSM という名前も Hierarchical State Machine (階層型状態遷移機械) に由来する。

入れ子状態とは、たとえばゲーム中の主人公キャラクタの状態として大きく「生きている」「死んでいる」の二状態を用意し、「生きている」の内部にさらに「立ち止まっている」「歩いている」といった状態を設けること。共通処理を基底クラスに切り出すのと同様に、共通処理を包含するクラスに切り出すことでコードの再利用と差分プログラミングが促進される。

チュートリアル

FSM の設計に際しては、まず次の2点を決定する必要がある。

• 状態をどのように表現するか？
• イベントをどのように表現するか？

C++ で FSM を実装するもっともシンプルな方法は、状態を整数型もしくは列挙型のメンバ変数として保持し、イベントをメンバ関数呼び出しとすることである。次に例を示す。

• 状態はメンバ変数 m_state に保持。m_state の値を書き換えることで状態遷移を行う。
• イベントはメンバ関数 exec(), draw() 呼び出しに対応。イベント事にメンバ関数を追加する。

class FsmSample
{
public:
    FsmSample();
    // 状態に応じて動作を変えるメンバ関数1
    void exec();
    // 状態に応じて動作を変えるメンバ関数2
    void draw() const;
private:
    // 状態を記録するメンバ変数
    enum { STATE_INIT, STATE_MAIN, STATE_TERM } m_state;
};

FsmSample::FsmSample()
  : m_state(STATE_INIT)
{}

void FsmSample::exec()
{
    switch (m_state) {
    case STATE_INIT:
        // 初期化処理
        m_state = STATE_MAIN;
        break;
    case STATE_MAIN:
        // メイン処理
        if (終了要求がなされたら)
            m_state = STATE_TERM;
        break;
    case STATE_TERM:
        break;
    }
}

void FsmSample::draw() const
{
    switch (m_state) {
    case STATE_INIT:
    case STATE_TERM:
        break;
    case STATE_MAIN:
        // 描画処理
    }
}

本ライブラリでは、状態表現とイベント通知に関して次の選択を行った。

• 状態毎にメンバ関数を用意し、状態はメンバ関数ポインタとして保持する。
• イベントは FSM とは別個のクラスとする。イベント種別を識別するために、イベントクラスに int 型のシグナル値を記録する。
• 状態遷移機械・イベントいずれもクラステンプレートとして実装し、単一基底クラスからの派生を強制しない。

以下にイベントと状態の実装例を示す。

class HsmTest;

// イベントの例
class HsmTestEvent
    : public HsmEventBase<HsmTest, HsmTestEvent>
{
public:
    enum { NSIG_DRAW, NSIG_EXEC };
    // Drawイベントの作成
    static HsmTestEvent CreateDraw() { return HsmTestEvent(NSIG_DRAW); }
    // Execイベントの作成
    static HsmTestEvent CreateExec() { return HsmTestEvent(NSIG_EXEC); }

private:
    HsmTestEvent(int nsig) : HsmEventBase(nsig) {}
    friend class HsmEventBase<HsmTest, HsmTestEvent>;
};

// 状態遷移機械の例
class HsmTest
    : public HsmBase<HsmTest, HsmTestEvent>
{
public:
    void exec(ICtxTask& ctx, TASK_PRIO_TYPE prio);
    void draw(ICtxTask const& ctx, TASK_DPRIO_TYPE dprio) const;
private:
    // 状態関数
    HsmState _stateInit(HsmTestEvent const& event);
    HsmState _stateMain(HsmTestEvent const& event);
    HsmState _stateTerm(HsmTestEvent const& event);
};

状態に関しては、HsmTest クラスの基底クラスである HsmBase?<HsmTest, HsmTestEvent?> が保持するメンバ変数 m_cur に、&!HsmTest::_stateInit, &!HsmTest::_stateMain, &!HsmTest::_stateTerm のいずれかの値が保持される。この状態を表すメンバ関数を以下では状態関数と呼ぶ。

イベントは HsmTestEvent クラスを用いて表現し、特に基底クラス HsmEventBase?<HsmTest, HsmTestEvent?> のメンバ関数 getSignal() で、イベントの種別を表すシグナル値 NSIG_DRAW, NSIG_EXEC を取得できる。なお、シグナル値にはシステムが予約している NSIG_SUPER, NSIG_INIT, NSIG_ENTER, NSIG_EXIT があるが、詳しくは後述する。

状態関数

状態関数はイベントを受理し、そのイベントに従ってアクションを起こす。Drawイベント、Execイベントに対して動作を行う状態関数の例を以下に示す。

HsmTest::HsmState HsmTest::_stateInit(HsmTestEvent const& event)
{
    switch (event.getSignal()) {
    // 中略
    case HsmTestEvent::NSIG_DRAW:
        // draw 動作
        return 0;
    case HsmTestEvent::NSIG_EXEC:
        // exec 動作
        if (init_done())
            HSM_TRAN(&HsmState::_stateMain);
        return 0;
    }
    // 親状態を返す
    return HSM_TOP();
}

なお状態関数の記述に際しては、規則がある。

• その状態内でイベントを処理した場合は 0 を返す。
• その状態内でイベントを処理せず、親状態に処理をゆだねる場合には親状態のメンバ関数ポインタを返す。通常は関数の最後で親状態のメンバ関数ポインタを返すようにしておき、switch - case で、親状態にチェインしたいイベントに対応する case 文を省く。
• 親状態がない場合には HSM_TOP() を返す。
• 状態遷移を起こす場合には HSM_TRAN() を呼び出す。

状態関数には、ユーザ定義イベントに加えいくつかのシステム定義イベントが通知される。

NSIG_SUPER

親状態取得。通常は関数の最後で親状態のメンバ関数ポインタを返すようにしておき、switch - case で NSIG_SUPER に対応する case 文を書かないことで対応。

NSIG_INIT

デフォルト状態遷移。HSM_TRAN() 呼び出しでの状態遷移終了後、さらに連続して子状態に遷移したい場合に HSM_INIT() を呼び出すことができる。

NSIG_ENTER

入場動作。HSM_TRAN() が呼び出され、その状態に入ってきたときに一度だけ呼び出される。

NSIG_EXIT

退場動作。HSM_TRAN() が呼び出され、その状態から抜けるときに一度だけ呼び出される。

ライブラリ上の規則ではないが、HSM_TRAN(), HSM_INIT() 関数は状態関数にのみ記述し、状態関数から呼び出される別の関数には記述しないことが保守性向上のために望ましい。

デフォルト状態遷移は、包含している状態の詳細を隠蔽したい場合やカスタマイズしたい場合に役立つ。たとえば次のような状態関数を持つクラス Player を考える。

• 生きている (_stateAlive)
  • 立ち止まっている (_stateStand)
  • 浮いている (_stateFly)
• 死んでいる (_stateDead)

このうち _stateAlive は抽象基底クラスに相当する状態で、_stateStand, _stateFly の共通処理を括りだしたものであり、実際に実現する状態は _stateStand, _stateFly, _stateDead のいずれかであり、さらに _stateStand, _stateFly どちらになるかは他のメンバ変数の値 (装備品など) で決まるとする。デフォルト状態遷移がない場合は HSM_TRAN() 呼び出し側で状態遷移先を確定する必要があるため、次のようなコーディングが必要となる。

Player::HsmState Player::_stateDead(PlayerEvent const& event)
{
    switch (event.getSignal()) {
    case HsmTestEvent::NSIG_EXEC:
        if (getHp() > 0)    // 生き返った
            if (canFly())
                HSM_TRAN(&Player::_stateFly);
            else
                HSM_TRAN(&Player::_stateStand);
        return 0;
    }
    // 親状態を返す
    return HSM_TOP();
}

これは呼び出し側が _stateAlive の内部構造を熟知する必要がある上、_stateStand, _stateFly への遷移箇所が増えると同じコードを copy & paste で増殖させることとなる。デフォルト状態遷移を使うと、次のようにこの条件分岐が _stateAlive 内部に移動できる。

Player::HsmState Player::_stateAlive(PlayerEvent const& event)
{
    switch (event.getSignal()) {
    case HsmTestEvent::NSIG_INIT:
        if (canFly())
            HSM_INIT(&Player::_stateFly);
        else
            HSM_INIT(&Player::_stateStand);
        return 0;
    }
    // 親状態を返す
    return HSM_TOP();
}

Player::HsmState Player::_stateDead(PlayerEvent const& event)
{
    switch (event.getSignal()) {
    case HsmTestEvent::NSIG_EXEC:
        if (getHp() > 0)    // 生き返った
            HSM_TRAN(&Player::_stateAlive);
        return 0;
    }
    // 親状態を返す
    return HSM_TOP();
}

最後に、既存の状態を拡張したい場合、状態関数を仮想関数として定義し派生クラス側でオーバーライドすることで状態の再定義が可能である。

イベント

イベントは状態関数への通知内容を扱い、クラステンプレート HsmEventBase を継承してクラスを作成する。重要なメンバとしてイベントの種別を取得するメンバ関数 getSignal() があり、特に負のシグナル値はシステム予約であるため、ユーザが使用することはできない。また必要であれば、イベントにはシグナル以外のメンバを持たせることも可能である。

状態関数に対してシグナルを送信するには、HsmEventBase クラステンプレートで定義されている dispatchHsm() 関数を呼び出す。なお const メンバ関数に対するサポートがないため、現時点では const_cast を用いて this ポインタから const 制約を外して dispatchHsm() 関数を呼び出す必要がある。

HsmTest::HsmState HsmTest::draw() const
{
    const_cast<HsmTest*>(this)->dispatchHsm(HsmTestEvent::CreateDraw());
}

HsmTest::HsmState HsmTest::exec()
{
    dispatchHsm(HsmTestEvent::CreateExec());
}

リファレンス

source:GameLib/Hsm.h 中のコメント参照。

initHsm() 呼び出しを忘れずに。

メモ

• ライブラリ中で使用している dbAbort() は、第一引数が真でなければ停止して第二引数以降のメッセージを出力する assert() の拡張版。環境依存のコードになっていることと、実装は容易なためソースコード中に含めていない。
• 状態関数は戻り値として親状態に対応する状態関数を返すが、C++ の構文制約上、自分自身と同じ型を返す関数は定義できない。そこでメンバ関数ポインタをラップするクラステンプレートとして HsmState を用意した。

TODO

• dispatchHsm() の const 対応。
• リファレンスをまじめに書く。
• dbAbort() は assert() で置き換えるか検討。

参考文献

``Practical Statecharts in C/C++: Quantum Programming for Embedded Systems'' Miro Samek, Ph.D. (CMP Books)

本ライブラリの設計に際しては、書籍「Quantum Programming for Embedded Systems」で紹介されている QHsm クラスを参考にした。この書籍では QHsm クラスの設計・実装だけでなく、代表的な FSM の実装に関する長短比較や、頻繁に用いられる状態遷移のデザインパターンについても詳細に述べられている。推奨。

The Boost Statechart Library

C++ Boost Library の FSM ライブラリ。2006/11/02 現在、まだリリース版の Boost ライブラリには含まれていないが、既に CVS リポジトリには取り込まれているため、次回リリース以降で標準配布物に含まれると思われる。状態の管理に nested type を用いた Generic Programming の手法を用いている。やや規模が大きく使い方が複雑だが、設計は洗練されており性能も高い。

UML 2 状態マシン図の概要

UMLステートチャートに関する解説。