软件测试论坛 › [游戏测试] › 状态驱动的游戏智能体设计（中）

51testing 发表于 2007-11-30 14:49:02

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

作为一个如何利用有限状态机的创造智能体的实例，我们创建名为WestWorld的旧西部风格的淘金镇的游戏，并研究其中的智能体实现。一开始只存在一个名为Miner Bob的淘金者，随后他的妻子也出现。你可以想像风滚草、叽叽作响的淘金用具和沙漠的风把沙吹进你的眼睛，因为WestWorld只是一个简单的基于文本的控制台程序。所有的状态改变和状态动作产生的输出都作为文本传送到控制台窗口。我使用纯文本的原因是为了清晰地示范有限状态机的机制，不想增加代码以免搞得太过于复杂。
WestWorld有四个场景：一个金矿、一个储藏库（Bob把找到的金块存放在这里）、一个酒吧（喝水吃饭）和一个家（睡觉）。确切来讲就是他去哪里、做什么和什么去，都由Bob当前的状态决定。他根据饥渴度、疲惫度和从金旷获得的金块数量来改变状态。
在我们研究代码之前，我们先来看看WestWorld1可执行文件产生的输出：
Miner Bob: Pickin' up a nugget
Miner Bob: Pickin' up a nugget
Miner Bob: Ah'm leavin' the gold mine with mah pockets full o' sweet gold
Miner Bob: Goin' to the bank. Yes siree
Miner Bob: Depositin’ gold. Total savings now: 3
Miner Bob: Leavin' the bank
Miner Bob: Walkin' to the gold mine
Miner Bob: Pickin' up a nugget
Miner Bob: Ah'm leavin' the gold mine with mah pockets full o' sweet gold
Miner Bob: Boy, ah sure is thusty! Walkin' to the saloon
Miner Bob: That's mighty fine sippin liquor
Miner Bob: Leavin' the saloon, feelin' good
Miner Bob: Walkin' to the gold mine
Miner Bob: Pickin' up a nugget
Miner Bob: Pickin' up a nugget
Miner Bob: Ah'm leavin' the gold mine with mah pockets full o' sweet gold
Miner Bob: Goin' to the bank. Yes siree
Miner Bob: Depositin' gold. Total savings now: 4
Miner Bob: Leavin' the bank
Miner Bob: Walkin' to the gold mine
Miner Bob: Pickin' up a nugget
Miner Bob: Pickin' up a nugget
Miner Bob: Ah'm leavin' the gold mine with mah pockets full o' sweet gold
Miner Bob: Boy, ah sure is thusty! Walkin' to the saloon
Miner Bob: That's mighty fine sippin' liquor
Miner Bob: Leavin' the saloon, feelin' good
Miner Bob: Walkin' to the gold mine
Miner Bob: Pickin' up a nugget
Miner Bob: Ah'm leavin' the gold mine with mah pockets full o' sweet gold
Miner Bob: Goin' to the bank. Yes siree
Miner Bob: Depositin' gold. Total savings now: 5
Miner Bob: Woohoo! Rich enough for now. Back home to mah li'l lady
Miner Bob: Leavin' the bank
Miner Bob: Walkin' home
Miner Bob: ZZZZ...
Miner Bob: ZZZZ...
Miner Bob: ZZZZ...
Miner Bob: ZZZZ...
Miner Bob: What a God-darn fantastic nap! Time to find more gold

从程序的输出来看，Miner Bob每一次改变他所处的场景时，他都会改变状态。所有的其它事件都发生在状态里的动作。我们将会检测Miner Bob在每一时刻的每一个潜在状态，但现在让我来对demo的代码结构稍作解释。


BaseGameEntity类
WeskWorld游戏里的所有物体都从BaseGameEntity类派生。这是只有一个私有成员（用以保存ID）的简单类，此外就只有一个纯虚函数Update了，它必须在子类中实现。Update函数将在更新步骤里调用，用以给子类在每一个时间片依据其它数据更新他们的状态机里必须被更新的其它数据。

