状态驱动的游戏智能体设计（上）

51testing

就像经常听到的，有限状态机（简写为FSM）早就被AI程序员用来实现游戏智能体以体现智能感。你会发现在FSM几乎是所有视频游戏的基础构架，不管正在出现和流行的越来越深奥的智能体架构，FSM在长久的未来仍然有武之地。这里是一些为什么FSM如此强劲的原因：
1.可以快速简单地编写代码。实现有限状态机有多种途径，而且都可以简单实现。在本文你就能看到多种描述和赞成或者反对使用它们的理由。

2.易于调试。因为一个游戏智能体的行为由一个易于管理的代码段来实现，如果一个智能出现奇怪的行为，可以通过为每一个状态增加Tracer来调试。这样能够容易地跟踪事件序列，就可以针对之前的怪异行为修改代码了。
3.只需要付出少量计算代价。有限状态机几乎不使用宝贵的处理器时间，因为他们本质上跟硬编码是一样的。在那种“如果这样就那样”的思考处理中根本不存在真正的“思考”。

4.符合直觉。人类天生就以当前处以这种或者哪种状态来思考事情，所以我们常常听到我们自己处于什么状态的说法。多少次你“让你自己进入状态”或者发现你自己处于“正确的精神状态”？尽管人类并非真的像有限状态机那样工作，但通常我们发现这样有利于我们思考我们的行为。同样地，这易于通过一系列的状态和创造操作规则来实现一个游戏智能体的行为。基于同样的原因，有限状态机能让你和非程序员（如游戏策划和关卡设计师等）更好地进行关于你的AI设计的讨论，改进交流和交换观点。
5.可伸缩性。游戏智能体的有限状态机易于调整，能够很容易让程序员实现游戏设计师需要的行为，也易于通过增加新的状态和规则来扩展智能体的行为。此外，随着你AI技术的增进，你将发现有限状态机提供坚实的基础，让你能够把模糊逻辑和神经网络之类的技术组合到游戏中。


有限状态机定义
从历史观点上来说，有限状态机是一种严格的公式化的被数学家用以解决难题的一种策略。最著名的有限状态机可能是阿兰·图灵在1936年发表的论文《On Computable Numbers》上写下的的猜想——图灵机。这是现代计算机的雏形，能够通过在无限长的磁带上进行读、写和擦除符号来实现所有逻辑操作。幸运的是，作为AI程序员，我们能够对公式化的数学定义不加理会，如下描述已经足够：
有限状态机是一种策略或者一种策略模型，它由有限的一系列状态构成，在任一给定时刻，可以通过输入操作作出从一种状态到另一种状态的转换或者产生输出或者发生动作。有限状态机在任一时刻都只能够处于一种状态中。

因此，有限状态机背后的思想就是把一个对象的行为分解为易于管理的“块”或者状态。例如墙上的电灯开关，就是一种非常简单的有限状态机。它有两个状态：开与关。两个状态通过你指头产生的输入来切换。把开关扳上，它就从关的状态转换到开的状态，把开关扳下，它就从开的状态转换到关的状态。在关的状态没有任何输出或者动作（除非你装灯泡被关掉视为一种动作），但当在开的状态下时电流通过开关并且通过灯泡里的灯丝照亮房间。如图2.1



图2.1 开关是一种有限状态机。（注意：这种开关在欧洲和其它很多国家仍有存在。）
当然，游戏智能体的行为往往比灯泡要复杂得多。下文是一些在游戏中使用有限状态机的的例子。
· Pac-Mac里的精灵的行为用有限状态机实现。所有的精灵都有一种Evade（逃避）状态，它们的实现都是一样的；但每一个精灵都一个Chase（追踪）状态，它的实现各不相同。
· Quake系列的机器人以有限状态机实现。它们FindArmor（找装备）、FindHealth（找补血）、SeekCover（找掩护）和RunAway（逃跑）等多种状态。甚至Quake里实现的武器都带有小型有限状态机，例如一个火箭炮实现的状态就有Move（移动）、TouchObject（触到物体）和Die（死亡）等几种状态。

