有限狀態機FSM的實作與理解

有限狀態機（finite state machine）簡稱FSM，表示有限個狀態及在這些狀態之間的轉移和動作等行為的數學模型，在計算機領域有著廣泛的應用。 FSM是一種邏輯單元內部的一種高效程式設計方法，在伺服器程式設計中，伺服器可以根據不同狀態或訊息類型進行相應的處理邏輯，使得程式邏輯清晰易懂。

那有限狀態機通常在什麼地方被用到？

處理程式語言或自然語言的tokenizer,自底向上解析語法的parser，
各種通訊協定發送者和接受方傳遞資料對訊息處理，遊戲AI等都有應用場景。

狀態機有以下幾種實作方法，我將一一闡述它們的優缺點。

一、使用if/else if語句實作的FSM

使用if/else if語句是實作的FSM最簡單、最易懂的方法，我們只需要透過大量的if /else if語句來判斷狀態值來執行對應的邏輯處理。

看看下面的例子，我們使用了大量的if/else if語句實作了一個簡單的狀態機，做到了根據狀態的不同執行相應的操作，並且實現了狀態的跳躍。

//比如我们定义了小明一天的状态如下
enum
{
    GET_UP,
    GO_TO_SCHOOL,
    HAVE_LUNCH,
    GO_HOME,
    DO_HOMEWORK,
    SLEEP,
};


int main()
{
    int state = GET_UP;
    //小明的一天
    while (1)
    {
        if (state == GET_UP)
        {
            GetUp(); //具体调用的函数
            state = GO_TO_SCHOOL;  //状态的转移
        }
        else if (state == GO_TO_SCHOOL)
        {
            Go2School();
            state = HAVE_LUNCH;
        }
        else if (state == HAVE_LUNCH)
        {
            HaveLunch();
        }
        ...
        else if (state == SLEEP)
        {
            Go2Bed();
            state = GET_UP;
        }
    }

    return 0;
}

看完上面的例子，大家有什麼感受？是不是感覺程式雖然簡單易懂，但使用了大量的if判斷語句，使得程式碼很低端，同時程式碼膨脹的比較厲害。這個狀態機的狀態僅有幾個，程式碼膨脹並不明顯，但是如果我們需要處理的狀態有數十個的話，該狀態機的程式碼就不好讀了。

二、使用switch實作FSM

使用switch語句實現的FSM的結構變得更為清晰了，其缺點也是明顯的：這種設計方法雖然簡單，透過一大堆判斷來處理，適合小規模的狀態切換流程，但如果規模擴大難以擴展和維護。

int main()
{
    int state = GET_UP;
    //小明的一天
    while (1)
    {

        switch(state)
        {
        case GET_UP:
            GetUp(); //具体调用的函数
            state = GO_TO_SCHOOL;  //状态的转移
            break;
        case GO_TO_SCHOOL:
            Go2School();
            state = HAVE_LUNCH;
            break;
        case HAVE_LUNCH:
            HaveLunch();
            state = GO_HOME;
            break;
            ...
        default:
            break;
        }
    }

    return 0;
}

三、使用函數指標實作FSM

使用函數指標實作FSM的想法：建立對應的狀態表和動作查詢表，依照狀態表、事件、動作表定位對應的動作處理函數，執行完成後再進行狀態的切換。

當然使用函數指標實現的FSM的過程還是比較費時費力，但是這一切都是值得的，因為當你的程式規模大時候，基於這種表結構的狀態機，維護程序起來也是得心應手。

下面給出一個使用函數指標實作的FSM的框架：

我們還是以「小明的一天」為例設計出該FSM。

先給出該FSM的狀態轉移圖：

下面講解關鍵部分程式碼實作

##首先我們定義出小明一天的活動狀態

//比如我们定义了小明一天的状态如下
enum
{
    GET_UP,
    GO_TO_SCHOOL,
    HAVE_LUNCH,
    DO_HOMEWORK,
    SLEEP,
};

我們也定義出會發生的事件

enum
{
    EVENT1 = 1,
    EVENT2,
    EVENT3,
};

定義狀態表的資料結構

typedef struct FsmTable_s
{
    int event;   //事件
    int CurState;  //当前状态
    void (*eventActFun)();  //函数指针
    int NextState;  //下一个状态
}FsmTable_t;

接下來定義出最重要FSM的狀態表，我們整個FSM就是根據這個定義好的表格來運作的。

FsmTable_t XiaoMingTable[] =
{
    //{到来的事件，当前的状态，将要要执行的函数，下一个状态}
    { EVENT1,  SLEEP,           GetUp,        GET_UP },
    { EVENT2,  GET_UP,          Go2School,    GO_TO_SCHOOL },
    { EVENT3,  GO_TO_SCHOOL,    HaveLunch,    HAVE_LUNCH },
    { EVENT1,  HAVE_LUNCH,      DoHomework,   DO_HOMEWORK },
    { EVENT2,  DO_HOMEWORK,     Go2Bed,       SLEEP },

    //add your codes here
};

狀態機的註冊、狀態轉移、事件處理的動作實現

/*状态机注册*/
void FSM_Regist(FSM_t* pFsm, FsmTable_t* pTable)
{
    pFsm->FsmTable = pTable;
}

/*状态迁移*/
void FSM_StateTransfer(FSM_t* pFsm, int state)
{
    pFsm->curState = state;
}

/*事件处理*/
void FSM_EventHandle(FSM_t* pFsm, int event)
{
    FsmTable_t* pActTable = pFsm->FsmTable;
    void (*eventActFun)() = NULL;  //函数指针初始化为空
    int NextState;
    int CurState = pFsm->curState;
    int flag = 0; //标识是否满足条件
    int i;

    /*获取当前动作函数*/
    for (i = 0; i<g_max_num; i++)
    {
        //当且仅当当前状态下来个指定的事件，我才执行它
        if (event == pActTable[i].event && CurState == pActTable[i].CurState)
        {
            flag = 1;
            eventActFun = pActTable[i].eventActFun;
            NextState = pActTable[i].NextState;
            break;
        }
    }


    if (flag) //如果满足条件了
    {
        /*动作执行*/
        if (eventActFun)
        {
            eventActFun();
        }

        //跳转到下一个状态
        FSM_StateTransfer(pFsm, NextState);
    }
    else
    {
        // do nothing
    }
}

主函數我們這樣寫，然後觀察狀態機的運轉情況

int main()
{
    FSM_t fsm;
    InitFsm(&fsm);
    int event = EVENT1; 
    //小明的一天,周而复始的一天又一天，进行着相同的活动
    while (1)
    {
        printf("event %d is coming...\n", event);
        FSM_EventHandle(&fsm, event);
        printf("fsm current state %d\n", fsm.curState);
        test(&event); 
        sleep(1);  //休眠1秒，方便观察
    }

    return 0;
}

看一看此狀態機跑起來的狀態轉移情況：

上面的圖可以看出，當且僅當在指定的狀態下來了指定的事件才會發生函數的執行以及狀態的轉移，否則不會發生狀態的跳躍。這種機制使得這個狀態機不停地自動運轉，有條不絮地完成任務。

與前兩種方法相比，使用函數指標實作FSM能很好用於大規模的切換流程，只要我們實作搭好了FSM框架，以後進行擴充就很簡單了（只要在狀態表裡加一行來寫入新的狀態處理就可以了）。

需要FSM完整程式碼的童鞋請造訪我的github

#

以上是有限狀態機FSM的實作與理解的詳細內容。更多資訊請關注PHP中文網其他相關文章！