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| {
        res.push(*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 {
        // ...
    }
}

See example code for the full code.

Loading the tree structure from a yaml file (deprecated)

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. The usual file extension for this file format is .btc (behavior tree config). See the VSCode extension for syntax highlighting.

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, &registry, 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.

Variable assignment

A variable can be assigned value with this syntax:

value = true

Currently, only true or false can be used as the initializer.

It is a syntax sugar like below, but without variable declaration.

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

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.