02.6-State.md

状态模式

Confession time: I went a little overboard and packed way too much into this chapter. It’s ostensibly about the State design pattern, but I can’t talk about that and games without going into the more fundamental concept of finite state machines (or “FSMs”). But then once I went there, I figured I might as well introduce hierarchical state machines and pushdown automata. 交待时间: 我有点走远了，我往本章里面添加了太多东西。表面上这一章是介绍状态模式的，但是我不能抛开游戏里面的FSM（有限状态机）而单独只谈“状态模式”。不过，当我讲到FSM的时候，我发觉我还有必要再介绍一下层级状态机(hierarchical state machine)和下推自动机(pushdown automata).

That’s a lot to cover, so to keep things as short as possible, the code samples here leave out a few details that you’ll have to fill in on your own. I hope they’re still clear enough for you to get the big picture. 因为有太多东西需要讲，所以，我试图压缩本章的内容。本章中的代码片断没有涉及很细节的东西，所以，这些省略的部分需要靠读者自己脑补一下。我希望它们还是足够清楚到能让你掌握关键点（big picture）.

Don’t feel sad if you’ve never heard of a state machine. While well known to AI and compiler hackers, they aren’t that familiar to other programming circles. I think they should be more widely known, so I’m going to throw them at a different kind of problem here. 如果你从未听说过状态机，也不要感到沮丧。它们对于人工智能领域和编译器黑客来讲非常熟悉，不过对于其它编程领域的人可能不是那么被人熟知了。我觉得它们应该被更多的人所了解，因此，我将通过一个新的问题领域的应用来介绍它。

We’ve All Been There

我们曾经相遇过 We’re working on a little side-scrolling platformer. Our job is to implement the heroine that is the player’s avatar in the game world. That means making her respond to user input. Push the B button and she should jump. Simple enough: 假如我们现在正在开发一款横版游戏。我们的任务是实现女主角--即我们游戏世界里面的主人翁。我们需要根据玩家的输入来控件主角的行为。当按下B键的时候，她应该跳跃。我们可以这样实现:

void Heroine::handleInput(Input input)
{
  if (input == PRESS_B)
  {
    yVelocity_ = JUMP_VELOCITY;
    setGraphics(IMAGE_JUMP);
  }
}

Spot the bug? 找找看，bug在哪里？

There’s nothing to prevent “air jumping” — keep hammering B while she’s in the air, and she will float forever. The simple fix is to add an isJumping_ Boolean field to Heroine that tracks when she’s jumping, and then do: 我们没有防止主角“在空中跳跃”--当主角跳起来后持续按下B键。这样会导致她一直飘在空中,简单地修复方法可以是：添加一个 isJumping布尔值变量。当主角跳起来后，就把该变量设置为True.只有当该变量为False时，才让主角跳跃。

void Heroine::handleInput(Input input)
{
  if (input == PRESS_B)
  {
    if (!isJumping_)
    {
      isJumping_ = true;
      // Jump...
    }
  }
}

Next, we want the heroine to duck if the player presses down while she’s on the ground and stand back up when the button is released: 接下来，我们想实现主角的闪避动作。当主角站在地面上的时候，如果玩家按下方向“下键”，则躲避，如果松开此键，则起立。

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);
  }
}

Spot the bug this time? 找找看，有bug在哪里？

With this code, the player could: 通过上面的代码，玩家可以:

1. Press down to duck.
2. 按下键->闪避
3. Press B to jump from a ducking position.
4. 按B键从闪避的状态直接跳起来
5. Release down while still in the air.
6. 玩家还在空中的时候松开下键

The heroine will switch to her standing graphic in the middle of the jump. Time for another flag… 此时，当女主角在跳跃的状态的时候，显示的是站立的图像。是时候添加另外一个flag来解决该问题了...

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);
    }
  }
}

Next, it would be cool if the heroine did a dive attack if the player presses down in the middle of a jump: 接下来,如果我们的主角可以在跳起来的时候按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 hunting time again. Find it? 又是Bug解决时间到了。找到了吗？

We check that you can’t air jump while jumping, but not while diving. Yet another field… 我们需要添加一个判断，让主角在跳跃状态的时候不能再跳，但是在俯冲攻击的时候是可以跳跃的。又要添加一个成员变量。。。

Something is clearly wrong with our approach. Every time we touch this handful of code, we break something. We need to add a bunch more moves — we haven’t even added walking yet — but at this rate, it will collapse into a heap of bugs before we’re done with it. 很明显，我们的这种做法有问题。每次我们添加一些功能的时候，都会不经意地破坏已有代码的功能。而且，我们还没有添加“行走”的状态。如果我们还是采用类似的做法，那bug可能会更多。

Finite State Machines to the Rescue

