Behavior Trees

01Why behavior trees

Every NPC in a shipped AAA title makes decisions. Patrol a route, chase a target, take cover, reload, call for backup, retreat when hurt. In the early 2000s, those decisions lived in finite state machines: one state per behavior, explicit transitions between them. The approach works at five states. At fifteen it becomes unmanageable. At fifty it is a maintenance hazard that no one on the team wants to touch.

Behavior trees solved this by replacing the explicit-transition model with a tree of modular nodes evaluated top-down every frame. The survey literature puts the same point 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 new behavior means grafting a subtree onto an existing branch, not wiring transitions to every other state. Isla's GDC 2005 talk on the Halo 2 Covenant AI^[1] is the talk the industry treats as the starting point, though Isla claims no priority and calls the architecture a "hierarchical finite state machine (HFSM) or a behavior tree, or even more specifically, a behavior DAG". Unreal ships a behavior tree editor^[6] and, since 2022, StateTree 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.

The core advantages over FSMs:

• 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 O(1) work. Adding a state to an FSM is O(n) transitions in the worst case.
• 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 stays in its current state until an explicit transition fires, which means missed opportunities and stale decisions.

02A short history

Behavior trees emerged from the intersection of game AI engineering and robotics research. The timeline:

03The FSM problem

An FSM with n states has up to n(n - 1) directed transitions. Three states: 6 transitions. Eight states: 56. Not every pair needs a transition in practice, but every time a designer adds a new state, they have to answer "can the agent transition here from every existing state, and can it transition from here to every existing state?" Missing a transition is a bug (agent gets stuck in a state). Adding a redundant one is also a bug (agent escapes a state it shouldn't leave). The cost of answering the question is O(n) per new state; the total is O(n²).

Hierarchical FSMs (HFSMs) mitigate this by nesting sub-FSMs inside states, but the transition explosion still applies within each level. Pushdown automata (PDA-style stacks of states) help with "go to X, then return," but the core problem remains: the interaction between states is encoded in transitions, and transitions scale quadratically.

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

04Tree structure and tick

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 have multiple children and control evaluation order. Sequence, Selector, and Parallel.
• Decorator nodes have exactly one child and modify its result. Inverter, Repeat, Cooldown.
• 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. Children tick their children in turn. The result propagates 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 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 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 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's BT system uses decorators differently from the academic standard. In Unreal, decorators attach to composite nodes as auxiliary nodes rather than being tree nodes in their own right. The effect is the same (the decorator gates or modifies the composite's evaluation), but the visual layout in the editor differs. Decorators in Unreal also serve as abort triggers: a decorator can specify that when its condition changes, it aborts the subtree below and forces re-evaluation.^[6]

08Parallel nodes

A Parallel node ticks its children in the same tick rather than in sequence. Whether it re-ticks a child that has already returned is an implementation choice rather than a property of the idea, and the two best-documented runtimes disagree. BehaviorTree.CPP keeps a completed set and skips those children until the node resets^[20]. py_trees 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. Two success policies are common, and real implementations generalize both into a threshold (succeed once k children have):

• Succeed-on-all. Returns SUCCESS only when every child has returned SUCCESS. Returns FAILURE if any child fails. The "all must pass" gate.
• Succeed-on-one. Returns SUCCESS as soon as any child succeeds. Returns FAILURE only if all children fail. The "any will do" gate.

A typical use: [Parallel: MoveTo(cover), PlayAnimation(sprint)]. The agent moves and plays the sprint animation at the same time. When MoveTo finishes, the parallel node reports SUCCESS and the animation can be interrupted.

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

Nodes in a behavior tree need to share data: the target entity, its last-known position, the agent's health, ammo count, whether a perception query returned a result. The blackboard is a key-value store that serves this purpose. Every node can read from and write to the blackboard. The blackboard is scoped to one agent (one blackboard instance per entity), though some systems allow 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, Enum) 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, and watch the tree re-evaluate in real time.

10Actions and conditions

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 each of those frames. 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.

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.
class Sequence : public Node {
    std::vector<std::unique_ptr<Node>> children;
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();
    }

    Status tick() override {
        for (auto& child : children) {
            Status result = child->tick();
            if (result != Status::Success)
                return result;  // FAILURE or RUNNING propagates up
        }
        return Status::Success;  // all children succeeded
    }
};

