Behavior Trees

01Why behavior trees

An NPC decides, many times a second, whether to patrol a route, chase a target, take cover, reload, call for backup or retreat. In the early 2000s those decisions commonly lived in finite state machines (FSMs): the NPC is in exactly one state, such as Patrol, and a hand-written transition moves it to another, such as Chase. That works at five states. Every state added after that has to be checked against every existing one for transitions in both directions (§3), and by a few dozen states the transition set is hard to review and easy to break.

A behavior tree drops the transitions. Each behavior is a branch, the order of the branches sets their priority, and the game walks the tree from the root on every tick (one AI update, often once per frame) to find the first branch that can run. The survey literature puts it structurally: in a BT "the state transition logic is not dispersed across the individual states, but organized in a hierarchical tree structure, with the states as leaves"^[5]. Adding a behavior means grafting a subtree onto an existing branch, not wiring transitions to every other state. (Walking from the root every tick is the classic model; §11 covers the event-driven variants that keep running the active branch and re-check only when something they watch changes.)

You'll meet them in the major engines. Unreal ships a behavior tree editor^[6] and, since 2022, StateTree, a hybrid of trees and state machines, alongside it^[7]. Unity shipped its own first-party tool in September 2024, the com.unity.behavior package^[8], which Unity calls a behavior graph rather than a tree, since branches may merge back. Studios that hand-roll their AI often land somewhere else entirely, as §14 shows.

What the tree buys you over an FSM:

• Modularity. A subtree is self-contained. You can move it, copy it, disable it, or hand it to another designer. FSM states are tangled by their transitions.
• Scalability. Adding a branch to a BT is one edit in one place, however big the tree is. Adding a state to an FSM can mean a transition to and from each existing state.
• Debuggability. A BT's evaluation path is a single top-down walk. You can visualize it as a highlighted path through the tree. An FSM's history is a sequence of state transitions, and the current behavior depends on which transition fired last.
• Re-evaluation. A reactive BT re-checks higher-priority branches every tick. An FSM leaves its current state only through a transition someone authored from that state, so reacting to a new situation depends on that transition existing.

02A short history

Why does an idea from a 2004 shooter now drive Unreal's AI editor and robot navigation software? Behavior trees came out of game AI and were formalized later by robotics researchers, and the textbook terms you'll meet in engine docs come from both sides.

In short: game AI built the idea, starting with Isla's Halo 2 AI (shipped 2004, presented at GDC 2005)^[1] and Champandard's 2007 article that set out sequences, selectors and decorators as the standard nodes^[2]. Robotics formalized it, from the 2014 ICRA paper^[4] to Colledanchise and Ögren's 2018 book^[3]. A 2022 survey credits the key milestones to Michael Mateas and Andrew Stern's ABL behavior language and to Isla's talk^[5]. Isla himself claims no priority, and calls his architecture a "hierarchical finite state machine (HFSM) or a behavior tree, or even more specifically, a behavior DAG"^[1]: a directed acyclic graph, because one behavior subtree can sit in several places.

03The FSM problem

A designer asks for one more enemy state, Heal, in an FSM that already has seven: Idle, Patrol, Chase, Attack, Flee, Stunned and Search. Before anyone writes Heal, someone has to answer fourteen questions: can each of the seven existing states move to Heal, and can Heal move back to each of them? A wrong answer either way is a bug that playtesting finds later.