· FIFA2002之类的运动模拟游戏里的运动员是用状态机实现的，它们有Strike（踢出）、Dribble（带球）、ChaseBall（逐球）和MarkPlayer（盯人）等状态。此外，整个球队通常也是用FSM实现的，有KickOff（发球）、Defend（防守）和WalkOutOnField（不知道怎么翻译，请足球达人告知一下）。
· RTS（实时策略游戏）（例如Warcraft）中的NPC（非玩家角色）也利用有限状态机。它们的状态有MoveToPosition（移动到某地）、Patrol（巡逻）和FollowPath（跟随）等。


有限状态机实现
实现有限状态机有许多方式。一个直观的做法就是使用一系列的if-then语句或者稍显整洁的switch语句。使用switch的实现看起来就像这里的代码：
enum StateType{state_RunAway, state_Patrol, state_Attack};
void Agent::UpdateState(StateType CurrentState)
{
switch(CurrentState)
{
case state_RunAway:
EvadeEnemy();
if (Safe())
{
ChangeState(state_Patrol);
}
break;
case state_Patrol:
FollowPatrolPath();
if (Threatened())
{
if (StrongerThanEnemy())
{
ChangeState(state_Attack);
}
else
{
ChangeState(state_RunAway);
}
}
break;
case state_Attack:
if (WeakerThanEnemy())
{
ChangeState(state_RunAway);
}
else
{
BashEnemyOverHead();
}
break;
}//end switch
}

尽管咋一看这个方案还可以，但只要将其应用到比最简单的游戏对象稍为复杂的实际情况下，这个switch/if-then方案就变成了蛰伏在阴影下的怪物——随时都可能突袭你一下。随着大量的状态和条件的增加，那种结构很快就会变得像意大利面条一样，使用程序难以理解，并成为调试梦魇。此外，它不可伸缩并且难以在最初的设计范围之外进行扩展，然而我们都知道，它极为常见。除非你用状态机实现非常简单的行为（或者你是一个天才），否则当你第一次策划状态机的时候，在你“磨合”取得的结果和你希望取得的结果之前，你几乎肯定会发现你的智能体无法应用未考虑到的环境。
此外，作为一名AI程序员，你经常需要在某一状态实现一种特殊行为（或者一系列行为），比如在进入或者离开某一状态的时候。例如当一个智能体进行RunAway（逃跑）状态时你希望它把武器抛向空中并尖叫一声“Arghhhhhh（啊）！”当它成功逃脱并转换到Patrol（巡逻）状态，你可能想让它喘口气、擦擦额头然后说一声“Phew（呸）！”这些行为都只在进入和离开RunAway（逃跑）状态时才会发生，而不是整个普通的update（更新）阶段都会出现。因此这些额外的功能必须被完美地集成到你的状态机架构里。在switch或者if-then架构里实现这些将让人难以忍受，产生的代码将非常丑陋，不忍卒读。


状态转换表
一个能够更好地组织和进行状态转换的机制是状态转换表。顾名思义这就是一个包含条件和条件导致的状态的表。表2.1是前文代码的状态和条件影射表：

表2.1 简单状态转换表


智能体隔一定时间查询这个表格，以使得它能够基于从游戏环境接收到的消息来进行必须的状态转换。每一个状态都能够实现为彼此分离的与智能体不耦合的对象或函数，以提供清晰和可伸缩的架构。这一设计不再那么容易像前文讨论的if-then/switch架构那样容易成为意大利面条。

曾有人告诉我一个明晰而无聊的可视物能帮助人们理解抽象的理论，让我们来看看当它工作时……

