Crate behavior_tree_lite
source ·Expand description
behavior-tree-lite (Rust crate)
An experimental Rust crate for minimal behavior tree implementation
Overview
This is an implementation of behavior tree in Rust, inspired by BehaviorTreeCPP.
A behavior tree is an extension to finite state machines that makes describing transitional behavior easier. See BehaviorTreeCPP’s documentation for the thorough introduction to the idea.
See the historical notes at the bottom of this README.md for more full history.
How it looks like
First, you define the state with a data structure.
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(),
},
};
Then register the data to the context.
let mut ctx = Context::default();
ctx.set("body", body);
Then, you define a behavior tree.
Note that add_child
method takes a mapping of blackboard variables as the second argument.
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);
and call tick()
.
let result = root.tick(&mut |_| None, &mut ctx);
The first argument to the tick
has weird value &mut |_| None
.
It is a callback for the behavior nodes to communicate with the environment.
You could supply a closure to handle messages from the behavior nodes.
The closure, aliased as BehaviorCallback
, takes a &dyn std::any::Any
and returns a Box<dyn std::any::Any>
,
which allows the user to pass or return any type, but in exchange, the user needs to
check the type with downcast_ref
in order to use it like below.
tree.tick(
&mut |v: &dyn std::any::Any| {
println!("{}", *v.downcast_ref::<bool>().unwrap());
None
},
&mut Context::default(),
);
This design was adopted because there is no other good ways to communicate between behavior nodes and the envrionment whose lifetime is not ’static.
It is easy to communicate with global static variables, but users often want
to use behavior tree with limited lifetimes, like enemies’ AI in a game.
Because you can’t name a lifetime until you actually use the behavior tree,
you can’t define a type that can send/receive data with arbitrary type having
lifetime shorter than ’static.
std::any::Any
can’t circumvent the limitation, because it is also bounded by ’static lifetime,
so as soon as you put your custom payload into it, you can’t put any references other than &'static
.
With a closure, we don’t have to name the lifetime and it will clearly outlive the duration of the closure body, so we can pass references around.
Of course, you can also use blackboard variables, but they have the same limitation of lifetimes; you can’t pass a reference through blackboard. A callback is much more direct (and doesn’t require indirection of port names) way to communicate with the environment.
How to define your own node
The core of the library is the BehaviorNode
trait.
You can implement the trait to your own type to make a behavior node of your own.
It is very similar to BehaviorTreeCPP. For example a node to print the name of the arm can be defined like below.
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
}
}
In order to pass the variables, you need to set the variables to the blackboard.
This is done by Context::set
method.
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
}
}
}
Optimizing port access by caching symbols
If you use ports a lot, you can try to minimize the cost of comparing and finding the port names as strings by using symbols. Symbols are pointers that are guaranteed to compare equal if they point to the same string. So you can simply compare the address to check the equality of them.
You can use Lazy<Symbol>
to use cache-on-first-use pattern on the symbol like below.
Lazy
is re-exported type from 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
You can declare what ports you would use in a node by defining provided_ports
method.
This is optional, and only enforced if you specify check_ports
argument in the load
function explained later.
However, declaring provided_ports will help statically checking the code and source file consistency, so is generally encouraged.
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 {
// ...
BehaviorResult::Success
}
}
See example code for the full code.
Loading the tree structure from a yaml file
Deprecated in favor of the custom config file format. It doesn’t have much advantage over our custom format, except that it can be parsed by any yaml parser library (not limited to Rust). However, parsing is only a small part of the whole process of loading dynamically configured behavior tree. There are validation of port mapping and specifying input/output, which is not any easier with yaml. Our custom format has much more flexibility in load-time validation and error handling.
You can define the tree structure in a yaml file and configure it on runtime. Yaml file is very good for writing human readable/writable configuration file. It also looks similar to the actual tree structure.
behavior_tree:
type: Sequence
children:
- type: PrintBodyNode
- type: Sequence
children:
- type: PrintArmNode
ports:
arm: left_arm
- type: PrintArmNode
ports:
arm: right_arm
In order to load a tree from a yaml file, you need to register the node types to the registry.
let mut registry = Registry::default();
registry.register("PrintArmNode", boxify(|| PrintArmNode));
registry.register("PrintBodyNode", boxify(|| PrintBodyNode));
Some node types are registered by default, e.g. SequenceNode
and FallbackNode
.
The custom config file format
We have specific file format for describing behavior tree structure of our own. With this format, the same tree shown as YAML earlier can be written even more concisely like below.
tree main = Sequence {
PrintBodyNode
Sequence {
PrintArmNode (arm <- left_arm)
PrintArmNode (arm <- right_arm)
}
}
It can be converted to an AST with parse_file
function.
The AST (Abstract Syntax Tree) is a intermediate format of behavior tree,
from which you can instantiate actual behavior trees as many times as you want.
Note that the AST borrows lifetime of the argument string, so you cannot free the
source string before the AST.
let (_, tree_source) = parse_file(source_string)?;
and subsequently be instantiated to a tree.
The second argument registry
is the same as yaml parser.
The third argument check_ports
will switch port direction checking during loading.
If your BehaviorNode::provided_ports
and the source file’s direction arrow (<-
, ->
or <->
) disagree, it will become an error.
let tree = load(&tree_source, ®istry, check_ports)?;
Line comments
You can put a line comment starting with a hash (#
).
# 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.
Node definition
A node can be specified like below. It starts with a node name defined in Rust code. After that, it can take an optional list of input/output ports in parentheses.
PrintString (input <- "Hello, world!")
The direction of the arrow in the ports specify input, output or inout port types. The left hand side of the arrow is the port name defined in the node. The right hand side is the blackboard variable name or a literal.
a <- b input port
a -> b output port
a <-> b inout port
You can specify a literal string, surrounded by double quotes, to an input port,
but specifying a literal to output or inout node is an error.
The type of the literal is always a string, so if you want a number,
you may want to use Context::get_parse()
method, which will automatically try
to parse from a string, if the type was not desired one.
a <- "Hi!"
a -> "Error!"
a <-> "Error too!"
It is an error to try to read from an output port or write to an input port, but inout port can do both.
Child nodes
A node can have a list of child nodes in braces.
Sequence {
PrintString (input <- "First")
PrintString (input <- "Second")
}
Or even both ports and children.
Repeat (n <- "100") {
PrintString (input <- "Spam")
}
Subtrees
It is very easy to define subtrees and organize your huge tree into modular structure.
tree main = Sequence {
CanICallSubTree
SubTree
}
tree SubTree = Sequence {
PrintString (input <- "Hi there!")
}
A subtree has its own namespace of blackboard variables. It will keep the blackboard from being a huge table of global variables.
If you need blackboard variables to communicate between the parent tree and the subtree, you can put parentheses and a comma-separated list after subtree name to specify the port definition of a subtree.
A port “parameter” can be prefixed by either in
, out
or inout
.
It will indicate the direction of data flow.
The syntax is intentionally made similar to a function definition, because it really is.
tree main = Sequence {
SubTree (input <- "42", output -> subtreeResult)
PrintString (input <- subtreeResult)
}
tree SubTree(in input, out output) = Sequence {
Calculate (input <- input, result -> output)
}
Conditional syntax
Like a programming language, the format supports conditional syntax.
tree main = Sequence {
if (ConditionNode) {
Yes
}
}
If the ConditionNode
returns Success
, the inner braces are ticked
as a Sequence, otherwise it skips the nodes.
It is not an if
statement per se, because behavior tree does not have
the concept of a statement.
It is internally just a behavior node, having a special syntax for the
ease of editing and understanding.
The code above desugars into this:
tree main = Sequence {
if {
ConditionNode
Sequence {
Yes
}
}
}
As you may expect, you can put else
clause.
tree main = Sequence {
if (ConditionNode) {
Yes
} else {
No
}
}
if
is a built-in node type, which can take 2 or 3 child nodes.
The first child is the condition, the second is the then
clause, and
the optional third child is the else
clause.
then
and else
clause are implicitly wrapped in a Sequence
.
The syntax also supports negation operator (!
) in front of the condition node.
This code below is
tree main = Sequence {
if (!ConditionNode) {
Yes
}
}
equivalent to this one:
tree main = Sequence {
if (ConditionNode) {
} else {
Yes
}
}
You can put logical operators (&&
and ||
) like conditional expressions in programming languages.
&&
is just a shorthand for a Sequence node and ||
is a Fallback node.
tree main = Sequence {
if (!a || b && c) {}
}
In fact, a child node is implicitly a logical expression, so you can write like this:
tree main = Sequence {
!a || b && c
}
Parentheses can be used to group operators.
tree main = Sequence {
(!a || b) && c
}
if
node without else clause is semantically the same as a Sequence node like below,
but Sequence or Fallback nodes cannot represent else
clause easily.
tree main = Sequence {
Sequence {
ConditionNode
Sequence {
Yes
}
}
}
Blackboard variable declarations
You can optionally declare and initialize a blackboard variable.
It can be used as a node name, and its value is evaluated as a boolean.
So, you can put the variable into a if
condition.
tree main = Sequence {
var flag = true
if (flag) {
Yes
}
}
Currently, only true
or false
is allowed as the initializer (the right hand side of =
).
The variable declaration with initialization will desugar into a SetBool
node.
A reference to a variable name will desugar into a IsTrue
node.
tree main = Sequence {
SetBool (value <- "true", output -> flag)
if (IsTrue (input <- flag)) {
Yes
}
}
However, it is necessary to declare the variable name in order to use it as a
variable reference.
For example, the code below will be a load
error for MissingNode
, even though
the variable is set with SetBool
.
tree main = Sequence {
SetBool (value <- "true", output -> flag)
if (flag) {
Yes
}
}
This design is a step towards statically checked source code.
Syntax specification
Here is a pseudo-EBNF notation of the syntax.
Note that this specification is by no means accurate EBNF. The syntax is defined by recursive descent parser with parser combinator, which removes ambiguity, but this EBNF may have ambiguity.
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"
TODO
- Easier way to define constructors (macros?)
-
Full set of control nodes
- Reactive nodes
- Star nodes
- Decorator nodes
- Performance friendly blackboard keys
-
DSL for defining behavior tree structure
- Programming language-like flow control syntax
- Static type checking for behavior tree definition file
Historical notes
This is a sister project of tiny-behavior-tree which in turn inspired by BehaviorTreeCPP.
While tiny-behavior-tree aims for more innovative design and experimental features, this crate aims for more traditional behavior tree implementation. The goal is to make a crate lightweight enough to use in WebAssembly.
The difference from tiny-behavior-tree
The main premise of tiny-behavior-tree is that it passes data with function arguments. This is very good for making fast and small binary, but it suffers from mixed node types in a tree.
It requires ugly boilerplate code or macros to convert types between different node argument types, and there is the concept of “PeelNode” which would be unnecessary in traditional behavior tree design.
On top of that, uniform types make it much easier to implement configuration file parser that can change the behavior tree at runtime.
Performance consideration
One of the issues with behavior tree in general regarding performance is that the nodes communicate with blackboard variables, which is essentially a key-value store. It is not particularly bad, but if you read/write a lot of variables in the blackboard (which easily happens with a large behavior tree), you would pay the cost of constructing a string and looking up HashMap every time.
One of the tiny-behavior-tree’s goals is to address this issue by passing variables with function call arguments. Why would you pay the cost of looking up HashMap if you already know the address of the variable?
Also, the blackboard is not very scalable, since it is essentially a huge table of global variables. Although there is sub-blackboards in subtrees, it is difficult to keep track of similar to scripting language’s stack frame without proper debugging tools.
I might experiment with non-string keys to make it more efficient, but the nature of the variables need to be handled dynamically in uniformly typeds nodes.
Re-exports
pub use crate::parser::load;
pub use crate::parser::load_yaml;
pub use crate::parser::node_def;
pub use crate::parser::parse_file;
pub use crate::parser::parse_nodes;
pub use crate::parser::NodeDef;
Modules
Macros
Structs
- A value which is initialized on the first access.
- A thread-safe cell which can be written to only once.
- An interned string with O(1) equality.
Enums
Traits
Functions
Type Aliases
- Blackboard is a mapping of a variable names and their values. The value is wrapped in an
Any
trait object, so it can be any type.