An FSM with n states has up to n(n - 1) directed transitions, because each state can move to each of the other n - 1. Not every pair needs a transition in practice, but every new state raises the same two questions for every existing one. Missing a transition is a bug (the agent gets stuck in a state). Adding a redundant one is also a bug (the agent escapes a state it shouldn't leave). That's n - 1 pairs to check per new state, and the total grows with the square of the state count, O(n²).

Hierarchical FSMs (HFSMs) help by nesting a smaller state machine inside a state, so a transition every child shares, such as "any combat state can flee", is written once on the parent. The explosion still happens within each level. Pushdown automata, state machines with a stack of states, help with "go do X, then come back to what you were doing". Neither removes the core problem: the interaction between states lives in transitions, and transitions grow with the square of the state count.

The widget below makes this visible. Add states to the FSM on the left and the transition arrows multiply. The behavior tree on the right adds a leaf for each new behavior, and its edge count grows by one each time.

04Tree structure and tick

A guard is halfway through a walk to its next waypoint when the AI update runs again. The tree can't block the game until the walk finishes, and it can't forget the walk either. So every node answers each tick with one of three words: done, couldn't, or still working.

A behavior tree is a rooted tree. Every node has zero or more children. The tree is evaluated from the root every tick (typically once per frame, though some engines tick AI at a lower rate to save CPU). Each node's tick() function returns one of three statuses:

• SUCCESS: the node did its job.
• FAILURE: the node tried and could not do its job.
• RUNNING: the node is still working. Come back next tick.

Node types fall into three categories:

• Composite nodes (Sequence, Selector, Parallel) have multiple children and control evaluation order.
• Decorator nodes (Inverter, Repeat, Cooldown) have exactly one child and modify its result.
• Leaf nodes have no children: either an action (does work) or a condition (tests the world).

Evaluation is top-down, left-to-right. The root ticks its children according to its composite type, those children tick theirs, and the results propagate back up: one walk through the tree per tick.

The widget below shows this evaluation in action. A selector at the root tries three branches: Attack (sequence of condition + action), Chase (sequence of condition + action), and Patrol (single action). Switch the scenario to change which conditions pass, then step through or auto-play to watch the tick propagate.

05Sequences

A guard should fire only if it has ammo and has finished aiming. If any step fails, it shouldn't carry on to the next one. That "do these in order, stop at the first failure" pattern is a sequence.

A Sequence is AND logic. It executes its children left to right. If a child returns SUCCESS, the sequence moves to the next child. If a child returns FAILURE, the sequence stops and returns FAILURE. If all children return SUCCESS, the sequence returns SUCCESS. If any child returns RUNNING, the sequence returns RUNNING.

The mental model: "do A, then B, then C. If any step fails, abort." A patrol sequence might be: [HasWaypoint?, MoveToWaypoint, Wait(2s), NextWaypoint]. If HasWaypoint? fails, the entire patrol sequence fails and the parent selector tries something else.

06Selectors (fallbacks)

A guard has three things it could be doing: attacking, chasing or patrolling. It should attack if it can, chase if it can't attack, and patrol only when neither applies. That "try these in priority order, stop at the first one that works" pattern is a selector.

A Selector (sometimes called Fallback or Priority) is OR logic. It executes children left to right. If a child returns FAILURE, the selector moves to the next child. If a child returns SUCCESS, the selector stops and returns SUCCESS. If all children fail, the selector returns FAILURE. If any child returns RUNNING, the selector returns RUNNING.

The mental model: "try A. If that fails, try B. If that fails, try C." The leftmost child has the highest priority. A top-level selector with [AttackSequence, ChaseSequence, PatrolAction] tries combat first, pursuit second, and only patrols if neither applies.

The widget below puts a sequence and a selector side by side with the same three children. Toggle each child's result to see how the composite outcome differs.

07Decorators

A guard shouts "Over there!" when it spots you. Left alone, the bark's condition stays true while you're in view, so the guard starts a new bark the moment the last one ends. You don't want to edit the Bark action; you want to wrap it in "after each bark, stay quiet for ten seconds". That wrapper is a decorator.

A decorator wraps exactly one child and modifies its behavior or result. Common decorators:

• Inverter (NOT). Flips SUCCESS to FAILURE and vice versa. RUNNING passes through. Useful for negating conditions: "if NOT EnemyVisible, patrol."
• Repeat(n). Ticks its child up to n times. Returns SUCCESS after n completions, RUNNING while iterating, FAILURE if the child fails during any iteration.
• RetryUntilSuccess(n). Retries the child up to n times on FAILURE. Returns SUCCESS as soon as the child succeeds. Returns FAILURE after n failed attempts.
• Cooldown(t). After the child completes (SUCCESS or FAILURE), returns FAILURE for the next t seconds without ticking the child. Prevents behaviors from re-triggering immediately (barks, reload checks, perception queries).
• TimeLimit(t). If the child has been RUNNING for more than t seconds, forces a FAILURE. Prevents stuck actions from blocking the tree forever.

Unreal uses decorators differently. They attach to a composite or task node rather than sitting in the tree as a parent of their own, and Epic recommends them in place of condition leaves: "In the standard model for Behavior Trees, conditionals are Task leaf nodes", whereas Unreal's conditional decorators gate a branch so that every leaf is an action^[6][22]. Those decorators double as abort triggers: when a decorator's condition changes, it can abort its own subtree, the lower-priority branches to its right, or both (§11).

08Parallel nodes

A guard sprinting to cover should keep its gun pointed at you while it runs. A sequence can't do that: it would finish the run and only then start tracking you. You need a node that keeps both children going at once.

A Parallel node ticks all its children in the same tick rather than one after another, so several of them can be RUNNING at once. It then needs a rule for when it's done. Two success policies are common, and several implementations generalize both into a threshold (succeed once k children have):

• Succeed-on-all. Returns SUCCESS only when every child has returned SUCCESS: the "all must pass" gate.
• Succeed-on-one. Returns SUCCESS as soon as any child succeeds: the "any will do" gate.

Whether a parallel re-ticks a child that has already returned is an implementation choice rather than a property of the idea, and two widely used open-source runtimes disagree. BehaviorTree.CPP, a C++ library, keeps a set of completed children and skips them until the node resets^[20]. py_trees, a Python library, does the opposite by default: "A parallel ticks every child every time the parallel is itself ticked", with skipping available as an opt-in synchronised setting on its SuccessOnAll and SuccessOnSelected policies^[21]. Read your runtime before assuming either.

Failure rules vary more than the success policies. py_trees fails the parallel as soon as any child fails, under every policy^[21]; BehaviorTree.CPP makes the failure count a second threshold (below). A typical use: [Parallel: MoveTo(cover), TrackTarget]. The agent moves and keeps its aim on the enemy at the same time, and under succeed-on-one, MoveTo finishing resolves the node as SUCCESS and the still-running TrackTarget is halted: stopped, with whatever progress it had thrown away.

BehaviorTree.CPP does not expose named policies at all. It exposes two integer ports, success_count (default -1, meaning all children) and failure_count (default 1), and states the completion rule in one line: "It is completed when either the SUCCESS or FAILURE threshold is reached. Any remaining running children are halted."^[20] The source carries a second failure route the docs leave out: the node also fails the moment enough children have failed that the success threshold can no longer be reached^[20]. And for the case where the halt is the part you do not want, there is a separate node: ParallelAll "always executes ALL children to completion. It never halts children early."^[20]

09Blackboards

The Chase branch needs to know where the target is. The Attack branch needs the same target plus the ammo count. Perception found the target and the weapon system knows the ammo, and neither should have to know which nodes care.

Nodes in a behavior tree share that data through a blackboard: a key-value store, such as "target.distance" → 25, that any node can read from and write to. It holds the target entity, its last-known position, the agent's health, the ammo count, whether a perception query returned a result. Usually each agent gets its own blackboard instance, and some systems add shared parent scopes for squad-level data.

Unreal's blackboard is a first-class asset paired with the BT. You define typed keys (Object, Vector, Float, Bool and Enum, among others) in the blackboard definition. Decorators can observe specific keys and trigger re-evaluation when the value changes, which is the mechanism behind Unreal's event-driven BT model.^[6]

The widget below shows a behavior tree reading from a live blackboard. Adjust the sliders to change perception data; the tree re-evaluates on every change.

10Actions and conditions

Everything so far decides which leaf runs. The leaves are where the guard actually checks the world or does something, and the hard case is an action that takes longer than one frame, such as walking across a room.

Leaf nodes are where the actual work happens. Two kinds:

• Conditions test world state and return SUCCESS or FAILURE in a single tick. IsTargetVisible, IsHealthBelow(30), HasAmmo, IsInCover. They never return RUNNING.
• Actions perform work. MoveTo, Attack, PlayAnimation, Reload, Wait(t). Actions that complete in one tick return SUCCESS or FAILURE. Actions that span multiple frames (movement, animation playback) return RUNNING until they finish.

The RUNNING status is what makes BTs handle multi-frame actions cleanly. A MoveTo action that takes 200 frames to complete returns RUNNING on every frame until the last. The parent sequence sees RUNNING, returns RUNNING itself, and the tree pauses evaluation of that branch until next tick. This propagation continues all the way up to the root.

The composites below are reactive: every tick starts again at child 0, which is the default Colledanchise and Ögren build on^[3] and the baseline §11 compares memory against. Each one still records which child was RUNNING, for one reason: when an earlier child ends the tick first (a condition fails, a higher-priority branch takes over), the child that was running has to be halted, or it keeps a half-finished action alive.

Code: base node, sequence, selector

#include <memory>
#include <vector>

enum class Status { Success, Failure, Running };

// Base node. Every node implements tick(); halt() is optional.
class Node {
public:
    virtual ~Node() = default;
    virtual Status tick() = 0;

    // Called when a parent abandons this node while it was RUNNING.
    // Anything the node started and has not finished gets undone here.
    virtual void halt() {}
};

// Sequence: AND logic. Fail on first failure, succeed when all succeed.
// Reactive: every tick starts again at child 0.
class Sequence : public Node {
    std::vector<std::unique_ptr<Node>> children;
    int runningIndex = -1;  // child that returned RUNNING last tick, or -1
public:
    void addChild(std::unique_ptr<Node> child) {
        children.push_back(std::move(child));
    }

    // Abort is recursive: a composite that is dropped must drop whatever
    // it had running underneath, or that work leaks.
    void halt() override {
        for (auto& child : children) child->halt();
        runningIndex = -1;
    }

    Status tick() override {
        const int count = static_cast<int>(children.size());
        for (int i = 0; i < count; ++i) {
            Status result = children[i]->tick();
            if (result == Status::Success) continue;
            // An earlier child ended this tick before the one that was running
            // got ticked. Halt it, or its half-finished action lives on.
            if (runningIndex > i) children[runningIndex]->halt();
            runningIndex = (result == Status::Running) ? i : -1;
            return result;             // FAILURE or RUNNING propagates up
        }
        runningIndex = -1;
        return Status::Success;        // all children succeeded
    }
};

// Selector: OR logic. Succeed on first success, fail when all fail.
// Reactive: higher-priority children are re-checked every tick.
class Selector : public Node {
    std::vector<std::unique_ptr<Node>> children;
    int runningIndex = -1;  // child that returned RUNNING last tick, or -1
public:
    void addChild(std::unique_ptr<Node> child) {
        children.push_back(std::move(child));
    }

    void halt() override {
        for (auto& child : children) child->halt();
        runningIndex = -1;
    }

    Status tick() override {
        const int count = static_cast<int>(children.size());
        for (int i = 0; i < count; ++i) {
            Status result = children[i]->tick();
            if (result == Status::Failure) continue;
            // A higher-priority child took over from the one that was running.
            // That switch is the abort, and the loser must be halted.
            if (runningIndex > i) children[runningIndex]->halt();
            runningIndex = (result == Status::Running) ? i : -1;
            return result;             // SUCCESS or RUNNING propagates up
        }
        runningIndex = -1;
        return Status::Failure;        // all children failed
    }
};

// Stand-ins for the engine types. Blackboard gets its real definition
// in the blackboard pane below; NavAgent is whatever your pathfinding exposes.
pub struct Blackboard;
pub struct NavAgent;

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Status { Success, Failure, Running }

// Everything a node might touch travels in one place. The C++ pane gives
// MoveTo reference members instead; that does not port. Every action node
// needs &mut NavAgent, only one &mut can exist at a time, so the tree could
// hold at most one such node. Passing context per tick sidesteps that; the
// bonsai-bt crate does the same, handing the blackboard to a callback on each tick.
pub struct Context {
    pub blackboard: Blackboard,
    pub nav_agent: NavAgent,
}

// Base trait. Every node implements tick(); halt() is optional.
pub trait Node {
    fn tick(&mut self, context: &mut Context) -> Status;

    // Called when a parent abandons this node mid-RUNNING. Anything the
    // node started and has not finished gets undone here.
    fn halt(&mut self, _context: &mut Context) {}
}

// Sequence: AND logic. Fail on first failure, succeed when all succeed.
// Reactive: every tick starts again at child 0.
pub struct Sequence {
    children: Vec<Box<dyn Node>>,
    running_index: Option<usize>,  // child that returned Running last tick
}

impl Sequence {
    pub fn new(children: Vec<Box<dyn Node>>) -> Self {
        Sequence { children, running_index: None }
    }
}

impl Node for Sequence {
    fn tick(&mut self, context: &mut Context) -> Status {
        for i in 0..self.children.len() {
            let result = self.children[i].tick(context);
            if result == Status::Success {
                continue;
            }
            // An earlier child ended this tick before the one that was running
            // got ticked. Halt it, or its half-finished action lives on.
            if let Some(previous) = self.running_index.filter(|&previous| previous > i) {
                self.children[previous].halt(context);
            }
            self.running_index = if result == Status::Running { Some(i) } else { None };
            return result;  // FAILURE or RUNNING propagates up
        }
        self.running_index = None;
        Status::Success  // all children succeeded
    }

    fn halt(&mut self, context: &mut Context) {
        // Abort is recursive: a composite that is dropped must drop whatever
        // it had running underneath, or that work leaks.
        for child in &mut self.children { child.halt(context); }
        self.running_index = None;
    }
}

// Selector: OR logic. Succeed on first success, fail when all fail.
// Reactive: higher-priority children are re-checked every tick.
pub struct Selector {
    children: Vec<Box<dyn Node>>,
    running_index: Option<usize>,  // child that returned Running last tick
}

impl Selector {
    pub fn new(children: Vec<Box<dyn Node>>) -> Self {
        Selector { children, running_index: None }
    }
}

impl Node for Selector {
    fn tick(&mut self, context: &mut Context) -> Status {
        for i in 0..self.children.len() {
            let result = self.children[i].tick(context);
            if result == Status::Failure {
                continue;
            }
            // A higher-priority child took over from the one that was running.
            // That switch is the abort, and the loser must be halted.
            if let Some(previous) = self.running_index.filter(|&previous| previous > i) {
                self.children[previous].halt(context);
            }
            self.running_index = if result == Status::Running { Some(i) } else { None };
            return result;  // SUCCESS or RUNNING propagates up
        }
        self.running_index = None;
        Status::Failure  // all children failed
    }

    fn halt(&mut self, context: &mut Context) {
        for child in &mut self.children { child.halt(context); }
        self.running_index = None;
    }
}

Code: a concrete action (MoveTo with RUNNING)

// Restated from the neighbouring panes so this one compiles on its own.
enum class Status { Success, Failure, Running };
struct Vec3 { float x, y, z; };
class Node { public: virtual ~Node() = default; virtual Status tick() = 0; virtual void halt() {} };
struct Blackboard { template <typename T> T get(const char*) const { return T{}; } };
struct NavAgent { bool requestPath(Vec3); bool hasArrived() const; void cancelPath(); };

// MoveTo: navigate to a target position read from the blackboard.
// Returns RUNNING while pathfinding/moving, SUCCESS on arrival,
// FAILURE if the path is invalid or the target is unreachable.
class MoveTo : public Node {
    Blackboard& blackboard;
    NavAgent&   navAgent;
    bool started = false;
public:
    MoveTo(Blackboard& blackboard, NavAgent& navAgent)
        : blackboard(blackboard), navAgent(navAgent) {}

    Status tick() override {
        if (!started) {
            Vec3 target = blackboard.get<Vec3>("target.position");
            if (!navAgent.requestPath(target))
                return Status::Failure;  // no valid path
            started = true;
        }
        if (navAgent.hasArrived()) {
            started = false;          // reset for next invocation
            return Status::Success;
        }
        return Status::Running;      // still moving
    }

    // Without this, a higher-priority branch that preempts us mid-move
    // leaves started == true. On re-entry we skip requestPath and poll
    // hasArrived() against a stale path. That is the abort bug §11 is about,
    // and it is invisible until a designer adds a higher-priority branch.
    void halt() override {
        if (started) {
            navAgent.cancelPath();
            started = false;
        }
    }
};

// Restated from the neighbouring panes so this one compiles on its own.
#[derive(Clone, Copy)]
pub struct Vec3 { pub x: f32, pub y: f32, pub z: f32 }
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum Status { Success, Failure, Running }
pub struct Blackboard;
impl Blackboard { pub fn get<T>(&self, _key: &str) -> Option<T> { None } }
pub struct NavAgent;
impl NavAgent {
    pub fn request_path(&mut self, _target: Vec3) -> bool { true }
    pub fn has_arrived(&self) -> bool { true }
    pub fn cancel_path(&mut self) {}
}
pub struct Context { pub blackboard: Blackboard, pub nav_agent: NavAgent }
pub trait Node {
    fn tick(&mut self, context: &mut Context) -> Status;
    fn halt(&mut self, _context: &mut Context) {}
}

// MoveTo: navigate to a target position read from the blackboard.
// Returns Running while pathfinding/moving, Success on arrival,
// Failure if the path is invalid or the target is unreachable.
pub struct MoveTo {
    started: bool,
}

impl MoveTo {
    pub fn new() -> Self { MoveTo { started: false } }
}

impl Node for MoveTo {
    fn tick(&mut self, context: &mut Context) -> Status {
        if !self.started {
            // get returns Option here, unlike the C++ pane's by-value get:
            // a missing blackboard key is a failure, not a default-constructed
            // Vec3 that quietly sends the agent to the world origin.
            let Some(target) = context.blackboard.get::<Vec3>("target.position") else {
                return Status::Failure;  // no target set
            };
            if !context.nav_agent.request_path(target) {
                return Status::Failure;  // no valid path
            }
            self.started = true;
        }
        if context.nav_agent.has_arrived() {
            self.started = false;     // reset for next invocation
            return Status::Success;
        }
        Status::Running              // still moving
    }

    fn halt(&mut self, context: &mut Context) {
        if self.started {
            context.nav_agent.cancel_path();
            self.started = false;
        }
    }
}

Code: blackboard with typed access

#include <any>
#include <string>
#include <unordered_map>

// Blackboard: type-erased key-value store.
// Production code would use a fixed-layout struct for cache locality;
// the std::any version here prioritizes flexibility for prototyping.
class Blackboard {
    std::unordered_map<std::string, std::any> data;
public:
    template<typename T>
    void set(const std::string& key, T value) {
        data[key] = std::move(value);
    }

    template<typename T>
    T get(const std::string& key) const {
        auto it = data.find(key);
        if (it == data.end())
            return T{};               // default-constructed if missing
        return std::any_cast<T>(it->second);  // throws std::bad_any_cast on a type mismatch
    }

    bool has(const std::string& key) const {
        return data.count(key) > 0;
    }
};

use std::any::Any;
use std::collections::HashMap;

// Blackboard: type-erased key-value store.
// Production code would use a fixed-layout struct for cache locality;
// the Any version here prioritizes flexibility for prototyping.
pub struct Blackboard {
    data: HashMap<String, Box<dyn Any>>,
}

impl Blackboard {
    pub fn new() -> Self {
        Blackboard { data: HashMap::new() }
    }

    pub fn set<T: 'static>(&mut self, key: &str, value: T) {
        self.data.insert(key.to_string(), Box::new(value));
    }

    pub fn get<T: 'static + Clone>(&self, key: &str) -> Option<T> {
        self.data.get(key)?.downcast_ref::<T>().cloned()
    }

    pub fn has(&self, key: &str) -> bool {
        self.data.contains_key(key)
    }
}

