Behaviour trees

August 16, 2026

A behaviour tree is ticked. Once per control cycle, starting at the root, it walks down the tree and comes back with one of three answers: success, failure, or running.

Click inside the scene to send the robot toward a point. It will break off to go there. Drain the battery, or leave it running and let the battery drop on its own, and the robot breaks off from whatever it was doing and heads for the charger instead, whether or not it had a target.

What a tick does

A sequence ticks its children in order and stops at the first one that does not succeed. If every child succeeds, the sequence succeeds. If a child fails or goes running, the sequence takes that status and does not tick the children after it.

A fallback does the opposite: it stops at the first child that does not fail. If every child fails, the fallback fails.

Put a condition in front of an action inside a sequence and the action only runs once the condition has passed. Put several such sequences inside a fallback, in priority order, and the first one whose condition passes is the one that runs. That is the whole tree behind the tool above:

• If the battery is low, recharge.
• Otherwise, if a target is visible, approach it.
• Otherwise, patrol.

Three lines. Nothing about interrupting an approach to go recharge is written down anywhere in them.

Why running earns its own status

A sequence or a fallback that only ever returned success or failure would be a nested if-statement, evaluated once and forgotten. Running is what makes it a tree that keeps a task alive across many ticks instead of deciding once what to do this instant.

But running by itself does not explain the preemption in the tool. What does is what a tick does with it: the sweep starts at the root every single time. It does not resume at whichever leaf was running. It walks past every earlier sibling again, re-checking every condition on the way down, and only then reaches the leaf that was running before.

That is why the battery condition, sitting in front of the recharge action, is checked on the tick where the battery first drops and every tick after that, whether the robot was approaching a target or halfway round the patrol loop. There is no code path labelled “interrupt the current behaviour”. There is only a condition higher in the tree than the behaviour is, checked again on schedule.

The transition that is never stored

Ask which state the robot is in and the honest answer is: whichever leaf is running right now, which is also whichever leaf the last tick happened to stop on. That is the entire state. A tick is a pure function of the tree and whatever the blackboard says this cycle, so the same inputs always produce the same decision, and nothing about the previous decision has to be remembered to get there.

That is worth restating, because it is easy to picture a tree quietly tracking “currently in the approach branch” the way a state machine tracks its current state. It does not. Run the fallback again from a battery level that used to mean recharge and it recharges again, exactly as if this were the first tick it had ever seen.

Trees against tables

The panel below the tree draws the same decision as a state machine: three states, and an arrow for every ordered pair between them.

With $n$ states, a fully connected machine needs up to

directed transitions, one for every ordered pair, because in general which state you came from can change which state you go to next. Three states, six arrows, as the panel draws them.

A behaviour tree gets the same decision from structure instead. Adding a fourth behaviour, say returning to a docking bay when a task queue is empty, means inserting one more branch into the fallback. Nothing already there changes. The state-machine version of the same addition means asking, for every one of the three existing states, what happens now if the queue goes empty while in it, and wiring an edge for each answer.

That is a real difference and it is not about how many states either one can be in. A behaviour tree can express any finite state machine: put the current state in the blackboard, build one fallback branch per state whose condition checks for it, and each branch’s action is whatever that state does before writing the next state back. The reverse also holds. A tree ticked against blackboards drawn from a finite set of possibilities has only finitely many distinct running-leaf configurations reachable from the start, because a tick is a pure function of the tree and the blackboard and nothing else is remembered between ticks. That is exactly a state machine already: states are configurations, the transition function is tick, the input alphabet is whatever the blackboard can be.

So the two are equally expressive. The difference this post is actually about is which changes are cheap. A table grows the way a table grows. Structure grows by insertion.

The code

The module the tool ticks, in C++. A blackboard here is two flags, because that is all this tree’s leaves read, but nothing about tick depends on that; it only ever calls a leaf’s own function and looks at what came back.

#include <functional>
#include <memory>
#include <stdexcept>

enum class Status { Success, Failure, Running };

enum class Kind { Action, Condition, Sequence, Fallback, Parallel, Invert, Repeat };

struct Blackboard {
    bool batteryLow;
    bool targetVisible;
};

struct Node;
using NodePtr = std::shared_ptr<Node>;

// A leaf carries `fn`. A composite carries `children`. A decorator carries
// `child`. One struct rather than a hierarchy of them, because every node
// is built once, by a factory function below, and never edited afterwards.
struct Node {
    Kind kind;
    std::string name;
    std::function<Status(const Blackboard&)> fn;
    std::vector<NodePtr> children;
    NodePtr child;
};