In a fit of frustration, you sweep everything off your desk except a pen and paper and start drawing a flowchart. You draw a box for each thing the heroine can be doing: standing, jumping, ducking, and diving. When she can respond to a button press in one of those states, you draw an arrow from that box, label it with that button, and connect it to the state she changes to. 为了消除你心中的疑惑，你可以准备一张纸和一支笔，让我们一起来画一张流程图。对于，女主角能够进行的动作画一个“矩形”：站立、跳跃、躲避和俯冲。当你可以按下一个键让主角从一个状态切换到另一个状态的时候，我们画一个箭头，让它从一个矩形指向另一个矩形。同时在箭头上面添加文本，表示我们按下的按钮。

Congratulations, you’ve just created a finite state machine. These came out of a branch of computer science called automata theory whose family of data structures also includes the famous Turing machine. FSMs are the simplest member of that family. 恭喜，你刚刚已经成功创建了一个有限状态机。FSM是借鉴了计算机科学里的自动机理论（automata theory）中的一种数据结构(图灵机)的思想。FSM可以看作是最简单的图灵机。

The gist is: 这个FSM表达的是：

• You have a fixed set of states that the machine can be in. For our example, that’s standing, jumping, ducking, and diving.

• 你拥有一组状态，并且可以在这组状态之间进行切换。比如：站立、跳跃、躲避和俯冲。

• The machine can only be in one state at a time. Our heroine can’t be jumping and standing simultaneously. In fact, preventing that is one reason we’re going to use an FSM.

• 这个机器一次只能处于一种状态。

• A sequence of inputs or events is sent to the machine. In our example, that’s the raw button presses and releases. 有一组输入或者事件发送给状态机。在我们这个例子中，它们就是按钮的按下和释放。

Each state has a set of transitions, each associated with an input and pointing to a state. When an input comes in, if it matches a transition for the current state, the machine changes to the state that transition points to. 每一个状态有一组转换，每一个转换都关联着一个输入并指向另一个状态。当有一个输入进来的时候，如果有一个转换与此状态和输入事件对应，则状态机便会转换状态到输入事件所指的状态。

For example, pressing down while standing transitions to the ducking state. Pressing down while jumping transitions to diving. If no transition is defined for an input on the current state, the input is ignored. 在我们的例子中，在站立状态的时候如果按下down键，则状态转换到躲避状态。如果在跳跃状态的时候按下down键，则会转换到俯冲攻击状态。如果对于每一个输入事件没有对应的转换，则这个转入会被忽略。

In their pure form, that’s the whole banana: states, inputs, and transitions. You can draw it out like a little flowchart. Unfortunately, the compiler doesn’t recognize our scribbles, so how do we go about implementing one? The Gang of Four’s State pattern is one method — which we’ll get to — but let’s start simpler. 简而言之，整个状态机可以分为：状态，输入和转换。你可以通过画状态流程图来表示它们。但是，我们的编译器并不认识状态图，所以，我们接下来要介绍一个实现。四人帮(Gof)的状态模式是一种实现方法，但是让我们先从简单的方法开始。

Enums and Switches

枚举和分支

One problem our Heroine class has is some combinations of those Boolean fields aren’t valid: isJumping_ and isDucking_ should never both be true, for example. When you have a handful of flags where only one is true at a time, that’s a hint that what you really want is an enum. 我们的女主角类有一些布尔类型的成员变量：isJumping_和isDucking，但是这两个变量永远不可能同时为True. 当你有一系列的标记成员变量，而它们只能有且仅有一个为True时，这表明我们需要把它们定义成枚举(enum).

In this case, that enum is exactly the set of states for our FSM, so let’s define that: 在这个例子当中，我们的FSM的每一个状态可以用一个枚举来表示，所以，让我们定义以下枚举:

enum State
{
  STATE_STANDING,
  STATE_JUMPING,
  STATE_DUCKING,
  STATE_DIVING
};

Instead of a bunch of flags, Heroine will just have one state_ field. We also flip the order of our branching. In the previous code, we switched on input, then on state. This kept the code for handling one button press together, but it smeared around the code for one state. We want to keep that together, so we switch on state first. That gives us: 这里没有大量的flags，女主角类只有一个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;
  }
}

This seems trivial, but it’s a real improvement over the previous code. We still have some conditional branching, but we simplified the mutable state to a single field. All of the code for handling a single state is now nicely lumped together. This is the simplest way to implement a state machine and is fine for some uses. 这样看起来也挺普通的，但是它却是对前面的代码的一个提升。我们仍然有一些条件分支语句，但是我们简化了状态的处理。所有处理单个状态的代码都集中在一起了。这样做是最简单的方法来实现状态机，而且在某些情况下面，这样做也挺好的。