11Memory and reactive behavior

A guard is three ticks into a five-tick walk to its next waypoint when you step into view. Does it turn and fight on the next tick, or finish the walk first? That depends on whether the composites above the walk re-check their earlier children every tick, and each choice has a cost.

Two evaluation strategies:

• Reactive. The composite re-ticks its earlier children every tick, so a condition that has changed since last tick is seen immediately. The benefit is responsiveness: the agent reacts within one tick. The cost is that every condition to the left of the running child is re-evaluated every frame.
• With memory. The composite records which child was RUNNING and, on the next tick, skips straight past the children that already completed. The benefit is efficiency and not re-running work. The cost is missed priority changes: if an enemy appears while a patrol action is RUNNING, the combat branch is not reconsidered until the patrol resolves or something aborts it.

Production systems tend to mix the two. Unreal's BT does not re-evaluate from the root every tick: the active task keeps running until it finishes or a decorator aborts it, which behaves like memory composites throughout. Each decorator carries an Observer Aborts setting, and Epic's node reference defines the four values exactly: None, "Do not abort anything"; Self, "Abort self and any subtrees running under this node"; Lower Priority, "Abort any nodes to the right of this node"; Both, "Abort self, any subtrees running under this node, and any nodes to the right of this node."^[22] When the decorator's observed blackboard key changes, the configured abort fires and forces re-evaluation. That buys reactive behavior exactly where you asked for it, without re-checking every condition every frame.^[6]