// Selector: OR logic. Succeed on first success, fail when all fail.
class Selector : public Node {
    std::vector<std::unique_ptr<Node>> children;
public:
    void addChild(std::unique_ptr<Node> child) {
        children.push_back(std::move(child));
    }

    Status tick() override {
        for (auto& child : children) {
            Status result = child->tick();
            if (result != Status::Failure)
                return result;  // SUCCESS or RUNNING propagates up
        }
        return Status::Failure;  // all children failed
    }
};

// Stand-ins for the engine types. Blackboard gets its real definition
// in §9; 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, and
// it is what the real crates (BehaviorTree.CPP, bonsai-bt) do too.
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.
pub struct Sequence {
    children: Vec<Box<dyn Node>>,
}

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

impl Node for Sequence {
    fn tick(&mut self, context: &mut Context) -> Status {
        for child in &mut self.children {
            let result = child.tick(context);
            if result != Status::Success {
                return result;  // FAILURE or RUNNING propagates up
            }
        }
        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); }
    }
}

// Selector: OR logic. Succeed on first success, fail when all fail.
pub struct Selector {
    children: Vec<Box<dyn Node>>,
}

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

impl Node for Selector {
    fn tick(&mut self, context: &mut Context) -> Status {
        for child in &mut self.children {
            let result = child.tick(context);
            if result != Status::Failure {
                return result;  // SUCCESS or RUNNING propagates up
            }
        }
        Status::Failure  // all children failed
    }

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

Code: a concrete action (MoveTo with RUNNING)

// Carried over from §4 and §9, restated so this pane stands alone.
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;
        }
    }
};

// Carried over from §4 and §9, restated so this pane stands alone.
#[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);
    }

    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

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.

Most production systems use a hybrid. Unreal's BT is memory-based by default, but a 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. Doing that every frame because a condition is jittering is why abort types are set per decorator rather than as one global switch.

Worth being blunt about how hard this area is, because it is where BTs are weakest rather than a detail. Anguelov's assessment from the GDC 2017 stage is that behavior trees "are inherently bad at two things: Transitions/Interruptions, Behavior Prioritization"^[11], and his written follow-up traces the reason: event-driven BTs stopped re-evaluating the whole tree every frame, which fixed the cost but broke reactivity, and the standard repair, monitor nodes that watch conditions from outside the current branch, scales badly because "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"^[14]. Push that far enough and, in his words, you have "implicitly converted the BTs into an expensive, unreadable and error-prone finite state machine". That is the honest case for StateTree and the hybrids in §16.

The widget is the whole matrix, and it is a real evaluator: actions carry progress across ticks and return RUNNING until they finish, composites remember which child was running, and halt() genuinely throws that progress away and says so in the log.

12Utility-based selection

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 (GDC AI Summit 2013, refined at GDC 2015^[17]) is the canonical reference for this approach.

Hybrid BT+Utility trees are common in production. The tree structure handles the coarse decision hierarchy (combat vs exploration vs dialogue), while utility scoring handles the fine-grained choice within a category (which target to engage, which cover point to use). This avoids the combinatorial explosion of scoring everything against everything, while still getting smooth, 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

Behavior trees are not the only game AI architecture. Two planning-based alternatives ship in production: GOAP (Goal-Oriented Action Planning) and HTN (Hierarchical Task Networks).

F.E.A.R. (Monolith, 2005) is the canonical GOAP reference. 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 result is impressive emergent behavior (soldiers flanking, suppressing, flushing with grenades) but the debugging story is harder: "why did the AI throw a grenade?" requires replaying 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 that it was faster than the GOAP system used in the previous game (War for Cybertron).

Guerrilla Games used a different hybrid for Horizon Zero Dawn: HTN planning combined with utility-based decisions for the machine AI, handling both the high-level behavior hierarchy and the fine-grained machine ecology where different machine classes (Acquisition, Transport, Combat, Reconnaissance) coordinate in groups.^[16]

14Case studies

Halo 2 / Halo 3 (Bungie)

Isla's GDC 2005 talk^[1] describes the Covenant AI as a behavior DAG (directed acyclic graph, not strictly a tree, because some behaviors are shared across branches). The key insight: define behaviors as self-contained modules, evaluated in priority order. The system let Bungie scale from a handful of AI types in Halo 1 to the diverse enemy roster in Halo 2 without the codebase becoming unmaintainable. Halo 3 refined the architecture further, adding better squad-level coordination.

