Behavior Trees

Naive approach for implementing logic of NPCs using a bunch of ifs and flags often leads to very convoluted code. Behavior trees aims to solve this issue by creating a tree where each node represents an action and a condition to select the next execution node.

Overview

The behavior tree consists of at least one node, where each node can do something useful and define execution branch. A node can contain either one of built-in behavior, or a user-defined behavior.

Built-in nodes defined by BehaviorNode:

• BehaviorNode::Root - entry point of the tree, can contain only one child node.
• BehaviorNode::Composite - composite behavior node that contains multiple children nodes. The actual behavior of this node is defined by its kind, which can be one of the following:
  • CompositeNodeKind::Sequence - node will execute children nodes consecutively until Status::Failure is returned from any descendant node. In other words Sequence implements AND logical function.
  • CompositeNodeKind::Selector - node will execute children until Status::Success is returned from any descendant node. In other worlds Selector implements OR logical function.
• BehaviorNode::Inverter - A node, that inverts its child state (Status::Failure becomes Status::Success and vice versa, Status::Running remains unchanged)
• BehaviorNode::Leaf - a node with user-defined logic, contains an instance of a type that implements Behavior trait.

Behavior trait

Each node implements the Behavior trait, which defines the actual logic.

#![allow(unused)]
fn main() {
pub trait Behavior<'a>: BaseBehavior {
    /// A context in which the behavior will be performed.
    type Context;

    /// A function that will be called each frame depending on
    /// the current execution path of the behavior tree it belongs
    /// to.
    fn tick(&mut self, context: &mut Self::Context) -> Result<Status, GameError>;
}
}

The Context is typically PluginContext, but can be any type that may contain additional information. The logic of the behavior is defined by the contents of tick method. This method accepts a context and returns execution result. On success, it returns one of the Status enumeration variants or GameError on failure ( see error handling chapter for more info). Status enumeration has the following variants:

• Status::Success - an action was successful.
• Status::Failure - failed to perform an action.
• Status::Running - need another iteration to perform an action.

Example

The following example shows a simple behavior tree for a “bot” that can walk, open doors, step through doorways and close the door after itself.

#![allow(unused)]
fn main() {
struct Environment {
    // > 0 - door in front of
    // < 0 - door is behind
    distance_to_door: f32,
    door_opened: bool,
    done: bool,
}

impl Default for Environment {
    fn default() -> Self {
        Self {
            distance_to_door: 3.0,
            door_opened: false,
            done: false,
        }
    }
}

#[derive(Debug, PartialEq, Default, Visit, Clone)]
struct WalkAction;

impl Behavior<'_> for WalkAction {
    type Context = Environment;

    fn tick(&mut self, context: &mut Self::Context) -> BehaviorResult {
        if context.distance_to_door <= 0.0 {
            Ok(Status::Success)
        } else {
            context.distance_to_door -= 0.1;
            println!(
                "Approaching door, remaining distance: {}",
                context.distance_to_door
            );
            Ok(Status::Running)
        }
    }
}

#[derive(Debug, PartialEq, Default, Visit, Clone)]
struct OpenDoorAction;

impl Behavior<'_> for OpenDoorAction {
    type Context = Environment;

    fn tick(&mut self, context: &mut Self::Context) -> BehaviorResult {
        if !context.door_opened {
            context.door_opened = true;
            println!("Door was opened!");
        }
        Ok(Status::Success)
    }
}

#[derive(Debug, PartialEq, Default, Visit, Clone)]
struct StepThroughAction;

impl Behavior<'_> for StepThroughAction {
    type Context = Environment;

    fn tick(&mut self, context: &mut Self::Context) -> BehaviorResult {
        if context.distance_to_door < -1.0 {
            Ok(Status::Success)
        } else {
            context.distance_to_door -= 0.1;
            println!(
                "Stepping through doorway, remaining distance: {}",
                -1.0 - context.distance_to_door
            );
            Ok(Status::Running)
        }
    }
}

#[derive(Debug, PartialEq, Default, Visit, Clone)]
struct CloseDoorAction;

impl Behavior<'_> for CloseDoorAction {
    type Context = Environment;

    fn tick(&mut self, context: &mut Self::Context) -> BehaviorResult {
        if context.door_opened {
            context.door_opened = false;
            context.done = true;
            println!("Door was closed");
        }
        Ok(Status::Success)
    }
}

#[derive(Debug, PartialEq, Visit, Clone)]
enum BotAction {
    Walk(WalkAction),
    OpenDoor(OpenDoorAction),
    StepThrough(StepThroughAction),
    CloseDoor(CloseDoorAction),
}

impl Default for BotAction {
    fn default() -> Self {
        Self::Walk(Default::default())
    }
}

dispatch_behavior_variants!(
    BotAction,
    Environment,
    Walk,
    OpenDoor,
    StepThrough,
    CloseDoor
);

fn create_tree() -> BehaviorTree<BotAction> {
    let mut tree = BehaviorTree::new();

    let entry = sequence(
        [
            leaf(BotAction::Walk(WalkAction), &mut tree),
            leaf(BotAction::OpenDoor(OpenDoorAction), &mut tree),
            leaf(BotAction::StepThrough(StepThroughAction), &mut tree),
            leaf(BotAction::CloseDoor(CloseDoorAction), &mut tree),
        ],
        &mut tree,
    );

    tree.set_entry_node(entry);

    tree
}

fn test_behavior() {
    let tree = create_tree();

    let mut ctx = Environment::default();

    while !ctx.done {
        tree.tick(&mut ctx).unwrap();
    }
}

}