關(guān)注、星標(biāo)公眾號(hào)，直達(dá)精彩內(nèi)容

來源：https://www.cnblogs.com/skyfsm/p/7071386.html

作者：Madcola

有限狀態(tài)機(jī)（finite state machine）簡(jiǎn)稱 FSM，表示有限個(gè)狀態(tài)及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作等行為的數(shù)學(xué)模型，在計(jì)算機(jī)領(lǐng)域有著廣泛的應(yīng)用。FSM 是一種邏輯單元內(nèi)部的一種高效編程方法，在服務(wù)器編程中，服務(wù)器可以根據(jù)不同狀態(tài)或者消息類型進(jìn)行相應(yīng)的處理邏輯，使得程序邏輯清晰易懂。

那有限狀態(tài)機(jī)通常在什么地方被用到？

處理程序語言或者自然語言的 tokenizer, 自底向上解析語法的 parser，

各種通信協(xié)議發(fā)送方和接受方傳遞數(shù)據(jù)對(duì)消息處理，游戲 AI 等都有應(yīng)用場(chǎng)景。

狀態(tài)機(jī)有以下幾種實(shí)現(xiàn)方法，我將一一闡述它們的優(yōu)缺點(diǎn)。

一、使用 if/else if 語句實(shí)現(xiàn)的 FSM

使用 if/else if 語句是實(shí)現(xiàn)的 FSM 最簡(jiǎn)單最易懂的方法，我們只需要通過大量的 if /else if 語句來判斷狀態(tài)值來執(zhí)行相應(yīng)的邏輯處理。

看看下面的例子，我們使用了大量的 if/else if 語句實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的狀態(tài)機(jī)，做到了根據(jù)狀態(tài)的不同執(zhí)行相應(yīng)的操作，并且實(shí)現(xiàn)了狀態(tài)的跳轉(zhuǎn)。

1. enum

2. {

3. ? ?GET_UP,

4. ? ?GO_TO_SCHOOL,

5. ? ?HAVE_LUNCH,

6. ? ?GO_HOME,

7. ? ?DO_HOMEWORK,

8. ? ?SLEEP,

9. };

10. 
    

11. 
    

12. int main()

13. {

14. ? ?int state = GET_UP;

15. ? ?//小明的一天

16. ? ?while (1)

17. ? ?{

18. ? ? ? ?if (state == GET_UP)

19. ? ? ? ?{

20. ? ? ? ? ? ?GetUp(); //具體調(diào)用的函數(shù)

21. ? ? ? ? ? ?state = GO_TO_SCHOOL; ?//狀態(tài)的轉(zhuǎn)移

22. ? ? ? ?}

23. ? ? ? ?else if (state == GO_TO_SCHOOL)

24. ? ? ? ?{

25. ? ? ? ? ? ?Go2School();

26. ? ? ? ? ? ?state = HAVE_LUNCH;

27. ? ? ? ?}

28. ? ? ? ?else if (state == HAVE_LUNCH)

29. ? ? ? ?{

30. ? ? ? ? ? ?HaveLunch();

31. ? ? ? ?}

32. ? ? ? ?...

33. ? ? ? ?else if (state == SLEEP)

34. ? ? ? ?{

35. ? ? ? ? ? ?Go2Bed();

36. ? ? ? ? ? ?state = GET_UP;

37. ? ? ? ?}

38. ? ?}

39. 
    

40. ? ?return 0;

41. }


????看完上面的例子，大家有什么感受？是不是感覺程序雖然簡(jiǎn)單易懂，但是使用了大量的 if 判斷語句，使得代碼很低端，同時(shí)代碼膨脹的比較厲害。這個(gè)狀態(tài)機(jī)的狀態(tài)僅有幾個(gè)，代碼膨脹并不明顯，但是如果我們需要處理的狀態(tài)有數(shù)十個(gè)的話，該狀態(tài)機(jī)的代碼就不好讀了。

二、使用 switch 實(shí)現(xiàn) FSM

使用 switch 語句實(shí)現(xiàn)的 FSM 的結(jié)構(gòu)變得更為清晰了，其缺點(diǎn)也是明顯的：這種設(shè)計(jì)方法雖然簡(jiǎn)單，通過一大堆判斷來處理，適合小規(guī)模的狀態(tài)切換流程，但如果規(guī)模擴(kuò)大難以擴(kuò)展和維護(hù)。

1. {

2. ? ?int state = GET_UP;

3. ? ?//小明的一天

4. ? ?while (1)

5. ? ?{

6. 
   

7. ? ? ? ?switch(state)

8. ? ? ? ?{

9. ? ? ? ?case GET_UP:

10. ? ? ? ? ? ?GetUp(); //具體調(diào)用的函數(shù)

11. ? ? ? ? ? ?state = GO_TO_SCHOOL; ?//狀態(tài)的轉(zhuǎn)移

12. ? ? ? ? ? ?break;

13. ? ? ? ?case GO_TO_SCHOOL:

14. ? ? ? ? ? ?Go2School();

15. ? ? ? ? ? ?state = HAVE_LUNCH;

16. ? ? ? ? ? ?break;

17. ? ? ? ?case HAVE_LUNCH:

18. ? ? ? ? ? ?HaveLunch();

19. ? ? ? ? ? ?state = GO_HOME;

20. ? ? ? ? ? ?break;

21. ? ? ? ? ? ?...

22. ? ? ? ?default:

23. ? ? ? ? ? ?break;

24. ? ? ? ?}

25. ? ?}

26. 
    

27. ? ?return 0;

28. }

