浅谈状态机（FSM）

状态机在游戏，AI以及编译器程序方向应用很多，本文将介绍下移动端可以参考借鉴的思路。

为什么要使用状态机？

下面借用一段 游戏设计模式 书中的例子

假设下面我们实现一个游戏，玩家使用B键让女英雄跳跃

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

看到漏洞了吗？
没有东西阻止“空中跳跃”——当角色在空中时狂按B，她就会浮空。 简单的修复方法是给Heroine增加isJumping_布尔字段，追踪它跳跃的状态。然后这样做：

void Heroine::handleInput(Input input) {
  if (input == PRESS_B) {
    if (!isJumping_) {
      isJumping_ = true;
      // 跳跃……
    }
  }
}

接下来，当玩家按下下方向键时，如果角色在地上，我们想要她卧倒，而松开按键时站起来：

void Heroine::handleInput(Input input) {
  if (input == PRESS_B) {
    // 如果没在跳跃，就跳起来……
  } else if (input == PRESS_DOWN) {
    if (!isJumping_) {
      setGraphics(IMAGE_DUCK);
    }
  } else if (input == RELEASE_DOWN) {
    setGraphics(IMAGE_STAND);
  }
}

接下来书中的例子就不再继续罗列了，简单来说每次添加功能时，就需要破坏一些代码，上面的代码包含的易错代码的两大特点：复杂分支和可变状态。

为了解决上面越来越复杂的逻辑分支，画下了以下的状态图：

可以看到以下特点：
你拥有状态机所有可能状态的集合。 在我们的例子中，是站立，跳跃，俯卧和速降。
状态机同时只能在一个状态。 英雄不可能同时处于跳跃和站立状态。事实上，防止这点是使用FSM的理由之一。
一连串的输入或事件被发送给状态机。 在我们的例子中，就是按键按下和松开。
每个状态都有一系列的转移，每个转移与输入和另一状态相关。 当输入进来，如果它与当前状态的某个转移相匹配，机器转换为所指的状态。

上面介绍了我们为什么要使用状态机，上面的例子是一种有限状态机，有限状态机（Finite State Machine）是表示有限个状态（State）以及在这些状态之间的转移（Transition）和动作（Action）等行为的数据模型。
按照上面的例子来说：状态指的是方块中的跳跃，站立等，动作指的是 按B或者下键，转移指的是状态变化时代码要执行的操作。
当然你也可以加入 Guard（条件）：状态机对外部消息进行响应时，除了需要判断当前的状态，还需要判断跟这个状态相关的一些条件是否成立。这种判断称为 Guard（条件）。Guard 通过允许或者禁止某些操作来影响状态机的行为。

分层状态机：

上面只是一个简单的状态机，假设我们不是操作一个人了，而是操作一群人（球员）了，使用单一的状态机也会变得复杂不易理解，膨胀出许多状态判断。为了解决这个问题，有人提出了分层状态机这一设计。

还是假设控制一群篮球球员，使用分层状态机可以设计以下三种状态机：

基础状态机：直接控制角色动画和绘制、提供基础的动作实现，为上层提供支持。
行为状态机：实现分解动作，躲避跑、直线移动、原地站立、要球、传球、射球、追球、打人、跳。
角色状态机：实现更复杂的逻辑，比如防射球、篮板等都是由N次直线运动+跳跃或者打人完成。

每一层状态机都是通过为下一层状态机设定目标来实现控制(目标设定后，下层状态机将自动工作，上层不用关心动画到底播到哪了，现在到底是跑是跳)，从而为上层提供更加高级拟人化的行为，所有状态机固定频率更新(如每秒10次)，用于判断状态变迁和检查底层目标完成情况。
最高层的角色状态机的工作由团队AI来掌控，即角色分配的工作。
而行为状态机以上的状态抉择，比如回防，到底是跑到哪一点，射球，到底在哪里起跳，路径是怎样的，则由决策支持系统提供支持。
何为决策支持系统？
状态机为角色的大脑，而决策支持系统为角色的眼睛和耳朵，常见的工具有势力图(InfluenceMap)和白板(相当于不同角色间喊话)，概率统计等。
为了实现人机对战，我们还需要更高层的状态机：团队状态机
团队状态机由ai进行战术指导，给不同角色状态机设定目标。

那么引入了分层之后的HFSM到底带来了什么好处呢？

最大的好处便是在一定程度上规范了状态机的状态转换，从而有效地减少了状态之间的转换。
举一个简单的例子：例如RTS游戏中的士兵。如果逻辑没有层次上的划分，那么我们对士兵所定义的若干状态，例如前进、寻敌、攻击、防御、逃跑等等，就需要在这些状态之间定义转移，因为它们是平级的，因此我们需要考虑每一组状态的关系，并维护一大堆没有侧重点的转移。
如果在逻辑上是分层的，我们就可以将士兵的这些状态进行一个分类，把几个低级的状态归并到一个高级的状态中，并且状态的转移只发生在同级的状态中。
例如高级状态包括战斗、撤退，而战斗状态中又包括了寻敌、攻击等几个小状态；撤退状态中又包括了防御、逃跑这几个小状态。

