原文https://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php
联系不到原作,如侵权请告知
简介
尽管网上已经有很多关于行为树的教程和说明了,但是当我在我的项目Project Zomboid中尝试用的时候,我总是一再陷入同一个问题。我读到的大多数教程,要么致力于行为树实现的具体代码,要么执着于十分宽泛而没有上下文的节点流,没有任何实际应用的例子。
尽管它们对于帮我理解行为树的基本原理十分有用,但是我发现自己处于一个尴尬的境地:我知道行为树如何运行,但我却不知道在实际环境下我应该为游戏创建什么节点,或者一个开发完善的行为树应该长什么样子。
我用了巨量时间实验(由于Zomboid是用Java写的,我用了JBT-Java Behavior Trees (http://sourceforge.net/projects/jbt/),所以没能专注于实际代码实现。不过已经有很多教程教这个了,以及在很多广泛使用大的游戏引擎中也有具体实现。
很有可能我这里介绍的某些特定的装饰器节点类型,在JBT中已经有原生支持了,而不仅仅是行为树里的概念,但是我发现这些对于PZ的行为树工作是必不可少的,所以如果你使用的行为树没有支持的话,也可以考虑实现它们。
这个主题我并不是专家,但是在整个PZ NPCs开发过程中我发现我还是相当有发言权的,所以我考虑将一些东西分享出来,如果我早知道这些东西的话,我可能会在最初的尝试时少走弯路,或者至少能开阔眼界让我知道我可以用行为树做什么事。我不打算深入到实现层面,仅仅会给出一些在PZ中用到的抽象例子。
基础
顾名思义,不像有限状态机或者其他的AI编程系统,行为树是一棵“树”,是具有层的节点,它们控制了一个AI实体的决策流程。树上叶子节点才是控制AI实体的真正命令,形成树枝的是各种不同类型的节点,它们控制了在当前情形下AI选择哪条路径最适合。
树可以很深,子节点可以调用子树执行特定功能,这允许开发者开发行为库,链接起来以提供很有用的AI行为。开发过程高度可迭代化,你可以从构造一个基本行为开始,然后创建新的分支来处理不同的目标,分支可以按其匹配程度排序,这允许AI在某个特定行为失败时有兜底策略。相当好用。
数据驱动 vs 代码驱动
二者的差别跟本文没太大关系,不过应该注意,有可能有很多不同的行为树的实现。一个主要的区别是,行为树是定义在代码库外,是以XML或者其他合适的格式,用外部编辑器来维护,还是直接定义在代码内,通过嵌套类实例。
JBT使用了一种奇怪的混合方式,有一个编辑器用来可视化编辑你的行为树,同时有一个用于导出成Java代码的命令行工具,用来在代码中表示行为树。
无论怎么实现,叶子节点是用来执行特定游戏行为和控制你的角色,或者检查角色所处的情况和环境,这些是你自己需要在代码中定义的。用原生语言或者脚本语言如Lua,Python都无碍。你可以在你的树里调整这些节点,提供复杂的行为。这些节点可以如此地具有表现力,在树中操作数据时甚至更像一个标准库,而不仅仅是一些角色命令,这让我尤为兴奋。
树遍历
与代码库中的一个方法不同,行为树一个核心的特点是特定的节点或分支可能会花许多游戏时间来完成。在行为树的基本实现中,每个单帧时系统会从root开始向下遍历整个树,检查哪个节点是活跃的,然后再次检查路径上的节点,直到到达当前活跃的节点并再次执行(tick)它。
这个方法并不高效,特别是当随着开发进行,行为树越来越深时。我必须要说,你实现任何行为树的时候都应该将当前处理的节点存储起来,以便在行为树引擎内部直接访问激活它们,而不是每次都去遍历。幸好JBT已经这么做了。
流
一棵行为树由几种不同类型的节点构成,不过有些核心的功能是行为树中所有节点共有的。那就是它们可以返回三种状态之一。(依赖行为树的实现,可能有不止三种状态,但是我没有实际用过,而且这也不适用于这个主题的介绍)三种共有的状态是:
- Success
- Failure
- Running
正如其名,前两个状态是告知父亲节点,本节点的操作成功或失败了。第三个状态表示还不知道是成功还是失败,节点还在运行。下次树被执行的时候节点会被再次执行,到时它还会有这三种状态返回。
这个功能是行为树强大能力的关键,因为它允许一个节点的处理过程横跨游戏的多个执行周期。例如,一个Walk节点可能会在尝试计算路径的时候或者让角色走到特定地点的时候,返回Running状态。如果寻路失败,或者在行走时遇到什么复杂事情阻止了角色走到目标地点,则节点可以返回failure给父节点。任何时候,当角色的位置等于目标位置时,它可以返回Success表示Walk命令已经执行成功了。
这意味着这个节点有succes和failure两种截然不同的定义,任何使用这个节点的树都可以从它得到确定的结果。这些状态定义了树的流,提供一个事件序列和不同的执行路径,可以保证AI的行为如预期一样。
在这个共有的机制下,有三种典型的行为树节点:
- Composite
- Decorator
- Leaf
Composite 组合
组合节点是有一个或多个孩子的节点。它们会处理这些孩子节点中的一个或几个,顺序由这个节点决定,在某个阶段处理完毕后会传递success或failure的结果给父亲节点,通常这个结果由孩子节点的success或failure决定。在处理期间会持续返回Running状态。
最常见的组合节点是Sequence,它有序运行每个孩子节点,并在任意节点failure时返回failure,在所有节点都success时返回success。
Decorator 装饰器
装饰器节点跟组合节点一样也可以有一个孩子节点。不同于组合节点的是,它们只能有一个孩子。装饰器的功能可以是转换从孩子节点收到的结果,终止孩子节点,或者重复执行孩子节点,这取决于装饰器的类型。
常见的装饰器节点的例子是Inverter,它会简单地反转孩子的结果。孩子返回failure,它返回success,孩子返回success,它返回failure。
Leaf 叶子
这是最底层的节点类型了,它们不能有孩子。
叶子是最强大啊的节点类型,因为它们会用来实现特定的游戏或角色的测试或行为,这让你的树能做些有用的事。
例子比如上面提到的Walk。一个Walk叶子节点可以让一个角色走到地图上特定的点,并根据结果返回success或failure。
由于你可以定义你自己的叶子节点(通常代码量很少),它们放在组合和装饰器之上,可以非常有表达力,允许你创造相当强大的行为树,用来执行复杂的有优先权的智能行为。
用代码来类比的话,可以把组合和装饰器看作函数,if语句和while循环,以及其他语言中的定义代码流的结构,而叶子结点就可以看作特定的游戏的函数调用,它们用来为你的AI角色服务或检查AI角色的状态和情况。
这些节点可以定义参数。例如Walk节点可以有一个坐标让角色走过去。
这些参数可以从处理这棵树的AI角色的上下文中获取。比如,一个要走到的位置可以从一个'GetSafeLocation'的节点获取,存到变量里,然后一个'Walk'节点就能使用这个变量来决定目的地。全程使用了一个在节点间共享的上下文来存储和改变任意持久化数据,这让行为树异常强大。
另一种必不可少的叶子节点类型是调用其他行为树的类型。它可以将现有的树的数据上下文传递给被调用的树。
这些是关键,它们让你可以高度模块化你的树来创建可以在无数地方重用的行为树,可能会在上下文中使用一个特别的变量名来操作他们。例如,一个'Break into Building'的行为可能会期望一个'targetBuilding'的变量来操作,那么父树可以在上下文中设置这个变量,然后用一个子树节点来调用子树。
Composite Nodes
现在我们来看看在行为树中最常见的几种组合节点。还有一些其他的,但我们只会顾及最基本的类型,你写复杂的行为树时总会遇到他们。
Sequences 序列
最简单的组合节点,他们的名字代表了一切。一个序列会依次访问他的孩子,从第一个开始,成功了就会调用第二个,直到最后。如果任何节点失败了,就会立即返回失败给父节点。最后一个节点成功后,序列会返回成功。
需要重申的是,行为树中的节点类型有非常广泛的应用。序列最明显的用法就是定义一系列必须要全部完成的任务,任何任务的失败都意味着后续任务不再需要。例如:
image.png这个序列,会让指定的角色走过一道门,关闭它。事实上,在生产环境中这些节点可能更抽象,还会用到参数。Walk(location), Open(openable), Walk(location), Close(openable)
处理顺序是这样的:
Sequence -> Walk to Door (success) -> Sequence (running) -> Open Door (success) -> Sequence (running) -> Walk through Door (success) -> Sequence (running) -> Close Door (success) -> Sequence (success) -> Sequence返回成功给父亲
如果角色无法走到门——可能路被堵了——则后面就不需要开门或者走过门了。此时这个序列会返回失败,父亲就可以优雅地处理这个失败。
序列天然就是给一系列角色行为使用的,而且由于AI行为树倾向于暗示这是序列的唯一用法,这使有些事情不那么明显:让角色执行一系列的“事情”,有好几种不同的方法。例如:
image.png在以上的例子中,我们有一系列的检测而不是行动。子节点检测角色是否饥饿,是否有携带食物,是否处于安全位置,只有所有这些都返回成功,角色才可以吃东西。使用这样的序列可以让你在执行某个行为之前检查一个或多个条件。就好像是if语句,或者电路中的与门(AND gate)。因为所有子节点都需要成功,而且这些子节点可以是任意的组合节点、装饰器、叶子节点的组合,所以这就能实现相当厉害的条件检查。
考虑上文提到的Inverter:
image.png功能上跟前一个例子相同,这里我展示了如何用Inverter来反转所有的检测,你得到了一个非门(NOT gate)。这意味着你可以大量减少检查条件所需要的节点数。
Selector 选择器(条件节点)
如果序列是阴,选择器就是阳。序列是AND,要求所有孩子都返回success,选择器则是如果任意孩子返回success就返回success,不再处理剩余的孩子。它会从第一个孩子开始,失败则处理下一个,直到有一个成功则立即返回success。如果所有孩子都失败了则返回失败。意思是选择器就是或门(OR gate),可以作为条件语句检查多个条件中是否有为真的。
他们真正的能力在于可以表达多种不同系列的行动,以优先级最高到最低的顺序,如果在任意行动成功时则返回成功。这个影响很大,用选择器你可以很快地开发出复杂的AI行为。
让我们再来看一下前面穿门的例子,加点复杂度,用选择器解决它。
image.png没错,我们现在可以解决锁着的门了,只不过用了一丢丢新节点。
那么在处理这个选择器的时候发生了什么呢?
首先,它会处理'Open Door'节点。这个是最高优先级的行动。如果成功了那选择器就成功了,不用做别的。
如果门没有打开,因为某人把门锁上了,那么第一个节点就会失败,传递failure给选择器。这时候选择器就会尝试第二个节点,也是第二优先的行动,尝试开锁。
这里我们创建了另一个序列(必须完全成功才算成功),这个序列里我们首先开锁,然后尝试开门。
如果开锁的任意一步失败了(可能AI没有钥匙,或者需要开锁技能,或者虽然打开锁了但开门时发现门被钉死了)就会返回failure给选择器,选择器尝试第三个行动,砸烂门。
如果角色不够强壮,这也可能失败。这种情况下没有更多行动可以采取了,选择器会返回失败,导致选择器的父亲序列失败,于是放弃后续尝试穿门的操作。
更进一步,可能在这个穿门序列之上还有个选择器,当它失败时还可以采取另一个行动。
image.png我们把树顶部扩展出一个选择器。在左边(更高优先级)我们进入门,如果失败了我们尝试进入窗户。事实上真正的实现不是长这个样子,这只是我们在PZ中的实现的简化版,不过这足够演示重点了。后面我们会讲到更泛化和好用的实现。
简言之,我们已经有了'Enter Building'的行为,你可以用它来进入建筑,或者通知它的父亲你进入失败了。可能没有窗户?这种情况下顶部的选择器会失败,可能其上还有个选择器告诉AI去寻找其他的建筑?
行为树中一个大大简化我AI开发工作量的关键因素是, failure并不是我要做的事情的一个严格的终止(是,寻路失败了,这时应该怎么办呢?),而是决策过程的一个自然且在预期中的部分,它天然适配AI系统的范式。
你可以为每种可能的情形放置防故障措施和可选行动。PZ中的例子就是'EnsureItemInInventory'行为。
这个行为考虑某个物品栏道具类型,使用选择器从数种行为中进行决断,保证某个道具在NPC的库存中,包括使用不同的道具参数递归调用这同一个行为。
首先我会检查道具是不是已经在角色的主要顶层库存中了。这是最理想的状况,什么都不用做。如果是,选择器返回成功,道具已经在那里备用了。
如果道具不在角色的库存中,检查角色携带的其他包或背包。如果找到了道具,则把道具从包里放到顶层库存中。这就成功了。
如果这一步失败,第三个分支是在这个角色当前居住的建筑中寻找。如果它在,角色会到存放它的地方把它拿出来。然后就成功了。
如果这一步失败,另一个分支是列举可以制造出这个道具的所有配方,然后依次检查每个配方的所有原料,这里会递归调用'EnsureItemInInventory'行为。如果每个原料都成功了,那我们就知道NPC携带了制作这个道具的所有必需的原料。然后角色会制作出这个道具,然后返回success。
如果这一步失败,则整个'EnsureItemInInventory'行为失败,没有更多的兜底了,NPC会将这个道具加入清单,在清任务的时候顺便查找。
结果是,NPC突然就可以自己制作游戏中需要的道具了,只要他们有必需的原料或者这些原料能在建筑中获取。
由于行为的递归特性,如果他们没有那些原料,他们会尝试用更基础的原料去制作那些原料,必要时搜寻建筑物,制作出多个不同阶段的道具来,以最终制作出真正所需要的道具。
突然间,我们就有一个相当复杂而且令人印象深刻的AI行为了,它拆开了看只是简单的节点一层层堆叠起来。这个'EnsureItemInInventory'行为就可以自由地使用在其他树中,只要我们有必要让NPC保证他们的库存中有某个道具。
某种程度上我确信在开发过程中我们会不断地用其他兜底来扩展它,让NPC可以特地出去搜寻他们特别想要的某个道具,选择最有可能存在这个道具的地方作为目标。
(未完)
网友评论