Module 11 · Classical control

FSMs and Behavior Trees

What actually drives NPCs in shipped games — and why the "boring" classics beat ML at control.

write-up~15 min

The gist in 20 seconds

FSM is a finite state machine: the NPC is in one of several states (Idle/Chase/Attack/Flee), transitions fire on events. Simple, deterministic, O(1) — but at 30+ states it turns into spaghetti. A Behavior Tree is a hierarchy of Sequence/Selector/decorators/actions, traversed top-down every frame; a node returns Success/Failure/Running. BTs scale, get reused and are visible in an editor — which is why they've been the industry standard since Halo 2 (2004).

FSM — the finite state machine

The NPC is in one state; a transition is triggered by an event (spotted the player, took damage, the enemy died). A combat example:

Combat FSM transitions

Idle   → Chase   (player within sight radius)
Chase  → Attack  (player within melee radius)
Attack → Chase   (player moved away)
Attack → Flee    (health < 25%)
Flee   → Idle    (distance > sight radius)

With few states you can see what the NPC is doing right now. That's both the strength and the ceiling of an FSM.

Strengths: simple, debuggable (you can see the state), deterministic (good for replays), O(1)/frame, designer-friendly. Weaknesses: fragile past 30+ states; no emergence (if you didn't code it, it won't happen); 100 NPCs with complex FSMs = unmaintainable.

Behavior Tree — the industry standard

A DAG of hierarchical decisions, traversed depth-first left to right. Nodes: composites (Sequence — until the first failure; Selector — until the first success; Parallel), decorators (Inverter, Repeater, Condition guard), actions (the leaves). Each returns Success/Failure/Running.

Halo 2 Elite — a combat BT (simplified) tree

Root (Parallel)
 ├─ Sequence: Combat
 │   ├─ Condition: enemy visible?
 │   ├─ Selector: attack strategy
 │   │   ├─ Sequence: melee (in range? → Attack)
 │   │   ├─ Sequence: grenade (in range? have one? → Throw)
 │   │   └─ Sequence: ranged (have a weapon? → Shoot)
 │   └─ Action: tactical movement
 └─ Sequence: Patrol (Condition: enemy not visible)

Strengths: hierarchy (strategy + tactics), reusable subtrees, visualizable in an editor, emergence from subtrees interacting. Weaknesses: still hand-authored; traversing a complex tree every frame costs money. Halo 2 (2004) shipped on BTs, Bungie wrote the postmortem — and off it went: BTs are now in Unreal, Unity, Godot.

🕹 Games to play — and what to notice

One problem — "decide what the NPC does" — at three levels of complexity: a greedy state machine at a junction, a behavior tree, a planner. For each: how it's built and what to play to see it with your own hands.

Pac-Man 1980 · an FSM per ghost