Unreal Engine BT system

Unreal's BT^[6] is event-driven rather than polling-based. Decorators observe blackboard keys and trigger re-evaluation only when observed values change. This reduces CPU cost on large NPC counts by avoiding the per-tick full-tree walk. The system includes a visual debugger that highlights the active branch in real time, making it straightforward to diagnose why an NPC chose a particular behavior. Unreal's "Simple Parallel" node replaces the academic Parallel composite: it ticks a primary task and a background task simultaneously, finishing when the primary finishes.

The Last of Us (Naughty Dog)

Naughty Dog's enemy AI^[15] uses a priority-stacked skill/behavior system built on FSMs rather than behavior trees. Each NPC has a stack of "skills" (combat, investigate, patrol) prioritized by context. Low-level "behaviors" within each skill are FSM-driven. The architecture handles squad coordination (one suppresses while others advance) through a separate tactical layer. This is a useful contrast: TLOU shipped one of the most praised enemy AI systems in AAA without behavior trees, demonstrating that BTs are not the only viable approach.

Horizon Zero Dawn (Guerrilla Games)

Julian Berteling's GDC 2018 talk^[16] covers Guerrilla's transition from Killzone's corridor-shooter AI to Horizon's open-world navigation and animation systems. The machine AI uses HTN planning for high-level decisions and utility scoring for target selection, not behavior trees. Different machine classes (Watchers for reconnaissance, Grazers for acquisition, Thunderjaws for combat) have distinct behavior profiles and coordinate in mixed-species groups. The system uses "information packets" attached to stimuli (arrows, rocks, player movement) that feed into machine sensors, allowing each class to react differently to the same event.

Hitman (IO Interactive)

Hitman is usually cited for scale, and the real 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 CPU time for crowd AI and steering^[12]. The architectural detail worth taking away is that the crowd layer is not a behavior tree. Fauerby describes a deliberately lightweight state machine (idle, pending walk, walk, plus gameplay states like alert and scared), with agents "possessed" and upgraded to full NPC AI on demand when the player gets close enough for it to matter. Secondary reporting describes the core NPC AI as behavior-tree driven^[13]. That split is the lesson: BTs for the handful of agents the player is actually interacting with, something cheaper for the other 1,150.

15Pitfalls

• Deep trees that are hard to read. A tree with 10 levels of nesting is no better than spaghetti code. Keep the tree shallow. Extract reusable subtrees into named sub-behaviors. Unreal lets you reference sub-trees by asset, which keeps the visual 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 writing to the same blackboard key ("target") without coordination. Agent A's "target" is a cover point; Agent B's "target" is 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 the tree 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

• Machine-learned BTs. Using reinforcement learning or genetic programming to evolve tree structures from gameplay data. Colledanchise and Ogren cover this in their textbook^[3]. The challenge is that learned trees are often unreadable, which undermines the debuggability advantage.
• Procedural BT generation. Generating trees from designer-authored constraints or goal specifications. A middle ground between hand-crafted BTs and full planning systems.
• Event-driven BTs. Unreal already does this. The pure-academic model (tick everything from root every frame) is being replaced by event-driven evaluation where only branches affected by a state change are re-evaluated. Reduces CPU cost for large NPC populations.
• BTs for non-AI systems. Behavior trees work for any reactive decision-making: dialogue selection, tutorial sequencing, cutscene scripting, procedural audio mixing. The node types are the same; the leaf actions change.

17Sources

