关于有限自动机的一篇不错的文章
作者?肖文鵬?(xiaowp@263.net), 自由軟件愛好者
簡介：?有限自動機（Finite Automata Machine）是計算機科學的重要基石，它在軟件開發領域內通常被稱作有限狀態機（Finite State Machine），是一種應用非常廣泛的軟件設計模式（Design Pattern）。本文介紹如何構建基于狀態機的軟件系統，以及如何利用Linux下的工具來自動生成實用的狀態機框架。
?
一、什么是狀態機
有限狀態機是一種用來進行對象行為建模的工具，其作用主要是描述對象在它的生命周期內所經歷的狀態序列，以及如何響應來自外界的各種事件。在面向對象的軟件系統中，一個對象無論多么簡單或者多么復雜，都必然會經歷一個從開始創建到最終消亡的完整過程，這通常被稱為對象的生命周期。一般說來，對象在其生命期內是不可能完全孤立的，它必須通過發送消息來影響其它對象，或者通過接受消息來改變自身。在大多數情況下，這些消息都只不過是些簡單的、同步的方法調用而已。例如，在銀行客戶管理系統中，客戶類（Customer）的實例在需要的時候，可能會調用帳戶（Account）類中定義的getBalance()方法。在這種簡單的情況下，類Customer并不需要一個有限狀態機來描述自己的行為，主要原因在于它當前的行為并不依賴于過去的某個狀態。
遺憾的是并不是所有情況都會如此簡單，事實上許多實用的軟件系統都必須維護一兩個非常關鍵的對象，它們通常具有非常復雜的狀態轉換關系，而且需要對來自外部的各種異步事件進行響應。例如，在VoIP電話系統中，電話類（Telephone）的實例必須能夠響應來自對方的隨機呼叫，來自用戶的按鍵事件，以及來自網絡的信令等。在處理這些消息時，類Telephone所要采取的行為完全依賴于它當前所處的狀態，因而此時使用狀態機就將是一個不錯的選擇。
游戲引擎是有限狀態機最為成功的應用領域之一，由于設計良好的狀態機能夠被用來取代部分的人工智能算法，因此游戲中的每個角色或者器件都有可能內嵌一個狀態機。考慮RPG游戲中城門這樣一個簡單的對象，它具有打開（Opened）、關閉（Closed）、上鎖（Locked）、解鎖（Unlocked）四種狀態，如圖1所示。當玩家到達一個處于狀態Locked的門時，如果此時他已經找到了用來開門的鑰匙，那么他就可以利用它將門的當前狀態轉變為Unlocked，進一步還可以通過旋轉門上的把手將其狀態轉變為Opened，從而成功地進入城內。
圖1 控制城門的狀態機
?
在描述有限狀態機時，狀態、事件、轉換和動作是經常會碰到的幾個基本概念。
- 狀態（State） 指的是對象在其生命周期中的一種狀況，處于某個特定狀態中的對象必然會滿足某些條件、執行某些動作或者是等待某些事件。
- 事件（Event） 指的是在時間和空間上占有一定位置，并且對狀態機來講是有意義的那些事情。事件通常會引起狀態的變遷，促使狀態機從一種狀態切換到另一種狀態。
- 轉換（Transition） 指的是兩個狀態之間的一種關系，表明對象將在第一個狀態中執行一定的動作，并將在某個事件發生同時某個特定條件滿足時進入第二個狀態。
- 動作（Action） 指的是狀態機中可以執行的那些原子操作，所謂原子操作指的是它們在運行的過程中不能被其他消息所中斷，必須一直執行下去。
回頁首
二、手工編寫狀態機
與其他常用的設計模式有所不同，程序員想要在自己的軟件系統中加入狀態機時，必須再額外編寫一部分用于邏輯控制的代碼，如果系統足夠復雜的話，這部分代碼實現和維護起來還是相當困難的。在實現有限狀態機時，使用switch語句是最簡單也是最直接的一種方式，其基本思路是為狀態機中的每一種狀態都設置一個case分支，專門用于對該狀態進行控制。下面的代碼示范了如何運用switch語句，來實現圖1中所示的狀態機：
| switch (state) { // 處理狀態Opened的分支 case (Opened): { // 執行動作Open open(); // 檢查是否有CloseDoor事件 if (closeDoor()) { // 當前狀態轉換為Closed changeState(Closed) } break; } // 處理狀態Closed的分支 case (Closed): { // 執行動作Close close(); // 檢查是否有OpenDoor事件 if (openDoor()) { // 當前狀態轉換為Opened changeState(Opened); } // 檢查是否有LockDoor事件 if (lockDoor()) { // 當前狀態轉換為Locked changeState(Locked); } break; } // 處理狀態Locked的分支 case (Locked): { // 執行動作Lock lock(); // 檢查是否有UnlockDoor事件 if (unlockDoor()) { // 當前狀態轉換為Unlocked changeState(Unlocked); } break; } // 處理狀態Unlocked的分支 case (Unlocked): { // 執行動作Unlock unlock(); // 檢查是否有LockDoor事件 if (lockDoor()) { // 當前狀態轉換為Locked changeState(Locked) } // 檢查是否有OpenDoor事件 if (openDoor()) { // 當前狀態轉換為Opened changeSate(Opened); } break; } } |
使用switch語句實現的有限狀態機的確能夠很好地工作，但代碼的可讀性并不十分理想，主要原因是在實現狀態之間的轉換時，檢查轉換條件和進行狀態轉換都是混雜在當前狀態中來完成的。例如，當城門處于Opened狀態時，需要在相應的case中調用closeDoor()函數來檢查是否有必要進行狀態轉換，如果是的話則還需要調用changeState()函數將當前狀態切換到Closed。顯然，如果在每種狀態下都需要分別檢查多個不同的轉換條件，并且需要根據檢查結果讓狀態機切換到不同的狀態，那么這樣的代碼將是枯燥而難懂的。從代碼重構的角度來講，此時更好的做法是引入checkStateChange()和performStateChange()兩個函數，專門用來對轉換條件進行檢查，以及激活轉換時所需要執行的各種動作。這樣一來，程序結構將變得更加清晰：
| switch (state) { // 處理狀態Opened的分支 case (Opened): { // 執行動作Open open(); // 檢查是否有激發狀態轉換的事件產生 if (checkStateChange()) { // 對狀態機的狀態進行轉換 performStateChange(); } break; } // 處理狀態Closed的分支 case (Closed): { // 執行動作Close close(); // 檢查是否有激發狀態轉換的事件產生 if (checkStateChange()) { // 對狀態機的狀態進行轉換 performStateChange(); } break; } // 處理狀態Locked的分支 case (Locked): { // 執行動作Lock lock(); // 檢查是否有激發狀態轉換的事件產生 if (checkStateChange()) { // 對狀態機的狀態進行轉換 performStateChange(); } break; } // 處理狀態Unlocked的分支 case (Unlocked): { // 執行動作Lock unlock(); // 檢查是否有激發狀態轉換的事件產生 if (checkStateChange()) { // 對狀態機的狀態進行轉換 performStateChange(); } break; } } |
但checkStateChange()和performStateChange()這兩個函數本身依然會在面對很復雜的狀態機時，內部邏輯變得異常臃腫，甚至可能是難以實現。
在很長一段時期內，使用switch語句一直是實現有限狀態機的唯一方法，甚至像編譯器這樣復雜的軟件系統，大部分也都直接采用這種實現方式。但之后隨著狀態機應用的逐漸深入，構造出來的狀態機越來越復雜，這種方法也開始面臨各種嚴峻的考驗，其中最令人頭痛的是如果狀態機中的狀態非常多，或者狀態之間的轉換關系異常復雜，那么簡單地使用switch語句構造出來的狀態機將是不可維護的。
回頁首
三、自動生成狀態機
為實用的軟件系統編寫狀態機并不是一件十分輕松的事情，特別是當狀態機本身比較復雜的時候尤其如此，許多有過類似經歷的程序員往往將其形容為"毫無創意"的過程，因為他們需要將大量的時間與精力傾注在如何管理好狀態機中的各種狀態上，而不是程序本身的運行邏輯。作為一種通用的軟件設計模式，各種軟件系統的狀態機之間肯定會或多或少地存在著一些共性，因此人們開始嘗試開發一些工具來自動生成有限狀態機的框架代碼，而在Linux下就有一個挺不錯的選擇──FSME（Finite State Machine Editor）。
圖2 可視化的FSME
?
FSME是一個基于Qt的有限狀態機工具，它能夠讓用戶通過圖形化的方式來對程序中所需要的狀態機進行建模，并且還能夠自動生成用C++或者Python實現的狀態機框架代碼。下面就以圖1中城門的狀態機為例，來介紹如何利用FSME來自動生成程序中所需要的狀態機代碼。
3.1狀態機建模
首先運行fsme命令來啟動狀態機編輯器，然后單擊工具欄上的"New"按鈕來創建一個新的狀態機。FSME中用于構建狀態機的基本元素一共有五種：事件（Event）、輸入（Input）、輸出（Output）、狀態（State）和轉換（Transition），在界面左邊的樹形列表中可以找到其中的四種。
- 狀態建模?
在FSME界面左邊的樹形列表中選擇"States"項，然后按下鍵盤上的Insert鍵來插入一個新的狀態，接著在右下方的"Name"文本框中輸入狀態的名稱，再在右上方的繪圖區域單擊該狀態所要放置的位置，一個新的狀態就創建好了。用同樣的辦法可以添加狀態機所需要的所有狀態，如圖3所示。?
圖3 狀態建模
?
- 事件建模?
在FSME界面左邊的樹形列表中選擇"Events"項，然后按下鍵盤上的Insert鍵來添加一個新的事件，接著在右下方的"Name"文本框中輸入事件的名稱，再單擊"Apply"按鈕，一個新的事件就創建好了。用同樣的辦法可以添加狀態機所需要的所有事件，如圖4所示。
圖4 事件建模
?
- 轉換建模?
狀態轉換是整個建模過程中最重要的一個部分，它用來定義有限狀態機中的一個狀態是如何切換到另一個狀態的。例如，當用來控制城門的狀態機處于Opened狀態時，如果此時有Close事件產生，那么狀態機的當前狀態將切換到Closed狀態，這樣一個完整的過程在狀態機模型中可以用closeDoor這樣一個轉換來進行描述。
要在FSME中添加這樣一個轉換，首先需要在界面左邊的樹形列表中選擇"States"下的"Opened"項，然后按下鍵盤上的Insert鍵來添加一個新的轉換，接著在右下角的"Name"文本框中輸入轉換的名字"closeDoor"，在"Condition"文本框中輸入"Close"表明觸發該轉換的條件是事件Close的產生，在"Target"下拉框中選擇"Closed"項表明該轉換發生后狀態機將被切換到Closed狀態，最后再單擊"Apply"按鈕，一個新的狀態轉換關系就定義好了，如圖5所示。用同樣的辦法可以添加狀態機所需要的所有轉換。
圖5 轉換建模
?
3.2 生成狀態機框架
使用FSME不僅能夠進行可視化的狀態機建模，更重要的是它還可以根據得到的模型自動生成用C++或者Python實現的狀態機框架。首先在FSME界面左邊的樹形列表中選擇"Root"項，然后在右下角的"Name"文本框中輸入狀態機的名字"DoorFSM"，再從"Initial State"下拉列表中選擇狀態"Opened"作為狀態機的初始化狀態，如圖6所示。
圖6 設置初始屬性
?
在將狀態機模型保存為door.fsm文件之后，使用下面的命令可以生成包含有狀態機定義的頭文件：
| [xiaowp@linuxgam code]$ fsmc door.fsm -d -o DoorFSM.h |
進一步還可以生成包含有狀態機實現的框架代碼：
| [xiaowp@linuxgam code]$ fsmc door.fsm -d -impl DoorFSM.h -o DoorFSM.cpp |
如果想對生成的狀態機進行驗證，只需要再手工編寫一段用于測試的代碼就可以了：
| /* * TestFSM.cpp * 測試生成的狀態機框架 */ #include "DoorFSM.h" int main() { DoorFSM door; door.A(DoorFSM::Close); door.A(DoorFSM::Lock); door.A(DoorFSM::Unlock); door.A(DoorFSM::Open); } |
有限狀態機是由事件來進行驅動的，在FSME生成的狀態機框架代碼中，方法A()可以被用來向狀態機發送相應的事件，從而提供狀態機正常運轉所需要的"動力"。狀態機負責在其內部維護一個事件隊列，所有到達的事件都會先被放到事件隊列中進行等候，從而能夠保證它們將按照到達的先后順序被依次處理。在處理每一個到達的事件時，狀態機都會根據自己當前所處的狀態，檢查與該狀態對應的轉換條件是否已經被滿足，如果滿足的話則激活相應的狀態轉換過程。
使用下面的命令能夠將生成的狀態機框架和測試代碼編譯成一個可執行文件：
| [xiaowp@linuxgam code]$ g++ DoorFSM.cpp TestFSM.cpp -o fsm |
由于之前在用fsmc命令生成狀態機代碼時使用了-d選項，生成的狀態機框架中會包含一定的調試信息，包括狀態機中每次狀態轉換時的激活事件、轉換前的狀態、所經歷的轉換、轉換后的狀態等，如下所示：
| [xiaowp@linuxgam code]$ ./fsm DoorFSM:event:'Close' DoorFSM:state:'Opened' DoorFSM:transition:'closeDoor' DoorFSM:new state:'Closed' DoorFSM:event:'Lock' DoorFSM:state:'Closed' DoorFSM:transition:'lockDoor' DoorFSM:new state:'Locked' DoorFSM:event:'Unlock' DoorFSM:state:'Locked' DoorFSM:transition:'unlockDoor' DoorFSM:new state:'Unlocked' DoorFSM:event:'Open' DoorFSM:state:'Unlocked' DoorFSM:transition:'openDoor' DoorFSM:new state:'Opened' |
3.3 定制狀態機
目前得到的狀態機已經能夠響應來自外部的各種事件，并適當地調整自己當前所處的狀態，也就是說已經實現了狀態機引擎的功能，接下來要做的就是根據應用的具體需求來進行定制，為狀態機加入與軟件系統本身相關的那些處理邏輯。在FSME中，與具體應用相關的操作稱為輸出（Output），它們實際上就是一些需要用戶給出具體實現的虛函數，自動生成的狀態機引擎負責在進入或者退出某個狀態時調用它們。
仍然以控制城門的那個狀態機為例，假設我們希望在進入每個狀態時都添加一部分處理邏輯。首在FSME界面左邊的樹形列表選擇"Outputs"項，然后按下鍵盤上的Insert鍵來添加一個新的輸出，接著在右下方的"Name"文本框中輸入相應的名稱，再單擊"Apply"按鈕，一個新的輸出就創建好了，如圖7所示。用同樣的辦法可以添加狀態機所需要的所有輸出。
圖7 添加輸出
?
當所有的輸出都定義好之后，接下來就可以為狀態機中的每個狀態綁定相應的輸出。首先在FSME界面左側的"States"項中選擇相應的狀態，然后從右下角的"Available"列表框中選擇與該狀態對應的輸出，再單擊"<"按鈕將其添加到"In"列表中，如圖8所示。用同樣的辦法可以為狀態機中的所有狀態設置相應的輸出，同一個狀態可以對應有多個輸出，其中In列表中的輸出會在進入該狀態時被調用，而Out列表中的輸出則會在退出該狀態時被調用，輸出調用的順序是與其在In或者Out列表中的順序相一致的。
圖8 為狀態設置輸出
?
由于對狀態機模型進行了修改，我們需要再次生成狀態機的框架代碼，不過這次不需要加上-d參數：
| [xiaowp@linuxgam code]$ fsmc door.fsm -o DoorFSM.h [xiaowp@linuxgam code]$ fsmc door.fsm -d -impl DoorFSM.h -o DoorFSM.cpp |
我們在新的狀態機模型中添加了enterOpend、enterClosed、enterLocked和enterUnlocked四個輸出，因此生成的類DoorFSM中會包含如下幾個純虛函數：
| virtual void enterOpened() = 0; virtual void enterLocked() = 0; virtual void enterUnlocked() = 0; virtual void enterClosed() = 0; |
顯然，此時生成的狀態機框架不能夠再被直接編譯了，我們必須從類DoorFSM派生出一個子類，并提供對這幾個純虛函數的具體實現：
| /* * DoorFSMLogic.h * 狀態機控制邏輯的頭文件 */ #include "DoorFSM.h" class DoorFSMLogic : public DoorFSM { protected: virtual void enterOpened(); virtual void enterLocked(); virtual void enterUnlocked(); virtual void enterClosed(); }; |
正如前面所提到過的，這幾個函數實際上代表的正是應用系統的處理邏輯，作為例子我們只是簡單地輸出一些提示信息：
| /* * DoorFSMLogic.cpp * 狀態機控制邏輯的實現文件 */ #include "DoorFSMLogic.h" #include <iostream> void DoorFSMLogic::enterOpened() { std::cout << "Enter Opened state." << std::endl; } void DoorFSMLogic::enterClosed() { std::cout << "Enter Closed state." << std::endl; } void DoorFSMLogic::enterLocked() { std::cout << "Enter Locked state." << std::endl; } void DoorFSMLogic::enterUnlocked() { std::cout << "Enter Unlocked state." << std::endl; } |
同樣，為了對生成的狀態機進行驗證，我們還需要手工編寫一段測試代碼：
| /* * TestFSM.cpp * 測試狀態機邏輯 */ #include "DoorFSMLogic.h" int main() { DoorFSMLogic door; door.A(DoorFSM::Close); door.A(DoorFSM::Lock); door.A(DoorFSM::Unlock); door.A(DoorFSM::Open); } |
使用下面的命令能夠將生成的狀態機框架和測試代碼編譯成一個可執行文件：
| [xiaowp@linuxgam code]$ g++ DoorFSM.cpp DoorFSMLogic.cpp TestLogic.cpp -o logic |
運行結果如下所示：
| [xiaowp@linuxgam code]$ ./logic Enter Closed state. Enter Locked state. Enter Unlocked state. Enter Opened state. |
本文涉及代碼下載：?code.zip
回頁首
四、小結
在面向對象的軟件系統中，有些對象具有非常復雜的生命周期模型，使用有限狀態機是描述這類對象最好的方法。作為一種軟件設計模式，有限狀態機的概念雖然不算復雜，實現起來也并不困難，但它的問題是當狀態機的模型復雜到一定的程度之后，會帶來實現和維護上的困難。Linux下的FSME是一個可視化的有限狀態機建模工具，而且支持狀態機框架代碼的自動生成，借助它可以更加輕松地構建基于有限狀態機的應用系統。
參考資料
- 從Wiki百科全書?http://en.wikipedia.org/wiki/Finite_state_automaton開始，你可以了解到許多同狀態機相關的計算理論知識。?
- 狀態機是UML的一個重要組成部分，Robert C. Martin在他的文章UML Tutorial: Finite State Machines中，介紹了如何使用UML語言來對狀態機進行建模，你可以通過網址?http://www.objectmentor.com/resources/articles/umlfsm.pdf可以找到這一文檔。?
- FSME是Linux下一個基于Qt的狀態機建模工具，它能夠自動生成狀態機框架代碼，并且同時支持C++和Python語言，通過網站?http://fsme.sourceforge.net/你可以了解到有關FSME的更多信息，并能夠下載最新版本的FSME。?
- Qfsm也是一個運行在Linux下的狀態機建模工具，它不僅提供了可視化的狀態機編輯器，而且還能夠對生成的狀態機進行實時模擬，通過網站?http://qfsm.sourceforge.net/可以了解到Qfsm的更多信息。?
關于作者
總結
以上是生活随笔為你收集整理的关于有限自动机的一篇不错的文章的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Go游戏服务器开发的一些思考（九）：Do
- 下一篇： 深入浅出理解有限状态机