BaseGameEntity的声明如下：
class BaseGameEntity
{
private:

//every entity has a unique identifying number
int m_ID;

//this is the next valid ID. Each time a BaseGameEntity is instantiated
//this value is updated
static int m_iNextValidID;

//this is called within the constructor to make sure the ID is set
//correctly. It verifies that the value passed to the method is greater
//or equal to the next valid ID, before setting the ID and incrementing
//the next valid ID
void SetID(int val);

public:

BaseGameEntity(int id)
{
SetID(id);
}

virtual ~BaseGameEntity(){}

//all entities must implement an update function
virtual void Update()=0;

int ID()const{return m_ID;}
};


为游戏里的每一个实体设置一个唯一的ID是非常重要的，在本书后面的章节将为你讲述为什么非常重要。因此，在实例化的时候把ID通过构造函数传递，并通过SetID函数来测试它是否唯一，如果不唯一，程序将会退出，产生一个断言失败错误。在本文的例子中，将把一个枚举值作为唯一的ID，在EntityNames.h文件里可以找到ent_Miner_Bob和ent_Elsa等枚举值。

Miner类
Miner类从BaseGameEntity类派生，它包括健康、疲惫程度和位置等数据成员。像前文描述过的Troll例子，Miner也有一个指向State类实例的指针，当然也少不了用以改变State指针所指向的实例的方法。
Class Miner : public BaseGameEntity
{
private:

//a pointer to an instance of a State
State* m_pCurrentState;

// the place where the miner is currently situated
location_type m_Location;

//how many nuggets the miner has in his pockets
int m_iGoldCarried;

//how much money the miner has deposited in the bank
int m_iMoneyInBank;

//the higher the value, the thirstier the miner
int m_iThirst;

//the higher the value, the more tired the miner
int m_iFatigue;

public:

Miner(int ID);

//this must be implemented
void Update();

//this method changes the current state to the new state
void ChangeState(State* pNewState);

/* bulk of interface omitted */
};


Miner::Update方法直接明了：它在调用当前状态的Execute方法之前简单地增加m_iThirst。它的实现如下：
void Miner::Update()
{
m_iThirst += 1;

if (m_pCurrentState)
{
m_pCurrentState->Execute(this);
}
}


现在你知道Miner类的操作了，让我们来看看它的每一个状态是怎么样的。

Miner的状态
淘金者Bob能够进入这四个状态之一。下文是这些状态的名字（结合了动作的描述），状态转换发生在状态内部。
EnterMinAndDigForNugget：当Bob不在金矿的时候，他移动到金矿。如果已经在金矿，他会持续掘金。直到他的袋子装满金矿石，Bob将会转换到VisitBankAndDepositGold状态。但如果在掘金的时候觉得饥渴，他就会停下来，把状态转换到QuenchThirst。
VisitBankAndDepositGold：处于这个状态时淘金者会走到储藏库并把带来的金矿石保存起来。如果他觉得自己足够富有，他就转换到GoHomeAndSleepTilRested状态，否则就转换到EnterMineAndDigForNugget。

GoHomeAndSleepTilRested：处于此状态的淘金者会返回到他的房子里睡觉，直到疲惫程序下降到可接受的情况，这时转换到EnterMineAndDigForNugget。
QuenchThirst：任何时候当淘金者感到饥渴，他就改变他的状态去商店买威士忌，解渴后转换到EnterMineAndDigForNugget。
通过阅读来理解状态逻辑流是相当困难的，所以最后为你的游戏智能体画一张状态转换图。图2.2是淘金者的状态转换图，圆角矩形是独立的状态，它们之间的连线是允许的转换。
一个这样的图示有助于我们理解，也更容易找出逻辑流中的错误。
http://www.ai-junkie.com/architecture/state_driven/tut_state2_files/image001.jpg

