γ - Ursae Majoris

有限状态机的C语言实现

　　有限状态机（Finite-State Machine），简称状态机，是一种非常有用的数学模型，可以作为世界上大多数事物和事件的抽象。有限状态机（以下简称FSM）的主要元素有：状态（State）、事件（Event）和动作（Action）。

　　先让我们看一个现实生活中的例子吧：如何优雅地摧毁地球（这TM算哪门子的现实生活啊？！）。我们知道，一个合格的程序员是不会写出“摧毁地球”这样的程序的，他会写一个名为“摧毁行星”的函数，然后把地球作为参数传进去；但是作为一名高端程序员，这么做还不够，我们还要实现摧毁恒星的功能，以达到良好的向前兼容。

　　于是我们实现了一个“星球毁灭器”。为了避免误操作，不能直接下达类似“摧毁地球”的指令，而应该先将机器目标锁定为地球，然后按下“摧毁”按钮。另外，由于恒星的体积一般比行星大得多，所以摧毁一颗恒星后，机器将进入过热状态，需要冷却后才能再次使用。用有限状态机可以描述为下图：

星球毁灭者状态图

　　图中描述了状态在事件下的切换，没有表示出在状态切换的过程中，机器执行的操作，例如在按下“摧毁”按钮后，将执行摧毁操作，然后转换到待机或过热状态。

　　了解了FSM的基本概念后，接下来看FSM的实现方式。最初级，也是最直观的方式就是利用C语言的switch case或if语句，把所有状态和事件都写在同一个函数中，如：

switch (state)
{
case STAND_BY:
    switch (event)
    {
    case GET_PLANET:
        target = planet;
        Lock(target);
        state = LOCK_PLANET;
        break;
    case GET_STAR:
        target = star;
        Lock(target);
        state = LOCK_STAR;
        break;
    default:
        break;
    }
case LOCK_PLANET:
    switch (event)
    {
    case GET_STAR:
        target = star;
        Lock(target);
        state = LOCK_STAR;
        break;
    case PUSH:
        Destroy(target);
        state = STAND_BY;
        break;
    default:
        break;
    }
case LOCK_STAR:
    switch (event)
    {
    case GET_PLANET:
        target = planet;
        Lock(target);
        state = LOCK_PLANET;
        break;
    case PUSH:
        Destroy(target);
        state = OVERHEATING;
        break;
    default:
    }
case OVERHEATING:
    switch (event)
    {
    case COOL_DOWN:
        state = STAND_BY;
        break;
    default:
        break;
    }
}

　　代码进入状态的分支后，判断事件，随后根据不同事件执行不同的操作并跳转到相应的状态。但是当状态和时间变多之后，这种方法的代码和逻辑将变得十分复杂和混乱，所以一般只在逻辑和状态非常简单的情况下采用。下面介绍一种表驱动法。

　　FSM的本质是一张有向图，而有向图一般可以用一张二维表来描述，结合C语言的函数指针，我们可以实现FSM的所有特性。一般可以用一个坐标表示状态，另一个坐标表示事件，表中元素存储下一个状态和对应的操作。

#define STATE_NUM   4
#define EVENT_NUM   4

#define NO_STATE    -1
#define STAND_BY    0
#define LOCK_PLANET 1
#define LOCK_STAR   2
#define OVERHEATING 3

#define ANY_EVENT   -1
#define GET_PLANET  0
#define GET_STAR    1
#define PUSH        2
#define COOLDOWN    3

typedef struct 
{
    int nextState;
    int (*op)(void *);
}FSM_Item;

FSM_Item fsm[STATE_NUM][EVENT_NUM] = 
{
    { {LOCK_PLANET, Lock}, {LOCK_STAR, Lock}, {NO_STATE, NULL}, {NO_STATE, NULL} }, 
    { {NO_STATE, NULL}, {LOCK_STAR, Lock}, {STAND_BY, Destroy}, {NO_STATE, NULL} }, 
    { {LOCK_PLANET, Lock}, {NO_STATE, NULL}, {OVERHEATING, Destroy}, {NO_STATE, NULL} }, 
    { {NO_STATE, NULL}, {NO_STATE, NULL}, {NO_STATE, NULL}, {STAND_BY, NULL} }
};

while (1)
{
    int event = GetEvent();
    FSM_Item item = fsm[state][event];
    if (NULL != item.op)
    {
        op(parg);
    }
    if (NO_STATE != item.nextState)
    {
        state = item.nextState;
    }
}

　　以二维数组描述状态机，可读性比较高，而且在状态机发生变化时，可以很方便地修改数组。用状态和事件作为下标，可以免去遍历数组查找的工作，直接通过下标访问到正确的项。另外，还可以实现多个状态表，根据运行时需要可以随时切换状态表。缺点在于，状态描述表往往是一个稀疏矩阵，当状态和事件较多时，会占用较大的空间。

References

http://en.wikipedia.org/wiki/Finite-state_machine
C state-machine design
实现简易而强大的游戏AI–FSM

Post Info

Published

25 January 2014

Category

program

Tags