有限状态机.txt

有限状态机FSM思想广泛应用于硬件控制电路设计

有限状态机FSM思想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法(软件上称为FMM--有限消息机)。它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变连续处理为离散数字处理，符合计算机的工作特点。同时，因为有限状态机具有有限个状态，所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理，相反，有限状态机是闭环系统，有限无穷，可以用有限的状态，处理无穷的事务。
    有限状态机的工作原理如图1所示，发生事件(event)后，根据当前状态(cur_state)，决定执行的动作(action)，并设置下一个状态号(nxt_state)。

                         -------------
                         |           |-------->执行动作action
     发生事件event ----->| cur_state |
                         |           |-------->设置下一状态号nxt_state
                         -------------
                            当前状态
                      图1 有限状态机工作原理


                               e0/a0
                              --->--
                              |    |
                   -------->----------
             e0/a0 |        |   S0   |-----
                   |    -<------------    | e1/a1
                   |    | e2/a2           V
                 ----------           ----------
                 |   S2   |-----<-----|   S1   |
                 ----------   e2/a2   ----------
                       图2 一个有限状态机实例

              --------------------------------------------
              当前状态   s0        s1        s2     | 事件
              --------------------------------------------
                       a0/s0      --       a0/s0   |  e0
              --------------------------------------------
                       a1/s1      --        --     |  e1
              --------------------------------------------
                       a2/s2     a2/s2      --     |  e2
              --------------------------------------------

               表1 图2状态机实例的二维表格表示(动作/下一状态)

    图2为一个状态机实例的状态转移图，它的含义是：
        在s0状态，如果发生e0事件，那么就执行a0动作，并保持状态不变；
                 如果发生e1事件，那么就执行a1动作，并将状态转移到s1态；
                 如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；
        在s1状态，如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；
        在s2状态，如果发生e0事件，那么就执行a0动作，并将状态转移到s0态；
    有限状态机不仅能够用状态转移图表示，还可以用二维的表格代表。一般将当前状态号写在横行上，将事件写在纵列上，如表1所示。其中“--”表示空(不执行动作，也不进行状态转移)，“an/sn”表示执行动作an,同时将下一状态设置为sn。表1和图2表示的含义是完全相同的。
    观察表1可知，状态机可以用两种方法实现：竖着写(在状态中判断事件)和横着写(在事件中判断状态)。这两种实现在本质上是完全等效的，但在实际操作中，效果却截然不同。

==================================
竖着写(在状态中判断事件)C代码片段
==================================
    cur_state = nxt_state;
    switch(cur_state){                  //在当前状态中判断事件
        case s0:                        //在s0状态
            if(e0_event){               //如果发生e0事件，那么就执行a0动作，并保持状态不变；
                执行a0动作;
                //nxt_state = s0;       //因为状态号是自身，所以可以删除此句，以提高运行速度。
            }
            else if(e1_event){          //如果发生e1事件，那么就执行a1动作，并将状态转移到s1态；
                执行a1动作;
                nxt_state = s1;
            }
            else if(e2_event){          //如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；
                执行a2动作;
                nxt_state = s2;
            }
            break;
        case s1:                        //在s1状态
            if(e2_event){               //如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；
                执行a2动作;
                nxt_state = s2;
            }
            break;
        case s2:                        //在s2状态
            if(e0_event){               //如果发生e0事件，那么就执行a0动作，并将状态转移到s0态；
                执行a0动作;
                nxt_state = s0;
            }
    }

==================================
横着写(在事件中判断状态)C代码片段
==================================
//e0事件发生时，执行的函数
void e0_event_function(int * nxt_state)
{
    int cur_state;
    
    cur_state = *nxt_state;
    switch(cur_state){
        case s0:                        //观察表1，在e0事件发生时，s1处为空
        case s2:
            执行a0动作;
            *nxt_state = s0;
    }
}

//e1事件发生时，执行的函数
void e1_event_function(int * nxt_state)
{
    int cur_state;
    
    cur_state = *nxt_state;
    switch(cur_state){
        case s0:                        //观察表1，在e1事件发生时，s1和s2处为空
            执行a1动作;
            *nxt_state = s1;
    }
}