图2.2 淘金者Bob的状态转换图

重温状态设计模式
之前已经对这个模式作了简单介绍，但不够深入。每一个游戏智能体的状态机都作为唯一的类来实现，智能体拥有一个指向当前状态实例的指针。智能体需要实现ChangeState成员函数以实现状态切换。决定状态转换的逻辑包含在每一个State派生类的内部。所有的状态类都从一个抽象类派生，以获得统一接口。现在，你已经知道足够多关于状态设计模式的知识了。
之前也提及过通常每一个状态都有相应的Enter和Exit动作，这将使得程序员能够编写仅在进入或者离开状态只执行一次的逻辑以增强FSM的可伸缩性。为了实现这一点，让我们来看看改进后的State基类。
class State
{
public:

virtual ~State(){}

//this will execute when the state is entered
virtual void Enter(Miner*)=0;

//this is called by the miner’s update function each update-step
virtual void Execute(Miner*)=0;

//this will execute when the state is exited
virtual void Exit(Miner*)=0;
}
这两个方法仅在Miner改变状态的时候调用，当发生一个状态转换，Miner::ChangeState方法首先调用当前状态的Exit方法，然后它为当前状态指派一个新的状态，最后调用新状态的Enter方法。我认为代码比言语更清晰，所有这里列出ChangeState方法的代码：
void Miner::ChangeState(State* pNewState)
{
//make sure both states are valid before attempting to
//call their methods
assert (m_pCurrentState && pNewState);

//call the exit method of the existing state
m_pCurrentState->Exit(this);

//change state to the new state
m_pCurrentState = pNewState;

//call the entry method of the new state
m_pCurrentState->Enter(this);
}

注意Miner把this指针传递到每一个状态，使得状态能够使用Miner的接口获取相关数据。
提示：状态设计模式对于游戏主流程的组织也是非常有用的，例如，你可能有菜单状态、保存状态、暂停状态、设置状态和运行状态等。

Miner可能处于四个状态之一，它们都从State类派生而来，具体是：EnterMineAndDigForNugget，VisitBankAndDepositGold，GoHomeAndSleepTilRested和QuenchThirst。Miner::m_pCurrrentState可能指向其中的任何一个。当Miner的Update方法被调用，它就以this指针为参数调用当前活动状态的Execute方法。如果你能看图2.3的UML图，应该很容易理解这些类之间的关系。

每一个状态都以单件对象的形式实现，这是为了确保只有一个状态的实例，所有的智能体共享这一实例（想了解什么是单件，可以阅读这个文档）。使用单件使得这一设计更加高效，因为避免了在每一次状态转换的时候申请和释放内存。这在你有很多智能体共享复杂的FSM的时候变得极其重要，特别是你在资源受限的机器上进行开发的话

http://school.ogdev.net/upload/img/4856172912.gif

图2.3 Miner Bob的状态机实现的UML类图

注意：我乐于使用单件的原因在上文已经给出，但这也有一个缺陷。因为他们由客户共享，单件状态不能使用他们自有的，特定智能体的数据。例如，当某一处于某状态的智能体移动到某一位置时，他不能把这一位置存储在状态内（因为这个状态可能与其它正处于这一状态的智能体不同）。它只能把它存储在其它地方，然后由状态机通过智能体的接口来存取。如果你的状态只有一两个数据要存取，那这也不是什么大问题，但如果你在很多外部数据，那可能就值得考虑放弃单件设计，而转而写一代码来管理状态内存的申请与释放了。

好了，现在让我们来看看如何把所有的东西都融合在一起完成一个淘金者的状态。

EnterMineAndDigForNugget状态
淘金者在这个状态会改变所在地，去到金矿场，到矿场后就开始掘金，直到装满口袋，这时改变状态到VisitBankanDepositNugget。如果掘金中途感到口渴，淘金者就转换到QuenchThirst状态。