An abort is not free, and the widget's log is where that shows. BehaviorTree.CPP defines an asynchronous action as one that "May return RUNNING instead of SUCCESS or FAILURE, when ticked" and "Can be stopped as fast as possible when the method halt() is invoked", and notes that "Frequently, the method halt() must be implemented by the developer"^[23]. When another node triggers a halt, "the onHalted() method is invoked"^[23], and whatever the action had accumulated is yours to unwind: a path request in flight, a partially played animation, a reserved cover slot. Aborting a MoveTo three ticks into five throws away three ticks of pathing. A condition that flickers can trigger that every frame, which is one reason abort types are chosen per decorator rather than set once for the whole tree.

Interruption is where BTs are weakest. Anguelov's slide at GDC 2017 says behavior trees "are inherently bad at two things: Transitions/Interruptions, Behavior Prioritization"^[11], and his written follow-up gives the mechanism for each^[14]. For transitions: event-driven BTs stopped re-evaluating the tree from the root every update, which fixed the cost, but "behavioral switches will not occur until the currently selected branch completes or fails". The usual repair is monitor nodes that poll conditions outside the running branch and reset the tree when one fires, and "the deeper in the tree we are the more monitors we have registered and therefore the greater the evaluation cost of the tree for each update". For prioritization: forcing one behavior ahead of the tree's fixed order typically takes a global monitor that sets override flags every branch must check, which adds implicit transitions between unrelated branches. In his words, "we have implicitly converted the BTs into an expensive, unreadable and error-prone finite state machine". That is the case for StateTree and the other hybrids in §16.

