游戏编程设计模式-state
发表于2016-03-12
认错时刻：在这一章里，我有的包装和修饰有点过分了。看起来是在讲状态模式，但是我发现如果不讲有限状态机的基本概念，我几乎没法讨论状态模式和游戏。但是一旦我讲了，感觉就像是在介绍分层状态机和下推自动机。
这样牵扯的太多了，所以为了尽量保持简洁，实例代码留下了一些细节需要你自己去填写。我希望他们仍然能够表达清楚大体意思。
如果你没听说过状态机也不要慌。虽然在AI和编译器黑客们那里很常见，但是其他领域的程序员可能不熟悉。我想他们应该被广泛认知，所以我将在不同的问题中抛出他们。
一、其实我们早就知道
我们在做一个横向卷轴的小游戏。我们的工作是实现一个女英雄（heroine），就是玩家在游戏世界的阿凡达。也就是说她要相应玩家的输入。按B键她就会跳。很简单：
void Heroine::handleInput(Input input){
if (input == PRESS_B){
yVelocity_ = JUMP_VELOCITY;
setGraphics(IMAGE_JUMP);
}
}
出Bug了？
没有东西能够组织“跳跃”动作——当她在空中的时候持续按B键，她就永远悬在空中了。简单地解决办法是为Heroine类添加一个isJumping_布尔值，当她起跳的时候设为true，然后：
void Heroine::handleInput(Input input){
if (input == PRESS_B){
if (!isJumping_){
isJumping_ = true;
// Jump...
}
}
}
然后，当她站立时，一旦玩家按向下键，我们想让heroine下水。放开按键后回到站立状态。
void Heroine::handleInput(Input input){
if (input == PRESS_B){
// Jump if not jumping...
}else if (input == PRESS_DOWN){
if (!isJumping_){
setGraphics(IMAGE_DUCK);
}
}else if (input == RELEASE_DOWN){
setGraphics(IMAGE_STAND);
}
}
仍然有bug？
这些代码，玩家可以：
1、按向下键入水。
2、按B键从潜水的位置上起跳。
3、在空中释放向下键。
heroine就会在跳跃中间变成站立样子。应该加入另一个标志了：
void Heroine::handleInput(Input input){
if (input == PRESS_B){
if (!isJumping_ && !isDucking_){
// Jump...
}
}else if (input == PRESS_DOWN){
if (!isJumping_){
isDucking_ = true;
setGraphics(IMAGE_DUCK);
}
}else if (input == RELEASE_DOWN){
if (isDucking_){
isDucking_ = false;
setGraphics(IMAGE_STAND);
}
}
}
下一步，如果玩家在跳跃的中间按向下键，进行一个俯冲攻击，那一定很酷：
void Heroine::handleInput(Input input){
if (input == PRESS_B){
if (!isJumping_ && !isDucking_){
// Jump...
}
}else if (input == PRESS_DOWN){
if (!isJumping_){
isDucking_ = true;
setGraphics(IMAGE_DUCK);
}else{
isJumping_ = false;
setGraphics(IMAGE_DIVE);
}
}else if (input == RELEASE_DOWN){
if (isDucking_){
// Stand...
}
}
}
又到了找bug时间了。
我们发现你再跳跃时不能再次跳跃，但是在俯冲和其他状态下可以…
通过我们的方法，能找到一些明显的错误。每次我们动一动这些棘手的代码，都会引起一些错误。我们需要加入更多地运动——我们甚至还没有加入“走路”——但是照这样下去，在我们处理它之前，就会引起一系列的bug。
二、有限状态机救驾
面对这种挫折，你要清理掉桌面上的所有东西，只剩下一支笔和一张纸，开始画流程图。你画一个矩形代表heroine可以做的每一个动作：站立、跳跃、下潜和俯冲。当她能从一种状态响应一个按键消息，你画一个从这个矩形出发的箭头，并且用这个按钮来标记箭头，用它来指向下一个状态。
恭喜，你已经创建了一个有限状态机（FSM）。这出自计算机科学的一个叫做自动机理论的分支。这个家族里里还有大名鼎鼎的图灵机。FSM是这个家族最简单地一个成员。要点如下：
1、状态机的状态集合是确定的。例如在我们的例子里，有站立、跳跃、下蹲和俯冲。
2、状态机在某一时刻只能处于一种状态。我们的heroine不能同时跳跃和站立。其实，避免出现这种状况正是我们使用FSM的原因。
3、一连串的输入或者事件发送到这个状态机。我们的例子里，就是一串按键和释放消息。
4、每一种状态都由一些转化路径，每一个路径都通过一个输入关联到另外一种状态。当一个输入进来后，如果正好跟一个当前的转化路径匹配，状态机就会转到它所指向的另一个状态。
例如，站立的时候按向下键，转换到下蹲状态，跳跃的时候按向下键，转换到俯冲状态。如果当前状态下没有定义某种操作相应的转化，那这种操作将会被忽略。
理想状态下，状态机里就只有：状态，输入，转化这些东西了。你可以画一个很小的图表示出来。但是编译器并不能识别我们的草图，我们要怎么实现他们呢？GOF的State模式就是一种方法，下面将会讲到，让我从简单的入手。
三、枚举与开关
我们的Heroine类有一个问题就是无法使用这几个布尔值得组合，例如isJumping_和isDucking_永远不可能都为true。当你确定这些标志不可能同时为true时，这就表示你真正应该使用的是枚举。
在这个例子中，枚举就是我们FSM的状态集合，所以我们可以这样定义：
enum State{
STATE_STANDING,
STATE_JUMPING,
STATE_DUCKING,
STATE_DIVING
};
Heroine类不再需要一堆标志了，取而代之的是一个state_属性。并且需要颠倒代码的顺序。在前面的代码里，我们先判断输入，然后是状态。这把一个键的相关代码放在了一起，但是关于状态的代码被分散了。我们希望让它们集中起来，所以先判断状态，代码如下：
void Heroine::handleInput(Input input){
switch (state_){
case STATE_STANDING:
if (input == PRESS_B){
state_ = STATE_JUMPING;
yVelocity_ = JUMP_VELOCITY;
setGraphics(IMAGE_JUMP);
}else if (input == PRESS_DOWN){
state_ = STATE_DUCKING;
setGraphics(IMAGE_DUCK);
}
break;
case STATE_JUMPING:
if (input == PRESS_DOWN){
state_ = STATE_DIVING;
setGraphics(IMAGE_DIVE);
}
break;
case STATE_DUCKING:
if (input == RELEASE_DOWN){
state_ = STATE_STANDING;
setGraphics(IMAGE_STAND);
}
break;
}
}
}
这看起来很散乱，但是其实已经比前面的代码有很大进步了。我们仍然有很多判断分支，但是我们把分散的状态归纳到了一个地方。处理同一个状态的代码被很好的集中在一起。这是实现状态机的最简单的方式，而且在某些应用场景工作的很好。
但是你遇到的问题会超出这个解决方案的范围。比如说，我们想添加一个改动，让heroine能够下蹲蓄力然后发出一个特殊的大招。当她下蹲的时候，我们要记录时间。
我们在Heroine中添加一个 chargeTime_属性，用来记录她下蹲了多长时间。假如我们有一个update()函数，每帧调用一次。我们在其中加入代码：
void Heroine::update(){
if (state_ == STATE_DUCKING){
chargeTime_++;
if (chargeTime_ > MAX_CHARGE){
superBomb();
}
}
}
我们需要在她开始下蹲前重置这个计时器，所以修改handleInput函数：
void Heroine::handleInput(Input input)
{
switch (state_)
{
case STATE_STANDING:
if (input == PRESS_DOWN)
{
state_ = STATE_DUCKING;
chargeTime_ = 0;
setGraphics(IMAGE_DUCK);
}
// Handle other inputs...
break;
// Other states...
}
}
总之，为了添加大招，我们必须修改两个方法，并且在Heroine类中加入chargeTime_属性。尽管它只在下蹲状态下有意义。我们最理想的情况是把这些代码和数据封装在一起，GOF该出场了。
四、State模式
面向对象思想已经深入人心，每一种判断分支都提供了一个动态分配的机会（C++中用的是另外一个说法叫虚函数调用）。我想这是个坑，优势其实你所需要的只是一个if语句。
但是在我们的实例中，恰好更适合面向对象。它让我们能够使用State模式，GOF的描述是：
允许一个对象在内部状态改变时，改变其行为。这个对象会表现为改变它的类型。
这并没有告诉我们太多信息。搞笑的是swtch却做到了。这个模式的描述如果应用到我们的heroine上，会是这一个样子：
1、一个state 接口
首先，我们定义一个state的接口。每一个状态依赖的方法——之前我们放switch语句的地方——变成了一个虚方法。在这里就是handleInput() 和 update()
class HeroineState
{
public:
virtual ~HeroineState() {}
virtual void handleInput(Heroine& heroine, Input input) {}
virtual void update(Heroine& heroine) {}
};
2、每一个状态对应的类
对每种状态我们定义一个类去实现这个接口。它的方法定义了heroine在这个状态下的行为。也就是说，我们把原来swtich语句中每个case下的代码，移到了他们各自状态对应的类中。例如：
class DuckingState : public HeroineState
{
public:
DuckingState()
: chargeTime_(0)
{}
virtual void handleInput(Heroine& heroine, Input input) {
if (input == RELEASE_DOWN)
{
// Change to standing state...
heroine.setGraphics(IMAGE_STAND);
}
}
virtual void update(Heroine& heroine) {
chargeTime_++;
if (chargeTime_ > MAX_CHARGE)
{
heroine.superBomb();
}
}
private:
int chargeTime_;
};
注意我们把chargeTime_从Heroine类中移到了DuckingState类中。这是极好的——这条数据只在这个状态下有意义，现在我们的对象模型很明显得反应了这一点。
3、状态的代理
下一步，我们在Heroine中添加一个指向当前状态的指针，去掉那些大switch语句，把他们代理给 state：
class Heroine
{
public:
virtual void handleInput(Input input)
{
state_->handleInput(*this, input);
}
virtual void update()
{
state_->update(*this);
}
// Other methods...
private:
HeroineState* state_;
};
如果要切换状态，我们只需要将state_指针指向另外一个HeroineState对象即可。这就是State模式的
五、State对象在哪里
我在这里隐藏了一点细节。为了改变状态，我们需要让state_指向一个新的State对象，但是这些对象从哪里来呢？在我们的枚举实现中，他们是一些简单的数。但是现在状态是类，这就意味着我们需要指向一个实在的对象实例。这里有两种答案：
1、静态状态
如果状态对象没有其他的属性，那么他只会存储一个指向内部虚函数表的指针。这样，没有理由创建多个实例。每一个状态的实例都应该是唯一的。
这样，你可以用一个静态实例。即使你有一堆FSM 都用到了同一个状态，他们也可以指向同一个状态对象，因为它没有对某个状态机进行特化。
这些静态实例放在什么地方，取决于你。找一个合适的地方。如果没有特殊原因，我们可以放在基类里：
class HeroineState
{
public:
static StandingState standing;
static DuckingState ducking;
static JumpingState jumping;
static DivingState diving;
// Other code...
};
每一个静态域都是游戏中用到的状态对象。为了让heroine跳跃，站立状态可以像这样：
class HeroineState
{
public:
static StandingState standing;
static DuckingState ducking;
static JumpingState jumping;
static DivingState diving;
// Other code...
};
2、实例化状态
有时这种方法并不可行。静态状态不适合下蹲状态，它有一个chargeTime_属性，这个属性绑定在下蹲的heroine。不过这个恰巧在我们的游戏中也能用，因为我们只有一个heroine，但如果我们要加入两个玩家的玩法，在同一个名目中有两个heroine，就会出问题了。
这种情况下，我们必须在切换到一个状态的时候，创建它。这样才能做到每一个FSM都有专属自己的状态实例。当然，每当我们构建一个新状态，就要释放掉当前的状态对象。这里需要小心，因为触发切换的代码是在当前的状态对象中，我们不希望在这些对象中用delete this的方式销毁自己。
取而代之的是我们让HeroineState中的handleInput()方法能够返回一个新状态。如果返回了， Heroine就销毁老状态，切换到新状态上，就像这样：
void Heroine::handleInput(Input input)
{
HeroineState* state = state_->handleInput(*this, input);
if (state != NULL)
{
delete state_;
state_ = state;
}
}
这样，我们直到返回一个新状态后，才销毁掉前一个状态。现在站立状态可以用创建新对象的方式切换到下蹲状态。
HeroineState* StandingState::handleInput(Heroine& heroine,
Input input)
{
if (input == PRESS_DOWN)
{
// Other code...
return new DuckingState();
}
// Stay in this state.
return NULL;
}
如果可能，我会尽量使用静态状态，因为他们不消耗更多的内存和用来申请内存的CPU时钟。对状态来说，这些消耗太大了，尽管这也是一个方法。
六、进入和退出动作
State模式的目的在于把一种状态的代码和数据归到一个单独的类中。我们基本实现了，但是还有一些收尾工作。
当heroine改变状态，我们还要切换她的图片。现在这些代码被放在了前一个状态中。从下蹲到站立的过程，在下蹲的状态中设置站立的图片：
HeroineState* DuckingState::handleInput(Heroine& heroine,
Input input)
{
if (input == RELEASE_DOWN)
{
heroine.setGraphics(IMAGE_STAND);
return new StandingState();
}
// Other code...
}
我们想要的是每一个状态都控制它自己的图片，我们可以给状态添加一个entry动作，来做这个事情：
class StandingState : public HeroineState
{
public:
virtual void enter(Heroine& heroine)
{
heroine.setGraphics(IMAGE_STAND);
}
// Other code...
};
回到Heroine，我们修改代码，把状态改变后的变化放在新状态的调用中：
void Heroine::handleInput(Input input)
{
HeroineState* state = state_->handleInput(*this, input);
if (state != NULL)
{
delete state_;
state_ = state;
// Call the enter action on the new state.
state_->enter(*this);
}
}
现在我们就可以简化下蹲代码了：
HeroineState* DuckingState::handleInput(Heroine& heroine,
Input input)
{
if (input == RELEASE_DOWN)
{
return new StandingState();
}
// Other code...
}
它只需要切换到站立状态，而让站立状态自己去关心图像。现在我们的状态才算真正的归类了。进入事件只需要关注进入状态，而不用关心是从哪个状态转化而来。
现实中的状态图中，会有多个转化路径到同一个状态。例如，heroine跳跃和俯冲后都会进入站立状态。这就意味着我们会把一些相同的代码散布在这些地方。进入事件让我们可以把它们归拢到一个地方。
当然，我们也可以支持退出事件。其实就是一个离开一个状态时调用的方法。
七、有坑吗？
我用了大量的时间向大家兜售FSM，现在我要收一收了。到目前为止我说的都对，FSM也很好得解决了一些问题。但是他们最大的优点也是最大的缺点。
状态机帮助你整理一些杂乱的代码，用的方法把他们强制套用到一个结构中。你得到的就是一些状态集合，一个当前状态，和一些写死的转化。
如果你试着用状态机去做一些复杂的工作，如游戏AI，你会被它带来的很多限制甩一脸。幸运的是，我们的前辈们已经找到了很多方法去避开这些坑。在最后，我带大家来看看这些办法。
八、并发状态机
我们决定让heroine能带枪。当她带枪的时候，她仍然可以做他之前能做的所有动作：跑、跳、下蹲等等。但是她需要在做这些动作的同时开枪。
如果我们严格按照FSM来做，我们必须有原来两倍数量的状态机。对每个已有的状态，我们都要有一个对应的持枪动作：站立，持枪站立，跳跃，持枪跳跃。。。你懂得。
添加更多的武器，会组合出更多的状态。不止会产生大量的状态，还会产生大量的冗余。有武器和没有武器的状态几乎是相同的，除了少数的开火代码。
问题是我们把两种状态——她做了什么和她拿着什么——混淆进了一个状态机。为了产生所有组合，我们需要为每一对组合产生一个状态。解决办法也很明显：用两个分离的状态机。
我们保留原有的状态机，支持原来的功能。然后为她携带的武器单独定义一个状态机。Heroine将会两个状态引用，就像这样：
class Heroine
{
// Other code...
private:
HeroineState* state_;
HeroineState* equipment_;
};
当heroine响应状态输入的时候，她要处理两者：
void Heroine::handleInput(Input input)
{
state_->handleInput(*this, input);
equipment_->handleInput(*this, input);
}
每个状态机都可以响应输入，产生行为，并且变换状态时相互没有依赖。如果两个撞他集合几乎没有联系，它们会工作的很好。
在实际应用中，你会发现有的情况下这些状态会有交集。例如，可能她在跳跃的时候不能开火，或者可能她有装备的时候不能俯冲。要处理这个问题，在一种状态的代码里，你可能加入一些if语句去判断另一个状态机的状态。这不是一个优雅的解决方案，但是有效。
分层状态机
在给我们的heroine加强了一些行为以后，她拥有了一些相似的状态。例如，她会有站立，行走，跑，滑行等状态。它们都是按B跳跃，按向下就下蹲。
用简单的状态机实现方法，我们必须把这些代码在每一个状态中写一遍。如果我们能实现一遍然后在所有的状态中复用，那就更好了。
如果这只是一些面向对象的代码而不是状态机，一个复用代码的方法就是用继承。我们需要定义一个底层的状态，处理跳跃和下蹲。站立，行走，跑和滑行要继承它，并且加入他们附加的行为。
原来，这是一个常见的结构叫做分层状态机。一个状态可以有一个超状态（这样它就成了子状态）。当一个事件进来后，如果子状态不去处理它，事件将会沿着链条传递给超状态。另一种说法，它就像覆盖继承方法。
事实上，如果我们用到State模式去实现FSM，我们可以使用类继承去实现层次化。定义一个超状态基类：
class OnGroundState : public HeroineState
{
public:
virtual void handleInput(Heroine& heroine, Input input)
{
if (input == PRESS_B)
{
// Jump...
}
else if (input == PRESS_DOWN)
{
// Duck...
}
}
};
然后每个子状态继承它：
class DuckingState : public OnGroundState
{
public:
virtual void handleInput(Heroine& heroine, Input input)
{
if (input == RELEASE_DOWN)
{
// Stand up...
}
else
{
// Didn't handle input, so walk up hierarchy.
OnGroundState::handleInput(heroine, input);
}
}
};
这当然不是实现层次化的唯一方法。如果你不用GOF的State模式，这就不会奏效。然而，你可以用显式得使用状态栈来表示当前的超状态链，在宿主类（Heroine）中用它来替换那个单一的状态（state_）。
当前的状态就是栈顶的那个状态，它下面的就是它的直接超状态，然后是超状态的超状态，以此类推。当你遇到这个状态对应的行为时，从栈顶开始往下传递，直到有一个状态处理了它。（如果没有，就忽略。）
九、下推自动机
有限状态机另外有一个扩展就是使用栈式状态。不过容易使人迷惑的是，栈代表了完全不同的东西，经常被用来解决其他问题。
有限状态机的一个问题在于它不保留历史记录。你知道你当前的状态是什么，但是不记得之前的状态。并且没有返回到之前状态的简单办法。
这里有一个例子：前面，我们把我们无畏的heroine武装到了牙齿。当她开火的时候，我们需要一个新状态来播放开火动画，发射子弹和一些视觉特效。所以我们把他们放在FiringState中，在所有能够开火的状态中，添加一个到开火状态的转化。
问题是，当她开火完了之后，进入什么状态呢？她在站立、跑动、跳跃或者下蹲的时候，都能突然开火。当开火的一系列动作完成后，她应该返回到原来的的状态下。
如果我们必须要使用传统FSM，就已经忘掉她之前的状态了。为了解决这个问题，我们必须定义一些特定的状态——站着射击，跑着射击，跳着射击等等——这仅仅为了能写死一些代码，使得能转化回原来的状态。
我们真正希望的是一种能够记住射击前状态的方法，供后面使用。自动机就是一个有用的策略。相应的数据结构叫做下推自动机。
有限状态机有一个指向状态的指针，而下推自动机却有一个由这些指针构成的栈。在FSM中，转换状态用的是用一个新状态替换原来的。一个下推自动机也允许你这么做，不过它还提供另外一种操作：
1、你可以在栈中压入一个新状态，当前状态始终位于栈顶，所以这也相当于转换了新状态。但这把原状态留在了它下面，而不是直接丢弃掉。
2、你可以弹出栈顶的状态，丢掉，它下面的状态就变成了当前状态。
这正是我们开火所需要的。我们只需要创建一个开火状态。当在其他状态下开火键被按下时，我们把开火状态压入到栈中。等到开火动作结束后，我们弹出这个状态，然后下推自动机会自动得帮我们把状态转换到原有状态上。
十、那么他们有用吗？
即使那些扩展过的状态机，也有很多限定条件。当今游戏AI发展趋势是那些更吸引人的东西，如行为树，计划系统。如果你对更复杂的AI感兴趣，本章的内容旨在唤起你的兴趣。你需要阅读其他书籍来满足你的需求。
这不说明有限状态机，下推自动机，和其他简单系统没有用。他们是对一些特定的问题是一个很好的模型工具。有限状态机在下面的情况下比较有用。
1、你有一个东西，它的行为是基于一些内部状态的。
2、这些状态能够很容易地分离出少量明确的选项。
3、随着时间变化，这个东西要相应一系列输入和事件。
在游戏中，最有名的用法是在AI中。而在其他用法也很常见，如处理用户输入，菜单导航，解析文本，网络协议，以及一些其他异步行为。
加入GAD的核心用户QQ群：484290331，各类活动奖励任你拿，最新资讯任你读，众多教学任你免费学，如此好地方赶紧加入吧！另VR专属群：476511561，专业VR技术分享，专业导师指导为你答疑解惑，大型小型活动奖励等你拿，免费学习赚奖励的天地，欢迎你加入哟！