In particular, the heroine can no longer be in an invalid state. With the Boolean flags, some sets of values were possible but meaningless. With the enum, each value is valid. Your problem may outgrow this solution, though. Say we want to add a move where our heroine can duck for a while to charge up and unleash a special attack. While she’s ducking, we need to track the charge time. 不过，这样我们的女主角就不可能处于一个无效的状态。通过布尔值标识，我们可以设置一些没有意思的值。但是，使用枚举，每一个枚举值都是有意义的。你的问题可能也会超过此方案能解决的范围。比如，我们想在主角下蹲躲避的时候“蓄能”，然后等蓄满能量之后可以释放出一个特殊的技能。那么，当主角处理躲避状态的时候，我们需要添加一个变量来记录蓄能时间。

We add a chargeTime_ field to Heroine to store how long the attack has charged. Assume we already have an update() that gets called each frame. In there, we add: 我们可以添加一个chargeTime_成员来记录主角蓄能的时间长短。假设，我们已经有一个update方法了，并且这个方法会在每一帧被调用。在那里，我们可以使用如下代码片断能记录蓄能的时间:

void Heroine::update()
{
  if (state_ == STATE_DUCKING)
  {
    chargeTime_++;
    if (chargeTime_ > MAX_CHARGE)
    {
      superBomb();
    }
  }
}

We need to reset the timer when she starts ducking, so we modify handleInput(): 我们需要在主角躲避的时候重置这个蓄能时间，所以，我们还需要修改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...
  }
}

All in all, to add this charge attack, we had to modify two methods and add a chargeTime_ field onto Heroine even though it’s only meaningful while in the ducking state. What we’d prefer is to have all of that code and data nicely wrapped up in one place. The Gang of Four has us covered. 总之，为了添加蓄能攻击，我们不得不修改两个方法，并且添加一个 chargeTime_成员给主角，尽管这个成员变量只有在主角处于躲避状态的时候才有效。我们其实真正想要的是把所有这些与状态相关的数据和代码封装起来。接下来，我们介绍四人帮的状态模式来解决这个问题。

The State Pattern

状态模式

For people deeply into the object-oriented mindset, every conditional branch is an opportunity to use dynamic dispatch (in other words a virtual method call in C++). I think you can go too far down that rabbit hole. Sometimes an if is all you need. 对于熟知面向对象方法的人来说，每一个条件分支都可以用动态分发来解决（换句话说，都可以用c++里面的虚函数来解决）。但是，如果你这样做，可能会走远了。有时候，一个简单的if语句就足够了。

There’s a historical basis for this. Many of the original object-oriented apostles like Design Patterns‘ Gang of Four, and Refactoring‘s Martin Fowler came from Smalltalk. There, ifThen: is just a method you invoke on the condition, which is implemented differently by the true and false objects. 状态模式的由来也有一些历史原因。许多面向对象设计的信徒--四人帮和重构的作者Martin Fowler都是Smalltalk出生。在那里，如果有一个if语句，我们便可以用一个表示true和false的对象来操作。

But in our example, we’ve reached a tipping point where something object-oriented is a better fit. That gets us to the State pattern. In the words of the Gang of Four: 但是，在我们这个例子当中，我们也达到了设计模式的应用场景。在四人帮的状态模式中是这么描述的：

Allow an object to alter its behavior when its internal state changes. The object will appear to change its class. 当一个对象在其内部状态改变时改变它的行为，对象看起来好像是修改其类

That doesn’t tell us much. Heck, our switch does that. The concrete pattern they describe looks like this when applied to our heroine: 这句话并没有给我们太多信息。真见鬼，我们的switch却做到了。这个模式应用到我们的主角中，恰好和模式定义中描述的差不多。

A state interface

一个状态接口

First, we define an interface for the state. Every bit of behavior that is state-dependent — every place we had a switch before — becomes a virtual method in that interface. For us, that’s handleInput() and update(): 首先，我们为状态定义一个接口。每一个与状态相关的行为都定义成虚函数。对于我们而言，就是handleInput和update函数。

class HeroineState
{
public:
  virtual ~HeroineState() {}
  virtual void handleInput(Heroine& heroine, Input input) {}
  virtual void update(Heroine& heroine) {}
};

Classes for each state

为每一个状态定义一个类

For each state, we define a class that implements the interface. Its methods define the heroine’s behavior when in that state. In other words, take each case from the earlier switch statements and move them into their state’s class. For example: 对于每一个状态，我们定义了一个类并继承至此状态接口。它覆盖的方法定义主角对应此状态的行为。换句话说，把之前的switch语句里面的每一个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_;
};

Note that we also moved chargeTime_ out of Heroine and into the DuckingState class. This is great — that piece of data is only meaningful while in that state, and now our object model reflects that explicitly. 注意，我们这里把 chargeTime_也放到了DuckingState(躲避状态)中。这样非常好，因为这个变量只是对躲避状态有意义，现在把它定义在这里，正好显式地反应了我们的对象模型。

Delegate to the state

状态委托

