C語言 有限狀態機

狀態 存儲關于過去的信息，就是說：它反映從系統開始到現在時刻的輸入變化。轉移指示 狀態 變更，并且用必須滿足來確使轉移發生的條件來描述它。動作是在給定時刻要進行的活動的描述。有多種類型的動作：

進入動作（entry action）：在進入 狀態 時進行

退出動作：在退出 狀態 時進行

輸入動作：依賴于當前 狀態 和輸入條件進行

轉移動作：在進行特定轉移時進行

下面展示最常見的表示：當前 狀態 （B）和條件（Y）的組合指示出下一個狀態（C）。完整的動作信息可以只使用腳注來增加。包括完整動作信息的FSM 定義可以使用狀態表。

除了建模這里介紹的反應系統之外， 有限狀態自動機 在很多不同領域中是重要的，包括 電子工程 、? 語言學 、 計算機科學 、 哲學 、 生物學 、 數學 和 邏輯學 。有限 狀態 機是在 自動機理論 和 計算理論 中研究的一類自動機。在 計算機科學 中，有限 狀態 機被廣泛用于建模應用行為、硬件電路系統設計、軟件工程，編譯器、網絡協議、和計算與語言的研究。

地位

在數字電路系統中，有限 狀態 機是一種十分重要的 時序邏輯電路 模塊

作用

它對 數字系統 的設計具有十分重要的作用。

有限 狀態 機是指輸出取決于過去輸入部分和當前輸入部分的 時序邏輯電路 。一般來說，除了輸入部分和輸出部分外，有限 狀態 機還含有一組具有“記憶”功能的 寄存器 ，這些寄存器的功能是記憶有限狀態機的內部狀態，它們常被稱為狀態寄存器。在有限 狀態 機中，狀態 寄存器 的的下一個狀態不僅與輸入信號有關，而且還與該寄存器的當前狀態有關，因此有限狀態機又可以認為是組合邏輯和寄存器邏輯的一種組合。其中， 寄存器 邏輯的功能是存儲有限 狀態 機的內部狀態；而組合邏輯又可以分為次態邏輯和輸出邏輯兩部分，次態邏輯的功能是確定有限狀態機的下一個狀態，輸出邏輯的功能是確定有限狀態機的輸出。

分類

在實際的應用中，根據有限 狀態 機是否使用輸入信號，設計人員經常將其分為Moore型有限狀態機和Mealy型有限狀態機兩種類型。1Moore型有限 狀態 機其輸出信號僅與當前狀態有關，即可以把Moore型有限狀態的輸出看成是當前狀態的函數。2 Mealy型有限 狀態 機其輸出信號不僅與當前狀態有關，而且還與所有的輸入信號有關，即可以把Mealy型有限狀態機的輸出看成是當前狀態和所有輸入信號的函數。

編程

有限狀態機體現了兩點：首先是離散的，然后是有限的。

State：

狀態 這個詞有些難以定義，狀態存儲關于過去的信息，就是說它反映從系統開始到現在時刻的輸入變化。

Actions & Transitions：

轉換指示 狀態 變更，并且用必須滿足來確使轉移發生的條件來描述它。動作是在給定時刻要進行的活動的描述。

Guards:

檢測器出現的原因是為了檢測是否滿足從一個 狀態 切換到另外一個狀態的條件。

Event：

事件，又見事件，籠統說來，對系統重要的某件事情被稱為事件。

恩，就這些了，有些迷惑么:),恩，我們來理清一下思路：先從事件說起，事件是有生命

的，它經歷:

1).被產生(被接受，等待被處理，一般放入事件隊列)

2).被分發(從事件隊列取出，分發到響應的 狀態 機處理)

3).死亡(當 狀態 機處理了該事件，它隨之死亡)

從一個 狀態 切換到另外一個狀態被稱為狀態轉換，而引起它的事件稱為觸發事件.(可以看到，不是所有的事件都會引起 狀態 的轉換).

提到 狀態 轉換，不能不提及檢測器(Guards)，只有當檢測器的值為TRUE時候，才能啟動轉換

應用

常見的計算機就是使用有限狀態機作為計算模型的：對于內存的不同狀態，CPU通過讀取內存值進行計算，更新內存中的狀態。CPU還通過消息總線接受外部輸入設備（如鍵盤、鼠標）的指令，計算后更改內存中的狀態，計算結果輸出到外部顯示設備（如顯示器），以及持久化存儲在硬盤。

電腦游戲設計中也經常使用有限狀態機模型。以水果忍者游戲為例，游戲中水果的狀態是有限狀態，其運行軌跡是由模擬物理運動規律的計算公式運算而成的，一個香蕉拋起來后會按照拋物線運行，其每一幀位置變化都是一個狀態的改變，狀態改變通過計算公式來決定。當然作為游戲不會僅僅這么簡單，如果這么簡單就是動畫了，游戲還有復雜的人機交互事件，比如用手在屏幕上“切”了水果，水果感知到這個事件后，會按照程序邏輯進入爆炸狀態。

1、狀態機的要素

狀態機可歸納為4個要素，即現態、條件、動作、次態。“現態”和“條件”是因，“動作”和“次態”是果。詳解如下：

①現態：是指當前所處的狀態。

②條件：又稱為“事件”。當一個條件被滿足，將會觸發一個動作，或者執行一次狀態的遷移。

③動作：條件滿足后執行的動作。動作執行完畢后，可以遷移到新的狀態，也可以仍舊保持原狀態。動作不是必需的，當條件滿足后，也可以不執行任何動作，直接遷移到新狀態。

④次態：條件滿足后要遷往的新狀態。“次態”是相對于“現態”而言的，“次態”一旦被激活，就轉變成新的“現態”了。

