趣说游戏AI开发：对状态机的褒扬和批判
发表于2016-04-27
0x00 前言
因为临近年关工作繁忙，已经有一段时间没有更新博客了。到了元旦终于有时间来写点东西，既是积累也是分享。如题目所示，本文要来聊一聊在游戏开发中经常会涉及到的话题——游戏AI。设计游戏AI的目标之一是要找到一种便于使用并容易拓展的的方案，常见的一些游戏AI方案包括了有限状态机(FSM)、分层有限状态机（HFSM）、面向目标的动作规划（GOAP）以及分层任务网络（HTN）和行为树（BT）等等。下面我们就来聊一聊比较有代表性的游戏AI方案——状态机。
0x01 有限状态机(FSM)
有限状态自动机 (Finite State Machine，FSM)是表示有限多个状态以及在这些状态（State）之间转移（Transition）和动作（Action）的数学模型。有限状态机的模型体现了两点：
· 状态首先是离散的：某一时刻只能处于某种状态之下，且需要满足某种条件才能从一种状态转移到另一种状态。
· 然后状态总数是有限的。
从它的定义，我们可以看到有限状态机的几个重要概念：
· 状态（State）：表示对象的某种形态，在当前形态下可能会拥有不同的行为和属性。
· 转移（Transition）：表示状态变更，并且必须满足确使转移发生的条件来执行。
· 动作（Action）：表示在给定时刻要进行的活动。
· 事件（Event）：事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。
而状态机便是用来控制对象状态的管理器。在满足了某种条件或者说在某个特定的事件被触发之后，对象的状态便会通过转换来变成另外一种状态，而对象在不同的状态之下也有可能会有不同的行为和属性。
当然，有限状态机的应用范围很广，但是显然游戏开发是有限状态机最为成功的应用领域之一。除了游戏AI的实现可以依靠有限状态机之外，游戏逻辑以及动作切换都可以借助有限状态机来实现。因此游戏中的每个角色或者器件或者逻辑都有可能内嵌一个状态机。
0x02 HFSM分层有限状态机
如果我们仔细观察一个有限状态机的话，可以发现它在逻辑结构上是没有层次的，如果和行为树来做对比的话可以发现这一点十分明显。在行为树中，节点是有层次（Hierarchical）的，子节点由其父节点来控制。例如行为树中有一种节点叫做“序列（Sequence）节点”，它的作用是顺序执行所有子节点（如果某个子节点失败返回失败，否则返回成功）。而将行为树的这个优势应用到有限状态机上，分层有限状态机HFSM便诞生了。
分层的好处
那么引入了分层之后的HFSM到底带来了什么好处呢？
最大的好处便是在一定程度上规范了状态机的状态转换，从而有效地减少了状态之间的转换。
举一个简单的小例子：例如RTS游戏中的士兵。如果逻辑没有层次上的划分，那么我们对士兵所定义的若干状态，例如前进、寻敌、攻击、防御、逃跑等等，就需要在这些状态之间定义转移，因为它们是平级的，因此我们需要考虑每一组状态的关系，并维护一大堆没有侧重点的转移。
如果在逻辑上是分层的，我们就可以将士兵的这些状态进行一个分类，把几个低级的状态归并到一个高级的状态中，并且状态的转移只发生在同级的状态中。
例如高级状态包括战斗、撤退，而战斗状态中又包括了寻敌、攻击等几个小状态；撤退状态中又包括了防御、逃跑这几个小状态。
总而言之，分层状态机HFSM从某种程度上规范了状态机的状态转移，而且状态内的子状态不需要关心外部状态的跳转，这样也做到了无关状态间的隔离。
0x03 有限状态机的实现
那么到底如何实现一个有限状态机呢？主要有两种方式来实现，即集中管理控制以及模块化管理。具体来说，这两种方式的实现如下：
· 使用switch语句：所有的状态之间的转移逻辑全都写在一个部分，需要根据不同的分支来判断转移条件是否符合。
· 使用状态模式（State Pattern）：一种常见的设计模式。在状态模式中，我们为每个状态创建与之对应的类，这样就将状态转移的逻辑从臃肿的switch语句中分散到了各个类中。
了解了有限状态机大体上可以分为这两种实现方式，那么接下来我们就具体来看一看这两种方式是如何实现的。
switch语句
在实现有限状态机时，使用switch语句是最简单同时也是最直接的一种方式。这种方式的基本思路是为状态机中的每一种状态都设置一个case分支，专门用来对该状态进行控制。
上图是一个具体的使用有限状态机实现游戏AI的场景，描述的是一个游戏单位的AI，下面我们就使用switch语句来实现图中的状态机。
switch (state) { // 处理状态Waiting的分支 case State.Waiting: // 执行等待 wait(); // 检查是否有可以攻击 if (canAttack()){ // 当前状态转换为Attacking changeState(State.Attacking); } // 若不可攻击，则检查是否有可以移动 else if (canMove()) { // 当前状态转换为Moving changeState(State.Moving) } break; // 处理状态Moving的分支 case State.Moving: // 执行动作move move(); // 检查是否可以攻击敌人 if (canAttack()) { // 当前状态转换为Attacking changeState(State.Attacking); } // 若不可攻击，则检查是否可以等待 else if (canWait()) { // 当前状态转换为Waiting changeState(State.Waiting); } break; // 处理状态Attacking的分支 case State.Attacking: // 执行攻击attack attack(); // 检查是否可以等待 if (canWait()) { // 当前状态转换为Waiting changeState(State.Waiting); } break; }通过这个小例子，我们可以看到使用switch语句实现的有限状态机的确可以很好的运行。不过我们还可以发现这种方式在实现状态之间的转换时，１、检查转换条件以及2、进行状态转换的代码都是混杂在当前的状态分支中来完成的，这样就会导致代码的可读性降低甚至会增加日后的维护成本。
这是因为在每个具体的状态下，都需要检查多个具体的转换条件，对符合条件的还需要转移到新的具体的状态，这样的代码是难以维护的，因为它们需要在具体的情况下处理具体的事物。即便我们将检查转换条件和进行状态转换的代码分别封装成两个专门的函数FuncA（检查转换条件）和FuncB（进行状态转换），switch语句中各个具体状态的代码可能会更加清晰。但是随着逻辑复杂度的增加，FuncA和FuncB这两个函数本身的复杂度可能也会增加，甚至最后变得臃肿不堪。
状态模式
当控制一个对象状态转换的条件表达式过于复杂时，把状态的判断逻辑转移到一系列类当中，可以把复杂的逻辑判断简单化。因此，使用状态模式来实现状态机虽然不如直接使用switch语句来的直接，但是对于状态更易维护也更易拓展。下面我们就来看一看状态模式中的角色：
· 上下文环境（Context）：它定义了客户程序需要的接口并维护一个具体状态的实例，将与状态相关的操作（1、检查转换条件；2、进行状态转换）交给当前的具体状态对象来处理。
· 抽象状态（State）：定义一个接口以封装使用上下文环境的的一个特定状态相关的行为。
· 具体状态（Concrete State）：实现抽象状态定义的接口。
下面，我们就按照这三个角色来实现上一小节图中的状态机吧。
context类：
public class Context { private State state; public Context(State state) { this.state = state; } public void Do() { state.CheckAndTran(this); } } 抽象状态类：
public abstract class State { public abstract void CheckAndTran(Context context); } 具体状态类
public class WaitingState : State { public override void CheckAndTran(Context context) { //执行等待动作 Wait(); //检查是否可以攻击敌人 if (canAttack()){ // 当前状态转换为Attacking context.State = new AttackingState(); } // 若不可攻击，则检查是否有可以移动 else if (canMove()) { // 当前状态转换为Moving context.State = new MovingState(); } } } ... 虽然看似状态模式缓解了使用switch语句那种代码臃肿、可读性维护性差的问题，但是状态模式并非没有自己的缺点。可以看出状态模式的使用必然会增加类和对象的个数，如果使用不当将导致程序结构和代码的混乱。
0x04 褒扬和批判
在游戏开发中使用状态机显然不失为一种不错的选择，首先它的概念并不复杂，其次它的实现也十分简单而直接。但它的缺点却也十分明显，例如难以复用，因为它往往需要根据具体的情况来做出反应，当然当状态机的模型复杂到一定的程度之后，也会带来实现和维护上的困难。如何选择，可能就是一个仁者见仁智者见智的问题了。