有限状态机时代终结的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个状态)将带来巨大的潜在风险"确实，我是做游戏辅助的，经常需要添加修改状态，几乎没改必错，调试找半天……