状態遷移表とハッシュテーブルを用いたいぶし銀な状態遷移

状態遷移を表す時に良く使われるのが「状態遷移図」です。こんな図、よく見ますよね：

状態遷移を表現するのは何もこれだけではありません。次のような「状態遷移表」というのもあります：

これは行が「状態」そして列が発生しうるイベントで、表内の数字は「遷移先のindex」を表しています。例えば今状態Aだとします。何もイベントが無い場合は今の状態を継続します。そしてイベント2が起きた時、そのイベントに対応する状態C(index=2)に移ります。後はこの繰り返し。これで状態遷移を表現しています。

状態遷移図と状態遷移表はお互いに変換できます。表現の方法が違うだけという事ですね。ただ、状態遷移表は遷移をデータ化しやすい利点があります。
今回はこの状態遷移表を活かした状態遷移を実装してみましょう。

イベント取得関数をまず設ける

状態遷移表の各行は起こりうるイベントです。まずはこのイベントを取得出来る関数を設けておきます。

EventID getEvent();   // イベント番号を取得

この関数は状態を監視する人が毎フレーム拾い、状態遷移の種にします。

状態関数をテーブル化

次に表の行に該当する状態関数を配列に登録します。funcTable[FuncID]でアクセスします。この要素番号が状態遷移表の中の番号になります：

bool stateA();
bool stateB();
bool stateC();
bool stateD();
 
bool (*funcTable[]) = {
    stateA, stateB, stateC, stateD
};

遷移表の遷移先番号をテーブル化

続いて状態遷移表をまるっと2次元配列にしてハッシュテーブル化します。hashTable[FuncID][EventID]としましょうか。EventIDはイベント番号で、FuncIDは状態関数テーブルのそれです：

const int FuncNum = 4;
const int EventNum = 4;
int hashTable[FuncNum][EventNum] = {
    { 0, 0, 2, 0 },   // 状態A
    { 1, 0, 1, 1 },   // 状態B
    { 2, 2, 3, 3 },   // 状態C
    { 0, 3, 1, 3 }    // 状態D
};

これで準備が整いました。後は至極簡単です。

テーブルを駆使して状態遷移！

イベント関数、状態関数テーブルそして状態遷移ハッシュテーブルが揃えば、次のようにして状態遷移をする機構を作る事ができます：

int curFuncId = 0;

int main() {
    while( true ) {
        bool IsTrans = funcTable[ curFuncId ]();    // 現在の状態を更新
        // 状態遷移を受け付ける時だけイベント取得
        if ( isTrans )
            curFuncId = hashTable[ curFuncId ][ getEvent() ];  // 遷移先決定
    }
}

毎フレームグルグル回して現在の状態関数（funcTable[ curFncId ]）を更新しています。状態関数が遷移しても大丈夫（IsTrans==true）な状態の時にイベントをチェックします。もし遷移対象なイベントが発生していたら、curFuncIdはハッシュテーブルにより自動的にその遷移先indexになっているので、次のフレームからは新しい状態に切り替わる。
ハッシュテーブルのお陰で判断する必要が無いので、すんごくシンプルな構造で状態遷移できます(^-^)

プログラムを変えずに状態遷移を変えられる！

この方式の大きな利点として、元のプログラムを変えずに状態遷移を変えられるというのがあります。なぜかと言うと状態遷移を判断しているのがハッシュテーブル、つまり「データ」だからです。このデータ部分を一部もしくは全部をごそっと取り換えてしまえば、同じ関数を使った別の遷移が直ちに出来上がります。

既に動いているプログラムを差し替えるのは容易な事ではありませんが、データ（メモリ）を書き換えるのははるかに簡単です。さらに言うと関数テーブルもデータと言えばデータなので、ここも差し替える事は可能です。今回の例のように関数ポインタの配列ではなく、状態遷移に使う関数にすべて番号を振って、関数ポインタの替わりに番号を関数テーブル（関数ハッシュテーブル）としてしまえば良いですよね。

このように状態遷移表からハッシュテーブルを作るこの方法は静的にも動的にも状態遷移を起こせる魅力があります。

人の手で作らない方が良いかも

この方法の大きなデメリットとしては、人が理解するに難しいというのがあります。ハッシュテーブルが巨大化してくると、数字祭りになって人の目では設定ミスがわからなくなってきます。プログラムを走らせて何か暴走しだした。一体どこだ？…わからーーん！っとなりやすいんです。まぁ今はステップ実行で追えるので間違い部分を追及できますが。

なので、人の目で理解しやすい状態遷移図から状態遷移表にコンバートし、それをハッシュテーブル化する所までを自動化すると良いかもしれません。状態遷移図を書くツールは色々あるでしょうし、XMLなどに連結状態を出力してくれる機能も大概あります。XMLを解析すれば状態遷移表は比較的簡単に作れます。表が出来ればハッシュ化は一瞬です。その最終的なハッシュデータをプログラムに読み込ませるんです。

遷移図からのコンバートはきついなぁ、という事であればExcelで状態遷移表を「人が理解しやすい形式」で作り、それをハッシュ化するという手も取れます。Excelの自由度は魔ですからw、こっちの方が潰しがききますしお手軽です。

イベントが巨大ならDictionaryに切り替えた方が良いかも

この方法はスケールが利くので、イベント数も対応する状態遷移の数も増やせます。ただ、増やせば増やすほど双方の掛け算分のハッシュ容量が必要になります。イベントが100、状態が50あるなら5000個の値を埋めなくてはいけないという事です。

「メモリ容量が…」という話ではありません。今メモリはGBな世界ですから5000個のデータ（20KBくらい）など湖に浮かぶ小舟くらいの占有率でしかありません。問題は「管理」です。普通1つの状態の先にある次の状態の数は多くて2～3個程度です。状態が50あるとしても矢印の数は200個くらいでしょう。ですから全5000個の遷移先値の内4800個くらいは遷移に関与しない値になります。200個の遷移を設定したいがために4800個の無駄な所まで作るのは、それこそ無駄ですし、ほぼ確実にヒューマンエラーが起こります。そして、そのミスった所がどこなのかを判読するのは多分至難の業です。

こういう規模になったらもう総当たりなハッシュテーブルでは管理が難しくなるので、Dictionary（C++ではstd::map）によるハッシュテーブルに切り替えた方が無難です。ハッシュ効率はちょっとだけ落ちますが、管理効率は維持できます。

状態遷移表を利用した状態遷移はデータ駆動的で魅力的ですが、人為ミスしやすいもろ刃の武器でもあります。昨今はプログラムリソースが潤沢になってきたので「人がミスを犯しにくい、メンテナンスしやすいなら、パフォーマンスやリソースを犠牲にしてもそちらへ」という流れはあります。なので、この方式をまともに使う事は少ないかもしれませんが、武器が大いに越した事はありません。適切な所で上手に活用できる柔軟さを持ちましょう(^-^)