从零开始学游戏编程模式之状态机

ChuanXin · 发表于 2022-2-4 13:40

最近在做一个小游戏，整理下状态机的教程：
原文链接：
才疏学浅，欢迎纠错！
<hr/>本文内容包含：

基础的状态机(State Machines)
并发状态机(Concurrent State Machines)
层次状态机(Hierarchical State Machines)
下推自动机(Pushdown Automata)

状态机可以解决的问题？

假如我们正在开发一款横版卷轴游戏，我们需要将用户的操作反应到游戏中的英雄角色上去，比如按下B键，游戏中的英雄角色会进行跳跃操作。我们可能会写出下面的代码：
void Heroine::handleInput(Input input)
{
  if (input == PRESS_B)
  {
yVelocity_ = JUMP_VELOCITY;
setGraphics(IMAGE_JUMP);
  }
}
那么，上面的代码有没有bug呢？
显然，上面的代码没有禁止在英雄角色在空中跳跃，我们可以通过连续按下B键，让英雄飞起来。
我们可以通过添加一个isJumping_变量追踪英雄是否已经跳起，来阻止英雄在空中还能跳跃，代码如下：
void Heroine::handleInput(Input input)
{
  if (input == PRESS_B)
  {
if (!isJumping_)
{
   isJumping_ = true;
   // Jump...
}
  }
}
这时，如果我们还想要让英雄在地面时，按下Down键会有闪避动作，松开Down键恢复站立，可能会写出下面这样的代码：
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？
对于上面的代码，玩家可以做到：

按下Down键让英雄闪避
在英雄闪避的同时按下B键让英雄跳跃
松开Down键时英雄在空中处于站立状态

也就是说英雄可能会在跳起后在空中变成站立状态。
我们继续通过加标记变量来解决bug，代码如下：
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);
}
  }
}
接着，考虑在英雄跳起后，按下Down键，英雄会做出向下俯冲的动作，我们可能会写出下面这样的代码：
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等着我们！
考虑使用有限状态机

尝试在纸上列出英雄可以做的所有行为：站立，跳跃，闪避，向下俯冲。如果英雄在某个行为下玩家按下或松开某个按键可以做出其它行为，就从这个行为连线到可以做出的其他行为，并在连线上标出玩家具体的操作。类似下图：

实际上，我们这时在纸上画出的就是有限状态机(finite state machine)。
定义上来讲，对于一个有限状态机：

只有有限的状态数量。对于我们的例子来说：只有站立，跳跃，闪避，向下俯冲这几个状态。
状态机某一时刻只能处于某一个状态。对于我们的例子来说：我们的英雄不能同时处于跳跃和站立状态。实际上，也是为了阻止这种情况，我们才选择使用有限状态机。
会有一系列输入或者叫事件被状态机处理。对于我们的例子来说就是玩家按下或松开某个按键。
每个状态可以支持一组转换，每个转换由输入(或者叫事件)和目标状态定义。当有一个当前状态所支持的的输入(或者叫事件)到来，状态机会从当前状态转换到目标状态。对于我们的例子来说：当英雄处于站立状态时，玩家按下Down键，英雄会从站立状态转换到闪避状态；当英雄处于跳跃状态时，玩家按下Down键，英雄会从跳跃状态转换到向下俯冲的状态。对于当前状态所没有支持的转换输入到来，状态机会直接忽略掉。

状态，输入和转换构成了状态机。如果在纸上画出来，状态机有点类似流程图。接下来让我们尝试实现一个状态机。
enum和switch

首先是使用枚举(enum)来定义状态，代码如下：
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;
  }
}
相较之前复杂的条件分支，我们将每个状态对应的操作都放在了一起进行处理，这也是最简单的实现状态机的方式。
更进一步，如果我们想要为闪避状态添加一个蓄能作用，在一定时间后，英雄可以发出技能。这就需要我们记录蓄能时间。为此，我们添加一个chargetTime_变量来统计蓄能时间，然后在每帧的update方法中，更新它：
void Heroine::update()
{
  if (state_ == STATE_DUCKING)
  {
chargeTime_++;
if (chargeTime_ > MAX_CHARGE)
{
   superBomb();
}
  }
}
在英雄开始闪避后，我们需要重置chargeTime_变量：
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...
  }
}
为了添加蓄能攻击，我们修改了两个方法update和handleInput，并且添加了一个chargeTime成员变量。但这些修改实际上只对闪避状态有用。显然，对于只对一个状态有用的代码和数据更好的做法是包装在状态内部。
状态模式

