こんにちは。プログラマーの尾関です。
今回は、プログラムの基本的アルゴリズムであるFSMについて紹介をします。
■ FSMとは
FSMとは、有限状態機械(Finite State Machine)の頭文字を取ったもので、ゲームでは非常によく使われます。
- ゲームの進行管理
- キャラクターの振る舞い
- AI
などなど。むしろ使わずにゲームを作るのが難しいのではないかと思うくらいです。
■FSMを使わない場合
まずは、あえてFSMを使わずに作るとどれだけ大変なのかを確認してみます。
具体的な例として、アクションゲームのキャラクターの制御を作ってみます。
|
1 2 3 4 5 6 |
// キャラクターの更新 void Update(Actor* ix) { if(IsPadPress(PAD_B)) { // ジャンプ } } |
これでジャンプは作れたように思えますが、実際には空中でもジャンプできてしまうため、それを防ぐコードを加えます。
|
1 2 3 4 5 6 7 8 |
void Update(Actor* ix) { if(IsPadPress(PAD_B)) { if(ix->bJumping == false) { // ジャンプしていなければジャンプする ix->bJumping = TRUE; // ジャンプ中 } } } |
次に、「下キー」でしゃがむようにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void Update(Actor* ix) { if(IsPadPress(PAD_B)) { if(ix->bJumping == false) { // ジャンプしていなければジャンプする ix->bJumping = TRUE; // ジャンプ中 } } else if(IsPadOn(PAD_DOWN)) { if(ix->bJumping == false) { // ジャンプしていなければしゃがむ ix->bDucking = true; // しゃがんでいる } } else if(IsPadRelease(PAD_DOWN)) { // しゃがんでいたら立ち上がる ix->bDucking = false; // 立ち上がる } } |
続けて、しゃがみジャンプを禁止します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void Update(Actor* ix) { if(IsPadPress(PAD_B)) { if(ix->bJumping == false && ix->bJumping == false) { // ←※ここに条件を追加しています // ジャンプしていなければジャンプする ix->bJumping = TRUE; // ジャンプ中 } } else if(IsPadOn(PAD_DOWN)) { if(ix->bJumping == false) { // ジャンプしていなければしゃがむ ix->bDucking = true; // しゃがんでいる } } else if(IsPadRelease(PAD_DOWN)) { // しゃがんでいたら立ち上がる ix->bDucking = false; // 立ち上がる } } |
最後に、空中で下キーを押すと、跳び蹴りをするようにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void Update(Actor* ix) { if(IsPadPress(PAD_B)) { if(ix->bJumping == false && ix->bJumping == false) { // ←※ここに条件を追加しています // ジャンプしていなければジャンプする ix->bJumping = TRUE; // ジャンプ中 } } else if(IsPadOn(PAD_DOWN)) { if(ix->bJumping == false) { // ジャンプしていなければしゃがむ ix->bDucking = true; // しゃがんでいる } else { // 跳び蹴りをする ←※ここを実装する } } else if(IsPadRelease(PAD_DOWN)) { // しゃがんでいたら立ち上がる ix->bDucking = false; // 立ち上がる } } |
これで実装できたように思えますが、いくつかの問題を抱えています。
- 跳び蹴り中にジャンプができてしまう
- 跳び蹴り中に跳び蹴りができてしまう
これらの問題を解決するには、適切な場所に適切な条件式とフラグを設定する必要があるのですが、コードの流れが追いにくく、読みにくいコードとなってしまいます。
なぜ、この書き方は良くないのかというと、「ジャンプ中」「しゃがみ中」などをフラグで管理しているためです。
■フラグ制御は煩雑になりやすい
フラグ制御は単純なシステム、または各フラグの用途が明確であれば管理しやすいです。しかしゲームキャラクタの制御は、フラグを使うと相互に監視する必要があり、かえって複雑になってしまいます。
また、フラグは数が増えるほど、考慮すべき処理が増えます（考慮すべき処理の数＝2^フラグの数)
(※表からはすべてOFFの場合は省略しています)
- フラグの数＝2 であれば、2^2=4
- フラグの数＝3 だと、2^3=8
- フラグの数＝4 になると、2^4=16
またいくつかの組み合わせは成立しないことも多いのですが、可能性としては考えられるため余計なことに頭を悩ませることになります。
FSMを使うと、考えられる可能性を少なくすることができます。
■FSMで状態遷移を実装する
FSMで状態遷移を実装した例が、以下の図となります。
「しゃがんでいる」「立っている」「ジャンプしている」「跳び蹴りしている」という4つの状態を定義し、遷移条件を満たしたら別の状態へ遷移します。
なお、FSMはオートマトン理論が元になっています。
- 機械はとりうる状態の集合で構成される
- 機械は一度に「1つの状態」にしかなり得ない
- 一連の入力もしくはイベントが機械には与えられる
- 各状態は遷移の集合を持ち、各遷移は入力と結びついて、遷移先の状態を指している
FSMを実装する方法ですが、おおよそ以下のものが考えられます。
- switch文で分岐する
- 関数テーブルで分岐する
- Stateパターンを使う
▼switch文を使ったFSMの実装
switch文を使ったFSMの実装は、まず、列挙型でFSMの状態を定義します。
|
1 2 3 4 5 6 7 8 |
enum eState { eState_Standing, // 立っている eState_Jumping, // ジャンプ中 eState_Ducking, // しゃがんでいる eState_Diving, // 跳び蹴り eState_Max, }; |
次に、switch文で状態変数「State」を使った分岐を行います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
void Update() { switch(_state) { case eState_Standing: // 立っている if(IsPadPress(PAD_B)) { ix->State = eState_Jumping; // ジャンプする } else if(IsPadPress(PAD_DOWN)) { ix->State = eState_Duking; // しゃがむ } break; case eState_Jumping: // ジャンプ中 if(IsPadPress(PAD_DOWN)) { ix->State = eState_Diving; // 跳び蹴り } else if(接地した) { ix->State = eState_Standing; } break; case eState_Ducking: // しゃがんでいる if(IsPadRelease(PAD_DOWN)) { ix->State = eState_Standing; // 立ち上がる } break; case eState_Diving: // 跳び蹴り if(接地した) { ix->State = eState_Standing; } break; } } |
この実装のメリットは、上から順に読めるコードになっているところです。
またある状態から別の状態への遷移が一目でわかります。
デメリットは、状態が増えたときにswitch文が長くなってしまうことです。
ただ、この欠点は関数テーブルを使うことで、ある程度軽減できます。
▼関数テーブルを使ったFSMの実装
ということで、関数テーブルを使ったFSMの実装です。
それぞれのcase文で記述していた部分を関数として分離します。
また遷移先を戻り値として返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// 立っているときの処理 eState _UpdateStanding(Actor* ix) { if(IsPadPress(PAD_B)) { return eState_Jumping; // ジャンプする } else if(IsPadPress(PAD_DOWN)) { return eState_Duking; // しゃがむ } // 遷移しない return ix->State; } |
そして、各関数をテーブルに登録すると、switch文で記述する必要がなくなります。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
void Update() { // 関数テーブル定義 typedef eStep(*FP_STEP)(Actor* ix); FP_STEP StepFuncTbl[eState_Max] = { _UpdateStanding, // eState_Standing, // 立っている _UpdateJumping, // eState_Jumping, // ジャンプ中 _UpdateDucking, // eState_Ducking, // しゃがんでいる _UpdateDiving, // eState_Diving, // 跳び蹴り }; ix->State = StepFuncTbl[ix->State](ix); } |
▼Stateパターンによる実装
デザインパターンの1つであるStateパターンによる実装です。
状態を1つのオブジェクトとして扱います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// 状態遷移クラス class ActorState { virtual ActorState* Update(Actor* ix) { return NULL; } }; これを継承した立ち状態クラスの実装例です。 // 立ち状態 class StandingState : public ActorState { virtual ActorState* Update(Actor* ix) { if(IsPadPress(PAD_B)) { // ジャンプ状態へ遷移 return new JumpingState(); } else if(IsPadPress(PAD_DOWN)) { // しゃがみ状態へ遷移 return new DuckingState(); } return this; } }; |
関数テーブルの例では、状態変数を返していましたが、Stateパターンでは、状態のインスタンスを返します。
これだけだと、記述が複雑になっただけに見えますが、その状態でのみ使用する変数や処理をカプセル化できるのがメリットです。
あと、毎回 new をするのはメモリが荒れる原因となるので、できればActorStateオブジェクトをあらかじめ全部作っておいた方が良いでしょう。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Actor { // 状態 enum eState { eState_Standing, // 立っている eState_Jumping, // ジャンプ中 eState_Ducking, // しゃがんでいる eState_Diving, // 跳び蹴り eState_Max, }; // コンストラクタ Actor() { m_StatePool.push_back(new StandingState()); // eState_Standing m_StatePool.push_back(new JumpingState()); // eState_Jumping m_StatePool.push_back(new DuckingState()); // eState_Ducking m_StatePool.push_back(new DivingState()); // eState_Diving } // 状態のインスタンスを取得する ActorState* GetActorState(eState State) { return m_StatePool[State]; } }; |
▼入り口関数を使って処理をすっきりさせる
ここからはFSMをより使いやすくするオマケ的な実装例です。
ある状態から別の状態へ遷移したとき、その瞬間だけ何か処理をさせたいことが良くあります。
例えば、立ち状態からしゃがみ状態になったら、しゃがみ状態のアニメーションに変更する、などです。
|
1 2 3 4 5 |
// 状態遷移クラス class ActorState { virtual ActorState* Update(Actor* ix) { return NULL; } virtual void Enter(Actor* ix) {} // 入り口関数 }; |
状態が切り替わったら、状態管理側で、Enter()を呼ぶようにすると入り口処理が行われるようになります。
|
1 2 3 4 5 6 7 8 9 |
void Actor::Update() { ActorState* pNext = m_pState->Update(this); if(pNext != m_pState) { // 入り口関数呼び出し pNext->Enter(this); // 状態遷移 m_pState = pNext; } } |
ちなみに入り口関数は、Stateパターンでなくても似たものが作れます。
以下は、関数テーブルの例です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// 立っているときの処理 eState _UpdateStanding(Actor* ix) { if(ix->bStateEnter) { // 状態遷移直後のみ実行される処理 } if(IsPadPress(PAD_B)) { return eState_Jumping; // ジャンプする } else if(IsPadPress(PAD_DOWN)) { return eState_Duking; // しゃがむ } // 遷移しない return ix->State; } void Update() { // 関数テーブル定義 typedef eStep(*FP_STEP)(Actor* ix); FP_STEP StepFuncTbl[eState_Max] = { _UpdateStanding, // eState_Standing, // 立っている _UpdateJumping, // eState_Jumping, // ジャンプ中 _UpdateDucking, // eState_Ducking, // しゃがんでいる _UpdateDiving, // eState_Diving, // 跳び蹴り }; eState Next = StepFuncTbl[ix->State](ix); ix->bStateEnter = false; // 入り口処理を有効 if(ix->State != Next) { // 次の状態に遷移する ix->State = Next; ix->bStateEnter = true; // 入り口処理を有効 } } |
正確には入り口関数ではなく、入り口フラグ (bStateEnter) を判定して入り口処理を行う、という実装です。
▼遷移条件をテーブル化する
状態遷移がかなり複雑な場合、遷移条件をテーブル化するのも有効です。
|
1 2 3 4 5 6 7 8 9 |
m_ConditionTbl[] = { // 遷移元, 遷移先, 遷移条件 {eState_Standing, eState_Jumping, IsPressJumpButton }, {eState_Standing, eState_Ducking, IsPressDownButton }, {eState_Jumping, eState_Diving, IsPressDownButton }, {eState_Jumping, eState_Standing, IsLanding }, {eState_Ducking, eState_Standing, IsReleaseDownButton }, {eState_Diving, eState_Standing, IsLanding }, }; |
このようなテーブルを定義し、「現在の状態が遷移元に一致」かつ「遷移条件を満たす」場合、遷移先に状態遷移します。
これを作ると、遷移条件を追加するのが簡単になります。
ただ、ターン制のRPGなどのように、複雑な状態遷移をたどるのでなければ、大げさな作りかもしれません。
仕事でなく趣味で作ったローグライクでは、ゲームの状態遷移に遷移条件テーブルを使用してかなり楽に実装ができました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// 状態遷移テーブル _fsm.transitions // ■開始 .add(Boot, Dg, Conditions.isEndWait) // 開始 -> ダンジョン // ■ダンジョン .add(Dg, DgSearch, Conditions.isSearch) // ダンジョン -> 探索 .add(Dg, DgRest, Conditions.isRest) // ダンジョン -> 休憩 .add(Dg, DgDrop, Conditions.isItemDel) // ダンジョン -> アイテム捨てる .add(Dg, DgUpgrade, Conditions.isUpgrade) // ダンジョン -> 強化 .add(Dg, DgNextFloor, Conditions.isNextFloor) // ダンジョン -> 次のフロアに進む .add(Dg, DgShop, Conditions.isShop) // ダンジョン -> ショップ // ダンジョン - 探索 .add(DgSearch, PlayerDead, Conditions.isDead) // 探索中... -> プレイヤー死亡 .add(DgSearch, DgSearch2, Conditions.isEndWait) // 探索中... -> 探索実行 .add(DgSearch2, BtlBoot, Conditions.isAppearEnemy) // 探索中... -> 敵に遭遇 .add(DgSearch2, DgGain, Conditions.isItemGain) // 探索中... -> アイテム獲得 .add(DgSearch2, DgBossNotice,Conditions.isBossNotice)// 探索中... -> ボス出現警告 .add(DgSearch2, DgShopFind, Conditions.isShopFind) // 探索中... -> ショップを見つけた .add(DgSearch2, DgUpgradeFind, Conditions.isUpgradeFind) // 探索中...-> 強化を見つけた .add(DgSearch2, DgSearch, Conditions.isEventNone) // 探索中... -> 再び探索 .add(DgSearch2, Dg, Conditions.isEndWait) // 探索中... -> ダンジョンに戻る // ダンジョン - 探索 - アイテム獲得 .add(DgGain, DgItemFull, Conditions.isItemFull) // アイテム獲得 -> アイテム一杯 .add(DgGain, Dg, Conditions.isEndWait) // アイテム獲得 -> ダンジョンに戻る // ダンジョン - 探索 - アイテム一杯 .add(DgItemFull, Dg, Conditions.isEndWait) // アイテム一杯 -> ダンジョンに戻る // ダンジョン - 探索 - ボス出現警告 .add(DgBossNotice, Dg, Conditions.isEndWait) // ボス出現警告 -> ダンジョンに戻る // ダンジョン - 探索 - ショップ発見 .add(DgShopFind, DgShop, Conditions.isEndWait) // ショップ発見 -> ショップ // ダンジョン - 探索 - 強化発見 .add(DgUpgradeFind, DgUpgrade, Conditions.isEndWait) // 強化発見 -> 強化 // ダンジョン - 休憩 .add(DgRest, Dg, Conditions.isEndWait) // 休憩 -> ダンジョン // ダンジョン - 強化 .add(DgUpgrade, Dg, Conditions.isEndWait) // 強化 -> ダンジョン // ダンジョン - アイテム捨てる .add(DgDrop, Dg, Conditions.isEndWait) // アイテム破棄 -> ダンジョン // ダンジョン - ショップ .add(DgShop, Dg, Conditions.isEndWait); // ショップ -> ダンジョン |
■2つ以上の状態を組み合わせたい場合
例えば、上半身と下半身の動きを分ける場合です。上半身は銃で弾を撃ちながら、下半身はジャンプしたりしゃがんだりする場合です。これを無理に1つの状態にまとめると、
- ジャンプ状態
- ジャンプしながら弾を撃つ状態
- しゃがみ状態
- しゃがみながら弾を撃つ状態
というように、組み合わせの数だけ状態が増えていきます。こうするよりは、上半身の状態変数、下半身の状態変数、というように2つの変数を用意した方がすっきり書けるはずです。
■まとめ
ひととおりFSMについて紹介しました。
- switch文で分岐する実装
- 関数テーブルで分岐する実装
- Stateパターンを使う
複雑な状態遷移でなければ、「1. switch文での実装」が一番簡単で読みやすいコードとなります。
そして、switch文が長くなるのであれば「2. 関数テーブルによる実装」ですっきりさせることができます。
「3. Stateパターンによる実装」は、もっと複雑で巨大な状態遷移をする場合に使うのが良いと思います。
なんでもかんでもStateパターンで実装するのではなく、求められている規模に応じたアルゴリズムを適用する方が読みやすいコードになるのでは、と個人的には考えています。
以上、FSMについてでした。