Next, we give the Heroine a pointer to her current state, lose each big switch, and delegate to the state instead: 接下来，我们在主角类中定义一个指针变量，让它指向当前的状态。我们把之前那个很大的switch语句去掉了，然后让它去调用状态接口的虚函数，最终这些虚方法就会动态地调用具体子状态的相应函数了.

class Heroine
{
public:
  virtual void handleInput(Input input)
  {
    state_->handleInput(*this, input);
  }

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

  // Other methods...
private:
  HeroineState* state_;
};

In order to “change state”, we just need to assign state_ to point to a different HeroineState object. That’s the State pattern in its entirety. 为了修改状态，我们需要把state_指针指向另一个不同的状态对象。至此，我们的状态模式就讲完了。

Where Are the State Objects?

状态对象应该放在哪里呢？

I did gloss over one bit here. To change states, we need to assign state_ to point to the new one, but where does that object come from? With our enum implementation, that was a no-brainer — enum values are primitives like numbers. But now our states are classes, which means we need an actual instance to point to. There are two common answers to this: 我这里忽略了一些细节。为了修改一个状态，我们需要给state_指针赋值为一个新的状态，但是这个新的状态对象要从哪里来呢？我们的之前的枚举方法是一些数字定义。但是，现在我们的状态是类，我们需要获取这些类的实例。通常来说，有两种实现方法：

Static states

静态状态

If the state object doesn’t have any other fields, then the only data it stores is a pointer to the internal virtual method table so that its methods can be called. In that case, there’s no reason to ever have more than one instance of it. Every instance would be identical anyway. 如果一个状态对象没有任何数据成员，那么它的惟一数据成员便是虚表指针了。那样的话，我们就没有必要创建此状态的多个实例了，因为它们的每一个实例都是相等的。

If your state has no fields and only one virtual method in it, you can simplify this pattern even more. Replace each state class with a state function — just a plain vanilla top-level function. Then, the state_ field in your main class becomes a simple function pointer. 如果你的状态类没有任何数据成员，并且它只有一个函数方法在里面。那么我们还可以进一步简化此模式。我们可以通过一个状态函数来替换状态类。这样的话，我们的state_变量只需要变成一个状态函数指针就可以了。

In that case, you can make a single static instance. Even if you have a bunch of FSMs all going at the same time in that same state, they can all point to the same instance since it has nothing machine-specific about it. 在那种情部下，我们可以定义一个静态实例。即使你有一系列的FSM在同时运转，所有的状态机都同时指向这一个惟一的实例。

This is the Flyweight pattern. 这个就是享元模式。

Where you put that static instance is up to you. Find a place that makes sense. For no particular reason, let’s put ours inside the base state class: 你把静态方法放置在哪里，这个由你自己来决定 。如果没有任何特殊原因的话，我们可以把它放置到基类状态类中：

class HeroineState
{
public:
  static StandingState standing;
  static DuckingState ducking;
  static JumpingState jumping;
  static DivingState diving;

  // Other code...
};

Each of those static fields is the one instance of that state that the game uses. To make the heroine jump, the standing state would do something like: 每一个静态成员变量都是对应状态类的一个实例。如果我们想让主角跳跃，那么站立状态应该是这样子：

if (input == PRESS_B)
{
  heroine.state_ = &HeroineState::jumping;
  heroine.setGraphics(IMAGE_JUMP);
}

###Instantiated states ###实例化状态

Sometimes, though, this doesn’t fly. A static state won’t work for the ducking state. It has a chargeTime_ field, and that’s specific to the heroine that happens to be ducking. This may coincidentally work in our game if there’s only one heroine, but if we try to add two-player co-op and have two heroines on screen at the same time, we’ll have problems. 有时候上面的方法可能不行。一个静态状态对于躲避状态而言是行不通的。因为它有一个 chargeTime_成员变量，这个是专属于每一个主角类在躲避状态下的。如果我们的游戏里面只有一个主角的话，那么定义一个静态类也是没有啥问题的。但是，如果我们想加入多个玩家，那么此方法就行不通了。

In that case, we have to create a state object when we transition to it. This lets each FSM have its own instance of the state. Of course, if we’re allocating a new state, that means we need to free the current one. We have to be careful here, since the code that’s triggering the change is in a method in the current state. We don’t want to delete this out from under ourselves. 在那种情况下面，我们不得不在状态切换的时候动态地创建一个躲避状态实例。这样，我们的FSM并拥有了它自己的实例。当然，如果我们又动态分配了一个新的状态实例，我们需要负责清理老的状态实例。我们这里必须要相当小心，因为当前状态修改的函数是处在当前状态里面，我们需要小心地处理删除的顺序。