状态接口

首先，我们定义一个通用的状态接口，之前代码中的switch下的代码对应现在的虚函数，对于我们这个例子来说，就是handleInput和update这两个虚函数：
class HeroineState
{
public:
  virtual ~HeroineState() {}
  virtual void handleInput(Heroine& heroine, Input input) {}
  virtual void update(Heroine& heroine) {}
};
每个不同的状态实现各自的handleInput和update方法

之前switch语句下每个状态的代码放在自己的类中实现：
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_被我们移动到了DuckingState中，对于其它不需要的状态，不需要定义它。
状态委托

接着，我们在英雄类中通过一个指针来引用英雄的当前状态：
class Heroine
{
public:
  virtual void handleInput(Input input)
  {
state_->handleInput(*this, input);
  }

  virtual void update()
  {
state_->update(*this);
  }

  // Other methods...
private:
  HeroineState* state_;
};
这样每次状态改变，只需要修改指针指向的英雄状态即可。
状态对象应该放在哪里？

我们使用state_指针来指向英雄的当前状态，那么它指向的状态对象又来自哪里？如果是我们最早使用枚举定义的状态，没有任何问题，本质上只是个整数，相当于将state_设置为了一个整数。但现在我们使用类来实现状态，我们就需要指向状态类的一个实例，常见的处理方式如下：
静态状态

对于内部没有任何成员变量的静态状态，我们只需要一份即可。
对于静态状态放在哪里并不重要。在这里，我们将所有静态状态放在了状态的基类中，如下所示：
class HeroineState
{
public:
  static StandingState standing;
  static DuckingState ducking;
  static JumpingState jumping;
  static DivingState diving;

  // Other code...
};
修改英雄的当前状态时，只需要像下面这样做即可：
if (input == PRESS_B)
{
  heroine.state_ = &HeroineState::jumping;
  heroine.setGraphics(IMAGE_JUMP);
}
实例化状态

对于我们的闪避状态，它包含了一个chargeTime_成员变量用来记录蓄力时间。因为我们的游戏可能需要支持多个英雄同时战斗，所以也就没法共享这一个chargeTime_成员变量。
这时，就需要我们在状态转换时创建一个新的状态实例，然后释放掉之前状态实例。又因为改变状态的代码是在状态自身的方法中实现的，不能立即释放旧状态，需要在外部释放掉，为了达成这样的目的，我们采用下面的代码：
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分配内存的耗时，我们应该尽可能地使用静态状态。
进入和退出动作

我们的目标是把和一个特定状态相关的代码都包装在一个状态类中。目前来说，我们还有一些地方没有做到。
当状态改变时，我们现在代码实现是在之前的状态设置新状态的英雄图像：
HeroineState* DuckingState::handleInput(Heroine& heroine,
                                    Input input)
{
  if (input == RELEASE_DOWN)
  {
heroine.setGraphics(IMAGE_STAND);
return new StandingState();
  }

  // Other code...
}
我们更希望状态自己完成英雄状态图像的设置，为此我们为状态添加enter虚函数，然后在其中设置英雄状态图像：
class StandingState : public HeroineState
{
public:
  virtual void enter(Heroine& heroine)
  {
heroine.setGraphics(IMAGE_STAND);
  }

  // Other code...
};
修改之前的代码，使用enter方法完成英雄状态图像设置：
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...
}
现在完全由状态本身来设置它对应的图像。这样做让我们不用再关心转换之前所处的状态。
实际上，我们经常需要从不同的状态转换到同一个状态，比如跳跃状态和向下俯冲状态都会转换到站立状态。enter方法避免了我们重复编写这部分代码。
除了enter方法，我们还可以添加exit方法处理离开一个状态时要做的操作。
有什么用呢？

状态机适合处理一些问题，但也有缺点。
状态机可以帮助我们将混乱的代码逻辑变成有限的几个状态，一个当前状态和若干个硬编码的转换操作。
但对于非常复杂的游戏AI，状态机就变得捉襟见肘。下面我们就介绍几种方式来尝试处理更复杂的游戏逻辑。
并发状态机

