Implementation and understanding of finite state machine FSM

Finite state machine (FSM), referred to as FSM, represents a mathematical model of finite states and behaviors such as transitions and actions between these states. It is widely used in the computer field. FSM is an efficient programming method within a logical unit. In server programming, the server can perform corresponding processing logic according to different states or message types, making the program logic clear and easy to understand.

Where are finite state machines usually used?

Tokenizer for processing programming language or natural language, parser for bottom-up parsing grammar,
Various communication protocols sender and receiver to transfer data, which has applications in message processing, game AI, etc. Scenes.

There are several implementation methods for state machines. I will explain their advantages and disadvantages one by one.

1. FSM implemented using if/else if statements

Using if/else if statements are the simplest and most understandable method to implement FSM. We only need to use a large number of if /else The if statement is used to determine the status value to perform corresponding logical processing.

Look at the example below. We use a large number of if/else if statements to implement a simple state machine, perform corresponding operations according to different states, and realize state jumps.

//比如我们定义了小明一天的状态如下
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;
}

After reading the above example, what do you think? Do you feel that although the program is simple and easy to understand, it uses a large number of if judgment statements, which makes the code very low-end and the code is bloated. There are only a few states of this state machine, and the code expansion is not obvious. However, if there are dozens of states that we need to process, the code of this state machine will be difficult to read.

2. Use switch to implement FSM

The structure of FSM implemented using switch statements becomes clearer, and its shortcomings are also obvious: although this design method is simple, through a lot of Judgment processing is suitable for small-scale state switching processes, but it is difficult to expand and maintain if the scale increases.

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;
}

3. Use function pointers to implement FSM

The idea of ​​using function pointers to implement FSM: establish the corresponding state table and action query table, and locate the corresponding action according to the state table, event, and action table The processing function is executed and then the state is switched.

Of course, the process of using function pointers to implement FSM is still relatively time-consuming and laborious, but it is all worth it, because when your program is large-scale, the state machine based on this table structure will also be difficult to maintain. Handy.

The following is a framework of FSM implemented using function pointers:

We still use "Xiao Ming's Day" as an example to design this FSM.

First give the state transition diagram of the FSM:

The key part of the code implementation is explained below

First we define Xiao Ming’s activity status for a day

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

We also define the events that will occur

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

Define the data structure of the status table

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

Next, define the status table of the most important FSM , our entire FSM operates based on this defined table.

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
};

Registration of state machine, state transfer, and event processing action implementation

/*状态机注册*/
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
    }
}

We write the main function like this, and then observe the operation of the state machine

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;
}

Take a look The state transition of the state machine when it is running:

As can be seen from the above figure, the function will occur when and only when the specified event occurs in the specified state. Execution and state transfer, otherwise the state jump will not occur. This mechanism makes the state machine run automatically and continuously to complete the task in an orderly manner.

Compared with the first two methods, using function pointers to implement FSM can be well used for large-scale switching processes. As long as we implement the FSM framework, future expansion will be very simple (as long as the state Just add a row to the table to write the new status processing).

If you need the complete code of FSM, please visit my github

The above is the detailed content of Implementation and understanding of finite state machine FSM. For more information, please follow other related articles on the PHP Chinese website!