//e2事件发生时，执行的函数
void e2_event_function(int * nxt_state)
{
    int cur_state;
    
    cur_state = *nxt_state;
    switch(cur_state){
        case s0:                        //观察表1，在e2事件发生时，s2处为空
        case s1:
            执行a2动作;
            *nxt_state = s2;
    }
}

    上面横竖两种写法的代码片段，实现的功能完全相同，但是，横着写的效果明显好于竖着写的效果。理由如下：
    1、竖着写隐含了优先级排序(其实各个事件是同优先级的)，排在前面的事件判断将毫无疑问地优先于排在后面的事件判断。这种if/else if写法上的限制将破坏事件间原有的关系。而横着写不存在此问题。
    2、由于处在每个状态时的事件数目不一致，而且事件发生的时间是随机的，无法预先确定，导致竖着写沦落为顺序查询方式，结构上的缺陷使得大量时间被浪费。对于横着写，在某个时间点，状态是唯一确定的，在事件里查找状态只要使用switch语句，就能一步定位到相应的状态，延迟时间可以预先准确估算。而且在事件发生时，调用事件函数，在函数里查找唯一确定的状态，并根据其执行动作和状态转移的思路清晰简洁，效率高，富有美感。
    总之，我个人认为，在软件里写状态机，使用横着写的方法比较妥帖。
    
    竖着写的方法也不是完全不能使用，在一些小项目里，逻辑不太复杂，功能精简，同时为了节约内存耗费，竖着写的方法也不失为一种合适的选择。
    在FPGA类硬件设计中，以状态为中心实现控制电路状态机(竖着写)似乎是唯一的选择，因为硬件不太可能靠事件驱动(横着写)。不过，在FPGA里有一个全局时钟，在每次上升沿时进行状态切换，使得竖着写的效率并不低。虽然在硬件里竖着写也要使用IF/ELSIF这类查询语句(用VHDL开发)，但他们映射到硬件上是组合逻辑，查询只会引起门级延迟(ns量级)，而且硬件是真正并行工作的，这样竖着写在硬件里就没有负面影响。因此，在硬件设计里，使用竖着写的方式成为必然的选择。这也是为什么很多搞硬件的工程师在设计软件状态机时下意识地只使用竖着写方式的原因，盖思维定势使然也。

    TCP和PPP框架协议里都使用了有限状态机，这类软件状态机最好使用横着写的方式实现。以某TCP协议为例，见图3，有三种类型的事件：上层下达的命令事件；下层到达的标志和数据的收包事件；超时定时器超时事件。
    
                    上层命令(open,close)事件
            -----------------------------------
                    --------------------
                    |       TCP        |  <----------超时事件timeout
                    --------------------
            -----------------------------------
                 RST/SYN/FIN/ACK/DATA等收包事件
                    
                    图3 三大类TCP状态机事件

    由图3可知，此TCP协议栈采用横着写方式实现，有3种事件处理函数，上层命令处理函数(如tcp_close)；超时事件处理函数(tmr_slow)；下层收包事件处理函数(tcp_process)。值得一提的是，在收包事件函数里，在各个状态里判断RST/SYN/FIN/ACK/DATA等标志(这些标志类似于事件)，看起来象竖着写方式，其实，如果把包头和数据看成一个整体，那么，RST/SYN/FIN/ACK/DATA等标志就不必被看成独立的事件，而是属于同一个收包事件里的细节，这样，就不会认为在状态里查找事件，而是总体上看，是在收包事件里查找状态(横着写)。
    
    在PPP里更是到处都能见到横着写的现象，有时间的话再细说。我个人感觉在实现PPP框架协议前必须了解横竖两种写法，而且只有使用横着写的方式才能比较完美地实现PPP。



----------------------------------------------



NIST 对有限状态机（Finite State Machine, FSM）的定义如下。
  
    包含一组状态集（states）、一个起始状态（start state）、一组输入符号集（alphabet）、一个映射输入符号和当前状态到下一状态的转换函数（transition function）的计算模型。当输入符号串，模型随即进入起始状态。它要改变到新的状态，依赖于转换函数。在有限状态机中，会有有许多变量，例如，状态机有很多与动作（actions）转换(Mealy机)或状态（摩尔机）关联的动作，多重起始状态，基于没有输入符号的转换，或者指定符号和状态（非定有限状态机）的多个转换，指派给接收状态（识别者）的一个或多个状态，等等。

    一个例子

                     

    上图是一个接受者 FSM 模型，用来分析单词“nice”。该分析器只接受字符输入，包含6种状态，状态切换由输入的字符驱动。理解起来非常简单，在此不作解释了。

    感谢宏云前辈对本文翻译提供的指导。

 


  
  
littlepig_2002   
 
 
  
游戏中的有限状态机(InGems)
 

这是GAMEGEMS中的第三章的第一部分，番的不好。你可以直接阅读原文。原本以为这是人工智能的部分，看到一半才发现只是一个简单的框架。如果你想学人工智能，这里没有，就不要浪费时间了。由于本人水平有限，其中难免会出现原则性的错误，希望指正。

关键字：有限状态机、状态、输入、状态转换、输出状态当前状态

一个有限状态机类
在这篇文章中，我们创建了一个通用的有限状态机（FSM）的C++类。有限状态机是计算机科学和数学理论的抽象，它在许多的方面是很有用处的。这里我们不去讲解有限状态机的理论上的知识。而是讲如何实现一个“有限状态机”，“有限状态机”在游戏的人工智能方面是很有用处的。

“有限状态机”是由有限的状态组成的一个机制。一个“状态”就是一个状况。你考虑一下门；它的“状态”有“开”或“关”以及“锁”与“未锁”。

