元ネタ？はところてんの日記。
昔格闘ゲームもどきを作っていたときにEBA先輩に教えてもらった話なんだけど、（非決定性有限）オートマトンが格闘ゲームのコマンド認識に使えるというお話です。
とりあえず、オートマトンについてはWikipediaでググレ。要するに、「現在の状態」を持っていて、「外から入力を受ける」ことができて、「状態と入力によって新しい状態への遷移や出力を行う」、って感じかな。
有名な「波動拳コマンド」（下・斜め前下・前。右を向いているならば下・右下・右。２３６。）のオートマトン（の状態遷移図）はこんな感じ↓
こんな。
ただし、これはもっとも単純化した例です。もしこれを１フレームごとに処理したとすれば、誰も波動拳を撃つことはできないでしょう。
何故ならば、「下と右が同時に押されている」状態から「右とパンチが押されている状態」へ１フレームで遷移しなくてはならないわけですが、60FPSのゲームであればそれを0.16秒できっちりやらなくてはならないわけです。おそらくほとんどの場合に状態Bから開始へ戻ってしまうことになるでしょう。
というわけで、実際にはもっと細かく制御する必要があります。例えばこんな感じに↓
詳細。
適当に書いたのでこれでも穴がありそうだけど、かなりマシになりました。
何気に状態が１つ増えていて、最後の右とパンチが同時じゃなくてもOKになりました。サムスピだかKOFだかなんだか忘れたけど、「少し歩いてからボタンを押しても技が出る」なんてシステムがありましたが、これで再現できますね。１秒は長いかも知れんけど。
さて、実際の格ゲーでは更に複雑化します。スト２じゃなくて竜虎の拳だったら気力ゲージがないと技が撃てないーーいや、威力が下がるだけだっけ？ーーし、キャラが空中にいるかどうかで技が変わるかもしれませんし、実は同じ十字キー入力をもう一回繰り返すと超必殺技かもしれません。
モノによっては受理の後に判定を入れることで変化を与えられますが、オートマトンそのものの数を増やして優先順位をつけるのが妥当な対策でしょうか。私は「真空波動拳の判定は波動拳の先にやっておき、発動したら波動拳のオートマトンは初期化する」みたいなことをやった記憶があります。
ついでに言ってしまうと、格ゲーであればコマンド入力だけではなくてキャラクターの状態遷移にも応用できます。っていうか、思いっきり状態遷移と言ってるわけで、状態遷移図を書けば幸せになれるよ！
全体。
ジャンプとか入れてないのにこの汚さというのはちょっとよろしくないけど、まあこんなもんです。
非決定性の意味がない件。
実際には決定性有限オートマトンがたくさんあって、イベントに反応して遷移開始しているわけです。んで並列に処理しまくった上で、あるタイミングで他のオートマトンを一斉に初期化するとかいうある意味キモイ？イベントが起きるわけだ。例えば波動拳が受理されたら真空波動拳が破棄されたみたいな。協調処理とするオートマトンみたいな？なんか微妙にエージェントっぽいな。
詳細。
こんなん。