想像存在一个机器猫，它闪闪发亮但是非常可爱，有着金属丝制作的胡须并且在胃部有一个插槽——可以依照状态插入可插入模组。每一个可插入模组都是一段逻辑程序，使得小猫能够实现一系列指定的动作。每一系列动作都编码为不同的行为，如play_with_string、eat_fish和poo_on_carpet。如果没有在小猫的胃部插上可插入模组，它就是一件死物——坐在那里，看起来蛮可爱。
这个小猫非常灵巧，并且能够根据指令自动地更换可插入模组。通过给定什么时候该更换可插入模组的规则，它能利用连贯地插入一系列的可插入模组创造所有有趣而复杂的行为。这些与前文讨论的状态转换表相类似的规则被编成程序写入到一个极小的芯片，放置在小猫的头部。芯片与小猫的内部功能通信，以获得处理规则时需要的信息（如Kitty有多饿和它感觉到的好玩度是多少）。状态转换芯片可以用如下的方式编写规则：
IF Kitty_Hungry AND NOT Kitty_Playful SWITCH_CARTRIDGE eat_fish
在每一个时间片都检测表中的所有的规则，从而给Kitty发送指令以切换弹可插入模组。
这种架构有良好的伸缩性，通过增加新的可插入模组就可以轻易扩展小猫的指令表。每一次增加新的可插入模组，只需要用起子打开小猫的头壳，重编程状态转换规则芯片即可，不需要与其它内部电路打交道。

规则内嵌

另一可选的方法是把状态转换规则内嵌到状态本身当中。在对机器猫应用这个概念后，可以去除状态转换芯片，直接将规则内置到可插入模组里。例如play_with_string可插入模组能够监视小猫的饥饿度并适时地命令它切换到eat_fish可插入模组。同样地，eat_fish可插入模组能够监视小猫是否已经吃饱，并在感觉到迫切的排泄感时命令它切换到poo_on_carpet可插入模组。
尽管每一个可插入模组需要知道其它模组的存在，但它们都是自包含的，无论是否要其它模组来替换自己，都并不需要任何外部逻辑来帮助决策。从而可以推论出其中的简明关系，甚至可以用全新的模组集合替换已有的集合（可能这会使用小猫的行为像鸟类一样）。使用这个方案不再需要用起子打开小猫的头部，只要改变可插入模组即可。
现在来看看在视频游戏中如何实现这一方案。像刚才讨论的小猫的可插入模组，可以封装到一个对象里，其中包含辅助状态转换的的逻辑。另外，所有的状态共享一个通用接口：一个命名为State的纯虚类。这里有个接口简单的实现：
Class State
{
public:

virtual void Execute (Troll* troll) = 0;
};

现在想象Troll类有一系列的数值成员变量：health、anger、stamina等，当然也有相应的接口以查询和设置这些变量值。Troll通过增加一个成员指针变量（指向State类派生类的实例）来增加有限状态机的功能，还提供一个改变指针指向的实例的方法。
class Troll
{
/* ATTRIBUTES OMITTED */

State* m_pCurrentState;

public:

/* INTERFACE TO ATTRIBUTES OMITTED */

void Update()
{
m_pCurrentState->Execute(this);
}

void ChangeState(const State* pNewState)
{
delete m_pCurrentState;
m_pCurrentState = pNewState;
}
};
当调用Troll的Update方法时，它以this指针为参数调用当前状态类型的Excecute方法。当前状态可能使用Troll的接口查询它的拥有者，设置拥有者的属性或者产生一个状态转换。换句话说，Troll能依赖当前状态的逻辑作出完整行为。这里有最好的例子表达这一观点，让我们来完成两个状态实现以使得Troll能够在危险时逃跑，或者在安全时睡觉。
//----------------------------------State_Runaway
class State_RunAway : public State
{
public:

void Execute(Troll* troll)
{
if (troll->isSafe())
{
troll->ChangeState(new State_Sleep());
}
else
{
troll->MoveAwayFromEnemy();
}
}
};

//----------------------------------State_Sleep
class State_Sleep : public State
{
public:

void Execute(Troll* troll)
{
if (troll->isThreatened())
{
troll->ChangeState(new State_RunAway())
}

else
{
troll->Snore();
}
}
};

如你所见，当调用Update时，Troll的行为依赖m_pCurrentState指向的状态不同而有所不同。两者状态都封装到对象里，并且都提供了产生状态转换的规则。所有这一切都灵巧而整洁。

这一架构即是有名的状态设计模式，它提供了雅致的状态驱动行为实现。尽管这有违FSM的数学形式，但它符合直觉、易于编码并且容易扩展。它同样也能够极其容易地增加进入和离开状态时的动作；你需要做只是实现 Enter和Exit方法并相应地改变ChangeState方法。你将可以看到完成这些所产生的代码真的非常短小。