簡介

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

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

只有兩個方法stop和go，分別執(zhí)行Stop和Run兩個按鈕功能。接下來我們編寫兩個狀態(tài)管理的類，用以處理當(dāng)按鈕被按下、彈起和保持時需要工作的流程：
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進入某狀態(tài)的時候調(diào)用——通常用來做一些初始化工作；exit_state也離開某狀態(tài)的時候調(diào)用——通常做一些清理工作；而 exec_state則在每一幀的時候都會被調(diào)用，通常做一些必要的工作，如檢測自己的消息隊列并處理消息等。在stop_fsm和run_fsm兩個類 的exec_state函數(shù)中，就調(diào)用了對象的stop和go函數(shù)，讓汽車保持原有的狀態(tài)。
至現(xiàn)在為止，Car還沒有接觸到FSM，所以我們需要提供一個接口，可以讓它擁有一個FSM：
       def attach_fsm(self, state, fsm):
              self.fsm = fsm
              self.curr_state = state 

我們還需要為Car提供一個狀態(tài)轉(zhuǎn)換函數(shù)：
       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提供一個保持狀態(tài)的函數(shù)：
       def keep_state(self):
              self.fsm.exec_state(self) 

現(xiàn)在只有兩個狀態(tài)，但我們知道需求隨時會改動，所以我們最好弄一個狀態(tài)機管理器來管理這些狀態(tài)：
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最重要的函數(shù)就是frame，在每一幀都被調(diào)用。在這里，frame根據(jù)對象現(xiàn)在的狀態(tài)和當(dāng)前的輸入決定讓對象保持狀態(tài)或者改變狀態(tài)。
這時候，我們的實例基本上完成了。但我們還要做一件事，就是建立一個世界（World）來驅(qū)動狀態(tài)機：
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):   # 生產(chǎn)汽車
                     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函數(shù)里，每0.5s執(zhí)行一次__frame函數(shù)（FPS = 2），而__frame函數(shù)只是驅(qū)動了fsm_mgr來刷新對象，新的命令是從state_factory函數(shù)里取出來的，這個函數(shù)用以模擬駕駛員的操作（按下Stop或者Run按鈕之一）：
def state_factory():
       return random.randint(0, 1) 

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

用python解釋器執(zhí)行上面的代碼，我們可以看到程序不停地輸出Car的狀態(tài)：
......
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!!!
...... 

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