三、使用函數(shù)指針實(shí)現(xiàn) FSM

使用函數(shù)指針實(shí)現(xiàn) FSM 的思路：建立相應(yīng)的狀態(tài)表和動(dòng)作查詢表，根據(jù)狀態(tài)表、事件、動(dòng)作表定位相應(yīng)的動(dòng)作處理函數(shù)，執(zhí)行完成后再進(jìn)行狀態(tài)的切換。

當(dāng)然使用函數(shù)指針實(shí)現(xiàn)的 FSM 的過程還是比較費(fèi)時(shí)費(fèi)力，但是這一切都是值得的，因?yàn)楫?dāng)你的程序規(guī)模大時(shí)候，基于這種表結(jié)構(gòu)的狀態(tài)機(jī)，維護(hù)程序起來也是得心應(yīng)手。

下面給出一個(gè)使用函數(shù)指針實(shí)現(xiàn)的 FSM 的框架：

我們還是以 “小明的一天” 為例設(shè)計(jì)出該 FSM。

先給出該 FSM 的狀態(tài)轉(zhuǎn)移圖：

下面講解關(guān)鍵部分代碼實(shí)現(xiàn)

首先我們定義出小明一天的活動(dòng)狀態(tài)：

//比如我們定義了小明一天的狀態(tài)如下

1. enum

2. {

3. ? ?GET_UP,

4. ? ?GO_TO_SCHOOL,

5. ? ?HAVE_LUNCH,

6. ? ?DO_HOMEWORK,

7. ? ?SLEEP,

8. };

我們也定義出會(huì)發(fā)生的事件

1. {

2. ? ?EVENT1 = 1,

3. ? ?EVENT2,

4. ? ?EVENT3,

5. };

定義狀態(tài)表的數(shù)據(jù)結(jié)構(gòu)

1. typedef struct FsmTable_s

2. {

3. ? ?int event; ? //事件

4. ? ?int CurState; ?//當(dāng)前狀態(tài)

5. ? ?void (*eventActFun)(); ?//函數(shù)指針

6. ? ?int NextState; ?//下一個(gè)狀態(tài)

7. }FsmTable_t;

8. 
   

接下來定義出最重要 FSM 的狀態(tài)表，我們整個(gè) FSM 就是根據(jù)這個(gè)定義好的表來運(yùn)轉(zhuǎn)的。

1. FsmTable_t XiaoMingTable[] =

2. {

3. ? ?//{到來的事件，當(dāng)前的狀態(tài)，將要要執(zhí)行的函數(shù)，下一個(gè)狀態(tài)}

4. ? ?{ EVENT1, ?SLEEP, ? ? ? ? ? GetUp, ? ? ? ?GET_UP },

5. ? ?{ EVENT2, ?GET_UP, ? ? ? ? ?Go2School, ? ?GO_TO_SCHOOL },

6. ? ?{ EVENT3, ?GO_TO_SCHOOL, ? ?HaveLunch, ? ?HAVE_LUNCH },

7. ? ?{ EVENT1, ?HAVE_LUNCH, ? ? ?DoHomework, ? DO_HOMEWORK },

8. ? ?{ EVENT2, ?DO_HOMEWORK, ? ? Go2Bed, ? ? ? SLEEP },

9. 
   

10. ? ?//add your codes here

11. };

狀態(tài)機(jī)的注冊(cè)、狀態(tài)轉(zhuǎn)移、事件處理的動(dòng)作實(shí)現(xiàn)

1. /*狀態(tài)機(jī)注冊(cè)*/

2. void FSM_Regist(FSM_t* pFsm, FsmTable_t* pTable)

3. {

4. ? ?pFsm->FsmTable = pTable;

5. }

6. 
   

7. /*狀態(tài)遷移*/

8. void FSM_StateTransfer(FSM_t* pFsm, int state)

9. {

10. ? ?pFsm->curState = state;

11. }

12. 
    

13. /*事件處理*/

14. void FSM_EventHandle(FSM_t* pFsm, int event)

15. {

16. ? ?FsmTable_t* pActTable = pFsm->FsmTable;

17. ? ?void (*eventActFun)() = NULL; ?//函數(shù)指針初始化為空

18. ? ?int NextState;

19. ? ?int CurState = pFsm->curState;

20. ? ?int flag = 0; //標(biāo)識(shí)是否滿足條件

21. ? ?int i;

22. 
    

23. ? ?/*獲取當(dāng)前動(dòng)作函數(shù)*/

24. ? ?for (i = 0; i

25. ? ?{

26. ? ? ? ?//當(dāng)且僅當(dāng)當(dāng)前狀態(tài)下來個(gè)指定的事件，我才執(zhí)行它

27. ? ? ? ?if (event == pActTable[i].event