|
|
本文出自游戏 Project Zomboid 的开发者 Chris Simpson，作者介绍了行为树的基本逻辑以及他使用行为树的一些经验，我前段时间在用行为树，看到这篇文章觉得还不错就翻译推荐给大家。作者的原文写的有点绕，我在翻译的时候对段落和结构稍作了调整来方便大家阅读理解。我不是技术背景的人所以翻译中肯定有不少错误，望大家指出。
原文链接：AI Behavior Trees: How They Work
介绍-Introduction
尽管网上已经有大量的关于行为树的教程了，但是当我在做 Project Zomboid 时还是反复遇到了关于行为树的问题。很多教程不是非常关注于具体的代码实现，就是给出一些不带任何实际应用场景、非常笼统的节点图，像这样：
因为这些教程在帮助我理解行为树的核心原则方面没什么帮助，我发现我不但不了解行为树的运作机制，更是对一个完整的行为树该是长什么样子毫无概念，也不知道我该如何为我的游戏中的行为树放置什么节点。
我花了大量时间去试验行为树的用法（我使用的是 JBT - Java Behavior Trees），所以我没有花很多时间在实际的代码实现上。不过网上这方面的内容很多，覆盖了各种不同的引擎，所以这对你来说应该不会是问题。
有可能我提到的某些装饰节点（Decorator Node）类型是专属于 JBT 而不是更加通用的行为树概念，不过因为它们对于 Project Zomboid 是不可或缺的一部分，所以即便你使用的行为树里不包含它们，你也可以考虑实现类似的功能去帮助你设计你的行为树。
我并不是这个领域的专家，但是我觉得我在 Project Zomboid 项目中积累下的一些经验还是很有用的，如果我能在一开始就知道这些东西的话，我可以少走不少弯路。我在下面不会把具体的实现讲的特别细致，而是会抽象地介绍一些我在 PZ 项目中用到的例子。
基础-Basics
行为树的名字很好地解释了它是什么。不像有限状态机（Finite State Machine）或其他用于 AI 编程的系统，行为树是一棵用于控制 AI 决策行为的、包含了层级节点的树结构。树的最末端——叶子，就是这些 AI 实际上去做事情的命令；连接树叶的树枝，就是各种类型的节点，这些节点决定了 AI 如何从树的顶端根据不同的情况，来沿着不同的路径来到最终的叶子这一过程。
行为树可以非常地“深”，层层节点向下延伸。凭借调用实现具体功能的子行为树，开发者可以建立相互连接的行为树库来做出非常让人信服的 AI 行为。并且，行为树的开发是高度迭代的，你可以从一个很简单的行为开始，然后做一些分支来应对不同的情境或是实现不同的目标，让 AI 的诉求来驱动行为，或是允许 AI 在行为树没有覆盖到的情境下使用备用方案等等。
数据驱动 vs 代码驱动-Data Driven vs Code Driven
尽管跟这篇文章关系不大，但我还是想向大家介绍两种不同的行为树实现方式。它们二者的主要区别在于，树是由代码之外的东西所定义的——如 XML 或是一些被专属工具控制的格式，还是由代码直接控制的。
JBT 是一种不常见的混合体——它的编辑器提供了直接构建行为树的工具，同时提供了一个可以将行为树导出为 java 代码的命令行工具。
但是不论用何种实现方法，这些叶节点（Leaf Node），也就是那些真正帮你的角色实现具体行为和条件判断的节点，是需要靠你通过代码来定义的。用行为树自带的语言，或是 Lua 和 Python 这样的脚本语言，它们都将通过你安排的行为树来产生复杂的行为。通过使用行为树内的节点之间的关联来驱动角色的行为，比直接用具体的代码告诉一个角色去做什么事情，要来得有意思得多，这也是行为树最让人兴奋的一点。
树的遍历-Tree Traversal
行为树的一个特点是，它会“一层一层”地去对节点依次进行检查，而这每一层都需要花费一个 tick 的时间，所以它需要花数个 tick 才能完成从顶部走到底的过程，来完成其逻辑，这和一般用代码实现功能是很不同的。
这并不是一个很有效率的方式，尤其是当你的树变得非常深的时候。我认为行为树的实现必须具备可以在一个 tick 内完成整个行为树的判断逻辑，还好 JBT 符合这一点要求。
工作流-Flow
行为树由多种不同类型的节点构成，它们都拥有一个共同的核心功能，即它们会返回三种状态中的一个作为结果。这三种状态分别是：
- 成功-Success；
- 失败-Failure；
- 运行中-Running；
前两个，正如它们的名字，是用来向它们的父节点通知运行的成功或失败的结果。第三种是指还在运行中，结果还未决定，在下一个 tick 的时候再去检查这个节点的运行结果。
这个功能非常重要，它可以让一个节点持续运行一段时间来维持某些行为。比如一个“walk（行走）”的节点会在计算寻路和让角色保持行走的过程中持续返回“Running”来让角色保持这一状态。如果寻路因为某些原因失败，或是除了某些状况让行走的行为不得不中止，那么这个节点会返回“Failure”来告诉它的父节点；如果这个角色走到了指定的目的地，那么节点返回“Success”来表示这个行走的指令已经成功完成。
这些状态可以用来决定行为树的走向，确保 AI 可以按照我们预期的方式来以某些顺序去执行行为树里的行为。
一共有三种节点类型，它们分别是：
- 组合节点-Composite；
- 修饰节点-Decorator；
- 叶节点-Leaf；
组合节点 -Composite
组合节点通常可以拥有一个或更多的子节点。这些子节点会按照一定的次序或是随机地执行，并会根据执行的结果向父节点返回“Success”、“Failure”，或是在未执行完毕时“Running”这样的结果值。
最常用的组合节点是 Sequence（次序节点），它很简单地按照固定的次序运行子节点，任何一个子节点返回 Failure，则这个组合节点向它的父节点返回 Failure；当所有子节点都返回 Success 时，这个组合节点返回 Success。
修饰节点-Decorator
修饰节点也可以拥有子节点，但是不同于组合节点，它只能拥有一个子节点。取决于修饰节点的类型，它的功能要么是修改子节点返回的结果、终止子节点，或是重复执行子节点等等。
一个比较常见的修饰节点的例子是 Inverter（逆变节点），它可以将子节点的结果倒转，比如子节点返回了 Failure，则这个修饰节点会向上返回 Success，以此类推。
叶节点-Leaf
叶节点是最低层的节点，它们不会拥有子节点。叶节点是最强大的节点类型，它们是真正让你的树做具体事情的基础元素。通过与组合节点和修饰节点的配合，再加上你自己对叶节点功能的定义，你可以实现非常复杂的、智能的行为逻辑。比如刚才提到过的一个例子，Walk。Walk 这个叶节点会让一个角色移动到场景里的指定位置，并根
拿代码作为类比的话，组合节点和修饰节点就好比那些改变代码 flow 的 if 判断和 while loop 等等，而叶节点就是那些真正起作用的被调用的方法，去让角色做什么或是进行某些条件判断。
参数可以在这些节点中起到作用，比如 Walk 的这个叶节点可以包含一个具体将要移动到的位置的参数。这些参数可以从其他变量里获得，比如角色将要前往的一个地点可以被 GetSafeLocation 这个节点所决定，存入一个变量里，然后 Walk 节点可以使用这个变量来定义它的目的地。行为树的运行中，这些不同的节点通过数据上下文来共同储存或使用一些持久数据（persistent data），使得行为树的功能变得强大。
另一种叶节点的类型是调用其他的行为树并把当前行为树的数据传给对方。
这些功能将允许你高度模块化你的树并把很多节点用在更多的地方。比如 Break into Building（闯入房间）行为需要先有一个 targetBuilding（目标房间）的变量来进行操作，那么父树可以先定义 targetBuilding 这个变量，在子树需要闯入房间时通过一个叶节点来把这个变量传入。
组合节点-Composite Nodes
接下来我们来看看这些行为树里最常见的组合节点。尽管这不是所有的内容，但是它们已经足以共同构建出足够复杂的行为树了。
次序节点-Sequences
正如它的名字所说，次序节点会依次（译者：通常是从左到右）访问子节点。每个子节点成功之后便轮到下一个，直到最后。如果所有子节点都 Success，则向次序节点返回 Success；其间任何一个子节点返回 Failure，就会立即向次序节点返回 Failure 的结果。（译者：用“和 and”的方式来理解次序节点就会非常清楚了）
次序节点有很多的用处，其中最显而易见的用法就是执行一连串有前后依存关系的行为，其中一个的失败必然导致后续的动作没有进行的意义，比如这个“进门”行为的例子：
这个次序节点下的子节点共同让角色实现了从走向门到进门关门的连串动作。过程如下：
次序节点 ->Walk to Door (Success) ->次序节点（Running） ->Open Door (Success) ->次序节点（运行中） ->Walk through Door (Success) ->次序节点（Running） ->Close Door (Success) ->次序节点（Running） -> 向次序节点的父节点返回 Success。
如果角色因为某些原因未能成功走到门前，比如路被挡住了之类的，那么试图开门这些动作都没有意义了。当走向门这个动作失败的时候，次序节点就会返回 Failure，其父节点就可以根据这个结果来进行后面的事情了。
次序节点除了非常自然地用于进行一系列前后依存的动作之外，还可以用来做一些其他的事情，比如：
在上面这个例子中，次序节点的子节点不是一系列动作而是一系列的检查。这些子节点会检查角色是不是饿了，有没有食物，是不是在安全的地点，只有在它们都返回 Success 时，角色才会吃东西。这样使用次序节点可以实现类似于代码中 if 判断和“与门（AND gate）”的效果。这些用于判断的子节点可以是其他的组合节点或是修饰节点等等来实现更丰富的效果。比如下面这个使用了逆变节点的例子：
尽管功能和前面的例子完全一样，但是通过逆变节点我们在这里创建了一个非门（NOT gate），只有在“Enemies Around（敌人在周围）”这个条件返回 Failure 时，这一步才会返回 Success，从而让角色继续进行吃东西的动作。这意味着这些节点的组合可以减少很多不必要的开发量。
选择节点-Selector
选择节点就是次序节点的反面。作为“与门”的次序节点要求子节点都返回 Success 来让自己返回 Success，选择节点则会在任何一个子节点返回 Success 时就返回 Success 并且不再继续运行后续的子节点。相应的，当所有子节点都 Failure 时，选择节点才会返回 Failure。选择节点其实可以被理解为一个“或门”（OR gate）。
它的主要作用在于它可以用来表示一个行为的多种方式，从最高优先级到最低，任何一个方式的成功都会让这个动作 Success（译者：比如“攻击”节点下的“劈”“砍”和“斩”，每当这个 AI 尝试攻击时，都会从这三个中选择一个来执行）。这个逻辑可以用在很多地方，乃至那些很复杂的 AI 行为。
让我们回到之前那个进门的例子，看看选择节点如何给这个行为增加复杂性。
我们只用了几个节点就制造了一套应对锁上的门的逻辑。我们来看看这个选择节点被执行时发生了什么吧。
首先，它执行了开门节点。它最希望得到的结果是直接打开门，如果这一步成功了，就没有后面的事儿了，没有必要走到其他选择节点的子节点里去检查该做什么。但是如果门没法成功打开，那么这个开门节点会 Failure，向它的父节点返回 Failure。在这个情况下，选择节点会继续尝试它的第二个子节点，或是优先级稍低于前一个的节点，来试图打开门锁。
我们在这里加入了一个执行打开门锁动作的次序节点，因为是次序节点，所以它的子节点的行为是有前后依存关系的，必须开锁成功才会执行后面的开门动作。两个子节点都 Success 后，这个次序节点的父节点——也就是那个选择节点也会返回 Success，那么角色就可以执行后面的穿过门的动作了。
如果前面的尝试都 Failure（比如角色没有钥匙，或是没有开锁的技能），它们的失败会让选择节点尝试第三个开门的方式——把门打烂！
假如角色连这一点也做不到的话，它也令整个选择节点 Failure，从而导致整个试图走进门的行为的 Failure。
也许我们可以添加一个新的行为来作为走进门这个行为 Failure 后的备选方案？
我们在树的顶部增加了一个选择节点。当角色试图进入房间时，他会先试着从门进去，当这样做行不通时，他会尝试从窗户进入。这个简化的示例很好地解释了这个逻辑，但实际的项目里的行为树可要比这个复杂多了。比如说，当这个房间没有窗户的时候，整个“进入房间”的节点会失败来告诉这个角色前往下一个房间？
相比我之前做过的各种 AI 开发的尝试，行为树能够简化 AI 开发的关键因素在于一项任务的失败不再意味着当前所做事情的完全终止（比如，“寻路失败。那我该干什么？”这样的情况），而是符合 AI 系统范式的，行为决策中很自然的一个可预期的结果。
你可以为所有的情况都安排一个“失败保险”来让角色总是知道该做什么。一个例子是 Project zomboid 当中的 EnsureItemInInventory 行为（确认物品在物品栏）（译者：Zomboid 游戏里的物品栏有点像暗黑2里面的腰带和异星工厂里的快捷栏，玩家可以把物品从背包放到这里以供便捷地使用）。这个行为用一个选择节点来决定使用一系列的动作中的某一个，并使用不同参数对相同行为进行递归调用，来确保某个物品在 NPC 的物品栏里（译者：我没有编程背景，故对递归相关的理解恐有偏差，如有错误望告知）。
首先它会检查这个物品是不是已经在这个角色的物品栏里。这是最好的状况，搞定。EnsureItemInInventory 成功，这个物品已经可供使用。
要是这个物品不再角色的物品栏里，那么我们要检查角色携带的一切背包和袋子来寻找这个物品。如果有，那这个物品会来到角色的物品栏上，返回成功。
如果仍然没找到，那么选择节点的第三个分支会判断角色当前所处的房间里有没有这件物品。如果有，那么角色会移动到放有这件物品的位置来将其加入其物品栏。
如果继续失败，NPC 还会有招数可用。他会检查他是否有他需要的那个物品的打造配方，并依次对配方里所需要的每一个素材进行 EnsureItemInInventory 行为的递归调用，这样我们就可以知道 NPC 是否持有用来打造那个物品的全部素材。接下来，角色就可以打造这个物品。又一次成功。
如果还是失败了，那么 EnsureItemInInventory 就失败了。没有其他后续方案，NPC 会将这个物品加入到他的需求列表（或可以理解为一个制造任务单）里，提醒自己接下来要去寻找这个物品。
角色可能会在后面的探索中突然凑齐制作的素材。由于么 EnsureItemInInventory 的递归属性，NPC 会尝试寻找和探索那些最基础的素材，一步一步地最终收集齐打造物品所需要的全部素材。
只是借助于这些相对简单的节点和相互的层级关系，我们一下子就拥有了一个看上去很聪明的 AI。每当 NPC 在其他的行为树里需要确认他是否拥有某件物品时，我们就可以拿出 EnsureItemInInventory 行为反复使用。
我相信在随着游戏的开发，我可能会让 NPC 在没有找到物品之后有其他的后续方案来影响他寻找特别需要的物品时的行为模式，比如在急需工具锤子时会优先前往五金店这样的地点寻找来提高成功率。又比如，有一天我开发了一些新的游戏玩法，让某些物品拥有了临时的替代品，那么寻找物品时的优先级肯定也会受到这一因素的影响。举个例子，与其穿过重重僵尸的包围潜入到一家五金店去寻找一把锤子，不如就拿手头的石头来敲钉子好了，哪怕它没有锤子那么好使。
这些例子所表明的行为树的可扩展性，使得 AI 的开发可以从最简单的“把事情办了”开始逐渐迭代，用新的选择节点添加分支来扩展不同情况下 AI 的行为。丰富的后续方案可以降低一个行为彻底失败情况的出现，从而展现更加合理的 AI 行为。前面提到，NPC 找不到物品时会试图打造物品，实际上这个功能也是后面才加入的。即便没有这个行为逻辑，NPC 也会尝试寻找物品，但这一行为大大提高了 NPC 达成自己目标的能力。
再加上合理地为各种后续方案赋予优先级和条件，哪怕都是编程好的行为，它们也能让 AI 在行为决策时表现得更加自然和聪明。
随机选择节点和随机次序节点-Random Selectors and Random Sequences
这两种节点跟它们的非随机版本运作起来几乎一样，除了它们在选择要执行的子节点时是随机的。当子节点上的行为没有明确的优先级时，使用这种节点可以为 AI 的行为提供更多的的不可预测性。
修饰节点-Decorator Nodes
逆变节点-Inverter
前面提到过这个节点，他会反置或否定子节点的结果。
成功节点-Succeeder
成功节点不管它的子节点向其返回的结果为何，它总是返回 Success 的结果。这个往往用在当你知道一个子节点一定会返回 Failure 的结果，而它的父节点是次序节点，会因此而终止，那么你可以强行让这个子节点返回 Success，来避免这一情况的发生。我们并不需要一个专门的失败节点，因为一个逆变节点加上成功节点就可以达到这一效果。
重复节点-Repeater
重复节点会在它的子节点返回结果后反复继续执行它。重复节点常常被用在一棵树的最顶部来确保树的持续运行。另外重复节点也可以被设定重复执行的次数。
重复直至失败节点-Repeat Until Fail
类似重复节点重复执行子节点，但这一节点会在子节点 Failure 的时候返回 Failure。
数据上下文-Data Context
接下来的内容涉及到具体的行为树的实现，以及所使用的编程语言等问题，所以方法上会因人而异。因此，我会尽量保持内容的抽象和概念化。
当一个行为树被调用时，一个数据上下文也被创建出来。它的用途是存储被节点所解释和改变的变量。这些变量随后可以被节点结合着数据的上下文加以读写，从而使整个行为树保持为一个统一的整体。当你开始深入了解这部分内容时，你会发现行为树的灵活性和适用范围是多么出色，你对它的设计的力量变得更为明显。我将以前面提到过的门和窗的行为为例，来继续讨论这一话题。
定义叶节点-Defining Leaf Nodes
这里的内容是关于行为树的具体实现的，所以不同的方法和系统会有所区别。但为了通过叶节点来将游戏的具体功能加入到行为树中，大部分的系统都会有下面这两个功能。
Init（初始） -- 在一个节点第一次被其父节点访问时被调用。比如一个次序节点会在轮到它执行的时候调用 Init。在所有的子节点都完成了执行并返回了结果给父节点以前，即走完一次流程之前，Init 不会再次被调用。这个功能用来初始化这个节点并开始执行它的动作。以 Walk 这个行为为例，它会获取一些参数来初始化这个寻路的任务。
Process（执行）-- 在节点运行时的每一 tick 都会被调用。如果得到了 Running 的结果则会一直运行下去；而一旦这个功能得到了成功或失败的结果，运行就会终止，结果也被返回给父节点。在 Walk 这个例子里，它会返回 Running，直到寻路成功或是失败。
节点可以有属性，既可以是被明确指定传入的参数，也可以是根据数据上下文从控制这个 AI 的实体里的变量引用而来。我不会涉及具体的实现方式，因为它会因使用的编程语言和行为树系统而有所不同，但是行为树的参数和数据存储的概念是通用的。
比如，我们这样定义一个 Walk 节点：
Walk（character，destination）
- Success：到达目的地
- Failure： 未能达到目的地
- Running：行进中
在这个例子中 Walk 节点有两个参数，分别是 character（角色）和 destination（目的地）。尽管很自然地会认为运行这个 AI 行为的对象就是这个节点的所有者，所以不需要专门把这个信息作为参数传入，但是最好还是不要这样默认。很多次我发现，尤其是在作为条件判断的节点上，我经常需要为了测试其他角色的行为或与他们交互而重新写代码。所以我们最好还是多走一步，哪怕你认为只有这个 AI 会使用这个行为，也还是把角色的信息也作为参数传入。
至于 destination，可以手动地填入 XYZ 的坐标。但是更有可能的情况，是这些坐标信息作为上下文变量被引用，如从其他的对象中获取的位置，或是根据 NPC 所在位置计算出的一个最近的安全躲避点等等。
栈-Stacks
当第一次使用行为树时，很自然地会把节点的适用范围与角色的行为、判断条件和情境联系起来。带着这些限制，行为树的能力得不到最大发挥。
我发现用节点实现栈操作会有很显著的作用，于是我为游戏加入了下面这些节点：
- PushToStack(item, stackVar)
- PopFromStack(stack, itemVar)
- IsEmpty(stack)
就是这样，三个节点而已。它们只需要 init/ process 功能的支持就可以实现一个标准库的创建和修改的栈操作，只用了几行代码，它们就打开了一系列的可能性。
比如 PushToStack 创建一个新的栈，并且将传入的变量名存入，压入栈。类似的，PopFromStack 将一个前面压入的变量弹出栈并储存为 itemVar 变量。当栈已经为空时返回失败。IsEmpty 就是用来检查这个栈是否是空的，如果是则返回成功，否则失败。
使用这些节点，我们就可以用这样的树来遍历整个栈：
PopFromStack，加上一个在栈为空之前都会重复让其执行的 Until fail repeater 父节点就可以实现我们需要的结果。
接下来是一些其他的我常用的功能性节点：
- SetVariable(varName, object)
- IsNull(object)
现在假设我们添加一个叫做 GetDoorStackFromBuilding 的节点，你可以传入一个房间物体，然后它会将这个房间的门物体全部取出并建立一个栈来储存它们并以其作为我们的目标对象。那么接下来我们可以用它来做什么事情呢？
呃，看起来变得有些复杂了。不过最终，跟任何语言一样，当你理解了其中原理你就可以轻松读懂它，而且在失去了可读性的时候，我们还获得了灵活性。
它做了什么呢？简而言之，这个行为会提取一个房间的所有门并尝试进入，如果角色成功地进入了任何一个则返回 Success，否则会 Failure。
首先它会获取这个包含了所有门的栈，通过调用 Until Fail repeater 节点，它会反复执行它的子节点，直到返回 Failure 为止。它的子节点是一个次序节点，会用 PopFromStack 从前面提到的栈里弹出一个门，并将其保存在 door 这个变量里，后面会用到 door 这个变量来告诉角色该去试图进入哪个门。
如果因为栈空了而弹出失败，则这个节点会返回 Failure 并用这个结果结束了前面的 Until Fail repeater 节点，继续最顶上的这个次序节点的执行，来到了这个结果被逆变的 IsNull 节点。它会检查 usedDoor 这个变量的 IsNull（是不是空的），显然它一定是空的，即返回 Success，因为我们还从来没有机会去设置它，所以这个成功被逆变节点返回为 Failure，于是整个行为 Failure。
如果栈确实弹出了门，那么它会调用另一个次序节点（也是带有逆变节点的），它会尝试走向那扇门，打开它然后走进去。
如果因为种种原因 NPC 没能成功穿过这扇门，那么这个次序节点会 Failure，而逆变节点会将这个 Failure 转化为 Success 向上返回，导致它的父节点仍然走不出这个 Until Fail repeater，故而会继续重复 PopFromStack，改变 door 变量的值，让 NPC 去尝试进入另一个门。
如果 NPC 成功穿过了一扇门，那么它会将这扇门赋值给 usedDoor 变量，并返回 Success。你会注意到我用到了一个 Succeeder 来修饰关门这个动作，这是因为要是前面 NPC 使用了破门的方式来开门的话，这里关门的动作应该就不会成功了，所以我需要这个修饰节点来确保它的成功结果。最后，整个次序节点的成功会被逆变节点转化为失败并让父节点离开 Until Fail repeater。在这种情况下，行为树继续往下走，我们会在 usedDoor 的 IsNull 中 Failure，因为刚刚 usedDoor 被赋了值，通过被逆变后，结果为 Success，现在它的父节点也会返回 Success，得知 NPC 成功地找到了一扇门并走了进去。
如果还是失败的话，我们可以用 GetWindowStackFromBuilding 来使用一样的步骤再对所有的窗户走一遍流程。
翻译：金盟
来源：INDIENOVA
地址：https://indienova.com/indie-game-development/ai-behavior-trees-how-they-work/
|
|
发表于 2019-6-6 11:15:22
发表于 2020-5-25 10:43:57