有限狀態(tài)機(jī)時代終結(jié)的10大理由
作者：alexjc
譯者：賴勇浩（戀花蝶）
原文地址：http://aigamedev.com/questions/fsm-age-is-over
本文最初發(fā)表于戀花蝶的博客（http://blog.csdn.net/lanphaday），如蒙轉(zhuǎn)載，敬請保留全文完整，包括本聲明。
經(jīng)過幾個月的發(fā)展， AiGameDev.com 形成了一個小有氣候的社區(qū)，謝謝大家支持！每個周五，我將抽出時間來回答大家的問題，你可以在 blog 和論壇 上提問。
有限狀態(tài)機(jī)在過去十年里變得非常流行，游戲開發(fā)者用它開發(fā)了很多極具趣味的游戲。但再好的事情也有個結(jié)束，是否到了使用比 FSM 更好的技術(shù)來完成 AI 邏輯的時代了？
本周的問題是一個評論，erm@duh.org提出了一個與周三的教程系列有關(guān)的有趣話題，讓我把它改得更有建設(shè)性一些：
“據(jù)我所知很多領(lǐng)域（如游戲業(yè)界）都使用有限狀態(tài)機(jī)來實(shí)現(xiàn)游戲 AI。為什么你不用它來實(shí)現(xiàn)這個模擬游戲里的狗的行為？”
這個教程使用行為樹來體現(xiàn)它與狀態(tài)機(jī)的不同，而且游戲 AI 開發(fā)者也能夠從中得到分級邏輯的好處。
當(dāng)然我們也可以用有限狀態(tài)機(jī)（FSM）來構(gòu)建相同的行為。但業(yè)內(nèi)人士都知道這一技術(shù)在邏輯增長時有多么有脆弱。遠(yuǎn)離 FSM 是避免游戲項(xiàng)目變得一塌糊涂的選擇！
非正統(tǒng)
問題： 構(gòu)建 FSM 的方式對于不同的軟件工程師而言是完全不同的流程。是的，概念上它是“設(shè)計(jì)師友好”的，但實(shí)際上應(yīng)用 FSM 需要應(yīng)用非常多的編程知識和細(xì)節(jié)。
原因： FSM 要求每一個狀態(tài)明確地轉(zhuǎn)換到另一狀態(tài)。沒有一個編程語言需要這樣，語言本身的語義就隱含了所有轉(zhuǎn)換（如C++編譯器從語句構(gòu)造執(zhí)行指令序列）。
過于底層
問題： 編輯FSM的邏輯非常底層，而且機(jī)械性十足。我們常常會發(fā)現(xiàn)自己總是在構(gòu)建相似的行為，而且這會花費(fèi)我們大部分時間。
原因： 我們所能做的僅是編輯從一狀態(tài)到另一狀態(tài)的轉(zhuǎn)換，而無法做出更高層次的模式導(dǎo)致頻繁重復(fù)相似的序列或條件。有限狀態(tài)機(jī)的世界不存在元編程（Meta-programming）。
邏輯受限
問題： 有限狀態(tài)機(jī)形式固定，從而導(dǎo)致計(jì)算受限（又稱為非圖靈完備）。這意味著我們不能像計(jì)數(shù)一樣做事。
原因： 如果我們把事件當(dāng)作符號，我們只能用有限狀態(tài)自動機(jī)識別正則文法，這一方法下一個正則表達(dá)式不能識別某些類別的文本模式。同樣，有限狀態(tài)機(jī)僅能作為正則語言的傳感器。
需要自定義擴(kuò)展
問題： 游戲開發(fā)者在實(shí)踐中經(jīng)常需要擴(kuò)展 FSM 才能將其用于項(xiàng)目，然而這并不容易被理解，甚至還缺乏文檔。這是與FSM的學(xué)術(shù)基礎(chǔ)并不相同。
原因： 因?yàn)?span lang="EN-US"> FSM 受限于理論，開發(fā)者必須自行增加功能擴(kuò)展以實(shí)現(xiàn)確定的某些特性。這意味著要用編程語言去實(shí)現(xiàn)計(jì)數(shù)器、計(jì)時器和任何形式的內(nèi)存對象。
難以標(biāo)準(zhǔn)化
問題： 不像規(guī)劃器（HTN）或搜索算法（A*），它們能用相關(guān)的通用方法實(shí)現(xiàn)。而 FSM 則非常難以在不同的游戲間重用，甚至在引擎是不同的部分重用也不可能。
原因： 因?yàn)?span lang="EN-US"> FSM 是非圖靈完備的， FSM 需要為每一問題自定義特定的解決方案。這使得它們適用度極低，而不像腳本語言一樣能夠很容易地重新打包。
非自主的
問題： 使用 FSM 實(shí)現(xiàn)目標(biāo)導(dǎo)向的行為需要做很多工作。這是一個大問題，因?yàn)榇蟛糠钟嗅槍π缘?span lang="EN-US"> AI 需要處理長遠(yuǎn)目標(biāo)。
原因： FSM 運(yùn)作于反應(yīng)模式，只能處理事件和觸發(fā)跳轉(zhuǎn)。它們無法自動向前（又稱為自主），因此我們必須為所有不同的目標(biāo)手動轉(zhuǎn)換。
難以并發(fā)
問題： FSM 難以并發(fā)。當(dāng)并行運(yùn)行多個狀態(tài)機(jī)，要么死鎖，要么我們通過手工編輯來確保它們在某個程度上能夠兼容。
原因： FSM 存儲的信息越多在處理外部資源沖突上的問題就越多。使?fàn)顟B(tài)機(jī)并發(fā)的解決方案通常是擴(kuò)展 FSM 自身，把它作為支持邏輯或一套工具來保證并發(fā)安全。
大規(guī)模支持較差
問題： 有限狀態(tài)機(jī)，甚至是分層的，也難以大規(guī)模擴(kuò)展。它們往往是在其中夾雜一大塊邏輯代碼，而非行為編輯模塊化。
原因： FSM 并不利用編程語言提供的用以解決大問題的規(guī)模化特性，同樣地FSM 也難以同步多個行為模塊。
勞動密集型
問題： 用 FSM 實(shí)現(xiàn)任何設(shè)計(jì)都需要做大量工作。甚至狀態(tài)機(jī)本身也有著無數(shù)問題。
原因： 如前所述，應(yīng)對所有挑戰(zhàn)需要花費(fèi)設(shè)計(jì)師的大量時間，甚至最終這還會成行為中的 bugs 的來源！
行業(yè)進(jìn)步
事實(shí)： 許多資深游戲開發(fā)者已經(jīng)不再使用有限狀態(tài)機(jī)，而是使用行為樹之類的可替換方案。
事實(shí)： 現(xiàn)在多個游戲 AI 中間件提供商致力于規(guī)劃器實(shí)現(xiàn)的 AI，在 2008 年將會見到更多可用的此類產(chǎn)品。
結(jié)論
FSM，就像其它技術(shù)一樣，在游戲開發(fā)的進(jìn)程中占有了應(yīng)得的一席之地。然而，開發(fā)者默認(rèn)使用有限狀態(tài)機(jī)來實(shí)現(xiàn) AI 的時代，已經(jīng)行將結(jié)束。帶有協(xié)程的腳本在今天已經(jīng)極其流行，而分級規(guī)劃器將越來越多地應(yīng)用在游戲及其中間件。
發(fā)表于 @ 2008年01月28日 22:40:00 | | 編輯| 舉報| 收藏
那么用什么？協(xié)程？
元編程（Meat-programming）？肉編程？hehe...
Re jq0123: 謝謝指正，當(dāng)時筆誤，已經(jīng)改正過來了。是 meta-programming。
FSM 發(fā)表于2008年1月30日 12:52:11 IP:舉報刪除
只能說是游戲開發(fā)者設(shè)計(jì)的FSM不夠完善。
有限狀態(tài)自動機(jī)不僅僅用于游戲，現(xiàn)代通訊軟件都是采用FSM原理來完成狀態(tài)變遷。通訊軟件的開發(fā)難度比游戲要大得多，而且可靠性要強(qiáng)得多。
非正統(tǒng)？作者怎么能將FSM和編程語言做比較，而得出如此結(jié)論？
過于底層？任何復(fù)雜的事情最終都可以分解實(shí)現(xiàn)，就像編程，你還是得去寫賦值語句，條件判斷
邏輯受限？這正是FSM的強(qiáng)項(xiàng)，邏輯清晰
難以并發(fā)？交換機(jī)上同時運(yùn)行的FSM何其多
大規(guī)模支持較差？中國移動都2億用戶了
其實(shí)原因文中也已說明“游戲開發(fā)者使用有限狀態(tài)機(jī)的經(jīng)驗(yàn)極其缺乏”
我不太懂規(guī)劃器，但是如果把MetaProgramming理解為“動態(tài)生成需要的優(yōu)先狀態(tài)自動機(jī)”的話我并不覺得是問題，FSM的算法支持抽象和分層結(jié)構(gòu)。在我看來把一些需要的動作的FSM規(guī)范出來形成工具包也是一個可行的辦法，雖然也許不是最通用的，但如果在同類型游戲之間的話我相信這種抽象還是可以辦到的。
抱歉忘了說，我承認(rèn)FSM不是圖靈完備的，不過我不太相信現(xiàn)在的游戲已經(jīng)復(fù)雜到需要圖靈自動機(jī)來設(shè)計(jì)人工智能。我更傾向于認(rèn)為現(xiàn)在的引擎難以通用的原因是由于工程的壓力無法進(jìn)行合理的全局規(guī)劃的原因。理解難免片面，歡迎大家執(zhí)政。
不同意作者的觀點(diǎn)，FSM 在嵌入式控制，通訊等系統(tǒng)都具有不可替代的有點(diǎn)。
FSM確實(shí)需要非常好的設(shè)計(jì)，不能憑感覺就開始coding,否則終歸會有崩潰的一天，不管是人還是代碼！！
感覺作者僅僅只是搬概念而已。自己是否真的深入研究過了？
概念,扯不明白
翻譯好像有點(diǎn)問題。。。
事實(shí)： 游戲開發(fā)者使用有限狀態(tài)機(jī)的經(jīng)驗(yàn)極其缺乏，不如改用行為樹。
Fact: Experienced game developers are using finite state machines less and less, switching to alternatives like behavior trees.
Re reader: 謝謝提醒，已經(jīng)更改為：許多資深游戲開發(fā)者已經(jīng)不再有限狀態(tài)機(jī)，而是使用行為樹之類的可替換方案。
Right。切換太復(fù)雜，編碼不好編。就像在編譯過程中，用遞歸函數(shù)實(shí)現(xiàn) Parse 一樣，不使用有限狀態(tài)機(jī)代碼更流利。
同意你的觀點(diǎn).
我在TX的一款MMO養(yǎng)成游戲里面大規(guī)模使用Lua的協(xié)程機(jī)制.
感覺還行.
:)
其實(shí), 腳本里也是用的條件判斷呀, 只是換成腳本之后, 程序變得靈活多了. 但歸根到底還是用的FSM的原理嘛!
這世界, 幾乎任何事情都離不開狀態(tài)判斷, 不管有限無限, 根據(jù)條件來判斷是最普遍的.
假如有一天人們不用條件作判斷,那世界將變成什么樣子呢,誰都不知道,呵呵.
因此, 我想狀態(tài)機(jī)根本還不存在被終結(jié)的理由吧. 除非哪位天才發(fā)明了更科學(xué)的方法, 這也將是科學(xué)的大發(fā)展了!
MARK
FSM根本的弱點(diǎn)是封閉性.FSM一旦有變化(比如添加1個狀態(tài))將帶來巨大的潛在風(fēng)險.
模式匹配則小的多,便于模糊處理以及分級處理.
我覺得在大規(guī)模擴(kuò)展性良好要求的軟件開發(fā)領(lǐng)域(這方面要求抓住行業(yè)本質(zhì)),FSM退出舞臺是必然.在嵌入式領(lǐng)域或更硬的領(lǐng)域,FSM還是比較易懂,因?yàn)樗７铝藬?shù)字邏輯的本質(zhì).
"FSM一旦有變化(比如添加1個狀態(tài))將帶來巨大的潛在風(fēng)險"確實(shí)，我是做游戲輔助的，經(jīng)常需要添加修改狀態(tài)，幾乎沒改必錯，調(diào)試找半天……