五邑隐侠，本名关健昌，10年游戏生涯，现隐居五邑。本系列文章以TypeScript为介绍语言。

本篇介绍有限状态机和行为树。有限状态机用于有限的状态下的AI，由于同时只能处于一个状态，多个状态需要多个有限状态机，一般用于简单的AI行为。行为树是基于固定行为，通过遍历树来决定采用哪种行为。行为的设计和执行采用解释器模式，由策划设计数据，程序解析执行，行为组合的灵活性高，比较适合剧情NPC。但当树比较深、分支比较多时，遍历的效率就需要考虑优化。一般我们认为有限状态机执行的性能优于行为树，但不能胜任复杂、灵活的AI设计。而行为树则比较适合复杂、灵活的AI设计。

先介绍下有限状态机。考虑在一个类似《刀塔传奇》的横版动作卡牌游戏的战斗里，每个英雄有出场、站立、走位、受击、吟唱、施法等状态。英雄每时每刻只能处在这些状态中其中一个状态，每个状态都有自己的逻辑，状态的改变都由事件驱动。像这样简单的AI，可以使用有限状态机来实现。

有限状态机包括几个要素：

1.状态，状态机同时只能处于一个状态，在指定状态下有相应的逻辑，例如行走状态，播放行走动画，每帧修改英雄的x、y值

2.事件，事件是状态转变的触发器，包括内部事件和外部事件。例如最近的敌人达到攻击距离，触发从行走状态转变为站立状态。CD时间到达，触发从站立状态转变为施法状态

3.状态转变，状态间可以相互转变，转变过程有对应的逻辑。例如从行走状态转变为站立状态，播放站立动作。

现在来介绍下行为树。在RPG游戏中，地图上存在一些剧情NPC，不同的剧情下，NPC的行为会不一样。这些NPC的行为可以通过行为树进行管理。行为树是在固有行为集下，进行行为抉择的AI算法。行为树包括数据解析、逻辑控制、行为执行三部分。

行为树数据由节点组成，每个节点有对应的行为类型、参数、返回值。节点有一个子节点数组，通过这种方式将节点组织成树状。

export class BehaviorNode {

    private type: number = 0;

    private params: any = null;

    private retVal: any = null;

    private subBehaviors: Array<BehaviorNode> = [];

}

逻辑控制节点都有子节点，逻辑控制指的是跟编程类似的if条件判断、while循环、串行执行、并行执行等。if行为如果返回true，执行子节点行为，子行为结束则整体行为结束。while行为如果返回true，执行子节点行为，如果子节点结束，重置子节点重新执行。串行行为，子节点一条一条的依次执行，子节点结束则整体结束。并行行为，子节点同时执行，子节点结束则整体结束。

行为树的叶节点是实际行为执行的节点，在开发一款RPG游戏时，需要根据剧情需要，提炼出角色的细粒行为，例如行走、对话、播放表情、切换动画、触发战斗等。一般地，RPG都会开发一个对应的剧情编辑器，对地图上的NPC进行行为设定，导出对应行为的参数。游戏加载这些数据，解析生成行为树，NPC每帧执行行为树，叶节点行为有对应的执行方法，方法的参数为行为节点的参数。

private _parseWalkData(): BehaviorNode {

    // TODO 二进制数据解析为json

}

public execBehavior(b: BehaviorNode): void {

    if (!b) {

        return;

    }

    switch(b.type) {

        case BehaviorType.WALK:

            this.execWalk(b);

            break;

    }

}

private _execWalk(b: BehaviorNode): void {

    let actorId = b.params.id;

    let destGridX = b.params.destGridX;

    let destGridY = b.params.destGridY;

    let actor = map.getActor(actorId);

    let curGridX = actor.gridX;

    let curGridY = actor.gridY;

    let loadGrids = AStar.findLoad(curGridX, curGridY, destGridX, destGridY);

    actor.setLoad(loadGrids);

}

一般地，游戏地图中的物件都可以挂载行为树，地图本身、角色、地图物品等，将一个剧情的复杂行为，分拆到每一个地图物件上，通过剧情任务作为条件区分触发，简化行为的组织。程序员只负责将策划的设定提取出细粒行为，编写对应的数据解析和执行方法，由策划使用编辑器编辑数据，由数据驱动剧情的推进。

有限状态机和行为树先说到这里，下一篇我们将介绍状态同步。