行为树及其实现 Domi●Cat

前两周一直在忙于ai的优化,之前的ai实现有一点类似状态机的做法,写起了有点不太简洁优雅,可维护性比较低。 加之之前对行为树有一点了解,所以寻思将之前的ai改为行为树的方式。

在动手之前,自己也参考了网上很多关于行为树的介绍,以及行为树相关项目。

关于行为树的介绍:

主要参考了育碧大神finney关于行为树介绍的文章。大神的博客里面有很多关于ai设计的文章,干货十足。

另外,可以参考资料《The Behavior Tree Starter Kit》,出自《Game AI Pro》第一版第二部分(Section 2: Architecture)的第六章节。 对应的代码在github上。我会抽个时间翻译一下。

行为树的相关项目:

我看过的项目主要有两个:

饥荒的脚本是lua实现,而且是未编译成字节码的,所以可以看到整个游戏的lua层代码,其中就包括了饥荒整个ai框架。
ai相关的主要代码在:behavioursbrainsstategraphs 这三个文件夹,其中stategraphs是状态机的实现,也有参考意义。 我也是将里面行为树部分移除出来,并做了一些修改运用到我们的游戏中。

什么是行为树

先看一个简单的怪物行为树: 怪物简单行为树

行为树是一种树形结构,它其实可以看成是一个分层状态机从网状图拉成了一个树。一颗树包含了中间节点和叶子节点, 中间节点控制决策的走向,叶子节点则负责展现行为。

行为树的节点

行为树节点主要分为:

  1. 组合节点(序列节点、选择节点、并行节点等)
  2. 装饰节点(有且仅有一个子节点)
  3. 条件节点
  4. 动作节点

组合节点和装饰节点只能作为行为树的中间节点,而条件节点和动作节点作为树的叶子节点。 所以,条件和动作节点称为行为节点(Behavior Node),组合和装饰节点称为决策节点(Decider Node)。

在详细介绍每个节点之前,首先要了解节点的状态。行为树的每个节点的运行状态只会有两种:

  • 运行中(running)
  • 运行完毕(success/failed)

父节点通过每个子节点的运行状态,来决定自己的状态。

如何理解running状态?

举个例子,假如人吃饭是一个行为,但是吃饭需要花一段时间,所以当人执行吃饭的行为时,这个吃饭的节点就处于running中, 直到吃完后,才会变成success状态(吃饭成功),或者吃到一半时发现菜里有屎,变成failed状态(吃饭失败)。

当然,如果是瞬时动作,可以不需要running。

组合节点

  • 序列节点

它实现的是and的逻辑,例如:r = x and y and z,则先执行x,如果x为true,则继续执行y,如果x为false,则直接返回false,以此类推 执行该节点时,它会一个接一个运行, 如果子节点状态为success,则执行下一个子节点; 如果子节点状态为running,则把自身设置为running,并等待返回其他结果(success或failed); 如果子节点状态为failed,则把自身设置为failed,并返回; 如果所有节点都为success,则把自身设置为success并返回。 原则:只要一个子节点返回”失败”或”运行中”,则返回;若返回”成功”,则执行下一个子节点。

  • 选择节点

它实现的是or的逻辑,例如:r = x or y or z,则先执行x,如果x为false,则继续执行y,如果x为true,则直接返回true,以此类推 执行该节点时,它会一个接一个运行, 如果子节点状态为success,则把自身设置为success并返回; 如果子节点状态为running,则把自身设置为running,并等待返回其他结果(success或failed); 如果子节点状态为failed,则会执行下一个子节点; 如果所有没子节点都不为success,则把自身设置为failed并返回。 原则:只要一个子节点返回”成功”或”运行中”,则返回;若返回”失败”,则执行下一个子节点。

  • 并行节点

看上去是同时执行所有的子节点,但是真正的逻辑还是一个一个执行子节点。 可以自己设定并行节点的退出条件,比如:如果子节点失败,则并行节点返回,并将自身状态也设为失败。

装饰节点

顾名思义,它只是对它的子节点的运行状态做一些修饰,比如取反、限制次数等。

条件节点

条件节点根据比较结果返回成功或失败,但永远不会返回正在执行(Running)

动作节点

即真正的行为,可能一些行为需要特殊实现,所以,可以根据需要自行定制。

行为树的实现

我移植的行为树实现,已经放在了github repo, 但是在实现上稍微有一些区别。在饥荒原版的实现中,ai固定思考的频率是变动的,而我将它改为了固定频率。

什么意思呢?

首先,要明白饥荒行为树的执行流程。

行为树根节点(PriorityNode)有一个最大思考间隔_period,每次思考(执行)一次后,如果思考耗时未超过_period,则有两种处理方式:

  1. 如果思考后的结果为running,则根节点会记录这个running的子节点,并在思考后计算出下一次思考的间隔时间,那么下一次则直接从这个running的子节点开始思考;
  2. 如果思考后的结果为成功或者失败,则在下一个逻辑帧时从根节点重新思考。

如果思考超过了最大思考间隔,则从根节点重新思考一次,不管上次思考的结果是否是running。

举个例子:

假设 _period=1000 ms, 游戏的逻辑帧为10ms, 并且按照下面的思考流程:

  1. 第一次思考的时间戳是0,思考完后有一个子节点A返回running,并且需要在300ms后进行下一次思考;
  2. 等待300ms后,开始第二次思考(此时时间戳为300),直接从A开始执行,这里需要注意,返回的结果不同,下次思考的流程也会不同;

    • 若思考后返回success,并且下一个逻辑帧(10ms后)又需要从头重新思考;
    • 若思考后返回running,并且需要等待800ms,那么,300+800>1000,所以下次思考的间隔时间为(0+1000)-300=700ms。

换句话说,最大思考间隔的作用是,防止某个子节点一直running,而导致其他满足条件的子节点得不到运行的机会。

而我改成固定频率,是担心ai思考过于频繁,还是上面的例子,在第二次思考后,如果返回成功,下一次思考还是需要等待700ms,而不是在下一次逻辑帧从头重新思考。