Instead, we’ll allow handleInput() in HeroineState to optionally return a new state. When it does, Heroine will delete the old one and swap in the new one, like so: 另外，我们也会在handleInput方法里面可选地返回一个新的状态。当这个状态返回的时候，主角将会删除老的状态并切换到这个新的状态，如下所示:

void Heroine::handleInput(Input input)
{
  HeroineState* state = state_->handleInput(*this, input);
  if (state != NULL)
  {
    delete state_;
    state_ = state;
  }
}

That way, we don’t delete the previous state until we’ve returned from its method. Now, the standing state can transition to ducking by creating a new instance: 那样的话，我们只有在从handleInput方法返回的时候才有可能去删除前面的对象。现在，站立状态可以通过创建一个躲避状态的实例来切换状态了。

HeroineState* StandingState::handleInput(Heroine& heroine,
                                         Input input)
{
  if (input == PRESS_DOWN)
  {
    // Other code...
    return new DuckingState();
  }

  // Stay in this state.
  return NULL;
}

When I can, I prefer to use static states since they don’t burn memory and CPU cycles allocating objects each state change. For states that are more, uh, stateful, though, this is the way to go. 当我在做选择的时候，我倾向于使用静态状态。因数它们不会占用太多的CPU和内存资源。

##Enter and Exit Actions

进入状态和退出状态的行为

The goal of the State pattern is to encapsulate all of the behavior and data for one state in a single class. We’re partway there, but we still have some loose ends. 状态模式的目标就是封装所有的数据和行为到一个状态类里面。万里长征，我们仅仅是迈出去了一步，我们还可以走地更远。

When the heroine changes state, we also switch her sprite. Right now, that code is owned by the state she’s switching from. When she goes from ducking to standing, the ducking state sets her image: 当主角更改状态的时候，我们也会切换它的精灵。现在，这段代码是包含在它要切换的状态的上一个状态里面。当她从躲避状态切换到站立状态的时候，躲避状态将会修改它的图像：

HeroineState* DuckingState::handleInput(Heroine& heroine,
                                        Input input)
{
  if (input == RELEASE_DOWN)
  {
    heroine.setGraphics(IMAGE_STAND);
    return new StandingState();
  }

  // Other code...
}

What we really want is each state to control its own graphics. We can handle that by giving the state an enter action: 我们希望的是，每一个状态来自己控件自己的图像。我们可以通过给每一个状态添加一个enter行为。

class StandingState : public HeroineState
{
public:
  virtual void enter(Heroine& heroine)
  {
    heroine.setGraphics(IMAGE_STAND);
  }

  // Other code...
};

Back in Heroine, we modify the code for handling state changes to call that on the new state: 回到女主角的例子，我们修改代码来处理状态切换的情况：

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);
  }
}

This lets us simplify the ducking code to: 这样也可以让我们简化躲避状态的代码：

HeroineState* DuckingState::handleInput(Heroine& heroine,
                                        Input input)
{
  if (input == RELEASE_DOWN)
  {
    return new StandingState();
  }

  // Other code...
}

All it does is switch to standing and the standing state takes care of the graphics. Now our states really are encapsulated. One particularly nice thing about entry actions is that they run when you enter the state regardless of which state you’re coming from. 它所做的就是切换到站立状态，然后站立状态会自己设置自己的图像。现在，我们的状态已经封装好了。entry动作的一个最大的好处就是它一个状态进来的时候，它不用关心上一个状态是什么，它只需要根据自己的状态来处理图像和行为就ok了。

Most real-world state graphs have multiple transitions into the same state. For example, our heroine will also end up standing after she lands a jump or dive. That means we would end up duplicating some code everywhere that transition occurs. Entry actions give us a place to consolidate that. 大部分的真实状态图里面，我们有多个状态对应同一个状态。比如，我们的女主角会在她俯冲或者跳跃之后站立在地面上。这意味着，我们可能会在每一个状态发生变化的时候重复写很多代码。但是，entry动作帮我们很好地解决了这个问题。

We can, of course, also extend this to support an exit action. This is just a method we call on the state we’re leaving right before we switch to the new state. 当然，我们也可以扩展这个功能来支持退出状态的行为。我们可以定义一个exit函数来定义一些在状态改变后的处理。

发现什么问题了吗？

I’ve spent all this time selling you on FSMs, and now I’m going to pull the rug out from under you. Everything I’ve said so far is true, and FSMs are a good fit for some problems. But their greatest virtue is also their greatest flaw. 我已经花了大量的时间来向你兜售FSM了。现在，我将要把你拉回来。到目前为止，我跟你讲的任何事情都是对的，FSM对于某些应用来讲是非常合适的。但是，往往最大的优点也是最大的缺点。

State machines help you untangle hairy code by enforcing a very constrained structure on it. All you’ve got is a fixed set of states, a single current state, and some hardcoded transitions. 状态机帮助你把千丝万缕的逻辑判断代码封装起来了。你需要的只是一组状态，一个当前状态和一些硬编码的状态切换。