然而，关于状态机的故事并没有结束。。。
在07年的AIGameDev上有人提出了FSM时代结束的十大原因（http://aigamedev.com/open/article/fsm-age-is-over/ 并有人做了翻译 https://blog.csdn.net/gzlaiyonghao/article/details/2070675）

状态机在实现状态（State）数量少的时候没有问题，然而随着状态的增加会有爆发性的代码需要维护：

行为树

行为树是一种无环图，对于用行为树定模型构造的系统来说，每次执行时 ，系统都会从根节点遍历整个树，父节点执行子节点，子节点执行完后将结果返回父节点，然后父节点根据子节点的结果来决定接下来怎么做。下面是行为树的示例图：

可以看到行为树分为两类基本节点：控制节点和行为节点，行为树就是通过行为节点，控制节点，以及每个节点上的前提，把整个AI的决策逻辑描述了出来，

控制节点

在行为树中我们所看到的所有父节点都被称为控制节点。控制节点是行为树的核心部分，它与具体的业务是无关的，它只负责整个行为树的逻辑控制。其包含以下几种类型：

选择节点(Selector)：属于组合节点，顺序执行子节点，只要碰到一个子节点返回true，则停止继续执行，并返回true，否则返回false，类似于程序中的逻辑或。
顺序节点(Sequence)：属于组合节点，顺序执行子节点，只要碰到一个子节点返回false，则停止继续执行，并返回false，否则返回true，类似于程序中的逻辑与。
平行节点(Parallel)：也有叫并行节点的，提供了平行的概念，无论子节点返回值是什么都会遍历所有子节点。所以不需要像 Selector/Sequence 那样预判哪个 Child Node 应摆前，哪个应摆后。Parallel Node增加方便性的同时，也增加实现和维护复杂度。
组合节点(Coposite)：可以组合多个子节点。
装饰节点(Decoraor)：可以作为某种节点的一种额外的附加条件，如允许次数限制，时间限制，错误处理等。
循环节点(Loop)：循环执行相应的动作，并返回结果。
随机选择节点(Random): 之前的选择节点是有优先级顺序的，而随机选择节点的执行顺序是随机的。当一个节点返回 Success 或者 Running 时，则停止执行后续节点，向父节点返回 Success或Running，若全部失败则返回Fail。

这里再说下并行节点：
不同于选择和顺序节点依次执行每个节点，并行节点是“同时”执行所有的节点，然后根据所有节点的返回值判断最终返回的结果。
这里的“同时”会迷惑住不少人，实际上，行为树是运行在单一线程上的，并不会在并行节点上开多个线程来进行真正的同时执行，那么“同时”的含义是什么？
我们知道选择或顺序节点会依次执行所有的子节点，当子节点返回“成功”或“失败”后就会停止后续节点的执行，而并行节点也会依次执行所有的子节点，无论子节点返回“成功”或“失败”都会继续运行后续节点，保证所有子节点都得到运行后在根据每个子节点的返回值来确定最终的返回结果。
并行节点一般可以设定退出该节点的条件，比如：

当全部节点都返回成功时退出；
当某一个节点返回成功时退出；
当全部节点都返回成功或失败时退出；
当某一个节点返回成功或失败时退出；
当全部节点都返回失败时退出；
当某一个节点返回失败时退出；

行为节点

行为树的行为定义都在行为节点中，也就是我们说的叶子节点。行为节点是与我们的具体需求相关的，不同的需求定义会有不同的行为节点。

条件节点(Condition)：属于叶子节点，判断条件是否成立。
动作节点(Action)：属于叶子节点，执行动作，一般返回true。

节点的返回
每个节点都会有一个返回值，可能出现的返回值有3个，如下：

运行中：表示当前节点还在运行中，下一次调用行为树时任然运行当前节点；
失败：表示当前节点运行失败；
成功：表示当前节点运行成功；

为什么要返回节点的运行状态呢？

序列控制节点中，需要用运行状态来控制序列的执行
外部世界需要了解行为的运行状态，来决定是否要更新决策（如果行为树在决策层）/请求（如果行为树在行为层）

推荐的行为树构建步骤：
1.思考需求，分解动作，包括需要的参数
2.和程序沟通核对，调整具体需求
3.程序完成后，核实节点是否有效并且满足需求
这是游戏开发界产品需要做的事情，对于APP开发过程中大多还是需要开发人员主动和产品沟通核对（产品了解技术实现并不容易，并且APP开发现状是并没有行为树的界面编辑器，产品就更无从下手了）

状态机和行为树对于大多数的游戏开发已经很熟悉了，但是对于APP开发人员并没有被大家广泛认知。其中缘由个人认为可能是业务状态的变化并不是很复杂，并且没有很成熟的框架，上手难度较高。对于iOS开发，Objective C和Swift语言有部分状态机的实现框架，但从GitHub Star数可以看出并没有广泛的被采用。
对于APP开发人员来说如何使用状态机/行为树就是一个问题，但更重要的一个问题是我该在什么场景（业务）下使用状态机，行为树。下面是部分采取状态机的业务，希望对你有所启发：
1.页面跳转。例如下图的登录流程：

