有限状態マシン FSM の実装と理解

有限状態マシン (FSM) は、FSM と略され、有限状態とこれらの状態間の遷移や動作などの動作の数学的モデルを表し、コンピューター分野で広く使用されています。 FSM は、サーバー プログラミングにおいて、論理ユニット内の効率的なプログラミング方法であり、サーバーはさまざまな状態やメッセージ タイプに応じて対応する処理ロジックを実行できるため、プログラム ロジックが明確で理解しやすくなります。

有限状態マシンは通常どこで使用されますか?

プログラミング言語や自然言語を扱うトークナイザー、文法をボトムアップで解析するパーサー、
データを転送するためのさまざまな通信プロトコルの送信側と受信側、メッセージ処理、ゲームAIなどのアプリケーションシナリオを備えています。

ステートマシンの実装方法はいくつかありますが、それぞれのメリットとデメリットを一つずつ説明していきます。

1. if/else if ステートメントを使用して FSM を実装する

if/else if ステートメントを使用することは、多数の 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判定文が多用されているため、非常にローエンドでコードが肥大化していると感じませんか。このステート マシンの状態はわずかであり、コードの拡張は明らかではありませんが、処理する必要がある状態が数十ある場合、このステート マシンのコードは読みにくくなります。

2. switch を使用して FSM を実装する

switch ステートメントを使用して実装された FSM の構造がより明確になり、その欠点も明らかになります。この設計方法は単純ですが、多くの判断を経て処理されるため、小規模なアプリケーションに適しています。 -scale 状態切り替え処理ですが、規模が大きくなると拡張や維持が困難になります。

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. 関数ポインターを使用して FSM を実装する

関数ポインターを使用して FSM を実装するというアイデア: 対応する状態テーブルとアクション クエリ テーブルを確立し、状態テーブル、イベント、およびアクションテーブルを参照し、実行完了後に続行します。 ステータス切り替え。

もちろん、関数ポインターを使用して FSM を実装するプロセスは依然として比較的時間と労力がかかりますが、プログラムが大規模な場合、このテーブル構造に基づくステート マシンによって簡単に実行できるため、それだけの価値はあります。プログラムを維持するため。

以下は、関数ポインターを使用して実装された FSM のフレームワークです:

この FSM を設計する例として、今でも「暁明の日」を使用しています。

最初に FSM の状態遷移図を示します:

コード実装の重要な部分を以下で説明します

まず、Xiao Ming の 1 日のアクティビティ ステータスを定義します

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

このようにmain関数を書いて、ステートマシンの動作を観察していきます

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

の状態転送を見てみましょう実行中のステート マシン:

上の図からわかるように、関数の実行と状態の転送は、指定されたイベントが指定された状態で発生した場合にのみ発生します。それ以外の場合は、ステートジャンプは発生しません。このメカニズムにより、ステート マシンが自動的かつ継続的に実行され、タスクが順序どおりに完了します。

最初の 2 つの方法と比較して、関数ポインターを使用して FSM を実装する方法は、FSM フレームワークを実装する限り、将来の拡張が非常に簡単になります (状態テーブルに行を追加するだけです)。 ) 新しい状態ハンドラーを作成するだけです)。

FSM の完全なコードが必要な場合は、私の github にアクセスしてください

以上が有限状態マシン FSM の実装と理解の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。