這里需要注意的兩個問題：

1、避免把某個“程序動作”當作是一種“狀態”來處理。那么如何區分“動作”和“狀態”？“動作”是不穩定的，即使沒有條件的觸發，“動作”一旦執行完畢就結束了；而“狀態”是相對穩定的，如果沒有外部條件的觸發，一個狀態會一直持續下去。

2、狀態劃分時漏掉一些狀態，導致跳轉邏輯不完整。

所以維護上述一張狀態表就非常必要，而且有意義了。從表中可以直觀看出那些狀態直接存在跳轉路徑，那些狀態直接不存在。如果不存在，就把對應的單元格置灰。每次寫代碼之前先把表格填寫好，并且對置灰的部分重點review，看看是否有“漏態”，然后才是寫代碼。QA拿到這張表格之后，寫測試用例也是手到擒來。

有限狀態機FSM

思想廣泛應用于硬件控制電路設計，也是軟件上常用的一種處理方法(軟件上稱為FMM--有限消息機)。它把復雜的控制邏輯分解成有限個穩定狀態，在每個狀態上判斷事件，變連續處理為離散數字處理，符合計算機的工作特點。同時，因為有限狀態機具有有限個狀態，所以可以在實際的工程上實現。但這并不意味著其只能進行有限次的處理，相反，有限狀態機是閉環系統，有限無窮，可以用有限的狀態，處理無窮的事務。

有限狀態機的工作原理如圖1所示，發生事件(event)后，根據當前狀態(cur_state)，決定執行的動作(action)，并設置下一個狀態號(nxt_state)。

-------------

| |-------->執行動作action

發生事件event ----->| cur_state |

| |-------->設置下一狀態號nxt_state

-------------

當前狀態

圖1 有限狀態機工作原理

e0/a0

--->--

| |

-------->----------

e0/a0 | | S0 |-----

| -<------------ | e1/a1

| | e2/a2 V

---------- ----------

| S2 |-----<-----| S1 |

---------- e2/a2 ----------

圖2 一個有限狀態機實例

--------------------------------------------

當前狀態 s0 s1 s2 | 事件

--------------------------------------------

a0/s0 -- a0/s0 | e0

--------------------------------------------

a1/s1 -- -- | e1

--------------------------------------------

a2/s2 a2/s2 -- | e2

--------------------------------------------

表1 圖2狀態機實例的二維表格表示(動作/下一狀態)

圖2為一個狀態機實例的狀態轉移圖，它的含義是：

在s0狀態，如果發生e0事件，那么就執行a0動作，并保持狀態不變；

如果發生e1事件，那么就執行a1動作，并將狀態轉移到s1態；

如果發生e2事件，那么就執行a2動作，并將狀態轉移到s2態；

在s1狀態，如果發生e2事件，那么就執行a2動作，并將狀態轉移到s2態；

在s2狀態，如果發生e0事件，那么就執行a0動作，并將狀態轉移到s0態；

有限狀態機不僅能夠用狀態轉移圖表示，還可以用二維的表格代表。一般將當前狀態號寫在橫行上，將事件寫在縱列上，如表1所示。其中“--”表示空(不執行動作，也不進行狀態轉移)，“an/sn”表示執行動作an,同時將下一狀態設置為sn。表1和圖2表示 的含義是完全相同的。

觀察表1可知，狀態機可以用兩種方法實現：豎著寫(在狀態中判斷事件)和橫著寫(在事件中判斷狀態)。這兩種實現在本質上是完全等效的，但在實際操作中，效果卻截然 不同。

豎著寫C代碼片段

cur_state = nxt_state;

switch(cur_state){ //在當前狀態中判斷事件

case s0: //在s0狀態

if(e0_event){ //如果發生e0事件，那么就執行a0動作，

并保持狀態不變；

執行a0動作;

//nxt_state = s0; //因為狀態號是自身，所以可以刪除此句

，以提高運行速度。

}

else if(e1_event){ //如果發生e1事件，那么就執行a1動作，

并將狀態轉移到s1態；

執行a1動作;

nxt_state = s1;

}

else if(e2_event){ //如果發生e2事件，那么就執行a2動作，

并將狀態轉移到s2態；

執行a2動作;

nxt_state = s2;

}

break;

case s1: //在s1狀態

if(e2_event){ //如果發生e2事件，那么就執行a2動作，

并將狀態轉移到s2態；

執行a2動作;

nxt_state = s2;

}

break;

case s2: //在s2狀態

if(e0_event){ //如果發生e0事件，那么就執行a0動作，

并將狀態轉移到s0態；

執行a0動作;

nxt_state = s0;

}

}

橫著寫(在事件中判斷狀態)C代碼片段

//e0事件發生時，執行的函數

void e0_event_function(int * nxt_state)

{

int cur_state;

cur_state = *nxt_state;

switch(cur_state){

case s0: //觀察表1，在e0事件發生時，s1處為空

case s2:

執行a0動作;

*nxt_state = s0;

}

}

//e1事件發生時，執行的函數

void e1_event_function(int * nxt_state)

{

int cur_state;

cur_state = *nxt_state;

switch(cur_state){

case s0: //觀察表1，在e1事件發生時，s1和s2處為

空

執行a1動作;

*nxt_state = s1;

}

}

//e2事件發生時，執行的函數

void e2_event_function(int * nxt_state)

{

int cur_state;

cur_state = *nxt_state;

switch(cur_state){

case s0: //觀察表1，在e2事件發生時，s2處為空

case s1:

執行a2動作;

*nxt_state = s2;

}

}

5G游戲 C 語言

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。