1 个不稳定版本

0.3.2	2023年11月18日

#10 in #behavior-tree

MIT 许可证

170KB
3.5K SLoC

behavior-tree-lite (Rust 包)

这是一个用于最小化行为树实现的实验性 Rust 包。

概述

这是 Rust 中行为树的一个实现，灵感来自 BehaviorTreeCPP。

行为树是有限状态机的扩展，使得描述过渡行为变得更加容易。关于该概念的详细介绍，请参阅 BehaviorTreeCPP 的文档。

有关更完整的历史信息，请参阅此 README.md 文件的底部。

外观

首先，您使用数据结构定义状态。

struct Arm {
    name: String,
}

struct Body {
    left_arm: Arm,
    right_arm: Arm,
}

let body = Body {
    left_arm: Arm {
        name: "leftArm".to_string(),
    },
    right_arm: Arm {
        name: "rightArm".to_string(),
    },
};

然后，将数据注册到上下文中。

let mut ctx = Context::default();
ctx.set("body", body);

然后，定义一个行为树。请注意，add_child 方法将黑板变量映射作为第二个参数。

let mut root = BehaviorNodeContainer::new_node(SequenceNode::default());
root.add_child(BehaviorNodeContainer::new_node(PrintBodyNode));

let mut print_arms = BehaviorNodeContainer::new_node(SequenceNode::default());
print_arms.add_child(BehaviorNodeContainer::new(Box::new(PrintArmNode), hash_map!("arm" => "left_arm")));
print_arms.add_child(BehaviorNodeContainer::new(Box::new(PrintArmNode), hash_map!("arm" => "right_arm")));

root.add_child(print_arms);

并调用 tick()。

let result = root.tick(&mut |_| None, &mut ctx);

tick 的第一个参数具有奇怪的值 &mut ||_:. 它是行为节点与环境通信的回调。您可以为 BehaviorCallback 提供一个闭包来处理来自行为节点的消息。该闭包接受一个 &mut ||std::any::Any<dyn std::any::Any> 参数，并返回一个 Box<dyn std::any::Any>，允许用户传递或返回任何类型，但用户需要使用 downcast_ref 检查类型，如下所示。

tree.tick(
    &mut |v: &dyn std::any::Any| {
        res.push(*v.downcast_ref::<bool>().unwrap());
        None
    },
    &mut Context::default(),
)

采用这种设计是因为没有其他更好的方法可以在行为节点和环境（其生命周期不是 'static'）之间进行通信。

与全局静态变量通信很容易，但用户通常希望使用有限生命周期的行为树，比如游戏中的敌人AI。因为直到你实际使用行为树之前，你不能命名其生命周期，所以你不能定义一个可以发送/接收任意类型数据的类型，其生命周期短于 'static。 std::any::Any 无法绕过这个限制，因为它也受 'static 生命周期的限制，所以当你将自定义负载放入其中后，你只能放入除 &'static 之外的其他引用。

使用闭包，我们不需要命名生命周期，并且它将比闭包体的持续时间更长，因此我们可以传递引用。

当然，你还可以使用黑板变量，但它们也有同样的生命周期限制；你不能通过黑板传递引用。回调是与环境通信的更直接（并且不需要端口名称间接）的方式。

如何定义自己的节点

库的核心是 BehaviorNode trait。你可以实现这个trait到你的自定义类型，以创建你自己的行为节点。

它与 BehaviorTreeCPP 非常相似。例如，可以定义一个打印臂名称的节点，如下所示。

struct PrintArmNode;

impl BehaviorNode for PrintArmNode {
    fn tick(&mut self, _arg: BehaviorCallback, ctx: &mut Context) -> BehaviorResult {
        println!("Arm {:?}", ctx);

        if let Some(arm) = ctx.get::<Arm>("arm") {
            println!("Got {}", arm.name);
        }
        BehaviorResult::Success
    }
}

为了传递变量，你需要将变量设置到黑板。这是通过 Context::set 方法完成的。

struct PrintBodyNode;

impl BehaviorNode for PrintBodyNode {
    fn tick(&mut self, _arg: BehaviorCallback, ctx: &mut Context) -> BehaviorResult {
        if let Some(body) = ctx.get::<Body>("body") {
            let left_arm = body.left_arm.clone();
            let right_arm = body.right_arm.clone();
            println!("Got Body: {:?}", body);
            ctx.set("left_arm", left_arm);
            ctx.set("right_arm", right_arm);
            BehaviorResult::Success
        } else {
            BehaviorResult::Fail
        }
    }
}

