Behavior Trees for NPC AI — Design, Tick, and Blackboard

1. Why FSMs Break Down

A Finite State Machine models AI as a graph: nodes are states, edges are transitions. This works for simple characters but degrades fast:

• State explosion: N behaviours require O(N²) transitions to cover every state-to-state path.
• No reuse: You can't easily share the "retreat to cover when low health" logic between an infantry unit and a mage — each FSM encodes it independently.
• Hard to prioritise: What should an NPC do when simultaneously "low ammo" AND "enemy spotted" AND "wounded"? FSM priority is implicit in edge ordering, hard to audit.

2. The Four Core Node Types

3. Tick Protocol and Status Flow

4. The Blackboard — Shared Memory

The Blackboard is a shared key-value store that decouples perception, reasoning, and action. Nodes read and write the Blackboard instead of calling each other directly.

5. Decorators and Subtree Reuse

6. BT vs FSM — Design Trade-offs

7. JavaScript Behavior Tree Engine

// Minimal synchronous Behavior Tree engine
const Status = Object.freeze({ SUCCESS: 'S', FAILURE: 'F', RUNNING: 'R' });

class Sequence {
  constructor(...children) { this.children = children; }
  tick(bb) {
    for (const c of this.children) {
      const s = c.tick(bb);
      if (s !== Status.SUCCESS) return s;
    }
    return Status.SUCCESS;
  }
}

class Selector {
  constructor(...children) { this.children = children; }
  tick(bb) {
    for (const c of this.children) {
      const s = c.tick(bb);
      if (s !== Status.FAILURE) return s;
    }
    return Status.FAILURE;
  }
}

class Action {
  constructor(fn) { this.fn = fn; }
  tick(bb) { return this.fn(bb); }
}

class Condition {
  constructor(pred) { this.pred = pred; }
  tick(bb) { return this.pred(bb) ? Status.SUCCESS : Status.FAILURE; }
}

class Inverter {
  constructor(child) { this.child = child; }
  tick(bb) {
    const s = this.child.tick(bb);
    if (s === Status.SUCCESS) return Status.FAILURE;
    if (s === Status.FAILURE) return Status.SUCCESS;
    return Status.RUNNING;
  }
}

class Blackboard {
  constructor() { this.data = {}; }
  set(k, v) { this.data[k] = v; }
  get(k) { return this.data[k]; }
  has(k) { return k in this.data; }
}

// Example: Guard NPC tree
const tree = new Selector(
  new Sequence(
    new Condition(bb => bb.get('enemy_visible')),
    new Action(bb => { console.log('Chasing enemy'); return Status.RUNNING; })
  ),
  new Sequence(
    new Condition(bb => bb.get('noise_heard')),
    new Action(bb => { console.log('Investigating'); return Status.SUCCESS; })
  ),
  new Action(bb => { console.log('Patrolling'); return Status.RUNNING; })
);

const bb = new Blackboard();
bb.set('enemy_visible', false);
bb.set('noise_heard', true);
tree.tick(bb);  // → "Investigating"

8. Parallel Nodes, Event-Driven, and HFSM Hybrids

• Parallel node: Ticks all children simultaneously. Parameterised by success/failure thresholds — e.g. succeed if ≥1 child succeeds, fail if all fail. Useful for simultaneously checking health and proximity while moving.
• Event-driven BTs: Rather than polling conditions every tick, observers subscribe to world events. When the event fires, re-evaluate the tree from the affected node upward. Halo uses event-driven BTs to interrupt running behaviours instantly on AI perception events.
• Utility-weighted selectors: Instead of fixed left-to-right priority, children are scored by a utility function and the highest-scoring child is selected. Bridges BT and utility AI (The Sims).
• BT + FSM hybrids: Use a state machine to switch between high-level modes (Peaceful/Alert/Combat), with a dedicated BT sub-graph per state. Common in open-world RPGs where NPCs also handle non-combat daily routines.
• Tools: Unreal Engine's AI Module, Unity's Behavior Designer, ROS2 BehaviorTree.CPP, Godot's BeehaveTree add-on.