The widget below is a real evaluator: actions carry progress across ticks and return RUNNING until they finish, composites remember which child was running, and halt() throws that progress away and says so in the log. The Root and Patrol modes are switchable; Combat is a memory sequence, as an Unreal branch gated by a decorator would be.

12Utility-based selection

A guard sees two enemies. A selector picks the first branch whose conditions hold, so the guard attacks whichever enemy the designer's tree happens to check first. You want it to weigh how close and how dangerous each enemy is, which takes a score rather than a fixed order.

Standard selectors pick children by fixed left-to-right priority. Utility AI replaces that with a scoring function: each child is assigned a utility value (a float computed from threat level, distance, ammo count, health, cooldown timers), and the child with the highest score wins. Dave Mark's Infinite Axis Utility System, shown briefly in a shared GDC 2013 AI Summit talk and presented in full with Mike Lewis at GDC 2015 as the rebuilt AI for Guild Wars 2, is a widely cited formulation^[17].

A common hybrid keeps the tree for the coarse decision hierarchy (combat vs exploration vs dialogue) and uses utility scoring for the fine-grained choice within a category (which target to engage, which cover point to use). That avoids scoring everything against everything while still getting context-sensitive decisions where they matter.

Implementation: replace the Selector's left-to-right loop with a "score all children, sort by score, evaluate in score order" loop. The child evaluation still follows the standard tick protocol (SUCCESS/FAILURE/RUNNING), so the rest of the tree machinery is unchanged.

13BT vs GOAP vs HTN

Sometimes the designer doesn't want to author each decision. They want to say "kill the player" and have the soldier work out "pick up a gun, reload, flank" on its own, in whatever order the level allows. That's what a planner does, and two planning-based alternatives to behavior trees ship in production.

GOAP (Goal-Oriented Action Planning) gives every action preconditions and effects, such as "Reload needs ammo in the bag and leaves the gun loaded", and lets a search find a chain of actions that reaches the goal. HTN (Hierarchical Task Network) planning has designers write how each big task breaks into smaller ones, and a planner picks the breakdown that fits the current world state.