NodePtr action(std::string name, std::function<Status(const Blackboard&)> fn) {
    return std::make_shared<Node>(Node{Kind::Action, std::move(name), std::move(fn), {}, nullptr});
}

NodePtr condition(std::string name, std::function<Status(const Blackboard&)> fn) {
    return std::make_shared<Node>(Node{Kind::Condition, std::move(name), std::move(fn), {}, nullptr});
}

NodePtr sequence(std::string name, std::vector<NodePtr> children) {
    return std::make_shared<Node>(Node{Kind::Sequence, std::move(name), nullptr, std::move(children), nullptr});
}

NodePtr fallback(std::string name, std::vector<NodePtr> children) {
    return std::make_shared<Node>(Node{Kind::Fallback, std::move(name), nullptr, std::move(children), nullptr});
}

NodePtr parallel(std::string name, std::vector<NodePtr> children) {
    return std::make_shared<Node>(Node{Kind::Parallel, std::move(name), nullptr, std::move(children), nullptr});
}

NodePtr invert(std::string name, NodePtr child) {
    return std::make_shared<Node>(Node{Kind::Invert, std::move(name), nullptr, {}, std::move(child)});
}

NodePtr repeatUntilFailure(std::string name, NodePtr child) {
    return std::make_shared<Node>(Node{Kind::Repeat, std::move(name), nullptr, {}, std::move(child)});
}

// The tree actually walked this cycle. `children` holds only the children
// that were ticked, in the order they were ticked, so a child a
// short-circuit skipped is simply absent rather than present with no
// status.
struct Result {
    std::string name;
    Kind kind;
    Status status;
    std::vector<Result> children;
};

Result tick(const Node& node, const Blackboard& blackboard) {
    switch (node.kind) {
        case Kind::Action:
        case Kind::Condition: {
            const Status status = node.fn(blackboard);
            return {node.name, node.kind, status, {}};
        }

        case Kind::Sequence: {
            std::vector<Result> children;
            Status status = Status::Success;
            for (const NodePtr& c : node.children) {
                Result result = tick(*c, blackboard);
                status = result.status;
                children.push_back(std::move(result));
                if (status != Status::Success) break;
            }
            return {node.name, node.kind, status, std::move(children)};
        }

        case Kind::Fallback: {
            std::vector<Result> children;
            Status status = Status::Failure;
            for (const NodePtr& c : node.children) {
                Result result = tick(*c, blackboard);
                status = result.status;
                children.push_back(std::move(result));
                if (status != Status::Failure) break;
            }
            return {node.name, node.kind, status, std::move(children)};
        }

        case Kind::Parallel: {
            std::vector<Result> children;
            for (const NodePtr& c : node.children) children.push_back(tick(*c, blackboard));

            bool anyFailed = false, allSucceeded = true;
            for (const Result& r : children) {
                if (r.status == Status::Failure) anyFailed = true;
                if (r.status != Status::Success) allSucceeded = false;
            }
            const Status status = anyFailed ? Status::Failure
                                 : allSucceeded ? Status::Success
                                 : Status::Running;
            return {node.name, node.kind, status, std::move(children)};
        }

        case Kind::Invert: {
            Result child = tick(*node.child, blackboard);
            const Status status = child.status == Status::Success ? Status::Failure
                                 : child.status == Status::Failure ? Status::Success
                                 : Status::Running;
            std::vector<Result> children;
            children.push_back(std::move(child));
            return {node.name, node.kind, status, std::move(children)};
        }

        case Kind::Repeat: {
            Result child = tick(*node.child, blackboard);
            const Status status = child.status == Status::Success ? Status::Running : child.status;
            std::vector<Result> children;
            children.push_back(std::move(child));
            return {node.name, node.kind, status, std::move(children)};
        }
    }
    throw std::logic_error("unknown node kind");
}

// The leaf that decided this tick: follow the last child ticked at each
// level, which is always the one a composite stopped on and a decorator's
// only child.
std::string activeLeaf(const Result& result) {
    const Result* node = &result;
    while (!node->children.empty()) node = &node->children.back();
    return node->name;
}

Root to leaf, every tick, is the whole algorithm. Nothing here remembers which branch ran last time, because nothing needs to: the next tick finds it again on its own.