行为树

发表于 | 分类于 |

简介

游戏开发中，怪物的AI系统主要实现方法有状态机，行为树等。本文主要介绍行为树的概念，以及基于behaviac中行为树的源码分析。

行为树是一种由根节点，控制节点以及执行节点组成的树状结构，也可以理解为一种图形化的模型语言。节点之间的连接用父子节点的形式表示。在behaviac中节点从左到右，从上到下依次执行。每个节点执行完成后将自身状态返回给它的父节点，父节点根据自身类型，综合子节点执行结果决定它的后续子节点的执行或者它自身的执行结果。

节点执行结果有三种状态，分别是:

  • RUNNING：代表节点还没有执行完成；
  • SUCCESS：代表节点执行成功；
  • FAILURE：代表节点执行失败；

节点的分类

由上可知，行为树有三种类型的节点，分别是:

  • 根节点：没有父节点，只有一个子节点，它是起始节点。
  • 控制节点：有一个父节点，至少一个子节点。它有两种类型节点：
    • 组合节点，常见的组合节点包括:
      • 序列节点，依次执行所有子节点，如果某个子节点返回失败，序列节点结束后续子节点的执行并返回给它的父节点失败状态。如果所有子节点都返回成功，序列节点返回给它的父节点成功状态。类似编程中&&语法。
      • 选择节点，依次执行所有子节点，如果某个子节点返回成功，序列节点结束后续子节点的执行并返回给它的父节点成功状态。如果所有子节点都返回失败，序列节点返回给它的父节点失败状态。类似编程中||语法。
      • 并行节点，同时执行所有子节点，根据所有子节点的返回结果决定本身结果。
    • 装饰器节点，顾名思义，它对子节点的处理结果进行额外处理，并将处理后的结果返回给它的父节点，常见节点包括:
      • 非节点，对子节点的返回值取反。类似编程中!语法。
      • 循环节点，循环执行子节点指定的次数。类似编程中while语法。
  • 执行节点：有一个父节点，没有子节点。执行节点也可以称为叶节点，只有叶节点需要特别定制。它也包括两类节点:
    • 条件节点，根据条件的比较结果，返回成功或失败。
    • 行为节点，根据动作结果返回成功，失败，或运行。

简单的怪物AI

这张图表示一个简单的怪物AI行为树，绿色节点是根节点，蓝色节点是控制节点，其他的是执行节点。

behaviac源码分析

下文是针对behaviac库中行为树源码的简单分析，并梳理其核心的结构与过程。

基础数据结构

每种节点都是由BehaviorNode(或者它的子类)与BehaviorTask(或者它的子类)两部分组成，它们一一对应，通过BehaviorNode::CreateTask生成BehaviorTask，BehaviorTask::GetNode获得属于它的BehaviorNode。

  • BehaviorNode，代表节点的配置信息，它是各类节点的配置所对应结构体的基类。如，
    • DecoratorNode
    • BehaviorTree
    • Action
  • BehaviorTask，代表节点的运行时结构，它是各类节点运行时结构体的基类。如，
    • CompositeTask
    • BehaviorTreeTask
    • ActionTask

BehaviorTask执行流程

每个节点的执行是通过BehaviorTask::exec实现的，BehaviorTask::exec过程简化如下:

  1. 首先，BehaviorTask::onenter_action，在进入节点之前执行，例如一些前置判断。virtual函数 BehaviorTask::onenter，子类的差异化通过此函数实现。
  2. 其次，virtual函数 BehaviorTask::update_current，节点自身的执行过程，子类的差异化通过它与BehaviorTask::update两个函数实现。
  3. 最后，BehaviorTask::onexit_action，在退出节点之后执行，例如一些后置判断。virtual函数 BehaviorTask::onexit，子类的差异化通过此函数实现。

常见节点分析

从上可知，每种类型的节点都有两部组成，详细的代码不一一罗列，简单说明如下:

  • 行为节点（action.h action.cpp）
    • struct Action - 配置信息
    • struct ActionTask - 运行时信息
  • 序列节点（sequence.h sequence.cpp）
    • struct Sequence - 配置信息
    • struct SequenceTask - 运行时信息
  • 选择节点（selector.h selector.cpp）
    • struct Selector - 配置信息
    • struct SelectorTask - 运行时信息
  • 并行节点（parallor.h parallor.cpp）
    • struct Parallor - 配置信息
    • struct ParallorTask - 运行时信息

自定义类型信息加载

behaviac系统中自定义的类型信息会生成单独的cpp文件，运行时自动加载(通过static变量的初始化)到系统中，过程如下:

  1. AgentMeta::SetBehaviorLoader，被自定义类型信息生产的代码(behaviac_agent_meta.cpp)中调用。
  2. TryStart
  3. BaseStart
  4. AgentMeta::Register
  5. BehaviorLoaderImplement::load

行为树执行流程

首先介绍一下BehaviorTree，BehaviorTreeTask两个结构体，

  • BehaviorTree，它是BehaviorNode的子类，代表一颗完整行为树配置信息，在Workspace::Load中生成。
  • BehaviorTreeTask，它是BehaviorTask的子类，在Workspace::CreateBehaviorTreeTask中生成，对于BehaviorTree运行时结构体。

行为树执行过程就是BehaviorTreeTask执行过程，如下:

  1. Agent::btexec，Agent中包含BehaviorTreeTask
  2. BehaviorTreeTask::exec
  3. BehaviorTask::exec
    • onenter_action
    • update_current
    • onexit_action
  4. BranchTask::SetCurrentTask，它涉及子节点RUNNING状态的处理，详见代码。

以上就是简单的行为树源码分析。这里也说明一下我个人阅读一个代码库方法：

  1. 对于库的作用有一个基本的了解，通过阅读相关文档，在这里，例如:Behavior Tree(wiki))，behaviac-腾讯开源项目
  2. 从入口函数开始浏览整个代码，比如Agent::btexec。
  3. 找到核心点仔细阅读，比如BehaviorNode与BehaviorTask。
  4. 库中不理解的知识点，有针对性的阅读相关代码，例如并行节点。
  5. 多调试。