通过缓存符号优化端口访问

如果你大量使用端口，你可以尝试通过使用符号最小化比较和查找端口名称字符串的成本。符号是保证如果它们指向相同的字符串，则比较相等的指针。因此，你可以简单地比较地址来检查它们的相等性。

你可以使用 Lazy<Symbol> 在符号上使用类似于以下方式的首次使用缓存模式。 Lazy 是从 once_cell 中导出的类型。

use ::behavior_tree_lite::{
    BehaviorNode, BehaviorResult, BehaviorCallback, Symbol, Lazy, Context
};

struct PrintBodyNode;

impl BehaviorNode for PrintBodyNode {
    fn tick(&mut self, _: BehaviorCallback, ctx: &mut Context) -> BehaviorResult {
        static BODY_SYM: Lazy<Symbol> = Lazy::new(|| "body".into());
        static LEFT_ARM_SYM: Lazy<Symbol> = Lazy::new(|| "left_arm".into());
        static RIGHT_ARM_SYM: Lazy<Symbol> = Lazy::new(|| "right_arm".into());

        if let Some(body) = ctx.get::<Body>(*BODY_SYM) {
            // ...
            BehaviorResult::Success
        } else {
            BehaviorResult::Fail
        }
    }
}

提供的端口

你可以通过定义 provided_ports 方法声明节点中会使用哪些端口。这是可选的，并且仅在指定了后面解释的 load 函数中的 check_ports 参数时强制执行。然而，声明 provided_ports 将有助于静态检查代码和源文件一致性，因此通常被鼓励。

use ::behavior_tree_lite::{
    BehaviorNode, BehaviorCallback, BehaviorResult, Context, Symbol, Lazy, PortSpec
};

struct PrintBodyNode;

impl BehaviorNode for PrintBodyNode {
    fn provided_ports(&self) -> Vec<PortSpec> {
        vec![PortSpec::new_in("body"), PortSpec::new_out("left_arm"), PortSpec::new_out("right_arm")]
    }

    fn tick(&mut self, _: BehaviorCallback, ctx: &mut Context) -> BehaviorResult {
        // ...
    }
}

请参阅示例代码以获取完整代码。

从 yaml 文件中加载树结构（已弃用）

已弃用，改为自定义配置文件格式。它在我们自定义格式上没有太多优势，除了它可以用任何 yaml 解析库（不仅限于 Rust）解析。然而，解析只是动态配置行为树加载过程中的很小一部分。还有端口映射验证和指定输入/输出，这些在 yaml 中并不容易。我们的自定义格式在加载时验证和错误处理方面具有更大的灵活性。

你可以在 yaml 文件中定义树结构，并在运行时进行配置。yaml 文件非常适合编写人类可读/可写的配置文件。它也看起来与实际的树结构相似。

behavior_tree:
  type: Sequence
  children:
  - type: PrintBodyNode
  - type: Sequence
    children:
    - type: PrintArmNode
      ports:
        arm: left_arm
    - type: PrintArmNode
      ports:
        arm: right_arm

为了从 yaml 文件加载树，你需要将节点类型注册到注册表中。

let mut registry = Registry::default();
registry.register("PrintArmNode", boxify(|| PrintArmNode));
registry.register("PrintBodyNode", boxify(|| PrintBodyNode));

一些节点类型默认注册，例如 SequenceNode 和 FallbackNode。

自定义配置文件格式

我们有一种特定的文件格式来描述我们自己的行为树结构。这种文件格式的常用文件扩展名是 .btc（行为树配置）。请参阅 VSCode 扩展以获取语法高亮。

使用此格式，之前用 YAML 展示的相同树可以更简洁地写成如下。

tree main = Sequence {
  PrintBodyNode
  Sequence {
    PrintArmNode (arm <- left_arm)
    PrintArmNode (arm <- right_arm)
  }
}

可以使用 parse_file 函数将其转换为 AST（抽象语法树）。AST（抽象语法树）是行为树的中介格式，您可以从它实例化实际的行为树，次数不限。请注意，AST 借用了参数字符串的生命周期，因此在 AST 之前不能释放源字符串。

let (_, tree_source) = parse_file(source_string)?;

