文章目录
- 有限状态机
- 状态机的表示
- 状态转移图
- 二维表
- 实现
- 穷举法
- 查表法
- 状态模式
- 总结
有限状态机
有限状态机(Finite State Machine) 缩写为 FSM。以下简称为状态机。
状态机有 3 个组成部分：状态、事件、动作。
- 状态：所有可能存在的状态。包括当前状态和条件满足后要迁移的状态。
- 事件：也称为转移条件，当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。
- 动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是* 必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。
状态机的表示
状态转移图
我们举个例子，马里奥共有三种状态，可执行三个动作，如图中所示。
从图中可以看到，
- 在Small Mario状态下，A3，没有触发状态转移，也没有触发任何动作。
- 在Fire Mario状态下，A3，没有触发状态转移，触发了发射火球动作。
- 在Super Mario状态下，A2，触发状态转移到Small Mario，没有触发任何动作。
- 在Small Mario状态下，A1，触发状态转移到Super Mario，触发增加1000积分。
可见：动作的执行，和状态的转移，是相对独立的。并不是必须有状态转移，或必须触发动作。状态转移和动作之间也没有必然联系。
二维表
第一维表示当前状态，第二维表示事件，表格内容表示当前状态经过事件之后，转移到的新状态 或 要执行的动作，理论上状态转移和执行的动作可以是两个独立的表格。
合并后的：
| 吃蘑菇 | 碰到怪物 | 攻击 | |
|---|---|---|---|
| Small Mario | Super Mario/+1000 | Dead/- | -/- |
| Super Mario | Fire Mario/+1000 | Small Mario/- | -/- |
| Fire Mario | -/+1000 | Small Mario/- | -/发射火球 |
| Dead Mario | -/- | -/- | -/- |
状态转移表：
| 吃蘑菇 | 碰到怪物 | 攻击 | |
|---|---|---|---|
| Small Mario | Super Mario | Dead | - |
| Super Mario | Fire Mario | Small Mario | - |
| Fire Mario | - | Small Mario | - |
| Dead Mario | - | - | - |
动作表：
| 吃蘑菇 | 碰到怪物 | 攻击 | |
|---|---|---|---|
| Small Mario | +1000 | - | - |
| Super Mario | +1000 | - | - |
| Fire Mario | +1000 | - | 发射火球 |
| Dead Mario | - | - | - |
实现
定义State枚举，定义四种状态。
定义三个函数，对应三个事件。我们首先给出简单的测试程序。三个函数有待实现。
typedef enum State{DEAD = 0,SMALL,SUPER,FIRE
}State;class Mario{
private:State state; //状态int score; //积分
public:Mario():state(SMALL), score(0){}//吃蘑菇void eatMushRooms(){//todo something} //碰到怪物void contactMonsters(){//todo something} //攻击void attack(){//todo something}
};int main(int argc, char *argv[]){Mario m;m.eatMushRooms();//吃蘑菇m.eatMushRooms();//吃蘑菇m.eatMushRooms();//吃蘑菇m.attack();//发射火球m.contactMonsters();//变小m.attack();//nothingm.contactMonsters();//diedreturn 0;
}穷举法
参照状态转移图，代码直译的方式，用if-else或switch-case，简单堆砌完成。穷举所有状态下发声任何事件的所有可能。
class Mario{
private:State state; //状态int score; //积分void printState(){switch(state){case DEAD:cout << "died!" << endl;break;case SMALL:cout << "small!" << endl;break;case SUPER:cout << "super!" << endl;break;case FIRE:cout << "fire!" << endl;break;default:break;}cout << "score is " << score << endl;}public:Mario():state(SMALL), score(0){}//吃蘑菇void eatMushRooms(){cout << "eatMushRooms begin:" << endl;switch(state){case DEAD:break;case SMALL:state = SUPER;score += 1000;printState();break;case SUPER:state = FIRE;score += 1000;printState();break;case FIRE:score += 1000;printState();break;default:break;}cout << endl;}//碰到怪物void contactMonsters(){cout << "contactMonsters begin:" << endl;switch(state){case DEAD:break;case SMALL:state = DEAD;printState();break;case SUPER:state = SMALL;printState();break;case FIRE:state = SMALL;printState();break;default:break;}cout << endl;}//攻击void attack(){cout << "attack begin:" << endl;switch(state){case DEAD:cout << "do nothing!" << endl;break;case SMALL:cout << "do nothing!" << endl;break;case SUPER:cout << "do nothing!" << endl;break;case FIRE:cout << "shoot firebool!" << endl;break;default:break;}cout << endl;}
};eatMushRooms begin:
super!
score is 1000eatMushRooms begin:
fire!
score is 2000eatMushRooms begin:
fire!
score is 3000attack begin:
shoot firebool!contactMonsters begin:
small!
score is 3000attack begin:
do nothing!contactMonsters begin:
died!
score is 3000
对于简单的分支逻辑，这种方式是可以接受的。对于复杂的状态机来说，容易漏写或者错写状态转移。
目前四种状态，三种事件，代码中就已经充斥着大量的case语句。粗略估计要处理的分支数量大概是3*4。如果是10种状态，10种事件呢，就需要有100个分支需要处理，可读性和可维护性就会变得很差，修改也更容易出错。
查表法
结合二维表表示，查表法的代码更加清晰，可读性和可维护性更好。当修改状态机时，我们只需要修改 状态转移表 和 动作表 即可。
而且我们把这两个二维数组存储在配置文件中，当需要修改状态机时，我们甚至可以不修改任何代码，只需要修改配置文件就可以了。
需要注意的是，C++中，我们使用状态枚举编号和动作编号来定位数组对应的值。
State transitionTable[4][3] = {/*A1 A2 A3*/{DEAD, DEAD, DEAD}, //DEAD{SUPER, DEAD, SMALL}, //SMALL{FIRE, SMALL, SUPER}, //SUPER{FIRE, SMALL, FIRE} //FIRE
};int actionTable[4][3] = {/*A1 A2 A3*/{0, 0, 0}, //DEAD{1000, 0, 0}, //SMALL{1000, 0, 0}, //SUPER{1000, 0, 0} //FIRE
};bool actionFireboolTable[4][3] = {/*A1 A2 A3*/{false, false, false}, //DEAD{false, false, false}, //SMALL{false, false, false}, //SUPER{false, false, true}, //FIRE
};class Mario{
private:State state; //状态int score; //积分void printState(){switch(state){case DEAD:cout << "died!" << endl;break;case SMALL:cout << "small!" << endl;break;case SUPER:cout << "super!" << endl;break;case FIRE:cout << "fire!" << endl;break;default:break;}cout << "score is " << score << endl;cout << endl;}void action(int index){if(index == 2){if(actionFireboolTable[state][index]){cout << "shoot firebool!" << endl;}else{cout << "do nothing!" << endl;}}score += actionTable[state][index];}public:Mario():state(SMALL), score(0){} //吃蘑菇void eatMushRooms(){cout << "eatMushRooms begin:" << endl;action(0);state = transitionTable[state][0];printState();} //碰到怪物void contactMonsters(){cout << "contactMonsters begin:" << endl;action(1);state = transitionTable[state][1];printState();} //攻击 void attack(){cout << "attack begin:" << endl;action(2);state = transitionTable[state][2];printState();}
};
eatMushRooms begin:
super!
score is 1000eatMushRooms begin:
fire!
score is 2000eatMushRooms begin:
fire!
score is 3000attack begin:
shoot firebool!
fire!
score is 3000contactMonsters begin:
small!
score is 3000attack begin:
do nothing!
small!
score is 3000contactMonsters begin:
died!
score is 3000查表法明显在函数实现部分比较简洁。数组表格和状态、动作的对应顺序，需要对照二维表完成。如本例中，如果是简单的积分加减，不需要引入actionFireboolTable，代码就会更加简洁。对于更复杂的动作，我们可能要引入更多地表格和判断。这里就是查表法的局限，查表法仅能处理简单的 动作表。
当各个动作需要执行很多差异化很明显的代码(代码间难有共性，无法提炼)时。表格法的 动作表或者动作部分 就会变得复杂。
状态模式
状态模式通过将事件触发的状态转移和动作执行逻辑，分别放到不同的状态类中。转移到何种状态和执行何种动作，统一交个具体的状态类来处理。
定义状态类接口：
#include <string>//所有状态类的接口
class IMarioState{
public:IMarioState(){}virtual ~IMarioState(){}//输出状态名称virtual std::string getName() = 0;//吃蘑菇virtual void eatMushRooms() = 0;//碰到怪物virtual void contactMonsters() = 0;//攻击virtual void attack() = 0;
};状态机(Mario)依赖状态类接口(IMarioState)。
//mario.h//Mario状态机,状态机将具体的事件响应交给IMarioState来完成
class Mario{IMarioState *state; //状态int score; //积分
public:Mario();~Mario();void setCurrentState(IMarioState *st);void addScore(int s);void shootFirebool();void printState();//吃蘑菇void eatMushRooms();//碰到怪物void contactMonsters();//攻击void attack();};//mario.cppMario::Mario():state(NULL), score(0){state = new SmallMario(this);
}
Mario::~Mario(){if(this->state != NULL)delete this->state;
}
void Mario::setCurrentState(IMarioState *st){if(this->state != NULL)delete this->state;this->state = st;
}void Mario::addScore(int s){score += s;
}void Mario::shootFirebool(){cout << "shoot firebool!" << endl;
}void Mario::printState(){cout << state->getName() << endl;cout << "score is " << score << endl;cout << endl;
}//吃蘑菇
void Mario::eatMushRooms(){cout << "eatMushRooms begin:" << endl;state->eatMushRooms();printState();
}//碰到怪物
void Mario::contactMonsters(){cout << "contactMonsters begin:" << endl;state->contactMonsters();printState();
}//攻击
void Mario::attack(){cout << "attack begin:" << endl;state->attack();printState();
}具体的状态类(SmallMario、SurperMario、FireMario、DeadMario)同样依赖状态机(Mario)，具体状态类的某些行动，需要通过调用Mario来实现。以SmallMario为例。
//smallMario.hclass SmallMario: public IMarioState{
private:Mario *mario;public:SmallMario(Mario* mario);virtual std::string getName() override;virtual void eatMushRooms() override;virtual void contactMonsters() override;virtual void attack() override;
};//smallMario.cpp#include "smallMario.h"
#include "superMario.h"
#include "deadMario.h"SmallMario::SmallMario(Mario* mario):mario(mario){}std::string SmallMario::getName() {return "small!";
}void SmallMario::eatMushRooms() {mario->setCurrentState(new SuperMario(mario));mario->addScore(1000);
}void SmallMario::contactMonsters() {mario->setCurrentState(new DeadMario(mario));
}void SmallMario::attack() {
}测试代码：
```c++
#include <iostream>
#include "mario.h"int main(int argc, char *argv[]){Mario m;m.eatMushRooms();//吃蘑菇m.eatMushRooms();//吃蘑菇m.eatMushRooms();//吃蘑菇m.attack();//发射火球m.contactMonsters();//变小m.attack();//nothingm.contactMonsters();//diedreturn 0;
}结果：
eatMushRooms begin:
super!
score is 1000eatMushRooms begin:
fire!
score is 2000eatMushRooms begin:
fire!
score is 3000attack begin:
shoot firebool!
fire!
score is 3000contactMonsters begin:
small!
score is 3000attack begin:
small!
score is 3000contactMonsters begin:
dead!
score is 3000如果状态比较多，状态模式会引入非常多的状态类。
当然，状态模式有很多的变种，比如各个状态不需要每次new出来，可以采用单例模式等。这里就不深入讨论了。
总结
- 穷举法
优点：简单直接。
缺点：代码容易冗长，导致可读性和可维护性都很差。 - 查表法
优点：清晰，可读性和可维护性更好。
缺点：只适合执行的动作及其简单的情况。 - 状态模式：
优点：通过拆分，避免了大量if else或者switch case。
缺点：状态过多，状态类数量爆炸。阅读代码时需要打开各个状态类文件。
到这里，做了一个表格。如有错误，还请多指正。状态多暗含了状态转移复杂，动作多暗含了动作逻辑复杂。
| 动作少 | 动作多 | |
|---|---|---|
| 状态多 | 查表法 | 状态模式 |
| 状态少 | 穷举法 | 状态模式 |
