Advice on behavior trees in Bevy?

[tgecho]

I'm looking up for some advice on approaches to implement a behavior tree in a bevy app. I'll try to summarize my to-date attempts/thought process. Apologies if I say too much or little :)

My first try (https://discord.com/channels/691052431525675048/692648638823923732/983909053778497666) involved using Parent/Children relationships to structure an entity per node. Parent nodes (sequences, etc...) would manage an Active component on their children, and children would manage a Status component on themselves to communicate status back to their parents.

#[derive(Component)]
pub struct Active;

#[derive(Component)]
pub enum Status { Running, Succeeded, Failed }

Actually constructing the tree was relatively straightforward (with room for improved ergonomics later):

commands
    .entity(agent)
    .insert(Repeater)
    .insert(Active)
    .with_children(|repeater| {
        repeater
            .spawn()
            .insert(Sequence::new())
            .with_children(|sequence| {
                sequence.spawn().insert(MoveToDonut { agent });
                sequence.spawn().insert(EatDonut { agent });
            });
    });

And leaf nodes were implemented as systems:

pub fn move_to_donut_system(
    mut behavior_query: Query<(&MoveToDonut, &mut Status), With<Active>>,
    agent_query: Query<&Location, With<Agent>>,
    donut_query: Query<&Location, With<Donut>>,
    mut commands: Commands,
) {
    for (behavior, status) in behavior_query.iter_mut() {
        // ... look up the agent/donut locations and trigger a move if needed
    }
}

This felt nice in theory, but in practice it proved very tricky to get the control flow nodes correct. Even with unit tests I'm still having trouble shaking the bugs out, and race conditions abound.

This partly comes from the fact that nodes communicate via component changes, so it can take as long as a whole frame per node relationship for changes to propagate. I think this might be ok (maybe it'll even end up mimicing more realistic human response times!), but it feels a little loose and makes the flow quite tricky to follow. Not a dead end! But I'm feeling enough pain to wonder if it's a good path.

So my next thought was going from the other direction with an exclusive system. The naive first sketch quickly runs into the fact that I need to borrow the behavior tree from the world AND give nodes relatively arbitrary access:

pub fn behavior_tree_system(world: &mut World) {
    for mut behavior_tree in world.query::<&mut BehaviorTree>().iter_mut(world) {
        behavior_tree.tick(world);
                        // ^^^^^ cannot borrow `*world` as mutable more than once at a time
    }
}

I'm at a bit of a loss as to how to stitch this stuff together. It intuitively feels like leaf nodes as components/systems would be nice. You can write them in a relatively familiar pattern, they (I guess?) get all of the nice data orientation, can share caches as appropriate, etc... but maybe this is trying to shoehorn things? Is there maybe a better way to give leaf nodes relatively arbitrary query access without writing them as systems or handing them a &World reference?

Any thoughts? (and thanks for bearing with me!)

[nicopap]

Thank you for the research and sharing it with us here! I totally agree that behavior trees are entities is a great idea. And I understand how the component-based approach definitively can be difficult with the fact that it doesn't update the entities before the end of the stage. I'd really like to see you succeed setting up behavior trees as entities.

In bevy-ui-navigation I had a similar issue, and I solved it, somewhat by accident. Responsiveness is more important in UI stuff, so it came as a very positive surprise when suddenly everything felt snappy and smooth. I think ui-navigation is more relevant than expected to your issue, because it relies heavily on a hierarchy of nodes stored in the ECS. Here is a few pointers to help you:

• Use a Stage dedicated to the behavior tree handling, so that it's possible for systems inserted in later ones to see the changes to behavior trees. Component insertions and removal are persisted between stages. You might need several. However, this reduces concurrency, so not ideal.
• Have an "inactive" variant to your state enums. So that you do not rely on component insertion/removal, just mutating the value of the component. Component mutation are immediately visible to the rest of the ECS. For this to work as perfectly as possible, you need to use explicit system ordering with system.label(foo). This is how I did it.

[tgecho]

I appreciate the encouragement, and the tips!

I’m not totally clear on the ramifications of the incoming stageless work, but my naive take is that I shouldn’t plan to depend on stages too much :)

I can see how system ordering might increase determinism (and decrease latency) a bit. I can’t completely order all of the systems (since each type of node can exist at multiple arbitrary locations in the tree), but I think a few high level labels (e.g. control, decorator, leaf, etc…) could help!

The main reason I went with a single Active marker component was so I could use it in query filters to avoid processing inactive nodes (which will be most of them in any given frame). Assuming there are no & vs &mut ownership issues (I’m not sure about this) is there an appreciable performance difference between filtering in the query and doing it manually in the system?

Thanks again! I’m feeling better about trying to push this approach through.

[tgecho]

Progress!

I sort of took your advice and consolidated the Active/Status components into a single Behavior enum (names... I dunno):

#[derive(Component, PartialEq, Eq, Debug, Clone)]
pub enum Behavior {
    Inactive,
    Running,
    Succeeded,
    Failed,
}

I originally wanted to have clear responsibilities between parents and children and to steer clear of borrowing conflicts, but I think the split was a big source of issues. Now I can't accidentally have a node that is both not Active and Status::Running at the same time.

The main downsides are that I can't simply filter queries on the Active component but instead have to do an
if behavior.is_running() { ... } check at the beginning of systems. Not sure what if any performance ramifications there are to this.

Also having to juggle parent/child components borrowing is a little tricky. Fortunately this mostly only affects control nodes, of which there likely won't be too many types. Here's the current (still sketchy!) implementation of the sequence node:

pub fn child_updated_system(
    mut sequences: Query<(Entity, &mut Sequence, &Children)>,
    mut behaviors: Query<&mut Behavior>,
) {
    for (seq_entity, mut sequence, children) in sequences.iter_mut() {
        if behaviors.get(seq_entity).map_or(false, |s| s.is_running()) {
            let child_iter = children.iter().enumerate().skip(sequence.index);
            let mut parent_behavior = Behavior::Succeeded;
            for (index, child_entity) in child_iter {
                if let Ok(mut child_behavior) = behaviors.get_mut(*child_entity) {
                    match *child_behavior {
                        Behavior::Failed => {
                            sequence.index = 0;
                            child_behavior.set(Behavior::Inactive);
                            parent_behavior = Behavior::Failed;
                            break;
                        }
                        Behavior::Running => {
                            if index > sequence.index {
                                sequence.index = index;
                            }
                            parent_behavior = Behavior::Running;
                            break;
                        }
                        Behavior::Inactive => {
                            if index > sequence.index {
                                sequence.index = index;
                            }
                            child_behavior.set(Behavior::Running);
                            parent_behavior = Behavior::Running;
                            break;
                        }
                        Behavior::Succeeded => {
                            child_behavior.set(Behavior::Inactive);
                        }
                    }
                } else {
                    todo!("child missing a behavior!?");
                }
            }
            // running this outside of the child loop so we can get a &mut Behavior
            if let Ok(mut behavior) = behaviors.get_mut(seq_entity) {
                behavior.set(parent_behavior);
            }
        }
    }
}

The first attempt would often freeze up, especially as I added more agents. This one can handle a bunch racing each other around without getting stuck! (they do pause for a moment when they can't find a path): https://discord.com/channels/691052431525675048/692648638823923732/985366957580771348