1. Damian Isla. "Handling Complexity in the Halo 2 AI." GDC 2005 / Gamasutra. gamedeveloper.com. The foundational talk on behavior-centric AI architecture that kicked off industry adoption of behavior trees. Describes the Halo 2 Covenant AI as a behavior DAG with priority-ordered evaluation.
2. Alex J. Champandard. "Understanding Behavior Trees." AiGameDev.com, 2007. Formalizes the node taxonomy (composite, decorator, leaf) and names the Sequence/Selector pair. The article that standardized BT terminology for the game AI community.
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 Ogren. "Towards a Unified Behavior Trees Framework for Robot Control." IEEE ICRA 2014. ieeexplore.ieee.org. Formal semantics for BTs grounded in hybrid dynamical systems. Bridges the gap between game AI's informal descriptions and robotics' need for mathematical rigor.
5. Matteo Iovino, Edvards Scukins, Jonathan Styrud, Petter Ogren, Christian Smith. "A survey of Behavior Trees in robotics and AI." Robotics and Autonomous Systems, 2022. sciencedirect.com. Comprehensive survey of BT extensions, formal properties, and applications across game AI and robotics. Covers reactive, memory, and hybrid evaluation strategies.
6. Epic Games. "Behavior Trees in Unreal Engine." Unreal Engine 5 documentation. dev.epicgames.com. Documents the visual BT editor, blackboard asset system, decorator-based abort triggers, and the event-driven evaluation model.
7. Epic Games. "Overview of State Tree in Unreal Engine." UE 5.8 Documentation. dev.epicgames.com. Epic's definition, quoted in §1 and §16: StateTree "is a general-purpose hierarchical state machine that combines the Selectors from behavior trees with States and Transitions from state machines." Note Epic publishes no guidance recommending StateTree over Behavior Trees, and has not deprecated the latter, which is why this tutorial does not claim it has.
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." Version 1.0.0 shipped 13 September 2024 for Unity 6; 1.0.16 dated May 2026. Unity's own term is behavior graph, and the graph permits merges, 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. The de-facto open-source BT runtime, and the clearest statement that re-tick policy is per node type: it ships Sequence, ReactiveSequence, AsyncSequence and SequenceWithMemory as four separate control nodes with four different rules for what happens when a child returns FAILURE or RUNNING.
10. Alex J. Champandard and Philip Dunstan. "The Behavior Tree Starter Kit." Game AI Pro, Chapter 6. gameaipro.com. Reference implementation of a minimal BT runtime. The code most studios start from when building a custom BT system.
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. Supports the §11 and §15 material on interruption and prioritization, including the claim that BTs "are inherently bad at two things: Transitions/Interruptions, Behavior Prioritization". It names no shipped title, so it supports no game-specific claim.
12. Kasper Fauerby. "Crowds in Hitman: Absolution." GDC Europe 2012, IO Interactive. gdcvault.com (PDF, free). The real source for the Hitman crowd figures in §14: "Around 1200 agents per crowd, 500 on-screen", at roughly 2 ms PS3 CPU for crowd AI and steering. Also documents that the crowd layer is a lightweight state machine with on-demand "possession" upgrading an agent to full NPC AI, not a behavior tree.
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 §14 only for the claim that Hitman's core NPC AI is behavior-tree driven, which no IOI-authored public document states directly.
14. Bobby Anguelov. "Behavior Trees: Breaking the Cycle of Misuse." 2020. takinginitiative.wordpress.com (PDF). The written treatment of the abort and reactivity problems in §11, from the author of the GDC 2017 talk. Names the trade-off directly: event-driven BTs fixed the cost of re-evaluating from the root but created a reactivity problem, and the usual fix, monitor nodes, means "the deeper in the tree we are the more monitors we have registered and therefore the greater the evaluation cost".
15. Max Dyckhoff. "Ellie: Buddy AI in The Last of Us" and Travis McIntosh. "The Last of Us: Human Enemy AI." GDC 2014. gdcvault.com. Priority-stacked skill/behavior system built on FSMs, not behavior trees. Described in McIntosh's Game AI Pro 2 chapter (Ch. 34). A useful contrast showing AAA-quality AI without BTs.
16. Julian Berteling. "Beyond 'Killzone': Creating New AI Systems for 'Horizon Zero Dawn'." GDC 2018. gdcvault.com. HTN planning plus utility scoring for machine ecology. Describes how different machine classes coordinate in mixed-species groups using information-packet-based stimulus systems.
17. Dave Mark. "Architecture Tricks: Managing Behaviors in Time, Space, and Depth." GDC AI Summit, 2013. gdcvault.com. Introduces the Infinite Axis Utility System. The canonical reference for utility-based AI scoring, later refined at GDC 2015 with Mike Lewis.
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. Faster than GOAP for the same game's previous title.
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." Unreal Engine 5 documentation. dev.epicgames.com. The verbatim Observer Aborts definitions quoted in §11: None, Self, Lower Priority and Both.
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."