The bare minimum: each ghost has a tiny state machine of modes — Scatter / Chase / Frightened (a global timer switches them) — and inside Chase, a greedy choice of tile toward its own target. No tree, no planning: four simple FSMs produce an emergent "dragnet" because the targets differ (Blinky targets Pac-Man's tile, Pinky aims 4 ahead).

🎮 Play: fire up Pac-Man and learn the rhythm — the ghosts all reverse at once when the timer flips Scatter↔Chase (that's an FSM state transition you can see with your eyes). Eat a power pellet → they all go to Frightened. You are literally watching a finite state machine.

Halo 2 / 3 2004 · Behavior Tree, the turning point

The game that made BTs an industry. An Elite's behavior is a tree: a Selector picks the strategy (melee / grenade / shooting / retreat), a Sequence checks the conditions. The visible result is enemies that fall back under fire, look for cover and regroup instead of charging blindly.

🎮 Play: in Halo 2/3 (or MCC) pin an Elite down with heavy fire — watch it break the distance and hide, and see a squadmate panic and run once it's beaten down. That's a Selector descending through priorities and Condition nodes on health — behavior legible from the outside.

F.E.A.R. 2005 · GOAP, planning

The next level up: not "a tree written in advance" but a planner. Jeff Orkin's GOAP (Monolith) adapts STRIPS planning from 1971: the NPC has a goal (kill the player) and actions with preconditions/effects; the planner builds a chain on the fly to fit the situation. Hence the legendary replica soldiers: flanking, suppression, flipping tables into cover — none of it scripted, all of it derived from goals and available actions.

🎮 Play: in F.E.A.R., get into a firefight in a room with tables/windows and listen to the callouts ("Flush him out!", "Flanking!") — they're voicing the plan. Block one route and watch the enemies replan the flank. That's GOAP searching for a new chain of actions in real time.

Deep end: the automata theory behind FSM and BTskippable

Moore vs Mealy

In a Moore machine the output depends only on the state; in a Mealy machine it depends on the state and the input. Game FSMs are a hybrid: behavior is attached to the state (Moore style), but transitions carry actions (Mealy style). Mealy needs fewer states for the same behavior.

Expressiveness: FSM ⇔ regular languages

A finite automaton recognizes exactly the regular languages. It has no stack → it can't count without bound and can't handle arbitrarily nested/recursive behavior (you'd need a pushdown automaton). In practice: a pure FSM doesn't "remember" how many times something happened without an explicit state for every counter.

Why a BT and not one giant switch

A flat FSM encoding k independent boolean conditions needs up to 2^k states (state explosion). Hierarchical machines (HFSM) and BTs factor that combinatorics through composition — that's their real win, not "more computational power".

BT semantics as boolean algebra

Sequence = short-circuit AND (∧), Selector = OR (∨), Inverter = ¬. A BT without the Running status is a monotone and-or tree over conditions, i.e. the evaluation of a boolean function. The Running status adds time, turning the tree into a transducer over ticks. A tick is O(number of nodes) in the worst case; a reactive BT re-traverses from the root every frame (unlike an event-driven FSM).

Deep end · engineering: where game-AI bugs actually come fromskippable

Tools matter more than theory: 90% of the time goes to debugging "why is the NPC stuck". Visual debugging of the current state / active BT node saves days.
Data-driven authoring: trees/transition tables live in data, not in code — so a designer can edit them without a rebuild. The "code vs data" boundary is a key architectural decision.
Decoupling from the frame rate: AI logic often ticks slower than rendering (10–20 Hz) and is amortized across frames — 200 NPCs with BTs at 60 Hz will blow the frame.
Bug source #1 is state: a desynced blackboard, races between perception and decision, "stuck" transitions. FSM determinism is a lifesaver here for reproduction.

Analogy

An FSM is a traffic light: hard states, rule-based transitions, instantly legible. A BT is a job description with priorities: "first check whether an enemy is visible; if so, pick the best attack; otherwise patrol". The manager (the Selector) works down the list until something "fires".

Why it matters

This is the base that 95% of game AI rests on. Before dreaming about LLM NPCs and RL you need to know this — because control (when the NPC shoots, runs, starts talking) will almost always stay on an FSM/BT, even if the content (the lines) is generated by an LLM.

🔁 Beyond games — where this transfers

FSMs and behavior trees are an explicit model of state/behavior (finite automata, and-or decision trees). They're everywhere:

Backend / orchestration: workflow engines (Temporal, Step Functions) = state machines; protocol automata (TCP), regexes, parsers — all FSMs.

ML / AI: agent loops and tool use are BTs/FSMs on top of an LLM (a decision tree with conditions and fallbacks); constrained/structured decoding = a finite automaton over tokens (a grammar guarantees valid JSON). Markov chains = probabilistic FSMs.

UI / systems: component states (XState), retry/circuit breaker — state machines.

Principle: an explicit model of state is debuggable and testable; wherever there is "behavior by mode", there is an FSM/BT, in any field.

🔧 Run it and poke at it — on your home machine

What to play is above (🕹). Here it's about getting your hands into the tree:

🔧 Poke at it (debug) ~40 min, Godot

Open Godot and install any BehaviorTree add-on (LimboAI), or build the combat FSM from the lesson (Idle/Chase/Attack/Flee). Turn on visual debugging of the active node/state — watch which leaf ticks each frame. Break it on purpose: remove the exit condition from Attack and the NPC will get stuck in that state; add two competing transitions and you'll get flickering between states.

🧪 Test it (with QA eyes) ~15 min

Hunt for the classic game-AI bugs: a "stuck" transition, a desynced blackboard (perception says "enemy visible", the action says otherwise), oscillation between two states at the edge of a radius, a frozen NPC where no branch returned success. That's exactly the top bug source from the deep-end tab.

Checklist: saw the active BT node / FSM state ticking; broke a transition and caught the "stuck" case; found at least one oscillation or blackboard desync.

Connections

Pathfinding: A* and NavMesh — the "move toward the player" action from an FSM/BT calls pathfinding under the hood.

contrast

Classical vs ML — why FSM/BT (determinism, debuggability) beat RL for NPC control.

LLM NPCs — an LLM doesn't replace the FSM/BT, it lives on top: control on the classics, dialogue on the LLM.

Questions worth asking

Are FSMs and BTs equivalent in expressiveness?

By computational class — practically yes: one BT tick computes a function expressible by a large enough FSM (a BT is a structured way to author a big automaton). The BT's win is compositionality and readability, not power. Both go beyond regular languages only once you add unbounded memory (a blackboard) — at which point it's effectively a program.

Why not one giant switch covering every case?

State explosion: k independent boolean conditions → up to 2^k states and transitions by hand, plus Moore/Mealy confusion and unmaintainability. BTs/HFSMs factor the tree through composition — you write O(k) nodes instead of 2^k states. The reason is structural, not a matter of taste.

Is Sequence/Selector literally an and-or tree?

Yes: Sequence = ∧ (short-circuiting on the first Failure), Selector = ∨ (on the first Success), Inverter = ¬. Without the Running status a BT is a monotone and-or tree over conditions computing a boolean function. Running adds time: the tree becomes a transducer that remembers which leaf is "in progress".

How does an HFSM differ from a BT if both factor state?

An HFSM is nested states with explicit transitions (a graph); a BT is composites + return codes, with implicit flow (a traversal every tick). An HFSM is more compact for "modes" with clear transitions; a BT is better for priorities of the "try A, otherwise B" kind. In practice they get mixed (a BT with states as leaves).

Is an FSM a Markov chain, and what if the transitions are probabilistic?

Then it's a Markov chain in its pure form (the next state ~ a distribution given the current one); you can estimate and optimize it. Add rewards and actions and you have an MDP, and you're already in RL. A direct bridge from the "boring" FSM to the ML part of the module.