随后可实例化为树。第二个参数 registry 与 YAML 解析器相同。第三个参数 check_ports 将在加载期间切换端口方向的检查。如果您的 BehaviorNode::provided_ports 和源文件的箭头方向（<-、-> 或 <->）不一致，将变成错误。

let tree = load(&tree_source, &registry, check_ports)?;

行注释

您可以在以哈希（#）开头的行中放置注释。

# This is a comment at the top level.

tree main = Sequence { # This is a comment after opening brace.
           # This is a comment in a whole line.
    var a  # This is a comment after a variable declaration.
    Yes    # This is a comment after a node.
}          # This is a comment after a closing brace.

节点定义

节点可以指定如下。它以 Rust 代码中定义的节点名开始。之后，它可以在括号中包含一个可选的输入/输出端口列表。

PrintString (input <- "Hello, world!")

端口中的箭头方向指定输入、输出或双向端口类型。箭头的左边是节点中定义的端口名。右边是黑板变量名或文字。

a <- b      input port
a -> b      output port
a <-> b     inout port

您可以将双引号包围的字符串文字指定给输入端口，但将文字指定给输出或双向节点是错误的。文字的类型始终是字符串，因此如果您想使用数字，您可能希望使用 Context::get_parse() 方法，该方法将自动尝试从字符串解析，如果类型不是所需的类型。

a <- "Hi!"
a -> "Error!"
a <-> "Error too!"

从输出端口尝试读取或写入输入端口是错误的，但双向端口可以同时进行。

子节点

节点可以具有大括号中的子节点列表。

Sequence {
    PrintString (input <- "First")
    PrintString (input <- "Second")
}

甚至可以同时包含端口和子节点。

Repeat (n <- "100") {
    PrintString (input <- "Spam")
}

子树

定义子树并将您的巨大树组织成模块化结构非常容易。

tree main = Sequence {
    CanICallSubTree
    SubTree
}

tree SubTree = Sequence {
    PrintString (input <- "Hi there!")
}

子树有自己的黑板变量命名空间。这将防止黑板变成一个庞大的全局变量表。

如果您需要在父树和子树之间通信黑板变量，您可以在子树名称后放置括号和逗号分隔的列表来指定子树的端口定义。

端口“参数”可以由 in、out 或 inout 前缀。它将指示数据流的方向。

语法故意使其类似于函数定义，因为它确实如此。

tree main = Sequence {
    SubTree (input <- "42", output -> subtreeResult)
    PrintString (input <- subtreeResult)
}

tree SubTree(in input, out output) = Sequence {
    Calculate (input <- input, result -> output)
}

条件语法

类似于编程语言，该格式支持条件语法。

tree main = Sequence {
    if (ConditionNode) {
        Yes
    }
}

如果 ConditionNode 返回 Success，则内部大括号被标记为序列，否则跳过这些节点。

这本身不是一个 if 语句，因为行为树没有语句的概念。它只是一个行为节点，具有特殊的语法，以便于编辑和理解。

上面的代码可以简化为以下形式

tree main = Sequence {
    if {
        ConditionNode
        Sequence {
            Yes
        }
    }
}

正如您所预期的，您可以放置 else 子句。

tree main = Sequence {
    if (ConditionNode) {
        Yes
    } else {
        No
    }
}

if 是一个内置节点类型，可以接受 2 或 3 个子节点。第一个子节点是条件，第二个是 then 子句，可选的第三个子节点是 else 子句。then 和 else 子句隐式地封装在一个 Sequence 中。

语法还支持在条件节点前面使用否定运算符（!）。下面的代码如下

tree main = Sequence {
    if (!ConditionNode) {
        Yes
    }
}

等同于以下代码

tree main = Sequence {
    if (ConditionNode) {
    } else {
        Yes
    }
}

您可以在条件节点前面放置逻辑运算符（&& 和 ||），就像编程语言中的条件表达式一样。&& 是一个序列节点的简写，而 || 是一个回退节点。

tree main = Sequence {
    if (!a || b && c) {}
}

实际上，子节点隐式地是一个逻辑表达式，因此您可以像这样编写

tree main = Sequence {
    !a || b && c
}

括号可以用来分组运算符。

tree main = Sequence {
    (!a || b) && c
}

没有 else 子句的 if 节点在语义上与以下类似，但序列或回退节点不能很容易地表示 else 子句。