假设我们要给英雄添加一个枪支作为武器，英雄在使用枪支的同时仍然可以做之前的事：比如跑，跳跃，闪避等等。
考虑使用状态机实现，我们需要使用双倍的状态：站立，站立射击，跳跃，跳跃射击等等。
仅仅添加一个武器，不仅导致状态的组合爆炸，还造成了大量冗余：携带武器的状态和不携带武器的状态除了处理开火的代码，几乎完全一样。
如果只使用一个状态机，需要为携带武器和不携带武器的每一个组合定义一个状态。而使用两个状态机分别处理相对独立的状态可以避免这一问题。
我们让之前的实现的状态机保持原样，然后新定义一个状态机处理英雄是否携带武器，代码实现如下：
class Heroine
{
  // Other code...

private:
  HeroineState* state_;
  HeroineState* equipment_;
};
接着，在handleInput方法里，加上equipment_状态的处理：
void Heroine::handleInput(Input input)
{
  state_->handleInput(*this, input);
  equipment_->handleInput(*this, input);
}
像这样，每个独立的状态机可以独立地对输入作出反应，独立修改各自的状态。对于几乎不相干的两个状态集合，使用独立的状态机非常不错！
实践中，也会有状态会有一定的交互需求。比如，英雄在跳跃的过程中不能开火，在携带武器的情况下不能向下俯冲。对于这些交互需求，我们可以简单地在各自状态机中使用if语句来做简单的同步处理，虽然做法不优雅，但有效！
层次状态机

随着为英雄添加更多的行为，我们会发现有大量行为类似的状态出现，比如英雄的站立、行走、奔跑和滑行状态，都可能会支持按下B键跳跃，按下Down键闪避。
这些状态的实现包含了大量重复代码，我们最好是想办法只写一次，在多个不同状态重复使用这些代码。
考虑通过面向对象的方式组织代码。我们可以为跳跃、闪避、站立、行走、奔跑和滑行状态定义一个父状态on ground，然后在父状态中处理它们共同的跳跃和闪避行为。
这个父状态被称为super state，继承它的状态被称为sub state。当有输入需要处理时，如果sub state自己不能处理，就由它的super state处理。
下面我们尝试实现它：
class OnGroundState : public HeroineState
{
public:
  virtual void handleInput(Heroine& heroine, Input input)
  {
if (input == PRESS_B)
{
   // Jump...
}
else if (input == PRESS_DOWN)
{
   // Duck...
}
  }
};
接着继承super state实现sub state：
class DuckingState : public OnGroundState
{
public:
  virtual void handleInput(Heroine& heroine, Input input)
  {
if (input == RELEASE_DOWN)
{
   // Stand up...
}
else
{
   // Didn&#39;t handle input, so walk up hierarchy.
   OnGroundState::handleInput(heroine, input);
}
  }
};
除了使用虚函数的方式，我们也可以使用栈来实现相同的功能，每次有输入到来，从当前状态对应的栈的栈顶开始遍历，找到第一个可以处理它的state。
使用栈实现，当前状态位于栈顶，它的super state位于其后。
下推自动机

另一个利用到栈的实现状态机的方法就是下推自动机，但两者解决的问题不同，所以大家不要混淆它们。
下推自动机解决的是状态机的历史状态问题。方便我们回到之前的状态。
比如，我们的英雄在按下开火键后进入开火状态，当按键松开后，英雄回到之前的状态，就需要我们使用栈来完成。
下推自动机支持两个操作：

Push操作：压入一个新的状态到栈中。因为下推自动机的当前状态就是栈顶状态，这就相当于转换到一个新的状态。同时保留了之前的历史状态在栈中。
Pop操作：弹出栈顶状态。栈顶状态被丢弃，之前的历史状态重新成为当前状态。

对于我们的英雄开火行为来说，我们在进入开火状态时进行Push操作，开火结束后，弹出开火状态返回之前的状态。
它们很有用吗？

尽管通过扩展，状态机可以满足很多需求，但仍然很受限制。目前游戏AI的趋势更多是使用行为树(behavior trees)或规划系统(planning systems)。
但这并不意味着状态机没有用，它非常适合下面这些情况使用：

实体的行为改变基于一些内部状态
实体的状态数量较少
实体对一系列输入或事件作出反应

对于游戏来说，状态机常用于角色AI。对于非游戏领域，状态机常用来处理用户输入，导航菜单，文本分析，网络协议以及其它一些需要异步处理的问题。

Baste · 发表于 2022-2-4 13:47

想起个类似的技术，工作流引擎...

		自动登录	找回密码
密码			立即注册

从零开始学游戏编程模式之状态机

本帖子中包含更多资源