因为具类只是简单地实现虚基类State定义的接口，它们的声明非常简明：
class EnterMineAndDigForNugget : public State
{
private:

EnterMineAndDigForNugget(){}

/* copy ctor and assignment op omitted */

public:

//this is a singleton
static EnterMineAndDigForNugget* Instance();

virtual void Enter(Miner* pMiner);

virtual void Execute(Miner* pMiner);

virtual void Exit(Miner* pMiner);
};

如你所见，这只是一个模式，让我们来看看其它方法。

EnterMineAndDigForNugget::Enter

下面是EnterMineAndDigForNugget的Enter方法：
void EnterMineAndDigForNugget::Enter(Miner* pMiner)
{
//if the miner is not already located at the goldmine, he must
//change location to the gold mine
if (pMiner->Location() != goldmine)
{
cout << "\n" << GetNameOfEntity(pMiner->ID()) << ": "
<< "Walkin' to the goldmine";

pMiner->ChangeLocation(goldmine);
}
}

当淘金者第一次进入EnterMineAndDigForNugget状态时调用这个方法，这确保淘金者位于金矿场。智能体以枚举量的形式保存当前位置，ChangeLocation方法用以改变位置值。


EnterMineAndDigForNugget::Execute
Execute有点复杂，它包含了改变淘金者状态的逻辑。（不要忘记Miner::Update在每一个更新帧都会调用Execute方法。）
void EnterMineAndDigForNugget::Execute(Miner* pMiner)
{
//the miner digs for gold until he is carrying in excess of MaxNuggets.
//If he gets thirsty during his digging he stops work and
//changes state to go to the saloon for a beer.
pMiner->AddToGoldCarried(1);

//digging is hard work
pMiner->IncreaseFatigue();

cout << "\n" << GetNameOfEntity(pMiner->ID()) << ": "
<< "Pickin' up a nugget";

//if enough gold mined, go and put it in the bank
if (pMiner->PocketsFull())
{
pMiner->ChangeState(VisitBankAndDepositGold::Instance());
}

//if thirsty go and get a beer
if (pMiner->Thirsty())
{
pMiner->ChangeState(QuenchThirst::Instance());
}
}

值得注意的是Miner::ChangeState方法调用了QuenchThirst和VisitBankAndDepositGold的Instance成员函数，以获得指向该类唯一实例的指针。

EnterMineAndDigForNugget::Exit

EnterMineAndDigForNugget的Exit方法只是简单地输出一条消息告诉我们淘金者离开了金矿。
void EnterMineAndDigForNugget::Exit(Miner* pMiner)
{
cout << "\n" << GetNameOfEntity(pMiner->ID()) << ": "
<< "Ah'm leavin' the goldmine with mah pockets full o' sweet gold";
}

我希望前述的三个方法能帮助你理清头绪，现在你应该已经理解了每一个状态怎么改变智能体的行为，又如何从一个状态到另一个状态转换。你用IDE打开WestWorld1项目并浏览一遍代码应该有助于理解，可以抽取出MinerOwnedStates.cpp里的所有状态并检阅Miner类实现，让你熟悉它的成员变量。最重要的是，确定你理解了状态设计模式是如何工作的，然后再作进一步阅读。如果你有一些不了解，请重温上文直到你觉得已经完全理解了相关理论。
正如你所见，状态设计模式为状态驱动的智能体提供了具有非常好的伸缩性的机制，当需要的时候，你可以极其容易地增加新的状态。在你有非常复杂的设计，而且能更好地组织一系列的分散的小状态机的时候，甚至可以替换智能体的整个状态架构。例如，像Unreal2这样的第一人称射击游戏（FPS）有着巨大而复杂的状态机，当设计这种游戏的AI的时候，你将发现它能完美地应用于基于团队而设计的多个小状态机（对应的功能可能是“保旗”或者“探险”），使得能够在需要的时候进行切换。正在状态设计模式使它易于实现。

查看完整版本: 状态驱动的游戏智能体设计（中）