F.E.A.R. (Monolith, 2005) is the best-known shipped GOAP game. Jeff Orkin's GDC 2006 talk^[18] describes a system where the FSM has only three states (Goto, Animate, UseSmartObject) and A* plans over the action space to decide what to do. The soldiers flank, lay suppression fire and flush the player out with grenades; the cost lands on debugging, where "why did the AI throw a grenade?" means reconstructing the planner's search.

HTN planning (Humphreys, Game AI Pro^[19]) sits between BTs and GOAP. High-level tasks decompose into subtasks according to designer-authored rules. The planner picks decomposition paths based on world state. High Moon Studios shipped HTN in Transformers: Fall of Cybertron and reported it "considerably faster" than the GOAP system in the previous game, War for Cybertron, because the task hierarchy culls large parts of the search and the planner needs no heuristic sort.

Guerrilla's Horizon Zero Dawn uses a different hybrid for its machines: HTN planning combined with utility-based decisions, plus a group layer that coordinates herds of different machine classes (§14)^[16].

14Case studies

Shipped games show where the trade-offs above land in practice. Two of them, The Last of Us and Horizon Zero Dawn, don't drive their enemies with a behavior tree at all, and Hitman uses one only for the characters gameplay depends on.

Halo 2 / Halo 3 (Bungie)

Isla's GDC 2005 talk^[1] describes the Covenant AI as a behavior DAG (a directed acyclic graph rather than a strict tree, because one behavior subtree can occupy several places). Behaviors are self-contained modules picked by decision schemes such as prioritized lists, and extra machinery keeps the structure tractable: impulses that jump straight to a behavior, stimulus behaviors that event handlers insert at runtime, and behavior tagging that skips irrelevant relevancy checks. For Halo 3, Isla's GDC 2008 talk applies the prioritized-list idea one level up: encounter objectives form a tree of prioritized tasks that squads are poured into and filter down through, pulled up when a higher-priority task activates^[24].

Unreal Engine BT system

Epic describes Unreal's BTs as "event-driven to avoid doing unnecessary work every frame": instead of polling, the tree listens for events, and conditional decorators observe blackboard keys and abort when their values change^[6]. The editor's debugger highlights the active branch while the game runs, which makes it quick to see why an NPC chose a behavior. In place of a general Parallel composite, Unreal offers Simple Parallel, which runs a single main task alongside a background subtree; its Finish Mode decides whether the node ends as soon as the main task does, aborting the background, or waits for the background to finish^[22].

The Last of Us (Naughty Dog)

McIntosh's account of the human enemies^[15] describes an architecture built on FSMs rather than behavior trees. An NPC's top-level states, called skills (panic, advance, melee, gun combat, hide, investigate, flank and others), are prioritized: every frame each skill reports whether it wants to run, and the highest-priority one wins. Each skill runs its own state machine and pushes simpler behaviors, such as MoveToLocation, StandAndShoot and TakeCover, onto a behavior stack. Coordination goes through a global Combat Coordinator that hands out roles such as Flanker and OpportunisticShooter, so one NPC keeps shooting while the others take cover or flank. The per-frame skill check does the job a root selector does in a BT, with no tree.

Horizon Zero Dawn (Guerrilla Games)

The machines are not driven by behavior trees either. Guerrilla's own summary of their AI is "a combination of HTN planning and utility based decision making" plus "systems we developed to coordinate groups of agents"^[16], and the HTN planner grew out of the one Guerrilla had used since Killzone 2. Julian Berteling's GDC 2018 talk covers the move from Killzone's human enemies in corridors to more than 25 distinct character types in an open world, including navigation for agents of very different sizes. Thompson's write-up of the talks adds two details. Which machine gets to attack is balanced by a utility function over its state, its distance to the player, whether the player knows it is there and the damage it has taken. And objects that can trip a machine's sensors (the player, rocks, fired arrows, other machines) carry information packets that tell the machine what it sensed, so different classes (Watchers for reconnaissance, Grazers for acquisition, Thunderjaws for combat) can react differently to the same event.

Hitman (IO Interactive)

Hitman is usually cited for scale, and the crowd numbers come from Kasper Fauerby's GDC Europe 2012 talk on Absolution: around 1,200 crowd agents with 500 on screen, at roughly 2 ms of PS3 PPU time for crowd AI and steering^[12]. The crowd layer is not a behavior tree. Fauerby describes a state machine (idle, pending walk and walk for steering, plus gameplay states such as alert, prone and scared), and when a core mechanic such as close combat or a human shield needs a full character, a possession system upgrades the agent on demand to full NPC AI drawn from a small pool of invisible NPCs. The NPC layer is where the behavior trees are: Thompson's analysis of the 2016 game reports that its core AI "is reliant on behaviour trees", first devised for Absolution, with "over 300 active behaviour-tree-driven AI in a given level" and distant ones updated less often^[13]. The split is the lesson: BTs for the characters gameplay depends on, a far cheaper model for the crowd around them.

15Pitfalls