2.手势冲突的解决
3.网络数据的加载流程
4.具体复杂业务的控制：比如视频播放状态的切换等等。

其实对于状态机的应用来说，游戏方向在很早就开始应用状态机来模拟人工智能角色。在Halo2的分享中介绍了他们是如何用行为树实现AI（http://bbs.a9vg.com/thread-698454-1-1.html），其中也介绍了如何优化行为树的内存占用以及行为裁剪。
对于客户端可以应用到比如说登录/未登录状态的行为树，个人信息页的主态/客态的不同。

APP的实现可以简单的用以下函数表达：
App = UI(state)
再细化点
App = UI(viewState(domainState))
App = UI(视图状态(业务状态))
也就是对于业务状态的表达，那么状态机/行为树对于APP来说有很多地方可以应用。

什么时候应该选择行为树，什么时候应该选择状态机？
三重境界：
用 If/Else 硬编码；
使用状态机，基于事件编程；
使用行为树。

使用行为树当然最好，但是实现成本最高，在不复杂的业务中使用状态机也可以。

其实分层状态机和行为树很类似，都可以解决复杂状态之间的转换，但不同的是行为树抽象了控制节点更利于代码复用，在有行为树编辑器做支持的情况下，有更多人选择了行为树。

下面我们对比下状态机和行为树
行为树的优点:
行为逻辑和状态数据分离，任何节点写好以后可以反复利用
重用性高，可用通过重组不同的节点来实现不同的行为树
呈线性的方式扩展，易于扩展
可配置，把工作交给程序之外的人, 既保证了策划同学对于行为思考和实现的一致性，又解放了程序员的生产力
行为树的缺点:
每一帧都从 Root 开始，有可能会访问到所以的节点，相对 State Machine 消耗更多的 CPU
任何一个简单的操作都必须要使用节点

下面我们使用Objective c简单实现一个红绿灯的例子：

首先创建一个可以复用的状态机
有两个类组建一个可复用的状态机
状态类（PCState）：用于定义状态基本的行为转换方法，之后再由具体子类实现转换后的行为以及其他方法。
状态机类（PCStateMachine）：用于把状态组装成一个状态机，并可以转换状态。

接下来实现具体业务（红绿灯）相关的逻辑：
我们接着需要定义各种状态（PCGreenState，PCYellowState，PCRedState）它们继承自PCState，并实现关键的几个方法，以 PCGreenState 为例：

@implementation PCGreenState
// 用于判断是否可以转换到 指定的状态（stateClass）
- (BOOL)isValidNextState:(Class)stateClass {
    return stateClass == PCYellowState.class;
}

// 变换到某种状态后调用
- (void)didEnterWithPreviousState:(PCState *)previousState {
    NSLog(@"💚");
}
@end

剩下的任务就是我们怎么调用状态机了：

 // Create the states
    PCGreenState *greenState = [PCGreenState new];
    PCYellowState *yellowState = [PCYellowState new];
    PCRedState *redState = [PCRedState new];
    
    // Initialize the state machine
    PCStateMachine *stateMachine = [PCStateMachine stateMachineWithStates:@[greenState, yellowState, redState]];
    
    // Try entering various states...
    if (![stateMachine enterState:PCGreenState.class]) {
        NSLog(@"failed to move to green");
    }
    
    if (![stateMachine enterState:PCRedState.class]) {
        NSLog(@"failed to move to red");
    }
    
    if (![stateMachine enterState:PCYellowState.class]) {
        NSLog(@"failed to move to yellow");
    }
    
    if (![stateMachine enterState:PCGreenState.class]) {
        NSLog(@"failed to move to green");
    }
    
    if (![stateMachine enterState:PCRedState.class]) {
        NSLog(@"failed to move to red");
    }
}

调用后会输出如下内容：

2019-06-19 15:19:59.148568+0800 OCStateMachineDemo[763:7482211] 💚
2019-06-19 15:19:59.148737+0800 OCStateMachineDemo[763:7482211] failed to move to red
2019-06-19 15:19:59.148834+0800 OCStateMachineDemo[763:7482211] 💛
2019-06-19 15:19:59.148920+0800 OCStateMachineDemo[763:7482211] failed to move to green
2019-06-19 15:19:59.149037+0800 OCStateMachineDemo[763:7482211] ❤️

这个例子的源码在 https://github.com/wgywgy/OCStateMachine
例子中模仿了 苹果应用于游戏方向的GKStateMachine，GKStateMachine对于较老的iOS不支持，所以有了上面的库。
对于Swift，你也可以看看另一个项目：https://github.com/wgywgy/SwiftStateMachine

感谢以下书籍和文章：

游戏设计模式
https://gameinstitute.qq.com/community/detail/126389