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