プッシュダウンステートマシンのサンプル実装（階層構造を扱える状態遷移機械の話）

　プッシュダウンオートマトン形式のステートマシン（以下プッシュダウンステートマシン）について人に説明するときにいつもサンプルコードを探すのに手間取るので、デモ用のコードを書きました。ゲーム開発ではよく使うイディオムだと思いますが、一般的な実装があるわけではなく（少なくとも土屋は知らない）、あくまで自己流です。

https://gist.github.com/t-tutiya/f78399201e818a5ec7fc3aa74d5f0833

　せっかくなので、以下プッシュダウンステートマシンについて解説します。

プッシュダウンステートマシン概要

　プッシュダウンステートマシンとはなにかと言いますと、個々のオブジェクトがステートを格納するＬＩＦＯ形式のスタックを持つステートマシン（状態遷移機械）のことです。土屋がそう呼んでいるだけで、もっと一般的に使われている呼称があるのかもしれません（スタック式ステートマシンとかかなあ？　ご存知の方教えてください）。

　一般的なステートマシンで実装される有限状態オートマトンは、現在のステートを基準に次のステートが決定されます。通常は、ＡからＢにステートを遷移させる場合、Ａの処理中に処理対象ステートをＡからＢに差し替えることになるでしょう。

　さて、「Ａ→Ｂ→Ａ→Ｂ→Ｃ」という風にステートを遷移させたい場合は、どのような実装になるでしょうか。Ｂの実装の中で、遷移先がＡなのかＣなのかを判断するために、なんらかのフラグを保持する必要があるのではないでしょうか。これは、ステート自体がステートを管理していることになり、若干本末転倒感があります。

　一般的なやり方は、新しいステートＤを用意し、その中でＡとＢを順に呼び出す方法だと思います。これ自体は上手く行くのですが、ゲームの場合「Ａが終わった時点でいったん処理を返して１フレ進めたい」という状況が超頻発します。その場合、Ｄの内部でマイクロスタック的な管理が必要になり、やはりステート管理が複雑になります。この問題は、コルーチン的なアーキテクチャでは簡潔に対策できないのです。

　プッシュダウンステートマシンでは、スタックで複数のステートを保持することができるので、スタックに「ＡＢＡＢＣ（←ボトム）」という順にステートをpushしておけば、これらを順番に実行してくれます。スタックがステートの遷移順序を保持してくれるので、ステートマシンはそれを実行するだけで良いわけです。

　プッシュダウンステートマシンの利点は、このように階層構造のステートを管理できること、また、各ステートが次の遷移先を把握しなくていいのでステート間の疎結合が促進されることが挙げられます。欠点は、通常の状態遷移機械と比べて処理が重くなることでしょうか（適材適所かと思います）。

コード解説

　短いコードですが、本体のクラスだけ簡単に解説しておきます（コードの全体はリンク先のgistを見てください）。Ｃ＃力が足りないので、もっと効率的＆効果的な実装がありましたら教えていただけると嬉しいです。

    abstract class PushDownStateMachine<StateType>
    {
        protected Stack<StateType> StateStack;

        public PushDownStateMachine()
        {
            StateStack = new Stack<StateType>();
        }

　ステートを格納するスタックの型はジェネリックにして、用途に合わせて生成することにします。

        public void PushState(StateType command)
        {
            StateStack.Push(command);
        }

        public void PushStateList(IEnumerable<StateType> commandList)
        {
            foreach (var command in commandList.Reverse())
            {
                StateStack.Push(command);
            }
        }

　ステートをスタックにプッシュするメソッドです。複数のステートをまとめてスタックする時は逆順にプッシュしなければなりません。これが非常に面倒なのでヘルパーメソッドとしてPushStateList()を用意しています。Reverse()のためにLINQを参照しているのがもったいない。これどうにかなんないかな……。

        public void EvalState()
        {
            while (true)
            {
                if (StateStack.Count == 0) return;

                if (DispatchState(StateStack.Pop())) return;
            }
        }

        protected abstract bool DispatchState(StateType state);
    }

　EvalState()を実行すると、スタックからステートをpopして、DispatchState()を呼び出します。whileは無限ループにしていて、スタックが空になるか、DispatchState()がtrueを返したら処理を終了します。
　DispatchState()がbool値を返す意味について、サンプルコードから一部抜粋して説明します。

    class Program
    {
        static void Main(string[] args)
        {
            var knight = new Knight();

            knight.PushStateList(new List<TacticalMethod>()
            {
                TacticalMethod.Attack,
                TacticalMethod.Guard,
                TacticalMethod.Wait,
                TacticalMethod.DubleAttackAndGurad,
            });

            knight.EvalState();
            Console.WriteLine("====");
            knight.EvalState();
            Console.WriteLine("end");
        }
    }

　KnightクラスはPushDownStateMachineの派生クラスです。EvalState()メソッドが２回実行されているのに注目してください。これを実行すると以下のような結果を返します。

Attack!
Guard!
Wait(Halt)
 ====
Attack!
Attack!
Guard!
end

　"===="は、Unityで言うところの、GameObjectのUpdate()巡回が終わって一度Unity側に処理が戻ったことをイメージしています。このように、ステート処理の途中で処理を戻すためにboolの返値を使います。このギミックを使うと、例えばテキストウィンドウで１フレごとに１文字ずつ表示したい場合などに、先に文字列を全部スタックさせるということができます。

おわり

　あくまでサンプル実装なのでこのまま使うことは難しいかもですが、ステートマシンのバリエーションとして知っておくと、いつか使う機会があるかもしれません（ないかもしれません）。

参考リンク

　ゲームでは、有限状態オートマトンよりも、プッシュダウンオートマトンの方が使う機会が多いのではないかと思っていますが、言及している記事はあまり見たことがありません。

　やねうらおさん（土屋のプログラミング師匠の一人です）の過去の記事では、「有限状態オートマトンは階層構造を表現するのに適していない」と書かれています（ここで書かれているシーン遷移の例を使わせてもらいました）。

第八章．シーン管理クラスの設計２ 2000/11/05
http://bm98.yaneu.com/intensive/ggg/log2.html

　やねうらおさんの著作「Windowsプロフェッショナルゲームプログラミング」の３４５ページにも「FSA(有限オートマトン）は、階層構造を表現するのに適していない」とあります。