進んで戻るスタックベース状態遷移

例えばゲームのアイテムメニューにある薬草を捨ててゲームに戻るまでの挙動を考えてみます：

1.  ゲーム画面からアイテムメニューを開く
2. アイテム項目「武器、道具、魔法」から「道具」を選択
3. 道具一覧から薬草を選択
4.「使う、渡す、捨てる」から「捨てる」を選択
5. 「捨てても大丈夫？」という警告ダイアログが出るので「はい」を選択
6. 道具一覧に戻る
7. アイテム項目へ戻る
8. ゲーム画面に戻る

こういう「どんどん先へ進んで末端まで行ったら戻る戻る戻る…」という状態遷移を実現するのがスタックベース状態遷移です。

各状態は「終わったよ～」を告げる

スタックというのは配列やリストのようなコンテナの一つです。追加した最新の物だけに注目するのが特徴で、アクセスも最新の物しか出来ません。そして、今注目している物がいらなくなったらpop（取り出し）すると、その前に追加した物が有効になります。これを状態遷移に利用するんです。

具体的に見てみましょう。C++の場合std::stackテンプレート、C#ならSystem.Collection.Generic.Stackクラスを使います。状態を表すクラスはStateクラスとしときましょう。

Stateクラスのオブジェクトをスタックに追加すると、状態を更新するupdateメソッドが呼ばれ続けるようになります。このメソッドが「もう自分はいらなくなりましたー」と宣言（falseを返す）したら、スタックから取り除かれます。Stateクラスは「継続か終了か」を毎回告げるだけで良いので単純明快(^-^)

もう一つ、Stateクラスの中からスタックに次の状態を積む事が出来ます。これを実現するにはStateクラスが積む方法を知っている必要があります。これには幾つか方法が考えられますが、ここでは「updateメソッドの引数に投げる」という手段を取る事にします。

Stateクラスはこんな感じでしょうか：

class State {
public:
    virtual ~State() {}
    virtual bool update( State **nextState ) = 0;    // 更新
};

シンプル(^-^)/

スタック管理者

Stateのスタックを保持したり状態を更新する管理者が必要です。StateStackManagerクラスとでもしておきましょう。この管理者は毎フレームスタックの先頭にあるStateの更新を行って戻り値と引数を監視します。もしfalseが返ってきたらスタックから状態を取り除き、引数に有効なポインタが戻されたらスタックに積みます：

 #include  <stack>

class StateStackManager {
public:
    StateStackManager( State* firstState ) {
        stack_.push( firstState );
    }
    virtual bool update() {
		if ( stack_.size() == 0 )
			return false;
		State *next = 0;
		if ( stack_.top()->update( &next ) == false ) {
			stack_.pop();
		}
		if ( next != 0 ) {
			stack_.push( next );
		}
		return ( stack_.size() > 0 );
    }
private:
    std::stack< State* > stack_;
};

実装例はこんな感じです。updateメソッドのstack_.top()でスタックの先頭にある対象Stateを更新しています。

この実装、Stateクラスのupdateメソッドの戻り値とnextの有無の組み合わせで振る舞いが色々変わるのが面白い所です。まずupdateメソッドがtrueを返しnextがnullの時、これは既存Stateの継続になります。falseを返してnextもnullの時は既存Stateの破棄、つまり「戻る」に該当する事になります。
updateメソッドがtrueを返しnextに有効なポインタが返った場合、これは状態の追加となり、次のフレームからは追加された状態の更新が走ります。追加した状態が終わるまで今の状態は停止します。
楽しいのがfalseを返しつつnextが有効というパターン。falseなので既存のStateは死にます。でもnextがあるのでそれはスタックに積まれる。これスタックトップの「交換」をしている事になるんです(^-^)。つまりこの技を用いればFSM的な状態遷移もやれるんです。お～～

「薬草誰がどうやって消す」問題

スタックベース状態遷移を使うと、冒頭のアイテムメニューのような進行して戻ってくるような状態遷移を表現できそうです。ただし実用するに注意もあります。

実際に実装して「あれ？」となるのが環境変更への対応です。冒頭の例では進んで進んで最後に「はい」を選択した時に初めて薬草を消す事が確定します。で「んじゃ消しましょう」となった時、今の状態が単なる「YesNoダイアログ」である事に気付きます。消せねぇーー！ってなるんです。

これは消す手段を知らせていない為です。何だかんだで一番簡単な解決方法は、環境をある程度渡してしまう設計です。State::updateメソッドは汎用性の為引数を変えられないので、例えばコンストラクタに環境を渡します。もしくはStateをテンプレートクラスにしてupdateメソッドの引数を汎化する手もあります：

template< class Env >
class State {
public:
    virtual bool update( Env *env, State **next ) = 0;
};
 
class YesNo : public State< ItemEnv > {
public:
    YesNo( Item *item ) : item_( item ) {}
    virtual bool update( Env *env, State **next ) {
        if ( decide_ == true ) {
            env->deleteItem( item_ );
            return false;   // 遷移終了
        }
        return true;
    }
private:
    Item *item_;
};

Envテンプレート引数がupdateメソッドに渡りますので、好きなように扱っていいよ～という実装です。直接消すのではなくてイベントドリブン（イベントだけ発行してそれを受けた人が振る舞うエンジン設計）にするものありです。

という事でスタックベースの状態遷移のお話でした。こちらの話題をリクエスト頂いたtoyboot4eさん、ありがとうございました～(^-^)/

※ 最後までお読み頂きありがとうございます。本コーナーで「こんな事について書いて欲しい」「こういう所がうまくいかないのだけどアイデア下さい」などリクエストやお困りな事がありましたらコメント、Twitter（@Marupeke_IKD）等でお気軽に教えて下さい(^-^)。出来る範囲で恐縮ですが検討させて頂き、記事としてアップ致します！