• Deep trees that are hard to read. Ten levels of nesting read about as well as spaghetti code. Keep the tree shallow and extract reusable subtrees into named sub-behaviors; Unreal lets a tree run another tree asset as a subtree, which keeps each graph manageable.
• Over-use of Parallel. Running multiple behaviors simultaneously creates interaction bugs. If a Parallel ticks both "move to cover" and "fire at enemy," the agent may try to shoot while running, producing broken animations. Use Parallel sparingly and test the interaction between concurrent children explicitly.
• Blackboard key collisions. Two subtrees write the same blackboard key ("target") without coordination: to the cover subtree it is a cover point, to the combat subtree an enemy. Fix: use namespaced keys ("combat.target", "cover.target") or separate blackboard scopes per subtree.
• Forgetting to handle RUNNING. An action that returns RUNNING but never transitions to SUCCESS or FAILURE blocks its branch forever (see the quiz in section 12). Every action that returns RUNNING must have a termination condition. Add TimeLimit decorators as safety nets.
• Priority starvation. A high-priority branch that succeeds every tick prevents lower-priority branches from ever running. If "CheckForEnemies" always succeeds (even when there's nothing to do about the enemy), everything below it starves. Conditions should return FAILURE when their associated behavior is not actionable, not just when the world state doesn't match.
• Condition/action ordering in sequences. Put conditions before actions. A sequence [Fire, HasAmmo?] fires first and checks ammo after, which is backwards. The tree reads left to right, so preconditions go on the left.

16What's next

Next in the series, Navmesh & Steering covers what happens after the tree picks a MoveTo: a path across a navigation mesh, then steering and local avoidance to follow it without walking into other agents. Beyond that, behavior trees themselves are still moving:

• Machine-learned BTs. Genetic programming and reinforcement learning can build or tune tree structures from experience, and Colledanchise and Ögren cover both^[3]. Learned trees are often hard to read, which undermines the debuggability advantage.
• Generated BTs. Trees built automatically from goal specifications sit between hand-authored BTs and full planning systems; the same book's planning chapter grows a BT by backchaining from a goal^[3].
• Event-driven BTs. Not new: Champandard and Dunstan point to Bulletstorm's event-driven BT (2011) and describe a scheduler that ticks only the active behaviors^[10], and Unreal has worked this way since UE4. They cut the per-tick cost for large NPC populations, and they bring the reactivity problem of §11 with them.
• State machines back in the mix. Unreal's StateTree "is a general-purpose hierarchical state machine that combines the Selectors from behavior trees with States and Transitions from state machines"^[7]. It runs state selection on demand, when a transition fires, rather than every update, which puts explicit transitions back where §11 says BTs are weakest. Epic has not deprecated Behavior Trees; the two ship side by side.
• BTs outside NPC AI. The same structure suits other reactive decision-making, such as dialogue selection, tutorial sequencing and cutscene scripting, and robot control, where most of the formal BT research now happens. The node types stay the same; the leaf actions change.

17Sources

1. Damian Isla. "Handling Complexity in the Halo 2 AI." GDC 2005 proceedings, Gamasutra, 11 March 2005. gamedeveloper.com. Describes the Halo 2 AI as "a hierarchical finite state machine (HFSM) or a behavior tree, or even more specifically, a behavior DAG", with prioritized-list and sequential decision schemes, impulses, stimulus behaviors and behavior tagging.
2. Alex J. Champandard. "Understanding Behavior Trees." AiGameDev.com, 6 September 2007. web.archive.org (the site is offline). Frames behaviors as HFSM states with their outgoing transitions removed, sequenced by the parent scope as in a programming language, with sequences and selectors as the standard composites and decorators on top.
3. Michele Colledanchise, Petter Ögren. Behavior Trees in Robotics and AI: An Introduction. Chapman & Hall/CRC, 2018; arXiv:1709.00084. arxiv.org. The strongest available reference for BT semantics, and the source for §11: reactive composites "keep sending ticks to the children to the left of a running child", composites with memory "always remember whether a child has returned Success or Failure", and memory nodes "can be considered to be syntactic sugar" since a memoryless tree plus auxiliary conditions reproduces them. Also formalizes why Condition nodes never return Running.
4. Alejandro Marzinotto, Michele Colledanchise, Christian Smith, Petter Ögren. "Towards a Unified Behavior Trees Framework for Robot Control." IEEE ICRA 2014. ieeexplore.ieee.org. Reviews the BT literature for its lack of "consistency and mathematical rigor", proposes a unified framework, and gives equivalence notions between BTs and controlled hybrid dynamical systems.
5. Matteo Iovino, Edvards Scukins, Jonathan Styrud, Petter Ögren, Christian Smith. "A survey of Behavior Trees in robotics and AI." Robotics and Autonomous Systems, 2022. sciencedirect.com. Survey of BT extensions, formal properties and applications across game AI and robotics. Source for the §1 quote on where the transition logic lives, and for the history crediting Mateas and Stern and Isla.
6. Epic Games. "Behavior Tree in Unreal Engine: Overview." Unreal Engine 5.8 documentation. dev.epicgames.com. States that Unreal BTs "are event-driven to avoid doing unnecessary work every frame", recommends conditional decorators over condition leaves, and replaces the general parallel composite with Simple Parallel, Services and Observer Aborts.
7. Epic Games. "Overview of State Tree in Unreal Engine." UE 5.8 Documentation. dev.epicgames.com. Epic's definition, quoted in §16: StateTree "is a general-purpose hierarchical state machine that combines the Selectors from behavior trees with States and Transitions from state machines", selecting states on demand through transitions. The page does not deprecate Behavior Trees or recommend StateTree over them.
8. Unity Technologies. Unity Behavior (com.unity.behavior) manual and changelog. docs.unity3d.com. "A visual tool for authoring behaviors that control non-player characters (NPCs), gameplay logic, objects, and scene interactions". The changelog dates 1.0.0 to 17 September 2024 and 1.0.16 to 26 May 2026. Unity's own term is behavior graph, because "branches can merge back", so it is BT-like rather than strictly a tree.
9. Davide Faconti et al. BehaviorTree.CPP (v4.x, MIT) and its documentation. behaviortree.dev. A widely used open-source BT runtime, and the clearest statement that re-tick policy is per node type: its Sequences page tabulates what Sequence, ReactiveSequence and SequenceWithMemory do when a child returns FAILURE or RUNNING (restart or tick again), with AsyncSequence behaving like Sequence but yielding after each successful child.
10. Alex J. Champandard and Philip Dunstan. "The Behavior Tree Starter Kit." Game AI Pro, Chapter 6. gameaipro.com. Builds a minimal BT runtime step by step; its open-source Behavior Tree Starter Kit is "intended to serve as an example of a working BT for you to learn from". Also defines first- and second-generation BTs and describes event-driven traversal with a behavior scheduler, citing Bulletstorm's event-driven version.
11. Mika Vehkala (Remedy), Bobby Anguelov (WB Games Montreal), Ben Weber (Twitch). "AI Arborist: Proper Cultivation and Care for Your Behavior Trees." GDC 2017. gdcvault.com (PDF, free). Studio-agnostic guidance on keeping large behavior trees maintainable. Source for the slide in Anguelov's section, quoted in §11, that BTs "are inherently bad at two things: Transitions/Interruptions, Behavior Prioritization".
12. Kasper Fauerby. "Crowds in Hitman: Absolution." GDC Europe 2012, IO Interactive. gdcvault.com (PDF, free). Source for the Hitman crowd figures in §14: "Around 1200 agents per crowd, 500 on-screen", and a PS3 budget of PPU 5 ms with crowd AI and steering at about 2 ms. Also documents the crowd's state machine and the possession system that upgrades an agent on demand to full NPC AI from a small pool of invisible NPCs.
13. Tommy Thompson. "The AI of Hitman (2016)." Game Developer, 7 August 2019. gamedeveloper.com. Secondary analysis drawing on IO Interactive conference talks; cited in §13 and §14 for the claims that the core NPC AI "is reliant on behaviour trees", first devised for Absolution, with "over 300 active behaviour-tree-driven AI in a given level" and distant AI updated less often.
14. Bobby Anguelov. "Behavior Trees: Breaking the Cycle of Misuse." 2020. takinginitiative.wordpress.com (PDF). The written treatment of the reactivity and prioritization problems in §11, by one of the GDC 2017 speakers. Event-driven BTs fixed the cost of re-evaluating from the root, but "behavioral switches will not occur until the currently selected branch completes or fails"; monitor nodes that "continuously poll the environment" restore it at a cost that grows with depth; and global override monitors for prioritization turn the tree into "an expensive, unreadable and error-prone finite state machine".
15. Travis McIntosh. "The Last of Us: Human Enemy AI." GDC 2014. gdcvault.com. Written up as "Human Enemy AI in The Last of Us," Game AI Pro 2, Chapter 34, 2015: gameaipro.com (PDF). Section 34.5 describes the prioritized skills in an FSM, each with its own state machine, and the behavior stack; the Combat Coordinator and its roles follow.
16. Julian Berteling. "Beyond 'Killzone': Creating New AI Systems for 'Horizon Zero Dawn'." GDC 2018. gdcvault.com. With Guerrilla Games, "The AI of Horizon Zero Dawn," Game AI North, 2017 (slides and abstract): guerrilla-games.com, the source of the "combination of HTN planning and utility based decision making" quote; and Tommy Thompson, "Behind the AI of Horizon Zero Dawn," Parts 1 and 2, Game Developer, 2019, which summarizes both talks and is the source for the attack-selection utility and the information packets.
17. Luke Dicken, Dino Dini, Dave Mark. "Architecture Tricks: Managing Behaviors in Time, Space, and Depth." GDC AI Summit, 2013. gdcvault.com. Mark's segment introduces the Infinite Axis Utility System, which he and Mike Lewis presented in full at GDC 2015 in "Building a Better Centaur: AI at Massive Scale," on the AI rebuild for Guild Wars 2.
18. Jeff Orkin. "Three States and a Plan: The A.I. of F.E.A.R." GDC 2006. gamedevs.org. Goal-Oriented Action Planning. The FSM has three states; A* plans over the action space. Emergent flanking, suppression, and grenade-flushing behavior.
19. Troy Humphreys. "Exploring HTN Planners Through Example." Game AI Pro, Chapter 12. gameaipro.com. Total-order forward decomposition planner used in Transformers: Fall of Cybertron, which the chapter reports as "considerably faster" than the GOAP system in War for Cybertron.
20. Davide Faconti et al. "Parallel Nodes." BehaviorTree.CPP 4.8 documentation, and src/controls/parallel_node.cpp. behaviortree.dev. Supports §8: the success_count and failure_count ports with their -1 and 1 defaults, "It is completed when either the SUCCESS or FAILURE threshold is reached. Any remaining running children are halted", and ParallelAll, which "always executes ALL children to completion. It never halts children early." The source adds the second failure route the docs omit, (children_count - failure_count_) < required_success_count, and the completed_list_ that keeps a resolved child from being re-ticked.
21. Daniel Stonier et al. "Composites." py_trees documentation (devel branch). py-trees.readthedocs.io. The counterexample cited in §8: "A parallel ticks every child every time the parallel is itself ticked", with the SuccessOnAll and SuccessOnSelected policies optionally "synchronised in which case children that tick with SUCCESS will be skipped on subsequent ticks."
22. Epic Games. "Behavior Tree Node Reference: Decorators" and "...: Composites." Unreal Engine 5 documentation. Decorators, Composites. The verbatim Observer Aborts definitions quoted in §11 (None, Self, Lower Priority and Both); decorators "are attached to either a Composite or a Task node"; and Simple Parallel's Finish Mode (Immediate or Delayed).
23. Davide Faconti et al. "Asynchronous Actions." BehaviorTree.CPP 4.8 documentation. behaviortree.dev. The halt contract used in §11: an asynchronous node "May return RUNNING instead of SUCCESS or FAILURE, when ticked" and "Can be stopped as fast as possible when the method halt() is invoked"; "Frequently, the method halt() must be implemented by the developer", and when another node triggers a halt "the onHalted() method is invoked."
24. Damián Isla. "Building a Better Battle: The Halo 3 AI Objectives System." GDC 2008. gdcvault.com. Builds on the Halo 2 behavior tree's prioritized-list scheme for encounter design: "A Tree of Prioritized Tasks" into which squads are poured and filter down, pulled up when a higher-priority task activates.