FSMの実装方法とより良い使い方

こんにちは。プログラマーの尾関です。

今回は、プログラムの基本的アルゴリズムであるFSMについて紹介をします。

■ FSMとは
FSMとは、有限状態機械(Finite State Machine)の頭文字を取ったもので、ゲームでは非常によく使われます。

  • ゲームの進行管理
  • キャラクターの振る舞い
  • AI

などなど。むしろ使わずにゲームを作るのが難しいのではないかと思うくらいです。

■FSMを使わない場合
まずは、あえてFSMを使わずに作るとどれだけ大変なのかを確認してみます。
具体的な例として、アクションゲームのキャラクターの制御を作ってみます。

これでジャンプは作れたように思えますが、実際には空中でもジャンプできてしまうため、それを防ぐコードを加えます。

次に、「下キー」でしゃがむようにします。

続けて、しゃがみジャンプを禁止します。

最後に、空中で下キーを押すと、跳び蹴りをするようにします。

これで実装できたように思えますが、いくつかの問題を抱えています。

  • 跳び蹴り中にジャンプができてしまう
  • 跳び蹴り中に跳び蹴りができてしまう

これらの問題を解決するには、適切な場所に適切な条件式とフラグを設定する必要があるのですが、コードの流れが追いにくく、読みにくいコードとなってしまいます。
なぜ、この書き方は良くないのかというと、「ジャンプ中」「しゃがみ中」などをフラグで管理しているためです。

■フラグ制御は煩雑になりやすい
フラグ制御は単純なシステム、または各フラグの用途が明確であれば管理しやすいです。しかしゲームキャラクタの制御は、フラグを使うと相互に監視する必要があり、かえって複雑になってしまいます。

また、フラグは数が増えるほど、考慮すべき処理が増えます(考慮すべき処理の数=2^フラグの数)

(※表からはすべてOFFの場合は省略しています)

  • フラグの数=2 であれば、2^2=4
  • フラグの数=3 だと、2^3=8
  • フラグの数=4 になると、2^4=16

またいくつかの組み合わせは成立しないことも多いのですが、可能性としては考えられるため余計なことに頭を悩ませることになります。
FSMを使うと、考えられる可能性を少なくすることができます。

■FSMで状態遷移を実装する

FSMで状態遷移を実装した例が、以下の図となります。

「しゃがんでいる」「立っている」「ジャンプしている」「跳び蹴りしている」という4つの状態を定義し、遷移条件を満たしたら別の状態へ遷移します。
なお、FSMはオートマトン理論が元になっています。

  1. 機械はとりうる状態の集合で構成される
  2. 機械は一度に「1つの状態」にしかなり得ない
  3. 一連の入力もしくはイベントが機械には与えられる
  4. 各状態は遷移の集合を持ち、各遷移は入力と結びついて、遷移先の状態を指している

FSMを実装する方法ですが、おおよそ以下のものが考えられます。

  • switch文で分岐する
  • 関数テーブルで分岐する
  • Stateパターンを使う

▼switch文を使ったFSMの実装

switch文を使ったFSMの実装は、まず、列挙型でFSMの状態を定義します。

次に、switch文で状態変数「State」を使った分岐を行います。

この実装のメリットは、上から順に読めるコードになっているところです。
またある状態から別の状態への遷移が一目でわかります。
デメリットは、状態が増えたときにswitch文が長くなってしまうことです。
ただ、この欠点は関数テーブルを使うことで、ある程度軽減できます。

▼関数テーブルを使ったFSMの実装
ということで、関数テーブルを使ったFSMの実装です。
それぞれのcase文で記述していた部分を関数として分離します。
また遷移先を戻り値として返します。

そして、各関数をテーブルに登録すると、switch文で記述する必要がなくなります。

▼Stateパターンによる実装
デザインパターンの1つであるStateパターンによる実装です。

状態を1つのオブジェクトとして扱います。

関数テーブルの例では、状態変数を返していましたが、Stateパターンでは、状態のインスタンスを返します。
これだけだと、記述が複雑になっただけに見えますが、その状態でのみ使用する変数や処理をカプセル化できるのがメリットです。

あと、毎回 new をするのはメモリが荒れる原因となるので、できればActorStateオブジェクトをあらかじめ全部作っておいた方が良いでしょう。

▼入り口関数を使って処理をすっきりさせる
ここからはFSMをより使いやすくするオマケ的な実装例です。
ある状態から別の状態へ遷移したとき、その瞬間だけ何か処理をさせたいことが良くあります。
例えば、立ち状態からしゃがみ状態になったら、しゃがみ状態のアニメーションに変更する、などです。

状態が切り替わったら、状態管理側で、Enter()を呼ぶようにすると入り口処理が行われるようになります。

ちなみに入り口関数は、Stateパターンでなくても似たものが作れます。
以下は、関数テーブルの例です。

正確には入り口関数ではなく、入り口フラグ (bStateEnter) を判定して入り口処理を行う、という実装です。

▼遷移条件をテーブル化する
状態遷移がかなり複雑な場合、遷移条件をテーブル化するのも有効です。

このようなテーブルを定義し、「現在の状態が遷移元に一致」かつ「遷移条件を満たす」場合、遷移先に状態遷移します。
これを作ると、遷移条件を追加するのが簡単になります。
ただ、ターン制のRPGなどのように、複雑な状態遷移をたどるのでなければ、大げさな作りかもしれません。

仕事でなく趣味で作ったローグライクでは、ゲームの状態遷移に遷移条件テーブルを使用してかなり楽に実装ができました。

■2つ以上の状態を組み合わせたい場合
例えば、上半身と下半身の動きを分ける場合です。上半身は銃で弾を撃ちながら、下半身はジャンプしたりしゃがんだりする場合です。これを無理に1つの状態にまとめると、

  • ジャンプ状態
  • ジャンプしながら弾を撃つ状態
  • しゃがみ状態
  • しゃがみながら弾を撃つ状態

というように、組み合わせの数だけ状態が増えていきます。こうするよりは、上半身の状態変数、下半身の状態変数、というように2つの変数を用意した方がすっきり書けるはずです。

■まとめ

ひととおりFSMについて紹介しました。

  1. switch文で分岐する実装
  2. 関数テーブルで分岐する実装
  3. Stateパターンを使う

複雑な状態遷移でなければ、「1. switch文での実装」が一番簡単で読みやすいコードとなります。
そして、switch文が長くなるのであれば「2. 関数テーブルによる実装」ですっきりさせることができます。
「3. Stateパターンによる実装」は、もっと複雑で巨大な状態遷移をする場合に使うのが良いと思います。

なんでもかんでもStateパターンで実装するのではなく、求められている規模に応じたアルゴリズムを適用する方が読みやすいコードになるのでは、と個人的には考えています。

以上、FSMについてでした。

Tweet about this on TwitterShare on Facebook0Share on Google+0

コメント投稿は締め切りました。