A finite state machine isn’t even Turing complete. Automata theory describes computation using a series of abstract models, each more complex than the previous. A Turing machine is one of the most expressive models. 一个有限状态机甚至都不是一个图灵机。自动化理论使用一系列抽象的模型来描述计算，并且每一个模型都比先前的模型更复杂。而图灵机只是这里面最具有表达力的模型。

“Turing complete” means a system (usually a programming language) is powerful enough to implement a Turing machine in it, which means all Turing complete languages are, in some ways, equally expressive. FSMs are not flexible enough to be in that club. “图灵完备”意味着一个系统（通常指的是一门编程语言）是足够强大的，强大到它可以实现一个图灵机。这也意味着，所有图灵完毕的编程语言，在某些程度上来也是一种FSM。

If you try using a state machine for something more complex like game AI, you will slam face-first into the limitations of that model. Thankfully, our forebears have found ways to dodge some of those barriers. I’ll close this chapter out by walking you through a couple of them. 如果你想要用一个状态机来表示一些复杂的游戏AI，你可能会面临这个模型的一些限制。幸运的是，我们的先辈们已经发现一些解决方案可以解决些问题。我将会在本章的最后简单地提到它们。

##并发状态机 We’ve decided to give our heroine the ability to carry a gun. When she’s packing heat, she can still do everything she could before: run, jump, duck, etc. But she also needs to be able to fire her weapon while doing it. 我们已经决定给我们的主角添加持枪功能。当她手持枪的时候，她仍然可以：跑、跳和躲避。但是，她同时也能够在这些状态过程中开火。

If we want to stick to the confines of an FSM, we have to double the number of states we have. For each existing state, we’ll need another one for doing the same thing while she’s armed: standing, standing with gun, jumping, jumping with gun, you get the idea. 如果你执着于传统的FSM，我们可能需要把之前的状态加倍。对于每一个已经存在的状态，我们需要定义另一个状态，它做的事情也差不多，不过就是多了持枪的操作。比如站立状态和状态开火状态，跳跃状态和跳跃开火状态等。

Add a couple of more weapons and the number of states explodes combinatorially. Not only is it a huge number of states, it’s a huge amount of redundancy: the unarmed and armed states are almost identical except for the little bit of code to handle firing. 如果我们添加更多的武器种类，那么这个状态种数会爆炸的。而且不仅仅是增加了大量的状态类实例而已，它还会重复编写相当多的重复代码。

The problem is that we’ve jammed two pieces of state — what she’s doing and what she’s carrying — into a single machine. To model all possible combinations, we would need a state for each pair. The fix is obvious: have two separate state machines. 这里的问题是，我们把两种状态杂合在一起了。我们把两种不同的状态硬塞到一个状态机里面去了。为了建模所有可能的组合，我们可能需要为每一种状态准备一组状态。解决方法比较直观 ，就是我们提供两个状态机。

If we want to cram n states for what she’s doing and m states for what she’s carrying into a single machine, we need n × m states. With two machines, it’s just n + m. 如果我们可以为主角定义n种状态，那么就可以为它所持装备定义m种状态，并把它们分别放入不同的状态机。因此，我们只需要n * m个状态就够了。如果有两个状态机，那么状态组合是n+m.

We keep our original state machine for what she’s doing and leave it alone. Then we define a separate state machine for what she’s carrying. Heroine will have two “state” references, one for each, like: 为了保持我们原来的状态机，我们这里先不管。接下来，我们定义了一个单独的状态机，用来处理主角携带的武器。现在，我们的主角会有两个状态索引，其中一个看起来如下所示：

class Heroine
{
  // Other code...

private:
  HeroineState* state_;
  HeroineState* equipment_;
};

When the heroine delegates inputs to the states, she hands it to both of them: 当主角派发输入事件给状态类的，需要给两种状态都派发一下。

void Heroine::handleInput(Input input)
{
  state_->handleInput(*this, input);
  equipment_->handleInput(*this, input);
}

Each state machine can then respond to inputs, spawn behavior, and change its state independently of the other machine. When the two sets of states are mostly unrelated, this works well. 这样每一个状态机都可以响应输入事件并以此切换状态而不用考虑其它状态机的内部。当两个状态没什么关系的时候，这种方法工作地很好。

In practice, you’ll find a few cases where the states do interact. For example, maybe she can’t fire while jumping, or maybe she can’t do a dive attack if she’s armed. To handle that, in the code for one state, you’ll probably just do some crude if tests on the other machine’s state to coordinate them. It’s not the most elegant solution, but it gets the job done. 在实际中，你可能会发现你需要对某些状态处理进行干预。比如，如果主角不能够在跳跃的过程中开火，或者她在装备武器的时候不能俯冲。为了处理这种情况，在代码里面，对于每一个状态，你可能需要做一些简单的if判断并做出特殊处理。虽然这可能不是最好的解决方案，但是至少它可以完成任务。

