簡(jiǎn)介
有限狀態(tài)機(jī)（以下用FSM指代）是一種算法思想，簡(jiǎn)單而言，有限狀態(tài)機(jī)由一組狀態(tài)、一個(gè)初始狀態(tài)、輸入和根據(jù)輸入及現(xiàn)有狀態(tài)轉(zhuǎn)換為下一個(gè)狀態(tài)的轉(zhuǎn)換函數(shù)組成。在Gof的23種設(shè)計(jì)模式里的state模式是一種面向?qū)ο蟮臓顟B(tài)機(jī)思想，可以適應(yīng)非常復(fù)雜的狀態(tài)管理。
現(xiàn) 在，FSM被普遍用于搜索引擎的分詞、編譯器實(shí)現(xiàn)和我們普遍關(guān)注的游戲開(kāi)發(fā)中。游戲開(kāi)發(fā)中，通常用FSM實(shí)現(xiàn)NPC控制，如當(dāng)NPC受到攻擊時(shí)根據(jù)健康、力量等選擇逃跑還是反攻的行為，一般是用FSM實(shí)現(xiàn)的。FSM的實(shí)現(xiàn)方法有很多種，不能簡(jiǎn)單地說(shuō)孰優(yōu)孰劣，但現(xiàn)代開(kāi)發(fā)中，一般都比較推薦面向?qū)ο蟮膶?shí)現(xiàn)方式：因?yàn)榭芍赜眯院徒研愿撸耶?dāng)需求變更的時(shí)候，也有很好的適應(yīng)性。
實(shí)踐
理 論從實(shí)踐中來(lái)，也要回到實(shí)踐中去。我們現(xiàn)在通過(guò)實(shí)例來(lái)探索一下FSM的實(shí)現(xiàn)吧。首先假設(shè)有這樣一個(gè)世界（World），世界里只有一臺(tái)永不缺乏動(dòng)力的汽車 （Car），汽車是次世代的，沒(méi)有油門(mén)方向盤(pán)之類的落后設(shè)備，只有兩個(gè)互斥的按鈕——停止（Stop）和行進(jìn)（Run），隨著時(shí)間的流逝，汽車根據(jù)駕駛員的操作走走停停。下面的代碼可以實(shí)現(xiàn)這種功能：
while True:
key = get_key() # 按下什么鍵
if key == "stop":
stop(car)
elif key == "run":
go(car)
keep(car) # 保持原態(tài)
完 成了功能而且直觀、簡(jiǎn)潔的程序員萬(wàn)歲！但這時(shí)候客戶（策劃或者玩家）覺(jué)得走走停停太沒(méi)意思了，他們想要掉頭、左轉(zhuǎn)和右轉(zhuǎn)的功能，我們就要在while循環(huán) 里增加更多的if...else分支；他們想要更多的車，我們就要要在每一個(gè)分枝里增加循環(huán)；他們不僅僅想要Car了，他們還要要玩Truck，這時(shí)我們 就需要在分枝的循環(huán)里判斷當(dāng)前的車是否支持這個(gè)操作（如Truck的裝卸貨物Car就不支持）；他們……
這個(gè)while循環(huán)終于無(wú)限地龐大起來(lái)，我們認(rèn)識(shí)到這樣的設(shè)計(jì)的確是有點(diǎn)問(wèn)題的，所以我們嘗試用另一種方法去實(shí)現(xiàn)FSM。首先我們來(lái)實(shí)現(xiàn)汽車（Car）：
class Car(object):
def stop(self):
print "Stop!!!"
def go(self):
print "Goooooo!!!"
只有兩個(gè)方法stop和go，分別執(zhí)行Stop和Run兩個(gè)按鈕功能。接下來(lái)我們編寫(xiě)兩個(gè)狀態(tài)管理的類，用以處理當(dāng)按鈕被按下、彈起和保持時(shí)需要工作的流程：
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是一個(gè)純虛的接口類：
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進(jìn)入某狀態(tài)的時(shí)候調(diào)用——通常用來(lái)做一些初始化工作；exit_state也離開(kāi)某狀態(tài)的時(shí)候調(diào)用——通常做一些清理工作；而 exec_state則在每一幀的時(shí)候都會(huì)被調(diào)用，通常做一些必要的工作，如檢測(cè)自己的消息隊(duì)列并處理消息等。在stop_fsm和run_fsm兩個(gè)類 的exec_state函數(shù)中，就調(diào)用了對(duì)象的stop和go函數(shù)，讓汽車保持原有的狀態(tài)。
至現(xiàn)在為止，Car還沒(méi)有接觸到FSM，所以我們需要提供一個(gè)接口，可以讓它擁有一個(gè)FSM：
def attach_fsm(self, state, fsm):
self.fsm = fsm
self.curr_state = state
我們還需要為Car提供一個(gè)狀態(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提供一個(gè)保持狀態(tài)的函數(shù)：
def keep_state(self):
self.fsm.exec_state(self)
現(xiàn)在只有兩個(gè)狀態(tài)，但我們知道需求隨時(shí)會(huì)改動(dòng)，所以我們最好弄一個(gè)狀態(tài)機(jī)管理器來(lá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ù)對(duì)象現(xiàn)在的狀態(tài)和當(dāng)前的輸入決定讓對(duì)象保持狀態(tài)或者改變狀態(tài)。
這時(shí)候，我們的實(shí)例基本上完成了。但我們還要做一件事，就是建立一個(gè)世界（World）來(lái)驅(qū)動(dòng)狀態(tài)機(jī)：
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)
從 代碼可見(jiàn)，World里有Car對(duì)象，fsm_mgr對(duì)象；在run函數(shù)里，每0.5s執(zhí)行一次__frame函數(shù)（FPS = 2），而__frame函數(shù)只是驅(qū)動(dòng)了fsm_mgr來(lái)刷新對(duì)象，新的命令是從state_factory函數(shù)里取出來(lái)的，這個(gè)函數(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é)論
這時(shí)再回頭來(lái)看看我們之前的問(wèn)題：
1、玩家想要功能更多的Car，比如掉頭。
我 們可以通過(guò)為Car增加一個(gè)調(diào)頭（back）的方法來(lái)執(zhí)行掉頭，然后從base_fsm中繼承一個(gè)back_fsm來(lái)處理調(diào)頭。之后在fsm_mgr里增 加一個(gè)back_fsm實(shí)例，及讓state_factory產(chǎn)生調(diào)頭指令。聽(tīng)起來(lái)似乎比之前while+if的方式還要麻煩不少，其實(shí)不然，這里只有 back_fsm和為fsm_mgr增加back_fsm實(shí)例才是特有的，其它步驟兩種方法都要執(zhí)行。
2、玩家要更多的Car。
這對(duì)于面向?qū)ο蟮?span lang="EN-US">FSM實(shí)現(xiàn)就太簡(jiǎn)單了，我們只要把World.__init_car里的生產(chǎn)數(shù)量修改一下就行了，要多少有多少。
3、玩家要更多型號(hào)的車，如Truck。
從Car派生一個(gè)Truck，然后增加裝貨、卸貨的接口。最大的改動(dòng)在于Truck狀態(tài)轉(zhuǎn)換的時(shí)候需要一些判斷，如不能直接從裝貨狀態(tài)轉(zhuǎn)換到開(kāi)動(dòng)狀態(tài)，而是裝貨、停止再開(kāi)動(dòng)。
通 過(guò)這幾個(gè)簡(jiǎn)單的問(wèn)題分析，我們可以看到，使用面向?qū)ο蟮姆绞絹?lái)設(shè)計(jì)FSM，在需求變更的時(shí)候，一般都只增刪代碼，而仍少需要改動(dòng)已有代碼，程序的擴(kuò)展性、適應(yīng)性和健壯性都得很大的提高；因此，在世界龐大、物種煩多、狀態(tài)復(fù)雜且條件交錯(cuò)的游戲開(kāi)發(fā)中應(yīng)用面向?qū)ο蟮?span lang="EN-US">FSM實(shí)在是明智之選。還有一點(diǎn)，面向?qū)ο蟮?span lang="EN-US"> FSM可以非常容易地模擬消息機(jī)制，這有利于模塊清晰化，更容易設(shè)計(jì)出正交的程序。