AI行为树的工作原理
原文： Behavior trees for AI: How they work 作者： Chris Simpson 译者： Anthony Han
最近在研究行为树相关的内容，看了不少很好的文章。不同于其它文章阐述行为树的原理和实现，这篇文章着重于实践使用，介绍了行为树一般用法，还有一些开阔眼界的特别技巧。为加深印象，我利用业余时间翻译了一下，也希望对他人也有帮助。
引言
虽然网上有很多行为树的教程和指南，但是在研究能不能用在 Project Zomboid 中时，我总是遇到同样的问题。许多教程把重点放在行为树的代码实现上，或者仅仅专注在无上下文的流程图上，而没有任何真正适用的示例，其图表就像这样：
虽然在帮助我理解行为树的核心原则方面，这些教程是非常有价值的。但我发现自己处于一种情况：即使知道行为树的运作机制，我也不知道我应该为游戏创建什么样的节点，或者一个真正的完全成型的行为树是什么样子。
我花了大量的时间进行实验（由于Zomboid项目是用Java写的，我一直在用很棒的JBT —— Java行为树（ http://sourceforge.net/projects/jbt/ ），所以我没有必要关心自己的实际代码实现。尽管有很多教程的重点在这方面，还有许多常用的游戏引擎中的实现。
我在这篇文章提到的某些特定装饰器的节点类型，可能来自于 JBT 而不是一般的行为树概念，但是我发现它们是行为树系统中不可或缺的一部分。如果你的行为树不支持的话，你可以考虑实现一下。
我不会自称是这个方面的专家，但是经过 Project Zomboid 游戏中NPC的开发工作，我觉得我还是有点本事的，所以我想我要爆料一些东西。如果我早点知道会让我的第一次尝试更顺利，或者至少打开了我的眼界，让我了解通过行为树可以做到什么。我不打算深入进行实现，但会给出一些在 Zomboid 项目中使用的抽象示例。
基础知识
顾名思义，与有限状态机或AI编程的其他系统不同，行为树是控制AI实体决策流程的分层节点树。在树的范围内，叶子节点是控制AI实体的实际命令，而分支节点则是各种类型的功能节点，用来控制AI沿树结构走到最符合情况的命令序列。
行为树可能非常深，带有很多执行特定功能子树的节点，允许开发人员创建可以链接在一起的行为库，用来产生非常令人信服的AI行为。开发是高度迭代的，你可以从构建基本行为开始，然后创建分支节点来处理实现目标的各种方法，分支节点按其需求排序，允许AI在特定行为失败时具有后备策略。这是它们的出众之处。
数据驱动与代码驱动
这个区别与本指南几乎没有关系，但是应该注意的是行为树有许多不同的实现。一个主要区别是树是否在代码库的外部定义，或许是以XML或专有格式定义的，并且使用外部编辑器进行操作，还是通过嵌套类实例直接在代码中定义树的结构。
JBT采用了这两种方式的混合方案，其中提供了一个编辑器来允许你可视化地构建行为树，但是导出器的命令行工具实际上会生成java代码来表现代码库中的行为树。
无论实现是什么样，叶子节点，实际执行游戏特定业务并控制角色或查看角色情况或环境的节点，都是你需要在代码中定义自己的东西。使用原生开发语言或使用Lua或Python等脚本语言。这些可以让你的行为树提供复杂的行为。这些节点可以表现得相当多，有时候作为一个标准库去操作树本身的数据，而不仅仅是简单的字符命令，这些都是行为树让我excited的原因。
树的遍历
行为树的一个核心部分是，与代码库中的方法不同，树上的特定节点或分支可能需要游戏中很多个循环才能完成。在行为树的基本实现中，系统在每一帧里从树的根节点向下遍历，测试每个节点以查看哪个是活动的，重新检查沿途的任何节点，直到到达当前活动的节点再进行下一次循环。
这不是一个非常有效的处理方式，尤其是行为树在开发过程中逐渐扩展时而变得越来越深时。在我看来，行为树有必要存储当前正在处理的节点，这样下次循环可以被直接处理，而不是每次循环重新遍历整个树。JBT就是采用这种处理方式的。
流程
行为树由几种类型的节点组成，但是一些核心功能对于行为树中的所有类型的节点都是通用的。就是它们都有三种返回状态。（根据行为树的实现情况，可能有三种以上的返回状态，但是我还没有用过，而且和本文的介绍内容无关）。三种常见的状态如下：
- 成功
- 失败
- 正在运行
前两个，如名字所示，告诉父节点，执行的动作是成功还是失败。第三个的意思是成功或失败尚未确定，节点仍在运行。下一次循环行为树再次运行的时候，该节点将被再次执行，这时它有可能成功，失败或继续运行。
这个功能是行为树强大的关键，因为它允许节点的处理持续多个游戏循环。例如，一个负责行走的 Walk 节点在计算路径时返回运行状态，以及在角色走到到指定位置的期间。如果由于任何原因导致寻路失败，或者在步行过程中出现某些其他复杂情况，以阻止该角色到达目标位置，则该节点将向父节点返回失败状态。如果角色的当前位置等于目标位置，则返回成功来表示 Walk 命令执行成功。
这意味着独立的节点一定会返回成功或失败，并且可以保证任何调用该节点的树一定会接收到其返回值。这些返回状态然后传播并明确了行为树的执行流程，提供了一系列事件和不同的执行路径，以保证AI的行为和期望的一样。
通过这种共有的功能，行为树节点有三个主要原型：
- 组合节点
- 装饰节点
- 叶子节点
组合节点
组合节点是可以有一个或多个子节点的节点。它会根据复合节点的特定规则以先后顺序或随机处理一个或多个子节点，并且在某些阶段将完成处理并将成功/失败状态传递给其父节点，其状态通常由子节点的成功/失败决定。组合节点在处理子节点的期间将持续返回正在运行状态。
最常用的组合节点是Sequence，它会依次执行每个子节点，当在任何一个孩子失败的时刻返回失败，并且如果每个孩子返回成功状态，则返回成功。
装饰节点
装饰节点，和组合节点一样也可以拥有一个子节点。不同的是，它们只能拥有单个子节点。装饰器节点根据其类型的不同，转换子节点返回状态中接收到的结果，以终止子节点，或重复处理子节点。
取反节点是一个常用的装饰节点，它会取反子节点的返回值。如果它的子节点失败，那么取反节点会返回成功，或者子节点成功，那么它会返回失败。
叶子节点
叶子节点是最低层级的节点类型，并且不能拥有任何子节点。
但子节点却是最强大的节点类型，因为它是由你的游戏定义并实现的，用来进行游戏相关或者角色相关的测试或行动，使你的行为树切实地发挥作用。
继续用上面那个例子，就是Walk。Walk叶子节点会让角色走到地图上的特定地点，并根据结果返回成功或失败。
既然你可以自己定义叶子节点（通常是非常精简的代码），那么当它布置在复合节点和装饰节点之上时，就会非常具有表现力，并且允许你创建功能相当强大的行为树，这些树具备相当复杂的层次和智能优先级的行为。
以游戏代码做类比，将复合节点和装饰节点视为函数、if语句、while循环以及定义代码流的其他语言结构，而叶子节点视作游戏特定的函数调用，使你的AI动起来或者检查它的状况。
这些节点可以定义参数。例如，Walk 叶子节点可能含有一个角色走向的目标坐标。
这些参数可以从存储在的AI角色行为树的上下文的变量获取。例如，移动到位置是由 GetSafeLocation 节点决定并存储在一个变量中，而 Walk 节点可以使用这个存储在上下文中的变量来定义目标位置。在行为树的运行过程中，在节点间共享的上下文来存储和更改持久化的数据，使得行为树非常的强大。
叶子节点的另一个主要类型是调用另一个行为树，将现有树的上下文数据传递到被调用的树。
这些功能是非常关键，因为它能行为树大幅模块化，来创建可以重用的行为树，也可以在使用上下文中特定变量进行操作。例如，“闯入建筑”行为可能需要一个targetBuilding变量，因此父树可以在上下文中设置这个变量，然后通过子树的叶子节点调用子树。
组合节点
这里我们会讨论在行为树中最常见的复合节点。还有其它类型的，但是我们会介绍一些你自己编写复杂的行为树时会碰到的基础知识。
序列节点
行为树中的最简单的复合节点，正如其名。序列节点会依次执行每个子节点，从第一个开始，成功则执行第二个，依此类推。如果任何一个子节点失败，它会立即返回失败。如果序列中的最后一个子节点返回成功，则该序列节点将返回成功。
需要明确的是，行为树中的节点类型具有相当广泛的应用。序列节点最常见的用法是用来定义必须全部完成的任务序列，一个任务失败就意味着任务序列的下一步处理变得多余。例如：
这个序列节点清楚地表明，会让给定的角色走过一扇门，然后关上门。实际上，这些节点在生产环境中可能会更为抽象并且会使用参数。Walk (location), Open (openable), Walk (location), Close (openable)
处理顺序是这样的：
序列节点 -> 走向门（成功） -> 序列节点（正在运行） -> 开门（成功） -> 序列节点（正在运行） -> 走过门（成功） -> 序列节点（正在运行） -> 关门（成功） -> 序列节点（成功） -> 序列节点返回成功。
如果一个角色不能走到门口，也许是因为路径被阻挡，那么尝试开门或走过门就没有意义了。当行走失败时序列节点会返回失败，序列节点的父节点可以正常地处理失败情况。
事实上，序列节点天生适用于角色的动作顺序，而由于看上去是序列节点在AI行为树的唯一用法，使得其除此之外的用法不那么明朗。请看：
在上面的例子中，我们没有一个行动列表，而是一个测试列表。子节点检查角色是否饥饿，他们身上是否有食物，他们是否在安全的位置，并且只有当所有这些都返回成功时，角色才会吃食物。使用这样的顺序可以让你在执行动作之前测试一个或多个条件。类似于代码中的if语句，以及电路中的与（AND）门。由于所有的子节点都需要成功，而这些子节点可能是复合/装饰或叶子节点的任何组合，它可以在AI大脑中进行非常强大的条件判断。
例如看一下上面提到的取反节点：
和前面的例子功能相同，在这里我们展示如何使用取反节点来否定判断，相当于给你一个非（NOT）门。这意味着你可以大大减少角色或游戏判断条件的节点数量。
选择节点
选择节点是序列节点的反面。序列节点是一个与（AND）门，所有的子节点返回成功才返回成功，如果选择节点的一个子节点返回成功，那么它会直接返回成功，并且不再处理其它的子节点。它会处理第一个子节点，如果失败那么处理第二个子节点，如果再失败会处理第三个子节点，直到有子节点返回成功，那么它将立即返回成功。如果所有的子节点全部失败则会返回失败。这意味着选择节点类似于或（OR）门，并且作为条件语句用来检查多个条件以判断其中任何一个是否为真。
选择节点的主要能力来自于他们可以表示多种不同的行动方式，按照从最有利到最不利的优先顺序，并且如果任何一个动作执行成功，都会返回成功。这样功能的潜力巨大，你可以通过使用选择节点快速开发出相当复杂的AI行为。
让我们重新看一下例子，增加一个潜在的复杂度，并用一个选择节点来解决问题。
是的，这里我们可以只用少量的新节点，就可以聪明地处理锁住的门。
那么在执行选择节点时发生了什么？
首先，开始执行开门的节点。最可取的行动是简单地打开门，没有什么复杂动作。如果成功，那么选择节点会返回成功，知道这个任务完成了。就没有必要处理其他子节点了。
然而，如果门被哪个家伙锁起来而没有被打开，那么开门节点将返回失败，将失败状态传递给选择节点。这种情况下选择节点将尝试执行第二个子节点，或第二种趋向的行动，即尝试解锁门。
我们在这里创建了另一个序列节点（必须全部完成返回成功），我们先解锁门，然后尝试打开它。
如果解锁门的任何一个步骤失败了（也许是AI没有钥匙，或者缺乏所需的撬锁技巧，或者是他们完成了开锁，但是门被钉死了？）那么它会向选择节点返回失败，然后尝试第三个种行动——把门砸开！
如果角色不够强壮，那么这样或许会失败。在这种情况下，没有更多的行动可选，选择节点会失败，这将导致选择节点的父节点——序列节点失败，放弃通过门的尝试。
为了更进一步，也许上面还有一个选择节点，由于这个序列节点的失败而选择另一个行动方案？
这是我们用顶端的选择节点进行扩展后的树。在左边（常用的一面），我们通过门，如果失败，我们会尝试从窗户进入。事实上，实际的实现可能不会是这样，这是我们在Zomboid项目上的一个简化版，但是它能说明问题。稍后我们会做一个更为通用和可用的实现方案。
简而言之，我们现在有了一个“进入建筑”的行为，你可以依靠这些行为进入有关建筑物，或通知其父节点执行失败。如果没有窗户会怎么样？在这种情况下，最上面的选择节点会执行失败，也许一个父选择节点会告诉AI到另一栋建筑？
经过之前的各种尝试，行为树大幅简化了AI的开发工作，它的一个关键因素是：而无论我在做什么，失败不再是一个致命终结（呃，路径失败，现在怎么办？），但只是自然而然的AI决策过程的一部分。
你可以针对每种可能的情况分别准备故障恢复和备用操作。Project Zomboid的一个例子就是 EnsureItemInInventory 行为。
这个行为传入一个物品类型参数，并使用选择节点从多个操作过程中来确定某个物品是否在NPC的物品栏中，包括用不同物品作为参数执行同一个行为的递归调用。
首先，它将检查物品是否在角色的主要物品栏中。这是理想的情况，因为什么都不用做。如果是，则选择节点成功，因此整个行为成功。EnsureItemInInventory已成功，物品在那里供使用。
如果该物品不在角色的物品栏中，则检查角色携带的袋子或背包。如果找到该物品，那么将物品从袋子中转移到他的顶级物品栏中。满足成功条件则会成功。
如果失败了，则选择节点的第三个分支将确定该项目位于该字符当前所在的建筑物中。如果是，那么角色将会移动到存放物品的容器那里并取出物品。再一次满足条件，成功！
如果这次又失败了，那么NPC还有一计可施。遍历所需物品的制作列表，并且对于每个原料，将遍历它的制作配方，并且依次递归地为每个物品执行EnsureItemInInventory行为。如果全部成功了，那么我们知道一个事实，就是NPC现在拥有了制作物品所需的各种原料。然后，在满足条件返回成功之前，角色将用这些原料制作物品。
如果这次还失败，那么EnsureItemInInventory行为会执行失败，没有其它后备方案，NPC会将该物品添加到所需项目的列表中，以便在拾荒任务期间寻找，并在没有该物品的情况下尽力生存下去。
这么做的结果就是，如果有所需的原料或者可以从房子里取得原料，那么NPC能够在游戏中立即制作出想要的任何物品。
由于行为的递归性质，如果他们自己没有原料，那么他们甚至会从基础的去尝试制造原料。如果必要的话会搜寻建筑物，多次制造原料以制作他们真正需要的物品。
突然间我们有了一个非常复杂和令人印象深刻的AI行为，实际上可以归结为相对简单的节点一个一个堆叠起来的。只要我们需要确认NPC的物品栏是否有某个物品时，那么可以在许多其它行为树上轻松使用EnsureItemInInventory这个行为。
我确信在开发过程的某个时候，我们还会添加其他的后备方案，允许NPC出去专门搜寻他们急需的物品，选择一个最有可能带有该物品的拾取目标。
另一个故障保护机制可能在优先级列表中的级别会更高，就是考虑与所选物品达成相同目标的其它物品。如果有一天我们最终为了支持“临时工具”而编写了代码，然后寻找不太有效的替代方案，那么用石头敲一个钉子，可能会胜过偷偷摸摸穿过城镇进到一家充斥僵尸的五金店。
由于在开发过程中行为树的易于扩展，因此很容易创建一个“干活的”的简单行为，然后通过选择节点添加额外的分支来持续迭代地改进NPC行为，以满足更加可靠的故障保护和后备方案，降低行为失败的可能性。物品制作的后备方案在最后阶段加入，给NPC配备一些行为以帮助他们他们实现目标。
此外，如果仔细确定优先级，这些后备方案虽然本质上是脚本行为，但却给AI角色提供了智能问题解决和自然决策的表现。
随机选择/序列节点
我不会去讨论这些，因为前面的章节已经清楚地介绍过了。随机序列/选择节点正如其名，但处理子节点的实际顺序是随机确定的。如果没有明确的执行顺序，这些可以用在AI行为中增加更多的不可预测性。
装饰节点
取反节点
我们已经讲过这个了。简单地说，它们会反转或否定其子节点的结果。成功变成失败，失败变成成功。它们常用于条件测试。
成功节点
无论子节点返回的什么，总返回成功。当你执行某个预期失败的分支，却又不想放弃执行分支所在的整个序列时，这个节点尤为有用。不需要这种节点的相反方式，因为如果需要向父节点返回失败，取反节点将把一个成功节点变成一个“失败节点”。
重复节点
重复节点会在其子节点返回结果时重新处理子节点。这些通常用于行为树的根基上，使树连续运行。重复节点可以选择在返回结果前多次执行他们的子节点。
重复直到失败
像重复节点一样，这些装饰节点会持续地执行其子节点。直到其子节点返回失败时，此节点才会返回成功。
数据上下文
具体细节取决于行为树的实际实现，所使用的编程语言以及所有其他方面的内容，所以我们将保持这些都是相当抽象和概念化的。
当在AI实体上调用行为树时，也会创建一个数据上下文来存储变量，这些变量由节点解释和修改（使用 C＃Dictionary 或 Java HashMap 中的 string/object pair，可能是C ++ 或者是 string / void * STL映射，因为我很久没用C++了，所以现在可能有更好的办法）
节点能够读取或写入变量，提供上下文数据给后面执行的节点，让行为树作为一个团结的整体有序运行。一旦你开始奋力利用这些，行为树的灵活性和作用范围变得非常令人印象深刻，你的指尖真正的威力变得如此耀眼。当我们重新讲门窗行为时再讨论这部分内容。
定义叶子节点
再次声明，该节点的细节取决于行为树的实际实现。为了提供叶子节点的功能，将特定于游戏的功能添加到行为树中，大多数系统有两个需要实现的函数。
init - 首次调用是节点的父节点执行期间，该节点被其父节点访问时。例如，当一个序列节点的子节点要被处理的时候，这个序列节点就会调用这个函数。直到下一次父节点完成处理并返回结果之后，重新出发父节点时，才会再次调用它。该函数用于初始化节点并启动节点所代表的动作。以前面的行走为例，它会获取参数，并可能启动寻路任务。
process - 在处理节点时，行为树的每次循环都会调用这个函数。如果此函数返回“成功”或“失败”，则其处理将结束，并将结果传递给其父节点。如果返回正在运行，下次循环时它会再次处理，一次又一次，直到它返回成功或失败。在Walk示例中，它会返回正在运行，直到寻路成功或失败。
节点可以具有与它们相关联的属性，可以显式地传递参数，或者控制AI实体的数据上下文内变量的引用。
我不会探讨实现的细节，因为这不仅依赖语言，也依赖于行为树的实现，但行为树实例中的参数和存储的概念是相当通用的。
所以例如，我们可以描述这样一个Walk节点：
Walk (character, destination) -成功：到达目的地 -失败：未到达目的地 -正在运行：在途中
这种情况下，Walk有两个参数，即角色和目标。假设执行AI行为的角色是一个节点的主体，看上去似乎是很自然的事情，因此也不需要作为参数显式地传递。最好不要做这个假设，尽管“走路”是一个相当安全的赌注。特别是在条件节点上，我已经很多次发现自己不得不重新编码节点，以满足测试另一个角色状态或以某种方式与其进行交互。即使你相当确定只有执行该行为的AI会用到它，最好多花点力气，传入要命令的角色参数。
如前所述，位置可以用X，Y，Z坐标手动输入。但更可能的是，位置被另一个节点作为变量存储在上下文中，获取一些游戏对象或者建筑的位置，或者计算NPC附近的安全地点。
堆栈
初见行为树时， 它自然地限制了他们用于角色动作的节点的范围，或对角色或其环境的条件测试。带着这个限制有时很难看出行为树的是多么的强大。
当我突然想到在实现节点的栈操作时，它的实用行才真的变得清晰起来。所以我将以下节点的实现添加到了游戏中：
PushToStack(item, stackVar) PopFromStack(stack, itemVar) IsEmpty(stack)
就是这三个节点。所需要的只是使用init/process函数来创建和修改标准库堆栈对象，只需几行代码，并且它们打开了一大堆可能性。
例如 PushToStack 创建一个原先不存在的新堆栈，并将其存储在传递的变量中，然后把 “物品”对象压到栈上去。
类似地，将一个物品从栈弹出，并将其存储在 itemVar 变量中， 如果堆栈已经为空则会产生问题 ，IsEmpty 检查堆栈是否为空，如果是则返回成功，否则失败。
有了这些节点，我们现在有能力遍历堆栈，如下所示：
使用“重复直到失败”节点，我们可以从堆栈中重复弹出元素并对其进行操作，直到堆栈为空，此时 PopFromStack 会返回失败并退出“重复直到失败”节点。
下面是我经常使用的其他几个重要的实用节点：
SetVariable(varName, object) IsNull(object)
这些可以让我们在复合和装饰节点无法允许我们获取所需信息的情况下，在整个行为树中设置任意变量。
现在假设我们添加了一个名为 GetDoorStackFromBuilding 的节点，你可以向其传入一个建筑对象，它会取得一个该建筑物的外部大门对象的列表，然后新建并将这些对象压入堆栈，并赋值对应的变量。那么我们可以用上面介绍的这些做什么？
哎呦，不错哦。这个更复杂一些。乍看起来，很难发现变化了什么。但是像任何语言一样，最终变得更一目了然，失去了可读性却获得了灵活性。
那这是做什么的呢？一开始可能会让人头大，但是一旦你熟悉了节点的运行方式，以及成功和失败状态是如何贯穿行为树的，它就变得清晰明了。必要的话，如果我的描述不够清楚，我会扩展本节内容，显示整个树的运行过程。
简而言之，这是一可以找到并尝试从每一扇门进入建筑物的行为，如果角色成功地从进入，就会返回成功，如果没有，它将返回失败。
首先，它会去找一个保存了进入建筑的所有门的堆栈。然后它调用“重复直到失败”节点，该节点将继续反复处理其子节点，直到其子节点返回失败。
那个序列子节点，首先从堆栈中弹出一个门，将其存储在门变量中。
如果没有门而堆栈是空的，那么该节点将失败，跳出“重复直到失败”节点并返回成功（“直到失败”节点总是成功），继续其父序列节点，我们这节点上放置了取反的IsNull(usedDoor)。如果 usedDoor 为null（它会为null，因为它没机会设置这个变量），那么返回失败，这会导致整个行为失败。
如果堆栈有一扇门，那么调用另一个序列节点（带有一个取反节点），它会尝试走向门，打开门，然后通过门。
如果NPC没有任何可行的方式通过门（门被锁住，或者NPC太弱而不能打破门），那么选择节点会失败，并返回失败到父节点，这时取反节点将失败转换为成功，这意味着它不会跳出“重复直到失败”节点，而“重复直到失败”节点会重复运行，并重新重新调用其子节点——序列节点，从堆栈弹出下一个门，然后继续让NPC继续尝试。
如果NPC成功通过一个门，那么它会将这扇门设置到usedDoor变量，此时序列节点将返回成功。这个成功状态被反转成为失败状态，所以我们可以跳出“重复直到失败”节点。
在这种情况下，我们会在对usedDoor的非空检查中失败，因为它不为null。但它被反转为成功状态，让整个行为返回了成功。其父节点会知道NPC成功地找到了一扇门并进入了建筑。
如果失败了，可以使用 GetWindowStackFromBuilding 节点重复相同过程来处理从窗子进入的情况。或者通过一些节点的堆栈操作，也许你可以调用GetDoorStackFromBuilding和GetWindowStackFromBuilding，把窗户压入到门堆栈的末尾，然后在同一个“重复直到失败”节点中处理，假设开门、解锁、砸门、关门这些操作是基于门窗的基类，或者在运行时检查NPC在操作的对象。
最后，你可能会注意到我在关门节点上添加了一个装饰节点——成功节点。因为我觉得如果一个NPC砸了门，那么毫无疑问他就不能把它关上。
没有了成功节点，会导致序列节点在设置usedDoor变量之前失败，并移动到下一扇门。一个替代的解决方案是将“关门”设计为始终成功，即使门被砸了也返回成功。但是，我们希望保留判断关门是否成功的能力（例如，在“保卫避难所”行为中使用该节点会认为门无法关闭而导致失败，因为它确实关不上！ ），因此成功节点可以确保在必要的时候忽略失败。