有限状态机

Posted on In

有限状态机和行为树在游戏 AI 领域比较常见，当然很多涉及到流程控制的逻辑都可以使用它们来降低复杂性并创建更具可读性的程序。

有限状态机

假如我们正在开发一款 RPG 游戏，游戏中的敌人在遇到玩家后会发起攻击，而玩家不在攻击范围内就进行巡逻。

1
2
3
4
5
if (视野范围内有目标) {
  攻击
} else {
  巡逻
}

这样写不会有啥问题，并且也很容易实现。但是随着开发的深入，游戏逻辑越来越复杂，经过几次修改，游戏逻辑可能会变成这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (视野范围有目标) {
    if (血量 > 10) {
        if (超过攻击距离) {
            追逐
        } else {
            攻击
        }
    } else {
        if (没有遇到同伴) {
            逃跑
        } else {
            一起攻击
        }
    }
} else {
    巡逻
}

也许你会说，这点逻辑我还能应对，但是我们不能保证后续是否还有更复杂的条件和逻辑需要添加，到时候我们还需要回到这里，继续修改和添加代码逻辑。随着时间的推移，这里的代码可以预见的会越来越复杂，难以维护。现在，是时候思考应该怎样拆分它了。

在上面的这个例子中，像攻击、追逐、逃跑等，可以抽象为状态，而视野范围内有目标、血量小于 10 等这些都是进入某个状态的触发条件，所以在这些逻辑当中，真正不断发生变化的是状态、触发条件以及它们之间的对应关系。通过分析，我们可以把上面例子中的逻辑（有些逻辑没有使用）总结为一个状态转换表：

当前状态 触发条件 目标状态
巡逻 血量为 0 死亡
巡逻 发现目标 追逐
追逐 血量为 0 死亡
追逐 目标进入攻击范围 攻击
追逐 丢失目标 巡逻
攻击 血量为 0 死亡
攻击 目标离开攻击范围 追逐
攻击 目标血量为 0 巡逻
死亡

根据当前逻辑，在罗列了所有可能的状态以及状态切换的触发条件之后，我们可以为每个状态和每个触发条件都创建一个对应的类，比如攻击状态就是 AttackState，血量为 0 的条件类就是 HPIsZero，它们都有一个对应的父类（或者接口），比如 AbstractState 和 AbstractCondition。状态接口主要提供进入状态、在状态中以及退出状态时需要执行的函数，而条件接口主要提供的是一个检测触发条件是否满足的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public abstract class AbstractState
{
    /// <summary>
    /// 在状态中
    /// </summary>
    public virtual void Tick()
    {
    }

    /// <summary>
    /// 进入状态
    /// </summary>
    public virtual void Enter()
    {
    }

    /// <summary>
    /// 退出状态
    /// </summary>
    public virtual void Exit()
    {
    }
}
1
2
3
4
5
6
7
public abstract class AbstractCondition
{
    /// <summary>
    /// 检测条件是否满足
    /// </summary>
    public abstract bool Predicate();
}

有了这些状态类和条件类，接下来的工作就是将它们组合起来，覆盖上述状态转换表，形成完整的逻辑。为此，我们还需要创建一个容器，这个容器负责存储和管理所有的状态、条件以及它们之间的映射关系，同时还需要提供进行状态切换的函数。这个容器就是我们所说的有限状态机（Finite State Machine）。当然，状态机的实现方式多种多样，有的会把映射关系维护到状态中。有的可能不会将触发条件独立出来，而是选择放到状态内部。

这大概就是实现一个有限状态机的完整过程，到这里，我们应该都对有限状态机是什么有了一个自己的答案。对于我来说，有限状态机就是一个能够在有限的状态内实现状态转换的数学计算模型。通过有限状态机，我们可以实现类似流程控制的逻辑，但是与一般的流程控制不同，使用有限状态机可以将流程控制语句与对应的处理逻辑分离，从而使程序的可读性和可维护性更好。

当然，有限状态机也是有缺陷的。首先它的可维护性并不好，添加或删除一个状态时，所有之前定义的状态、条件和映射关系可能都需要重新检查和修改。然后可扩展性也不高，当状态特别多的时候，可以想象应该需要一张很大的状态转换表，尤其是在 Unity 中，Animator 控制器的大量状态盒子和箭头就是一个噩梦。最后，对于当前状态来说，我并不能知道我的转换历史，也就是说，我很难知道我为什么会在这个状态里，这也是为什么现在主流的 AI 选择使用行为树的原因之一。

并发状态机

