簡介

有限狀態機（以下用FSM指代）是一種算法思想，簡單而言，有限狀態機由一組狀態、一個初始狀態、輸入和根據輸入及現有狀態轉換為下一個狀態的轉換函數組成。在Gof的23種設計模式里的state模式是一種面向對象的狀態機思想，可以適應非常復雜的狀態管理。
現 在，FSM被普遍用于搜索引擎的分詞、編譯器實現和我們普遍關注的游戲開發中。游戲開發中，通常用FSM實現NPC控制，如當NPC受到攻擊時根據健康、力量等選擇逃跑還是反攻的行為，一般是用FSM實現的。FSM的實現方法有很多種，不能簡單地說孰優孰劣，但現代開發中，一般都比較推薦面向對象的實現方式：因為可重用性和健壯性更高，而且當需求變更的時候，也有很好的適應性。
實踐
理 論從實踐中來，也要回到實踐中去。我們現在通過實例來探索一下FSM的實現吧。首先假設有這樣一個世界（World），世界里只有一臺永不缺乏動力的汽車 （Car），汽車是次世代的，沒有油門方向盤之類的落后設備，只有兩個互斥的按鈕——停止（Stop）和行進（Run），隨著時間的流逝，汽車根據駕駛員的操作走走停停。下面的代碼可以實現這種功能：
       while True:
       key = get_key() # 按下什么鍵
       if key == "stop":
              stop(car)
       elif key == "run":
              go(car)
       keep(car) # 保持原態  

完 成了功能而且直觀、簡潔的程序員萬歲！但這時候客戶（策劃或者玩家）覺得走走停停太沒意思了，他們想要掉頭、左轉和右轉的功能，我們就要在while循環 里增加更多的if...else分支；他們想要更多的車，我們就要要在每一個分枝里增加循環；他們不僅僅想要Car了，他們還要要玩Truck，這時我們 就需要在分枝的循環里判斷當前的車是否支持這個操作（如Truck的裝卸貨物Car就不支持）；他們……
這個while循環終于無限地龐大起來，我們認識到這樣的設計的確是有點問題的，所以我們嘗試用另一種方法去實現FSM。首先我們來實現汽車（Car）：
       class Car(object):
       def stop(self):
              print "Stop!!!"
       def go(self):
              print "Goooooo!!!" 

只有兩個方法stop和go，分別執行Stop和Run兩個按鈕功能。接下來我們編寫兩個狀態管理的類，用以處理當按鈕被按下、彈起和保持時需要工作的流程：
class stop_fsm(base_fsm):
       def enter_state(self, obj):
              print "Car%s enter stop state!"%(id(obj))
 
       def exec_state(self, obj):
              print "Car%s in stop state!"%(id(obj))
              obj.stop()
 
       def exit_state(self, obj):
              print "Car%s exit stop state!"%(id(obj)) 
class run_fsm(base_fsm):
       def enter_state(self, obj):
              print "Car%s enter run state!"%(id(obj))
 
       def exec_state(self, obj):
              print "Car%s in run state!"%(id(obj))
              obj.go()
 
       def exit_state(self, obj):
              print "Car%s exit run state!"%(id(obj)) 

stop_fsm和run_fsm都繼承自base_fsm，base_fsm是一個純虛的接口類：
class base_fsm(object):
       def enter_state(self, obj):
              raise NotImplementedError()
 
       def exec_state(self, obj):
              raise NotImplementedError()
 
       def exit_state(self, obj):
              raise NotImplementedError() 

enter_state 在obj進入某狀態的時候調用——通常用來做一些初始化工作；exit_state也離開某狀態的時候調用——通常做一些清理工作；而 exec_state則在每一幀的時候都會被調用，通常做一些必要的工作，如檢測自己的消息隊列并處理消息等。在stop_fsm和run_fsm兩個類 的exec_state函數中，就調用了對象的stop和go函數，讓汽車保持原有的狀態。
至現在為止，Car還沒有接觸到FSM，所以我們需要提供一個接口，可以讓它擁有一個FSM：
       def attach_fsm(self, state, fsm):
              self.fsm = fsm
              self.curr_state = state 