对于一个“有限状态机”，它应该有一个“输入”。这个“输入”可以影响“状态转换”。“有限状态机”应该有一个简单（或复杂）的状态转换函数，这个函数可以决定什么状态可以变成“当前状态”。

这个当前的新状态被称为“有限状态机”的“状态转换”的“输出状态”。如果你对这个概念有些迷惑，就把“门”做为理解“有限状态机”的例子。当一个“门”处于“关闭”状态和“锁”状态，当你输入了“使用钥匙”时，门的状态可以变成“未锁”状态（即“状态转换”的输出状态，也就是门的当前状态）。当你输入了“使用手”时，门的状态可以转换成“开”的状态。当门处于“开”的状态时，我们输入“使用手”时，会使门的状态重新回到“关”的状态。当“门”处于“关”的状态时，我们输入“使用钥匙”时，这将会使门重新回到“锁”的状态。当门处于“锁”的状态，我们输入“使用手”，就不能把门的状态转换到“开”的状态，门仍然会保持“锁”的状态。还有，当门处于“开”的状态时，我们输入“使用钥匙”是不能把门的状态转换成“锁”的状态的。

总之，“有限状态机”是一个有限的状态组成的，其中的一个状态是“当前状态”。“有限状态机”可以接受一个“输入”，这个“输入”的结果将导致一个“状态转换”的发生（即从“当前状态”转换到“输出”状态）。这个“状态转换”是基于“状态转换函数”的。状态转换完成之后，“输出状态”即变成了“当前状态”。

输入 状态转换函数
当前状态-----》状态转换-------------》输出状态（当前状态）

那么，人们是如何将这个概念应用到游戏的AI系统中的呢？有限状态机的功能很多：管理游戏世界、模拟NPC的思维、维护游戏状态、分析玩游戏的人的输入，或者管理一个对象的状态。

假如在一个冒险游戏中有一个NPC，名字可以叫MONSTER。我们可以先假设这个MONSTER在游戏中有如下的状态：BERSERK、RAGE、MAD、ANNOYED以及UNCARING。（前几个状态不好分别）。假设，MONSTER对于不同的状态可以执行不同的操作，并且假设你已经有了这些不同操作的代码。我们这时可以使用“有限状态机”来模拟这个MONSTER的行为了。只要我们给出不同的“输入”，MONSTER就会做出不同的反应。我们再来指出这些“输入”是什么：PLAYER SEEN、PLAYER ATTACKS、PLAYERGONE、MONSTER HURT、MONSTER HEALED。这样我们可以得到一个状态转换的表格，如下：游戏状态转换表：

当前状态 输入 输出状态
UNCARING PLAYER SEEN ANNOYED
UNCARING PLAYER ATTACKS MAD
MAD MONSTER HURT RAGE
MAD MONSTER HEALED UNCARING
RAGE MONSTER HURT BERSERK
RAGE MONSTER HEALED ANNOYED
BERSERK MONSTER HURT BERSERK
BERSERK MONSTER HEALED RAGE
ANNOYED PLAYER GONE UNCARING
ANNOYED PLAYER ATTACKS RAGE
ANNOYED MONSTER HEALED UNCARING

根据上面的这个表格，我们可以很容易的画出一个MONSTER的“状态转换图”，MONSTER的每一个状态就是图中的顶点。
因此，根据当前状态和对FSM的输入，MONSTER的状态将被改变。这时根据MONSTER的状态执行相应操作的代码（假设已经实现）将被执行，这时MONSTER好像是具备了人工智能。显然，我们可以定义更多的“状态”，写出更多的“输入”，写出更多的“状态转换”，这样，MONSTER可以表现的更真实，生动，当然，这些游戏的规则问题应该是策划制定的。

FSMclass以及FSMstate

现在，我们如何把这些方法变成现实？使用FSMclass和它的组成部分FSMstate可以实现这些想法。

定义FSMstate
class FSMstate
{
    unsigned m_usNumberOfTransition; //状态的最大数
    int* m_piInputs; //为了转换而使用的输入数组
    int* m_piOutputState; //输出状态数组
    int m_iStateID; //这个状态的唯一标识符
public:
    //一个构造函数，可以接受这个状态的ID和它支持的转换数目
    FSMstate(int iStateID,unsigned usTransitions);
    //析构函数，清除分配的数组
    ~FSMstate();
    //取这个状态的ID
    int GetID(){return m_iStateID;}
    //向数组中增加状态转换
    void AddTransition(int iInput,int iOutputID);
    //从数组中删除一个状态转换
    void DeleteTransition(int iOutputID);
    //进行状态转换并得到输出状态
    int GetOutput(int iInput);
};

对这个类的分析：
功能：主要是实现与一个状态相关的各种操作。我们前面假设了MONSTER的各种状态：
#define STATE_ID_UNCARING 1
#define STATE_ID_MAD 2
#define STATE_ID_RAGE 3
#define STATE_ID_BERSERK 4
#define STATE_ID_ANNOYED 5