tree main = Sequence {
    Sequence {
        ConditionNode
        Sequence {
            Yes
        }
    }
}

黑板变量声明

您可以可选地声明和初始化一个黑板变量。它可以作为节点名称使用，其值作为布尔值进行评估。因此，您可以将变量放入 if 条件中。

tree main = Sequence {
    var flag = true
    if (flag) {
        Yes
    }
}

目前，只有 true 或 false 可以用作初始化器（= 的右侧）。

具有初始化的变量声明将简化为 SetBool 节点。变量名称的引用将简化为 IsTrue 节点。

tree main = Sequence {
    SetBool (value <- "true", output -> flag)
    if (IsTrue (input <- flag)) {
        Yes
    }
}

但是，为了将其用作变量引用，必须声明变量名称。例如，下面的代码将因为 MissingNode 而产生 load 错误，即使变量已通过 SetBool 设置。

tree main = Sequence {
    SetBool (value <- "true", output -> flag)
    if (flag) {
        Yes
    }
}

这种设计是朝着静态检查源代码迈出的一步。

变量赋值

可以使用此语法给变量赋值

value = true

目前，只有 true 或 false 可以用作初始化器。

这是一个类似于以下的语法糖，但没有变量声明。

SetBool (value <- "true", output -> value)

语法规范

这里是一个伪 EBNF 语法表示。

请注意，这个规范绝对不是准确的 EBNF。该语法由递归下降解析器和解析器组合器定义，它消除了歧义，但这个 EBNF 可能存在歧义。

tree = "tree" tree-name [ "(" tree-port-list ")" ] "=" node

tree-port-list = port-def | tree-port-list "," port-def

port-def = ( "in" | "out" | "inout" ) tree-port-name

tree-port-name = identifier

node = if-syntax | conditional | var-def-syntax | var-assign

if-syntax = "if" "(" conditional ")"

conditional-factor = "!" conditional-factor | node-syntax

conditional-and =  conditional-factor | conditional "&&" conditional-factor

conditional =  conditional-and | conditional "||" conditional-and

node-syntax = node-name [ "(" port-list ")" ] [ "{" node* "}" ]

port-list = port [ "," port-list ]

port = node-port-name ("<-" | "->" | "<->") blackboard-port-name

node-port-name = identifier

blackboard-port-name = identifier

var-def-syntax = "var" identifier "=" initializer

var-assign = identifier "=" initializer

initializer = "true" | "false"

待办事项

定义构造函数（宏？）的更简单的方法
完整的控制节点集
- 响应式节点
- 星节点
- 装饰节点
性能友好的黑板键
定义行为树结构的 DSL
- 类似于编程语言的流程控制语法
行为树定义文件的静态类型检查

历史注释

这是 tiny-behavior-tree 的一个姐妹项目，而 tiny-behavior-tree 又受到了 BehaviorTreeCPP 的启发。

虽然 tiny-behavior-tree 旨在实现更多创新的设计和实验性功能，但本项目旨在实现更传统的行为树实现。目标是使这个库足够轻量，以便在 WebAssembly 中使用。

与 tiny-behavior-tree 的区别

tiny-behavior-tree 的主要前提是通过函数参数传递数据。这对于制作快速小巧的二进制文件非常有利，但它会在树中出现混合节点类型的问题。

它需要丑陋的样板代码或宏来在不同节点参数类型之间转换类型，并且还有一个“PeelNode”的概念，这在传统的行为树设计中可能是不必要的。

此外，统一的数据类型使得实现能够实时更改行为树的配置文件解析器变得容易得多。

性能考虑

关于行为树在性能方面的一般问题之一是节点与黑板变量进行通信，本质上是一个键值存储。这并不特别糟糕，但如果你在黑板上读取/写入很多变量（在大型行为树中很容易发生），你每次都会付出构造字符串和查找 HashMap 的代价。

tiny-behavior-tree 的一个目标是通过传递函数调用参数的变量来解决此问题。如果你已经知道变量的地址，为什么还要付出查找 HashMap 的代价呢？

此外，黑板可扩展性不强，因为它本质上是一个巨大的全局变量表。尽管在子树中有子黑板，但没有适当的调试工具，很难跟踪类似于脚本语言的堆栈帧。

我可能会尝试使用非字符串键来提高效率，但需要在统一类型的节点中动态处理变量的性质。

依赖项

~3MB
~59K SLoC