层级状态机

After fleshing out our heroine’s behavior some more, she’ll likely have a bunch of similar states. For example, she may have standing, walking, running, and sliding states. In any of those, pressing B jumps and pressing down ducks. 在我们把主角的行为更加具象化以后，她可能会包含大量相似的状态。比如，她可能有站立、走路、跑步和滑动状态。在这些状态中的任何一个状态按下B键，我们的主角要跳跃，按下down键，我们的主角要躲避。

With a simple state machine implementation, we have to duplicate that code in each of those states. It would be better if we could implement that once and reuse it across all of the states. 如果只是使用一个简单的状态机实现，我们可能会在这些状态中重复不少代码。更好的解决方案是，我们只需要实现一次那么它便可以在所有的状态下都有效。

If this was just object-oriented code instead of a state machine, one way to share code across those states would be using inheritance. We could define a class for an “on ground” state that handles jumping and ducking. Standing, walking, running, and sliding would then inherit from that and add their own additional behavior. 如果我们抛开状态机来谈面向对象，有一种共享代码的方式便是继承。我们可以定义一个类来代码在地上的状态，它用来处理跳跃状态和躲避状态。站立，走跳，跑步和滑行状态从这个在地面上的状态继承而来，并且在其类里面实现一些特殊行为。

This has both good and bad implications. Inheritance is a powerful means of code reuse, but it’s also a very strong coupling between two chunks of code. It’s a big hammer, so swing it carefully. It turns out, this is a common structure called a hierarchical state machine. A state can have a superstate (making itself a substate). When an event comes in, if the substate doesn’t handle it, it rolls up the chain of superstates. In other words, it works just like overriding inherited methods. 这可能既是一个好的设计，也可能是一个坏的设计。继承是一种强大的代码重用方式，但是，它也会使得子类与基类之间的代码变得紧耦合。它是一个很大的锤子，需小心使用才行。这里，我们通常把这种状态机叫做层级状态机。一个状态有一个父状态。当有一个事件进来的时候，如果子状态不处理它，那么并沿着继承链传给它的父状态来处理。换句话说，它有点像覆盖继承的方法。

in fact, if we’re using the State pattern to implement our FSM, we can use class inheritance to implement the hierarchy. Define a base class for the superstate: 实际上，如果我们正在使用状态模式来实现FSM，我们可以使用类层次来实现层级状态机。我们首先定义一个基类来表示父状态:

class OnGroundState : public HeroineState
{
public:
  virtual void handleInput(Heroine& heroine, Input input)
  {
    if (input == PRESS_B)
    {
      // Jump...
    }
    else if (input == PRESS_DOWN)
    {
      // Duck...
    }
  }
};

And then each substate inherits it: 然后，每一个子状态都继承至它:

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);
    }
  }
};        

This isn’t the only way to implement the hierarchy, of course. If you aren’t using the Gang of Four’s State pattern, this won’t work. Instead, you can model the current state’s chain of superstates explicitly using a stack of states instead of a single state in the main class. 当然，这不是实现层级状态机的惟一方式。如果你没有使用GoF的状态模式，这种做法可能并不奏效。相反，你也可以使用栈结构来显示地模拟当前状态的父级状态的状态链。

The current state is the one on the top of the stack, under that is its immediate superstate, and then that state’s superstate and so on. When you dish out some state-specific behavior, you start at the top of the stack and walk down until one of the states handles it. (If none do, you ignore it.) 我们当前的状态总是处于栈顶，栈顶下面的第一个元素则是它的父状态，再下一个状态则是它的爷爷状态，等等。如果你要进行一些与状态相关的行为操作，那么首先从栈顶状态开始。如果它不处理，则往上继承寻找到一个能处理此事件的状态为止。（如果找遍整个栈了，还是没人处理，则此事件忽略掉）.

##下推自动机 There’s another common extension to finite state machines that also uses a stack of states. Confusingly, the stack represents something entirely different, and is used to solve a different problem. 这里还有一种有限状态机的变种，它们使用状态栈。可能听起来有些奇怪，栈完全是另外一种截然不同的东西。

The problem is that finite state machines have no concept of history. You know what state you are in, but have no memory of what state you were in. There’s no easy way to go back to a previous state. 这里要解决的问题是，因为有限状态机是没有历史记录这个概念的。我们知道一个状态进来了，但是，我们并不知道这个状态的上一个状态是什么。而且，我们也没有简便地方法可以获取当前状态的上一个状态。

