Implementierung und Verständnis des Finite-State-Machine-FSM

Finite State Machine (FSM), kurz FSM genannt, stellt ein mathematisches Modell endlicher Zustände und Verhaltensweisen wie Übergänge und Aktionen zwischen diesen Zuständen dar. Es wird häufig im Computerbereich verwendet. FSM ist eine effiziente Programmiermethode innerhalb einer logischen Einheit. Bei der Serverprogrammierung kann der Server entsprechende Verarbeitungslogik entsprechend verschiedenen Zuständen oder Nachrichtentypen ausführen, wodurch die Programmlogik klar und leicht verständlich wird.

Wo werden Finite-State-Maschinen normalerweise verwendet?

Ein Tokenizer, der Programmiersprache oder natürliche Sprache verarbeitet, ein Parser, der die Grammatik von unten nach oben analysiert,
Der Sender und Empfänger verschiedener Kommunikationsprotokolle überträgt Daten, die in der Nachrichtenverarbeitung Anwendung finden, Spiel-KI usw. Szene.

Es gibt verschiedene Implementierungsmethoden für Zustandsmaschinen. Ich werde deren Vor- und Nachteile einzeln erläutern.

1. FSM implementiert mit if/else if-Anweisungen

Die Verwendung von if/else if-Anweisungen ist die einfachste und verständlichste Möglichkeit, FSM zu implementieren. Wir müssen nur viele if/else if-Anweisungen durchgehen. else Die if-Anweisung wird verwendet, um den Statuswert zu bestimmen und die entsprechende logische Verarbeitung durchzuführen.

Sehen Sie sich das folgende Beispiel an. Wir verwenden eine große Anzahl von if/else if-Anweisungen, um eine einfache Zustandsmaschine zu implementieren, entsprechende Operationen entsprechend verschiedenen Zuständen auszuführen und Zustandssprünge zu realisieren.

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

Was denken Sie, nachdem Sie die obigen Beispiele gelesen haben? Haben Sie das Gefühl, dass das Programm zwar einfach und leicht zu verstehen ist, aber eine große Anzahl von if-Beurteilungsanweisungen verwendet, was den Code sehr niedrig macht und den Code aufbläht? Es gibt nur wenige Zustände dieser Zustandsmaschine und die Codeerweiterung ist nicht offensichtlich. Wenn wir jedoch Dutzende Zustände verarbeiten müssen, ist der Code dieser Zustandsmaschine schwer zu lesen.

2. Verwenden Sie Switch, um FSM zu implementieren

Die Struktur von FSM, das mithilfe der Switch-Anweisung implementiert wird, wird klarer und seine Mängel sind ebenfalls offensichtlich: Obwohl diese Entwurfsmethode einfach ist, erfordert sie viel Beurteilungsverarbeitung eignet sich für Zustandswechselprozesse im kleinen Maßstab, ist jedoch bei Vergrößerung des Maßstabs schwierig zu erweitern und aufrechtzuerhalten.

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. Verwenden Sie Funktionszeiger, um FSM zu implementieren

Die Idee, Funktionszeiger zu verwenden, um FSM zu implementieren: Erstellen Sie die entsprechende Statustabelle und Aktionsabfragetabelle und suchen Sie den entsprechenden Status Tabelle, Ereignis und Aktionstabelle Die Aktionsverarbeitungsfunktion wechselt den Status, nachdem die Ausführung abgeschlossen ist.

Natürlich ist die Verwendung von Funktionszeigern zur Implementierung von FSM immer noch zeitaufwändig und arbeitsintensiv, aber es lohnt sich, denn wenn Ihr Programm groß ist, basiert die Zustandsmaschine darauf Auch die Tischstruktur wird schwer zu pflegen sein.

Das Folgende ist ein FSM-Framework, das mithilfe von Funktionszeigern implementiert wurde:

Wir verwenden immer noch „Xiao Ming's Day“ als Beispiel, um dieses FSM zu entwerfen.

Geben Sie zunächst das Zustandsübergangsdiagramm des FSM an:

Im Folgenden wird der Schlüsselteil der Codeimplementierung erläutert

Zuerst definieren wir den Aktivitätsstatus von Xiao Ming für einen Tag

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

Wir definieren auch die Ereignisse, die auftreten werden

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

Definieren Sie die Datenstruktur der Statustabelle

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

Dann definieren Sie die wichtigste FSM-Statustabelle. Unser gesamter FSM arbeitet auf Basis dieser definierten Tabelle.

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

Aktionsimplementierung der Zustandsmaschinenregistrierung, Zustandsübertragung und Ereignisverarbeitung

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

Wir schreiben die Hauptfunktion so und beobachten dann den Betrieb der Zustandsmaschine

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

Sehen Sie sich den Zustandsübergang der Zustandsmaschine an, wenn sie läuft:

Wie aus der obigen Abbildung ersichtlich ist, genau dann Wenn der angegebene Zustand in den angegebenen Zustand übergeht, erfolgt die Ausführung der Funktion und die Übertragung des Zustands nur dann, wenn das Ereignis eintritt, andernfalls erfolgt der Sprung des Zustands nicht. Dieser Mechanismus sorgt dafür, dass die Zustandsmaschine automatisch und kontinuierlich läuft, um die Aufgabe ordnungsgemäß abzuschließen.

Im Vergleich zu den ersten beiden Methoden kann die Verwendung von Funktionszeigern zur Implementierung von FSM gut für umfangreiche Switching-Prozesse verwendet werden. Solange wir das FSM-Framework implementieren, wird die zukünftige Erweiterung sehr einfach sein (solange die state Fügen Sie einfach eine Zeile zur Tabelle hinzu, um den neuen Status zu schreiben (Verarbeitung).

Wenn Sie den vollständigen Code von FSM benötigen, besuchen Sie bitte meinen Github

Das obige ist der detaillierte Inhalt vonImplementierung und Verständnis des Finite-State-Machine-FSM. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!