11有限状态机.docxVIP

PAGE6 / NUMPAGES6 1.什么是有限状态机 有限状态机，常常被称作FSM（Finite State Machine），多年来已经作为人工智能编程者们选用的工具用于设计具有智能幻觉的游戏智能体。你会发现从视频游戏的早期开始，这种或那种FSM正是每个游戏所选中的架构；尽管更专业的智能体结构越来越普及，但FSM架构还将在今后很长时间内无处不在。为何会这样？原因如下： 编程快速简单。有很多方法编码一个有限状态机，并且几乎所有的有限状态机实现都相当的简单。 易于调试。因为一个游戏智能体的行为被分解成简单的易于管理的块，如果一个智能体开始变得行动怪异，会通过对每一个状态增加跟踪代码来调试它。用这种方法，人工智能程序员可以很容易跟踪错误行为出现前的事件序列，并且采取相应的行动。 很少的计算开销。有限状态机几乎不占用珍贵的处理器时间，因为它们本质上遵守硬件编码的规则。除了if-this-then-that类型的思考处理之外，是不存在真正的“思考”的。 直觉性。人们总是自然地把事物思考为处在一种或另一种状态。并且我们也常常提到我们自己处在这样那样的状态中。有多少次你“使自己进入一种状态”或者发现自己处于“头脑的正确状态”，当然人类并不是像有限状态机一样工作，但是有时候我们发现在这种方式下考虑我们的行为是有用的。相似地，将一个游戏智能体的行为分解成一些状态并且创建需要的规则来操作它们是相当容易的。出于同样的原因，有限状态机能够使你很容易地与非程序员（例如与游戏制片人和关卡设计师）来讨论你的人工智能的设计，能够更好地进行设计概念的沟通和交流。 灵活性。一个游戏智能体的有限状态机可以很容易地由程序员进行调整，来达到游戏设计者所要求的行为。同样通过增添新的状态和规则也很容易扩展个智能体的行为的范围。此外，当你的人工智能技术提高了，你会发现有限状态机提供了一个坚固的支柱，使你可以用它来组合其他的技术，例如模糊逻辑和神经网络。 历史上来说，有限状态机是一个被数学家用来解决问题的严格形式化的设备。最著名的有限状态机可能是艾伦·图灵假想的设备——图灵机，他在1936年论文《关于可计算数字》中写道：这是一个预示着现代可编程计算机的机器，它们可以通过对无限长的磁带上的符号进行读写和擦除操作来进行任何逻辑运算。 幸运的是，作为一个人工智能程序员，我们可以放弃有限状态机的正式的数学定义，一个描述性的定义就足够了： 一个有限状态机是一个设备，或是一个设备模型，具有有限数量的状态，它可以在任何给定的时间根据输入进行操作，使得从一个状态变换到冗一个状态，或者是促使一个输出或者一种行为的发生。一个有限状态机在任何瞬间只能处在一种状态。 因此，有限状态机背后的概念是要把一个对象的行为分解成为易于处理的“块”或状态。例如，在你墙上的灯的开关，是一个非常简单的有限状态机。它有两种状态：开或关。状态之间的变换是通过你手指的输入产生的。向上按开关，产生从关到开的状态变换，向下按开关，产生从开到关的状态变换。 关闭状态没有相关的输出或行动（除非你考虑灯泡不亮也作为一个行动），但是当它处在开状态时，允许电流流过开关并且通过电灯泡罩的灯丝点亮你的房间，见图1。 图1 一个电灯开关是一个有限状态机 当然，一个游戏智能体的行为常常要比一个电灯泡复杂的多。下面是一些关于有限状态机是如何应用在游戏中的例子： 在Pac-Man中幽灵行动的实现就是一个有限状态机。存在一个规避状态，这对所有的幽灵都是相同的，并且每个幽灵都有自己的追踪状态，追踪行动的实现对于每个幽灵来说都是不同的。玩家吃了一个强力药丸的输入就是从追踪状态变换为规避状态的条件。 类似雷神之槌中的角色类型也可以作为一个有限状态机来实现。它们具有诸如找到武器、找到血包、寻求掩护和走开的状态。甚至雷神之槌中的武器也实现了它们自己的小型有限状态机。例如，火箭可以实现如移动、接触物体和消失的状态。 运动员仿真例如足球游戏FIFA2002，是作为有限状态机来实现的。他们具有状态例如碰撞、运球、追球和盯住对方队员。此外，球队本身也常常作为FSM来实现，并且具有状态如开球、防卫，或者退场。 NPC们（非玩家角色）在RTS（实时策略游戏）中，例如Warcraft也利用有限状态机。他们具有移动到位、巡逻和沿路经前进等状态。 有限状态机的实现 有一些方法来实现有限状态机。一种幼稚的方法就是使用一系列的if-then语句或者对switch语句稍加整理。使用一个具有枚举类型的switch语句来表达状态的代码如下所示。 enum StateType { RunAway, Patrol, Attacki}; public void UpdateState (StateType CurrentState) { switch (