状态机

基于C++有限状态机的实现技术一.引言有限状态机是一种用来进行对象行为建模的工具，其作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。在面向对象的软件系统中，一个对象无论多么简单或者多么复杂，都必然会经历一个从开始创建到最终消亡的完整过程，这通常被称为对象的生命周期。一般说来，对象在其生命期内是不可能完全孤立的，它必须通过发送消息来影响其它对象，或者通过接受消息来改变自身。在大多数情况下，这些消息都只不过是些简单的、同步的方法调用而已。例如，在银行客户管理系统中，客户类（Customer）的实例在需要的时候，可能会调用帐户（Account）类中定义的getBalance()方法。在这种简单的情况下，类Customer并不需要一个有限状态机来描述自己的行为，主要原因在于它当前的行为并不依赖于过去的某个状态。[1]遗憾的是并不是所有情况都会如此简单，事实上许多实用的软件系统都必须维护一两个非常关键的对象，它们通常具有非常复杂的状态转换关系，而且需要对来自外部的各种异步事件进行响应。例如，在VoIP电话系统中，电话类（Telephone）的实例必须能够响应来自对方的随机呼叫，来自用户的按键事件，以及来自网络的信令等。在处理这些消息时，类Telephone所要采取的行为完全依赖于它当前所处的状态，因而此时使用状态机就将是一个不错的选择。[1]游戏引擎是有限状态机最为成功的应用领域之一，由于设计良好的状态机能够被用来取代部分的人工智能算法，因此游戏中的每个角色或者器件都有可能内嵌一个状态机。考虑RPG游戏中城门这样一个简单的对象，它具有打开（Opened）、关闭（Closed）、上锁（Locked）、解锁（Unlocked）四种状态，如图1所示。当玩家到达一个处于状态Locked的门时，如果此时他已经找到了用来开门的钥匙，那么他就可以利用它将门的当前状态转变为Unlocked，进一步还可以通过旋转门上的把手将其状态转变为Opened，从而成功地进入城内。[1]图1控制城门的状态机在描述有限状态机时，状态、事件、转换和动作是经常会碰到的几个基本概念。状态（State）指的是对象在其生命周期中的一种状况，处于某个特定状态中的对象必然会满足某些条件、执行某些动作或者是等待某些事件。事件（Event）指的是在时间和空间上占有一定位置，并且对状态机来讲是有意义的那些事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。转换（Transition）指的是两个状态之间的一种关系，表明对象将在第一个状态中执行一定的动作，并将在某个事件发生同时某个特定条件满足时进入第二个状态。动作（Action）指的是状态机中可以执行的那些原子操作，所谓原子操作指的是它们在运行的过程中不能被其他消息所中断，必须一直执行下去。二、基于传统C语言的FSM实现技术2.1、基于switch（状态）的实现在实现有限状态机时，使用switch语句是最简单也是最直接的一种方式，其基本思路是为状态机中的每一种状态都设置一个case分支，专门用于对该状态进行控制。下面的代码示范了如何运用switch语句，来实现图1中所示的状态机：switch(state){//处理状态Opened的分支case(Opened):{//执行动作Openopen();//检查是否有CloseDoor事件if(closeDoor()){//当前状态转换为ClosedchangeState(Closed)}break;}//处理状态Closed的分支case(Closed):{//执行动作Closeclose();//检查是否有OpenDoor事件if(openDoor()){//当前状态转换为OpenedchangeState(Opened);}//检查是否有LockDoor事件if(lockDoor()){//当前状态转换为LockedchangeState(Locked);}break;}//处理状态Locked的分支case(Locked):{//执行动作Locklock();//检查是否有UnlockDoor事件if(unlockDoor()){//当前状态转换为UnlockedchangeState(Unlocked);}break;}//处理状态Unlocked的分支case(Unlocked):{//执行动作Unlockunlock();//检查是否有LockDoor事件if(lockDoor()){//当前状态转换为LockedchangeState(Locked)}//检查是否有OpenDoor事件if(openDoor()){//当前状态转换为OpenedchangeSate(Opened);}break;}}使用switch语句实现的有限状态机的确能够很好地工作，但代码的可读性并不十分理想，主要原因是在实现状态之间的转换时，检查转换条件和进行状态转换都是混杂在当前状态中来完成的。例如，当城门处于Opened状态时，需要在相应的case中调用closeDoor()函数来检查是否有必要进行状态转换，如果是的话则还需要调用changeState()函数将当前状态切换到Closed。显然，如果在每种状态下都需要分别检查多个不同的转换条件，并且需要根据检查结果让状态机切换到不同的状态，那么这样的代码将是枯燥而难懂的。从代码重构的角度来讲，此时更好的做法是引入checkStateChange()和performStateChange()两个函数，专门用来对转换条件进行检查，以及激活转换时所需要执行的各种动作。这样一来，程序结构将变得更加清晰：switch(state){//处理状态Opened的分支case(Opened):{//执行动作Openopen();//检查是否有激发状态转换的事件产生if(checkStateChange()){//对状态机的状态进行转换performStateChange();}break;}//处理状态Closed的分支case(Closed):{//执行动作Closeclose();//检查是否有激发状态转换的事件产生if(checkStateChange()){//对状态机的状态进行转换performStateChange();}break;}//处理状态Locked的分支case(Locked):{//执行动作Locklock();//检查是否有激发状态转换的事件产生if(checkStateChange()){//对状态机的状态进行转换performStateChange();}break;}//处理状态Unlocked的分支case(Unlocked):{//执行动作Lockunlock();//检查是否有激发状态转换的事件产生if(checkStateChange()){//对状态机的状态进行转换performStateChange();}break;}}但checkStateChange()和performStateChange()这两个函数本身依然会在面对很复杂的状态机时，内部逻辑变得异常臃肿，甚至可能是难以实现。在很长一段时期内，使用switch语句一直是实现有限状态机的唯一方法，甚至像编译器这样复杂的软件系统，大部分也都直接采用这种实现方式。但之后随着状态机应用的逐渐深入，构造出来的状态机越来越复杂，这种方法也开始面临各种严峻的考验，其中最令人头痛的是如果状态机中的状态非常多，或者状态之间的转换关系异常复杂，那么简单地使用switch语句构造出来的状态机将是不可维护的。三、基于面向对象的FSM实现技术3.1、用一个类实现FSMclassDoorFSM{private:States__Y;std::queueEvent__events;void__processEvent(Evente);protected:virtualvoidenterOpened()=0;virtualvoidenterLocked()=0;virtualvoidenterUnlocked()=0;virtualvoidenterClosed()=0;public:/*States*/enumStates{Closed,Unlocked,Locked,Opened};//states/*Events*/enumEvent{Lock,Unlock,Open,Close};///ConstructorDoorFSM(){__Y=Opened;}///Destructorvirtual~DoorFSM(){}/**GetcurrentFSMstate@returnscurrentFSMstate*/StatescurrentState(){return__Y;}/**SendeventtoFSMUsethisfunctiontosendeventtoDoorFSMAfteryoucallitgiveneventwillbehandled,and,ifsomeoftransitionconditionsmatch,appropriatetransitionwillbetriggered,andcurrentState()willbechanged.Ifthisfunctioniscalledduringexistingeventhandlingprocess,giveneventwillbeaddedtopendingeventqueue,andwillbehandledaftercurrenttransition.Seeexamplesfordetails.*/voidA(Evente);};voidDoorFSM::__processEvent(Evente){StatesyOld=__Y;boolpass=false;switch(__Y){//transitionscaseClosed:if(e==Open){//outcomeactions__Y=Opened;pass=true;}elseif(e==Lock){//outcomeactions__Y=Locked;pass=true;}break;caseUnlocked:if(e==Lock){//outcomeactions__Y=Locked;pass=true;}elseif(e==Open){//outcomeactions__Y=Opened;pass=true;}break;caseLocked:if(e==Unlock){//outcomeactions__Y=Unlocked;pass=true;}break;caseOpened:if(e==Close){//outcomeactions__Y=Closed;pass=true;}break;}if(yOld==__Y&&!pass){return;}switch(__Y){//incomeactionscaseClosed:enterClosed();break;caseUnlocked:enterUnlocked();break;caseLocked:enterLocked();break;caseOpened:enterOpened();break;}}voidDoorFSM::A(Evente){bool__empty=__events.empty();__events.push(e);if(__empty){while(!__events.empty()){__processEvent(__events.front());__events.pop();}}}classDoorFSMLogic:publicDoorFSM{protected:virtualvoidenterOpened(){std::coutEnterOpenedstate.std::endl;}virtualvoidenterLocked(){std::coutEnterClosedstate.