我們還需要為Car提供一個狀態轉換函數：
       def change_state(self, new_state, new_fsm):
              self.curr_state = new_state
              self.fsm.exit_state(self)
              self.fsm = new_fsm
              self.fsm.enter_state(self)
              self.fsm.exec_state(self) 

為Car提供一個保持狀態的函數：
       def keep_state(self):
              self.fsm.exec_state(self) 

現在只有兩個狀態，但我們知道需求隨時會改動，所以我們最好弄一個狀態機管理器來管理這些狀態：
class fsm_mgr(object):
       def __init__(self):
              self._fsms = {}
              self._fsms[0] = stop_fsm()
              self._fsms[1] = run_fsm()
      
       def get_fsm(self, state):
              return self._fsms[state]
      
       def frame(self, objs, state):
              for obj in objs:
                     if state == obj.curr_state:
                            obj.keep_state()
                     else:
                            obj.change_state(state, self._fsms[state]) 

fsm_mgr最重要的函數就是frame，在每一幀都被調用。在這里，frame根據對象現在的狀態和當前的輸入決定讓對象保持狀態或者改變狀態。
這時候，我們的實例基本上完成了。但我們還要做一件事，就是建立一個世界（World）來驅動狀態機：
class World(object):
       def init(self):
              self._cars = []
              self._fsm_mgr = fsm_mgr()
              self.__init_car()
 
       def __init_car(self):
              for i in xrange(1):   # 生產汽車
                     tmp = Car()
                     tmp.attach_fsm(0, self._fsm_mgr.get_fsm(0))
                     self._cars.append(tmp)
 
       def __frame(self):
              self._fsm_mgr.frame(self._cars, state_factory())
 
       def run(self):
              while True:
                     self.__frame()
                     sleep(0.5) 

從 代碼可見，World里有Car對象，fsm_mgr對象；在run函數里，每0.5s執行一次__frame函數（FPS = 2），而__frame函數只是驅動了fsm_mgr來刷新對象，新的命令是從state_factory函數里取出來的，這個函數用以模擬駕駛員的操作（按下Stop或者Run按鈕之一）：
def state_factory():
       return random.randint(0, 1) 

現在我們就要初始化世界（World）可以跑起我們的FSM了！
if __name__ == "__main__":
       world = World()
       world.init()
       world.run() 

用python解釋器執行上面的代碼，我們可以看到程序不停地輸出Car的狀態：
......
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
Car8453392 in run state!
Goooooo!!!
Car8453392 exit run state!
Car8453392 enter stop state!
Car8453392 in stop state!
Stop!!!
Car8453392 in stop state!
Stop!!!
Car8453392 exit stop state!
Car8453392 enter run state!
Car8453392 in run state!
Goooooo!!!
...... 

 
結論
這時再回頭來看看我們之前的問題：
1、玩家想要功能更多的Car，比如掉頭。
我 們可以通過為Car增加一個調頭（back）的方法來執行掉頭，然后從base_fsm中繼承一個back_fsm來處理調頭。之后在fsm_mgr里增 加一個back_fsm實例，及讓state_factory產生調頭指令。聽起來似乎比之前while+if的方式還要麻煩不少，其實不然，這里只有 back_fsm和為fsm_mgr增加back_fsm實例才是特有的，其它步驟兩種方法都要執行。
2、玩家要更多的Car。
這對于面向對象的FSM實現就太簡單了，我們只要把World.__init_car里的生產數量修改一下就行了，要多少有多少。
3、玩家要更多型號的車，如Truck。
從Car派生一個Truck，然后增加裝貨、卸貨的接口。最大的改動在于Truck狀態轉換的時候需要一些判斷，如不能直接從裝貨狀態轉換到開動狀態，而是裝貨、停止再開動。
通 過這幾個簡單的問題分析，我們可以看到，使用面向對象的方式來設計FSM，在需求變更的時候，一般都只增刪代碼，而仍少需要改動已有代碼，程序的擴展性、適應性和健壯性都得很大的提高；因此，在世界龐大、物種煩多、狀態復雜且條件交錯的游戲開發中應用面向對象的FSM實在是明智之選。還有一點，面向對象的 FSM可以非常容易地模擬消息機制，這有利于模塊清晰化，更容易設計出正交的程序。