有限状态机FSM
前言：
之前的工作中使用有限状态机模型管理游戏流程，趁这段工作空窗期总结一下状态机的相关知识。
一.状态机相关概念：
有限状态机(Finite State Machine)，以下简称FSM，是一种描述离散状态的数学模型，在FSM模型中，可以将系统分解成有限数目的离散稳定，相互独立又有联系的状态。FSM中最基本的三点：
(1)状态的定义；
(2)状态的迁移；(在FSM中，一般通过事件使状态发生迁移)
(3)伴随状态迁移而产生的动作；
除了这最基本的三点，还有其他的扩展，如：状态监护条件，状态进入或离开动作，状态机嵌套（子状态机），并行状态机，状态历史记录（深层，浅层记录）等等。
二.在游戏中的应用
这里只谈棋牌游戏类型，其本质是在游戏规则的约束下，通过一系列事件来改变自身的状态，直到游戏结束。以麻将游戏为例，其状态机图类型如1.0图(简化版)：
图1.0 麻将状态机图
椭圆形为状态，例如：游戏开始，摇色子定庄家，闲家**等；
方形为驱动状态变迁的事件，例如：定时器事件，**完成事件等；
注意到，状态的拓扑结构是静态的，而驱动状态变迁的事件发生是动态的。意思是游戏一旦开始跑起来，当前状态的变迁路径是固定的，A状态只能变迁到B状态或C状态，而不能变迁到D状态；而事件何时发生，能不能发生则和当局游戏过程，玩家的选择相关。
因此，游戏维护人员只要看游戏的状态拓扑结构就能知道整个游戏的流程是怎么样的。另外，当我们把游戏的状态拓扑关系放在配置文件中，例如用XML文件来配置游戏的状态变迁关系，则当需要改变游戏流程时可以只改配置文件，而无需改动代码。一个例子：如果现在不需要闲家**，则只需要改配置文件，将摇色字定庄家状态的下一个变迁状态定为摇色字定财神状态就可以了。
三.现有的FSM工具
(1)UML状态机图:
在设计阶段，可以借助UML状态机图进行建模，画出即将要实现的状态机原形。上面的图1.0麻将状态机就是一个简单的UML状态机图。（我画图的软件没找到标示事件的图形，所以用一个矩形代替了事件的图形。）
UML状态机图提供了描述一个状态机的所有元素的语法，例如：状态，事件，状态转移，监护条件，起始状态和结束状态等。具体的语法可以查阅相关的资料
(2)开源库：boost::statechart
boost的statechart库为FSM开发提供了很多好用的特性，它能够方便的将UML状态机图转化为可执行形代码，即statechart支持FSM的很多语法，包括嵌套状态机，深层/浅层历史记录，事件延迟等。具体的使用可以查阅对应的文档，这里就不多讲述了。
四.自造*
有时不想在项目中引入第三方库，或者第三方库使用成本比较高，那么就得考虑自己实现一个满足使用需求的库。自己实现的库一般以满足项目使用需求就可以，所以能够做到够轻量级，且使用和学习成本不高。
之前在做棋牌游戏的项目中，写过一个FSM，不能称之为库吧，毕竟只是实现了最基础的功能。这个FSM的设计基于对象而不是面向对象，即并没有把FSM中的状态，转移，事件等都抽象成对象，但是整个FSM被封装成一个类，并且能够作为基类被继承。
（一）FSM基类
FSM的基类只提供状态机最基本的功能点：状态，状态迁移，迁移动作。FSM有一个当前的状态，和一个路由表。路由表由多个路由项组成，每个路由项表示：一个源状态在特定事件的驱动下迁移到目的状态，并伴随着迁移动作的发生。路由项定义如下：
//状态机路由关系，指一个源状态在一个事件的触发下迁移到另一个状态，并伴随着某个动作的发生
template<class _TypeEvent , class _TypeStatus , class _TypeParam>
struct RouteRelation{
RouteRelation(_TypeStatus srcS , _TypeStatus destS , _TypeEvent event , std::function<void (_TypeParam)> act) : srcStatus(srcS),
destStatus(destS),transitionEvent(event),transitionAction(act)
{
}
virtual ~RouteRelation() {}
_TypeStatus srcStatus ; //源状态
_TypeStatus destStatus ; //目的状态
_TypeEvent transitionEvent ; //导致状态发生变迁的事件ID
std::function<void (_TypeParam)> transitionAction ; //状态变迁时发生的动作
};注意到：
(1)这是一个模板类，则我们能够自定义事件的类型_TypeEvent，状态的类型_TypeStatus,还有一个模板参数_TypeParam则是迁移动作的参数类型，迁移动作的函数原型为：std::function<void (_TypeParam)>，这种方式使得我们可以自定义迁移动作的函数调用形式。
(2)其虚构函数是虚析构函数。一般来说，作为基类的类才需要虚析构函数，没错，这里就是想让这个模板类能够被继承，下面会讲到让这个类能够被继承的好处。另外一个，有了虚函数，我们才能对这个类类型使用dynamic_cast。
定义了路由表项后就可以定义FSM了，前面说了，FSM管理着一个路由表和一个当前状态，其定义如下：
//对_TypeEvent类型的要求：必须有==操作
//对_TypeStatus类型的要求：必须有hash函数和==操作
template<class _TypeEvent , class _TypeStatus , class _TypeParam>
class FSM{
protected:
typedef std::shared_ptr<const RouteRelation<_TypeEvent , _TypeStatus,_TypeParam>> P_C_ROUTERELATION ;
typedef std::unordered_multimap<_TypeStatus , P_C_ROUTERELATION> ROUTETABLE ;
public:
virtual ~FSM(){}
protected:
//当前状态
_TypeStatus m_curStatus ;
//源状态到路由表的映射，一对多的关系，因为一个源状态可以在不同的事件驱动下变迁到不同的目的状态
ROUTETABLE m_routeTable ;
};模板参数就不说了，和上面的路由项一样。路由表是一对多的关系，即一个源状态可以根据不同的事件跳到不同的目的状态，基于此，用unordered_multimap来存储路由关系。
需要注意的是，路由表中存储的是路由项的指针，一方面是节省内存空间；另一方面更重要，只有存储指针，我们才能使用C++的多态特性，即路由表里不仅能存储上面定义的路由项类RouteRelation,也能存储其子类。
接着，就可以添加FSM类的操作了，构造函数，析构函数，注册，事件通知等。事件通知一般有同步和异步两种方式，这里我们用的是同步方式，如果需要用异步方式，则需重新实现。整个FSM代码：
//对_TypeEvent类型的要求：必须有==操作
//对_TypeStatus类型的要求：必须有hash函数和==操作
template<class _TypeEvent , class _TypeStatus , class _TypeParam>
class FSM{
protected:
typedef std::shared_ptr<const RouteRelation<_TypeEvent , _TypeStatus,_TypeParam>> P_C_ROUTERELATION ;
typedef std::unordered_multimap<_TypeStatus , P_C_ROUTERELATION> ROUTETABLE ;
public:
FSM(_TypeStatus startStatus , _TypeStatus endStatus) : m_curStatus(startStatus),m_startStatus(startStatus),m_endStatus(endStatus){}
virtual ~FSM(){}
//返回false表明该路由关系已经注册；返回true注册成功
bool Register(P_C_ROUTERELATION pRouteRelation)
{
if(IsInRouteTable(pRouteRelation))
return false ;
m_routeTable.insert(std::make_pair(pRouteRelation->srcStatus , pRouteRelation)) ;
return true ;
}
/*以同步方式执行事件通知，可以通过覆盖该函数实现不同的通知方式
* 状态变迁返回true，否则返回false
*/
virtual P_C_ROUTERELATION Notify(_TypeEvent event , _TypeParam param)
{
P_C_ROUTERELATION NullSp ;
if(m_curStatus == m_endStatus)
return NullSp;
ROUTETABLE::size_type count = m_routeTable.count(m_curStatus) ;
if(count > 0)
{
ROUTETABLE::const_iterator it = m_routeTable.find(m_curStatus) ;
if(it != m_routeTable.end())
{
for(; count > 0 ; --count)
{
if((it->second) && (it->second->transitionEvent == event))
{
//状态变迁
m_curStatus = it->second->destStatus ;
//执行状态转移动作
if(it->second->transitionAction)
it->second->transitionAction(param) ;
return it->second ;
}
}
}
}
return NullSp ; //返回空的指针
}
//将当前状态置为开始状态
void ReSetCurStatus(){m_curStatus = m_startStatus ;}
_TypeStatus getCurStatus() const {return m_curStatus ;}
_TypeStatus getStartStatus() const {return m_startStatus ;}
_TypeStatus getEndStatus() const {return m_endStatus ;}
protected:
bool IsInRouteTable(P_C_ROUTERELATION pRouteRelation)
{
ROUTETABLE::size_type count = m_routeTable.count(pRouteRelation->srcStatus) ;
if(count > 0)
{
ROUTETABLE::const_iterator it = m_routeTable.find(pRouteRelation->srcStatus) ;
if(it != m_routeTable.end())
{
for(;count > 0 ; --count)
{
//源状态和事件确定目的状态，所以这两个项一样的话则标明已经有该路由关系
if((it->second->srcStatus == pRouteRelation->srcStatus) && (it->second->transitionEvent == pRouteRelation->transitionEvent))
return true ;
++it ;
}
}
}
return false ;
}
//开始和结束状态
const _TypeStatus m_startStatus ;
const _TypeStatus m_endStatus ;
//当前状态
_TypeStatus m_curStatus ;
//源状态到路由表的映射，一对多的关系，因为一个源状态可以在不同的事件驱动下变迁到不同的目的状态
ROUTETABLE m_routeTable ;
};
（二）实际项目中的使用
前面说了，FSM基类只提供了最基本的功能，如果项目中需要用到其他功能，例如在进入一个新状态时，需要执行一个进入动作，则可以通过扩展路由项类RouteRelation和FSM类实现，这就是前面说的把这两个类设计成能被继承的原因。接下来利用FSM来实现一个游戏状态机GameFSM。
首先，定义事件类型，状态类型，参数类型等：
enum emGFsmEventId{
emGFsmEInvalid = -1,
emGFsmEAuto = 0,
emGFsmETimer,
emGFsmEGameBegin
};
enum emGFsmStatusId{
emGFsmSInvalid = -1,
emGFsmSGameBegin = 0,
emGFsmSMakeNt,
emGFsmSRandCard,
emGFsmSGiveNextToken
};
struct GFsmParam{
GFsmParam():transitionParam(0),enterParam(0){}
GFsmParam(LPARAM tP , LPARAM eP) : transitionParam(tP),enterParam(eP){}
LPARAM transitionParam; //转移动作参数
LPARAM enterParam; //进入动作参数
};然后扩展路由项,加了一个进入状态后的动作：
//FSM的路由关系中只定义了转移动作，如果需要其他动作可以通过继承基类来扩展,例如想扩展一个进入新状态后的动作
struct GameRouteRelation : public RouteRelation<emGFsmEventId , emGFsmStatusId , GFsmParam>
{
GameRouteRelation(emGFsmStatusId srcS , emGFsmStatusId destS , emGFsmEventId event , std::function<void (GFsmParam)> tranAct ,
std::function<void (GFsmParam)> enterAct):RouteRelation(srcS , destS , event , tranAct),enterAction(enterAct){}
std::function<void (GFsmParam)> enterAction; //进入新状态后执行的动作
};最后，通过继承FSM来定义GameFSM：
typedef std::shared_ptr<const GameRouteRelation> P_C_GAMEROUTERELATION ;
class GameFSM : public FSM<emGFsmEventId , emGFsmStatusId , GFsmParam>{
public:
GameFSM(emGFsmStatusId startStatus , emGFsmStatusId endStatus) :
FSM(startStatus , endStatus){}
bool Register(emGFsmStatusId srcStatus , emGFsmStatusId destStatus , emGFsmEventId event ,
std::function<void (GFsmParam)> transitionAction = nullptr,std::function<void (GFsmParam)> enterAction = nullptr)
{
return FSM::Register(std::make_shared<GameRouteRelation>(srcStatus , destStatus , event , transitionAction , enterAction)) ;
}
virtual P_C_ROUTERELATION Notify(emGFsmEventId eventId , GFsmParam param)
{
P_C_ROUTERELATION pCRouteRelation = __super::Notify(eventId ,param) ;
if(pCRouteRelation)
{
P_C_GAMEROUTERELATION pCGameR = std::dynamic_pointer_cast<const GameRouteRelation>(pCRouteRelation) ;
//执行新状态的进入动作
if(pCGameR)
{
if(pCGameR->enterAction)
pCGameR->enterAction(param) ;
}
}
return pCRouteRelation ;
}
};基类的Notify调用后会返回发生状态迁移的路由项基类对象指针，因此我们可以通过dynamic_cast转换成我们定义的扩展路由项，这就是为什么路由表要保存路由项指针的第二个原因了。
由于我们保存的是智能指针，std::shared_ptr,所以不能直接用dynamic_cast,而是用std::dynamic_pointer_cast进行转换。得到路由项之后，就可以调用进入状态动作函数了。这就是扩展的GamFSM的Notify需要做的事。
上一篇： 用VHDL实现有限状态机