关于有限状态机，它有一个隐含的特点就是：同一时刻只能处于一个状态中。然而很多时候，使用有限状态机的事物需要在同一时刻处于多种不同的状态中。比如一个角色，我们定义了静止、奔跑、跳跃等状态，同时我们赋予了角色使用枪支的能力，我们需要它在射击的时候能够自由选择静止、奔跑或者跳跃。如果我们坚持只使用一个状态机，那么我们需要再添加一些状态：静止射击、奔跑射击、跳跃射击等，对于每个现有的状态，我们都需要再添加一个状态来在它射击的时候做同样的事。这样状态数量会迅速膨胀，同时会有大量的冗余代码。

此时，一个很明显的解决方案就是：保留原有的状态机，然后为它携带的枪支提供一个单独的状态机。这样角色将持有两个状态机的引用，在同一时刻，玩家的操作都会传入两个状态机中，两个状态机会根据玩家的行为做出相应的响应动作，比如一边奔跑一边射击。

当两组状态大部分都是互不相关的时候，这种实现方式很合适。但是在实际开发中，两组状态确实可能会出现相互影响的情况，比如角色不能在跳跃的时候进行射击。一个不太优雅的解决方法就是在状态类（或者条件类）中对另一个状态机的当前状态进行判断。

分层状态机

很多时候，把一个事物具象化以后，可能会有很多“相似”的状态。比如一个玩家角色，它可能有站立、步行、奔跑和滑行等状态，当处在这些状态中的任何一个状态时，玩家都可以进行跳跃和下蹲的操作。如果使用常规的有限状态机，我们就需要给每个状态都添加这部分代码，一种常规的改进方式就是使用继承。我们可以将具有“相似”之处的状态分为一类，总结为一种新的状态，比如这里的站立、步行、奔跑和滑行等可以定义为“在地面上”这个新状态，然后之前的这些状态都继承它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class OnTheGroundState : IState {
  public virtual void handleInput(Player player, Input input) {
    if (input == PRESS_JUMP) {
      // change state to jump
    } else if (input == PRESS_DOWN) {
      // change state to duck
    }
  }
}

class RunState : OnTheGroundState {
  public override void handleInput(Player player, Input input) {
    if (input == PRESS_RUN) {
      // change state to run
    } else {
      OnTheGroundState::handleInput(player, input);
    }
  }
}

上面的例子就用到了分层状态机的思想。我们再来列举一个例子，这个例子是从别处看到的，是一个决策小狗行为的例子。我们对小狗定义了很多状态，比如吃饭、睡觉、奔跑、咆哮、撒娇和摇尾巴等，如果使用常规的状态机，我们就需要考量每个状态之间的关系，定义所有可能的转换。但是如果使用分层状态机，我们可以对小狗的行为进一步“分类”，比如我们定义疲劳、开心和愤怒三个状态，然后在这些状态中再定义一些小状态。比如在开心的状态中，就有撒娇、摇尾巴等小状态。这样在外部我们只需要关心三个大状态的转换，在每个大状态的内部则只需要关心自己的小状态的转换即可。这就大大降低了状态机的复杂度，状态之间的转换数量也就相应地减少了。

从上面的两个例子可以看出，在分层状态机中会有一些超级状态，超级状态间也可以进行转换。利用超级状态，我们可以实现仅仅将状态转换应用到超级状态一次，而不用分别为每个状态应用一次状态转换。需要注意的是，分层状态机中每一层都是一个状态机，这意味着超级状态的内部也是一个独立的状态机。只要满足某一层（某个超级状态）的转移触发条件，就可以不用管其内部的子状态，直接进行状态切换，但是在退出该层之前需要依次执行每个子状态的退出逻辑。

使用分层状态机，我们可以重用部分代码（本质上是重用状态转换），从而减少状态转换的数量，但是它仍然不是一种比较理想的解决方案，因为重用转换并不容易，为此我们需要进行大量的思考。

下推状态机

简单来说就是通过栈结构来存储一系列的状态对象。比如在一个射击游戏中，玩家角色处于站立的状态，那么栈顶的状态就是站立，执行的也是站立的逻辑。突然遇到敌人，玩家选择开火攻击，于是入栈一个射击的状态，此时会执行射击的逻辑。当敌人死亡，开火结束，为了恢复到开火前的上一个状态，选择弹出栈顶状态，此时就恢复到了之前的站立状态。总的来说，下推状态机适用于那些需要记忆状态的状态机。

参考

State

层次化状态机的讨论

状态机编程思想？