Implémentation et compréhension de la machine à états finis FSM

La machine à états finis (FSM), appelée FSM, représente un modèle mathématique d'états finis et de comportements tels que les transitions et les actions entre ces états. Elle est largement utilisée dans le domaine informatique. FSM est une méthode de programmation efficace au sein d'une unité logique. Dans la programmation serveur, le serveur peut effectuer la logique de traitement correspondante en fonction de différents états ou types de messages, rendant la logique du programme claire et facile à comprendre.

Où les machines à états finis sont-elles généralement utilisées ?

Un tokenizer qui gère le langage de programmation ou le langage naturel, un analyseur qui analyse la grammaire de bas en haut,
L'expéditeur et le destinataire de divers protocoles de communication transfèrent des données, qui ont des applications dans le traitement des messages, scène de jeu IA, etc.

Il existe plusieurs méthodes d'implémentation des machines à états. Je vais vous expliquer leurs avantages et inconvénients un par un.

1. FSM implémenté à l'aide de l'instruction if/else if

Utiliser l'instruction if/else if est le moyen le plus simple et le plus compréhensible d'implémenter FSM, il nous suffit de passer par beaucoup de if / else L'instruction if est utilisée pour déterminer la valeur d'état afin d'effectuer le traitement logique correspondant.

Regardez l'exemple ci-dessous. Nous utilisons un grand nombre d'instructions if/else if pour implémenter une machine à états simple, effectuer les opérations correspondantes en fonction de différents états et réaliser des sauts d'état.

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

Après avoir lu les exemples ci-dessus, qu'en pensez-vous ? Pensez-vous que même si le programme est simple et facile à comprendre, il utilise un grand nombre d'instructions de jugement if, ce qui rend le code très bas de gamme et le code est gonflé. Il n'y a que quelques états de cette machine à états, et l'expansion du code n'est pas évidente. Cependant, si nous devons traiter des dizaines d'états, le code de cette machine à états sera difficile à lire.

2. Utilisez switch pour implémenter FSM

La structure du FSM implémentée à l'aide de l'instruction switch devient plus claire et ses défauts sont également évidents : bien que cette méthode de conception soit simple, grâce à beaucoup de traitement de jugement convient aux processus de changement d'état à petite échelle, mais il est difficile de l'étendre et de le maintenir si l'échelle augmente.

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. Utiliser des pointeurs de fonction pour implémenter FSM

L'idée d'utiliser des pointeurs de fonction pour implémenter FSM : établir la table d'état et la table de requête d'action correspondantes, et localiser l'état correspondant table, table d'événements et table d'actions La fonction de traitement des actions changera d'état une fois l'exécution terminée.

Bien sûr, le processus d'utilisation des pointeurs de fonction pour implémenter FSM est encore relativement long et laborieux, mais cela en vaut la peine, car lorsque votre programme est à grande échelle, la machine d'état basée sur cette table La structure sera également difficile à maintenir.

Ce qui suit est un cadre de FSM implémenté à l'aide de pointeurs de fonction :

Nous utilisons toujours "Xiao Ming's Day" comme exemple pour concevoir ce FSM.

Donnez d'abord le diagramme de transition d'état du FSM :

Ce qui suit explique la partie clé de l'implémentation du code

Nous définissons d'abord le statut d'activité de Xiao Ming pour une journée

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

Nous définissons également les événements qui se produiront

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

Définissons la structure des données de la table d'état

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

Ensuite, définissez la table d'état FSM la plus importante, l'ensemble de notre FSM fonctionne sur la base de cette table définie.

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

Mise en œuvre de l'action de l'enregistrement de la machine à états, du transfert d'état et du traitement des événements

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

Nous écrivons la fonction principale comme ceci, puis observons le fonctionnement de la machine à états

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

Jetez un œil à la transition d'état de la machine à états lorsqu'elle est en cours d'exécution :

Comme le montre la figure ci-dessus, si et seulement si l'état spécifié descend dans l'état spécifié L'exécution de la fonction et le transfert de l'état n'auront lieu que lorsque l'événement se produira, sinon le saut d'état n'aura pas lieu. Ce mécanisme permet à la machine d'état de fonctionner automatiquement et en continu pour accomplir la tâche de manière ordonnée.

Par rapport aux deux premières méthodes, l'utilisation de pointeurs de fonction pour implémenter FSM peut être bien utilisée pour les processus de commutation à grande échelle. Tant que nous implémentons le framework FSM, il sera très simple de l'étendre à l'avenir (. tant que l'état ajoute simplement une ligne au tableau pour écrire le nouveau traitement de l'état).

Si vous avez besoin du code complet de FSM, veuillez visiter mon github

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!