Here’s an example: Earlier, we let our fearless heroine arm herself to the teeth. When she fires her gun, we need a new state that plays the firing animation and spawns the bullet and any visual effects. So we slap together a FiringState and make all of the states that she can fire from transition into that when the fire button is pressed. 这里有一个例子：之前，我们让我们无畏的主角全副武装。when她开枪的时候，我们需要一种新的状态来播放开枪的动画，但是发射子弹并显示一些特效。因此，我们需要定义一个FiringState，并且所有的状态都可以切换到这个状态，只要有玩家按下开火按键就行了。

Since this behavior is duplicated across several states, it may also be a good place to use a hierarchical state machine to reuse that code. The tricky part is what state she transitions to after firing. She can pop off a round while standing, running, jumping, and ducking. When the firing sequence is complete, she should transition back to what she was doing before. 因为这个行为在许多状态里面都重复了，所以，我们需要使用层级状态机来解决这个问题。 这里的问题来了，当她开完枪后，她要回到什么状态呢？主角可以处于站立、躲避、俯冲和跳跃状态。但开火的动画播放完以后，她应该要回到之前的状态。

If we’re sticking with a vanilla FSM, we’ve already forgotten what state she was in. To keep track of it, we’d have to define a slew of nearly identical states — firing while standing, firing while running, firing while jumping, and so on — just so that each one can have a hardcoded transition that goes back to the right state when it’s done. 如果我们仍然坚持使用以前的FSM，那么我们将无法获得上一个状态的信息。为了保留上一个状态的信息，我们不得不定义一些几乎对等的状态，比如站立开火状态，跑步开火状态等。这样的话，当我们的开火状态完成以后，就可以切换回之前的状态了。

What we’d really like is a way to store the state she was in before firing and then recall it later. Again, automata theory is here to help. The relevant data structure is called a pushdown automaton. 我们需要的仅仅是提供一种方式，让我们可以保存开火前的状态，这样在开火状态完成之后可以回去。好了，自动机理论可以帮助我们。相关的数据结构叫做下推自动机（pushdown automata）.

Where a finite state machine has a single pointer to a state, a pushdown automaton has a stack of them. In an FSM, transitioning to a new state replaces the previous one. A pushdown automaton lets you do that, but it also gives you two additional operations: 本来，一个有限状态机有一个指针指向一个状态。而下推自动机则有一个状态栈。在一个FSM里面，当有一个状态切进来，则替换掉之前的状态。下推自动机可以让你这样做，同时它还提供其它选择:

You can push a new state onto the stack. The “current” state is always the one on top of the stack, so this transitions to the new state. But it leaves the previous state directly under it on the stack instead of discarding it. 你可以把这个新的状态放入栈里面。那么当前的状态就永远存在栈顶，当你需要回退到上一个状态的时候，只需要栈顶出栈就可以得到上一个状态了。

此时，上一个状态就变成了新的栈顶状态了。

This is just what we need for firing. We create a single firing state. When the fire button is pressed while in any other state, we push the firing state onto the stack. When the firing animation is done, we pop that state off, and the pushdown automaton automatically transitions us right back to the state we were in before. 这个就是我们的开火状态所需要的。当开火按钮在任何一种状态下被按下的时候，我们把开火状态push到栈顶。当开火动画结束的时候，我们把这个开火状态pop出去。此时，状态机会自动切换到我们开火前的上一个状态。

现在知道它们有多有用了吧？

Even with those common extensions to state machines, they are still pretty limited. The trend these days in game AI is more toward exciting things like behavior trees and planning systems. If complex AI is what you’re interested in, all this chapter has done is whet your appetite. You’ll want to read other books to satisfy it. 即使有了这些通用的状态机扩展，它们的使用范围仍然是有限的。在游戏的AI领域的最近的趋势是越来越倾向于行为树和规划系统。如果你对复杂的AI感兴趣的话，那么本章所有这些内容只是在吊你的胃口。你可能还想通过阅读其它的书籍来了解它们。

This doesn’t mean finite state machines, pushdown automata, and other simple systems aren’t useful. They’re a good modeling tool for certain kinds of problems. Finite state machines are useful when: 但是这并不意味着有限状态机，下推自动机和其它简单的状态机没有用。它们对于解决某些特定的问题是一个很好的建模工具。当你的问题满足以下几点要求的时候，有限状态机将会非常有用:

• You have an entity whose behavior changes based on some internal state.

• 你有一个游戏裸体，它的行为基于它的内部状态而改变

• That state can be rigidly divided into one of a relatively small number of distinct options.

• 这些状态被严格划为为小个有限的小集合。

• The entity responds to a series of inputs or events over time.

• 游戏实体随着时间的变化会响应用户输入和一些游戏事件。

In games, they are most known for being used in AI, but they are also common in implementations of user input handling, navigating menu screens, parsing text, network protocols, and other asynchronous behavior. 在游戏里面，它们在AI里面被广泛使用，但是它们也经常被应用于"用户输入处理"，“浏览菜单屏幕”，“解析文件”，“网络协议”和其它异步的行为。