game-ai

# Behavior trees, FSMs, and the blackboard

A **behavior tree** (BT) is a tree of nodes ticked from the root each frame.
Every node's `tick()` returns one of three statuses:

- `SUCCESS` — the node finished its job this frame.
- `FAILURE` — the node could not do its job.
- `RUNNING` — the node needs more frames (a walk, an animation, a wait).

Control flows down from the root; status flows back up. The shape of the tree
*is* the priority logic, which is why BTs scale to many behaviors far better than
a flat FSM.

## Node taxonomy

| Category | Node | Behavior |
|---|---|---|
| Composite | **Sequence** | Tick children left→right; return on first non-`SUCCESS`. Logical AND. |
| Composite | **Selector** (Fallback) | Tick children left→right; return on first non-`FAILURE`. Logical OR. |
| Composite | **Parallel** | Tick all children; succeed/fail on a policy (e.g. N must succeed). |
| Decorator | **Inverter** | Swap `SUCCESS`↔`FAILURE`; pass `RUNNING` through. |
| Decorator | **Repeat / RepeatUntilFail** | Re-tick a child a number of times. |
| Decorator | **Cooldown / Timeout** | Gate or time-limit a child. |
| Leaf | **Condition** | Test the world/blackboard → `SUCCESS`/`FAILURE` (no side effects). |
| Leaf | **Action** | Do something; return `RUNNING` until complete. |

## Stateful composites and RUNNING

Naive composites restart from the first child every tick. For multi-frame
actions, a composite must **remember which child was RUNNING** and resume there:

```gdscript
class Sequence:
    var children = []
    var _running = 0                 # index of the child that returned RUNNING

    func tick(agent, dt) -> int:
        while _running < children.size():
            var s = children[_running].tick(agent, dt)
            if s == Status.RUNNING:
                return Status.RUNNING        # resume here next frame
            if s == Status.FAILURE:
                _running = 0                 # whole sequence fails; reset
                return Status.FAILURE
            _running += 1                    # child SUCCESS -> advance
        _running = 0                         # reached the end -> sequence succeeds
        return Status.SUCCESS
```

A Selector is the mirror image: it advances on `FAILURE`, returns on `SUCCESS`
or `RUNNING`, and resets its index when a child succeeds.

## Leaf examples

```gdscript
# Condition leaf: pure test, no side effects.
class CanSeePlayer:
    func tick(agent, dt) -> int:
        return Status.SUCCESS if agent.can_see(agent.blackboard.player) else Status.FAILURE

# Action leaf: multi-frame, returns RUNNING until it arrives.
class MoveTo:
    var key  # blackboard key holding the destination
    func tick(agent, dt) -> int:
        var dest = agent.blackboard.get(key)
        if dest == null: return Status.FAILURE
        agent.move_toward(dest, dt)
        return Status.SUCCESS if agent.position.distance_to(dest) < 4.0 else Status.RUNNING
```

A complete guard, as a tree:

```
Selector
├── Sequence            # attack branch (highest priority)
│   ├── CanSeePlayer
│   ├── MoveTo(player)
│   └── Attack
└── Patrol              # fallback when nothing else applies
```

## The blackboard

The **blackboard** is the shared memory that decouples nodes: conditions read it,
actions write it, and no node holds a hard reference to another. Store the
current target, last-known position, home point, path, and timers there. This is
what lets the same `MoveTo` action serve chase, patrol, and flee subtrees.

```gdscript
# A blackboard is just a typed key/value store on the agent.
agent.blackboard = {
    "player": null,            # set by perception each tick
    "home": Vector2(100, 100),
    "path": [],                # filled by the pathfinder
}
```

## FSM vs behavior tree — choosing

| Use an FSM when… | Use a behavior tree when… |
|---|---|
| 2–5 clearly named states | Many behaviors with priorities |
| Transitions are obvious and few | Behaviors interrupt/preempt each other |
| Behavior rarely changes | You want to reuse subtrees across enemies |
| You want the simplest thing | You need designer-tunable, data-driven AI |

Many shipping games use **both**: an FSM for top-level mode (Idle / Combat /
Dead) and a behavior tree inside the Combat state. Start with an FSM; graduate a
state to a behavior tree when its `if` logic outgrows a few transitions.

## Utility AI (brief)

When "how *much* do I want each option" matters more than discrete states, score
each candidate action with a utility function and pick the highest:

```
score(action) = sum of weighted considerations, each a 0..1 curve of a fact
choose the action with the maximum score (optionally softmax for variety)
```

Utility scales to nuanced trade-offs (heal vs attack vs flee by health/ammo/
distance) but is harder to debug than a tree. Reach for it when a BT's branching
becomes a thicket of conditions.

# Pathfinding: A* in full

A* finds the shortest path on a **graph** (nodes + weighted edges). A grid is
just one kind of graph. The algorithm is the same whether nodes are tiles, rooms,
or navmesh polygons — only `neighbors()` and `cost()` change.

A* keeps a priority queue (the *frontier*) ordered by `f = g + h`, where `g` is
the known cost from the start and `h` is a heuristic estimate to the goal. It is
optimal **iff** `h` never overestimates the true remaining cost (it is
*admissible*). With `h = 0`, A* degenerates to Dijkstra's algorithm.

## Complete A* (engine-neutral Python)

```python
import heapq

def a_star(graph, start, goal):
    # Priority queue of (f_score, tie, node). heapq pops the SMALLEST first.
    frontier = [(0, 0, start)]
    came_from = {start: None}      # node -> node we reached it from
    cost_so_far = {start: 0.0}     # node -> best known g cost from start
    counter = 0                    # stable tie-breaker so heapq never compares nodes

    while frontier:
        _, _, current = heapq.heappop(frontier)
        if current == goal:
            break                  # early exit: we popped the goal, path is optimal

        for nxt in graph.neighbors(current):
            new_cost = cost_so_far[current] + graph.cost(current, nxt)
            # Relax: accept this edge only if it improves the best known cost.
            if nxt not in cost_so_far or new_cost < cost_so_far[nxt]:
                cost_so_far[nxt] = new_cost
                priority = new_cost + heuristic(nxt, goal)   # f = g + h
                counter += 1
                heapq.heappush(frontier, (priority, counter, nxt))
                came_from[nxt] = current

    return came_from, cost_so_far

def reconstruct_path(came_from, start, goal):
    if goal not in came_from:
        return None                # unreachable
    path = []
    node = goal
    while node != start:
        path.append(node)
        node = came_from[node]
    path.append(start)
    path.reverse()                 # came_from points backward; flip to start->goal
    return path
```

Key correctness points:

- **Check the goal when *popping*, not when pushing.** Testing on push breaks as
  soon as edges have varying cost; testing on pop is always correct.
- **Relaxation** (`new_cost < cost_so_far[nxt]`) lets a node be improved if a
  cheaper route is found later — essential with non-uniform movement costs.
- **Tie-breaker**: push a monotonic counter alongside the node so the heap never
  has to order two equal-`f` nodes by the node object itself.

## Heuristics by movement type

| Allowed moves | Heuristic | Formula (`dx=|ax-bx|`, `dy=|ay-by|`) |
|---|---|---|
| 4-directional grid | Manhattan | `dx + dy` |
| 8-directional grid | Octile | `(dx + dy) + (sqrt(2) - 2) * min(dx, dy)` |
| Any-angle / Euclidean space | Euclidean | `sqrt(dx*dx + dy*dy)` |

Scale the heuristic by the minimum step cost so it stays in the same units as
`g`. If `h` can exceed the true cost, A* is faster but returns non-optimal paths
(this is the "weighted A*" trade-off — use it deliberately, not by accident).

## Grid graph adapter

```python
class GridGraph:
    def __init__(self, walls, width, height):
        self.walls, self.w, self.h = walls, width, height
    def in_bounds(self, p): return 0 <= p[0] < self.w and 0 <= p[1] < self.h
    def passable(self, p):  return p not in self.walls
    def neighbors(self, p):
        x, y = p
        candidates = [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]   # add diagonals for octile
        return [c for c in candidates if self.in_bounds(c) and self.passable(c)]
    def cost(self, a, b):
        return 1.0                  # uniform; return terrain weight for varied cost
```

## When to use an engine navmesh instead

Hand-rolled grid A* is ideal for 2D tile games and for understanding the
algorithm. For 3D worlds, arbitrary geometry, dynamic obstacle avoidance, and
agent radius/height, prefer the engine's baked navigation:

- **Unity** — bake a NavMesh and drive a `NavMeshAgent` (see `unity-navmesh`).
- **Unreal** — Nav Mesh Bounds + `AIController` MoveTo (see `unreal-behavior-trees`).
- **Godot** — `NavigationRegion2D/3D` + `NavigationAgent2D/3D`, querying
  `NavigationServer` for paths.

These handle path smoothing, off-mesh links, and crowd avoidance you would
otherwise reimplement. Use A* directly when the world is a discrete grid/graph or
when you need full control over the cost function.

## Performance notes

- Shrink the graph before optimizing the search: merge open areas, use waypoint
  graphs instead of dense grids, or precompute connected regions.
- Cap pathfinding work per frame (a budget of N searches), and queue the rest.
- For many agents heading to the same goal, compute one **flow field** (a
  Dijkstra pass from the goal outward) and have every agent follow the gradient,
  instead of running A* per agent.

---
name: game-ai
description: >
  Design NPC and enemy decision-making with finite state machines, behavior
  trees, steering behaviors, and A* pathfinding — engine-neutral algorithms
  that pair with the detected engine's navigation API. Use when building enemy
  AI, an FSM or behavior tree, steering/flocking, or pathfinding, or when the
  user mentions state machine, behavior tree, blackboard, A*, navmesh, seek, or
  patrol/chase.
---

# Game AI: decisions, steering, and pathfinding

Build believable NPC behavior from three separable layers: **decide** (what to
do), **steer** (how to move there), and **path** (how to route around the map).
Keep them decoupled — a behavior tree picks a target, the pathfinder produces
waypoints, steering follows them. This skill teaches the engine-neutral
algorithms; bind them to your engine via the related skills below.

## When to use

- Use when implementing enemy/NPC logic: patrols, chase/flee, guard states,
  group movement, or "find a path to the player".
- Use to choose between an **FSM** (few clear states), a **behavior tree** (many
  reactive behaviors with priorities), or **steering** (smooth local movement).
- Use when integrating pathfinding: A* on a grid/graph, or driving an engine
  navmesh agent.

**When *not* to use:** for the engine's concrete navmesh/agent API and baking,
use `unity-navmesh`, `unreal-behavior-trees`, or Godot's `NavigationAgent2D/3D`
(see that engine skill). For movement/collision feel, use `physics-tuning`. For
spawning waves along lanes, see the `tower-defense` genre skill.

## Core workflow

1. **Pick the decision model by complexity.** 2–5 states with obvious
   transitions → FSM. Many behaviors, priorities, interruption, reuse → behavior
   tree. Continuous "how strongly do I want each option" → utility scoring.
2. **Separate decision from motion.** The decision layer outputs an *intent*
   (target position, action). Steering or pathfinding turns intent into motion.
3. **Path on the right graph.** Grid tiles, waypoint graph, or a baked navmesh.
   Fewer nodes = faster A*. Prefer the engine's navmesh for 3D; A* on a grid for
   tile games.
4. **Steer along the path**, not straight to the goal — follow the next waypoint,
   advancing when close, so agents round corners.
5. **Recompute paths sparingly.** Pathfind on a timer or when the goal moves a
   tile, not every frame. Cache the path; only the waypoint index advances.
6. **Verify by observation.** Watch the agent: does it reach the goal, get stuck
   on corners, oscillate between states? Draw the path and current state on
   screen while tuning.

## Patterns

### 1. Finite state machine (one state object, explicit transitions)

```gdscript
# Each state is a small object with enter/update/exit. The machine owns "current".
class_name State
func enter(agent): pass
func update(agent, dt) -> State: return null   # return a new state to transition
func exit(agent): pass

# --- Chase state: returns Patrol when the player escapes sight range ---
class Chase extends State:
    func update(agent, dt) -> State:
        if not agent.can_see(agent.target):
            return Patrol.new()                 # transition by returning next state
        agent.move_toward(agent.target.position, dt)
        return null                             # null = stay in this state

# --- Driver: call once per frame ---
func tick(dt):
    var next = current.update(self, dt)
    if next != null:
        current.exit(self); next.enter(self); current = next
```

Keep transition logic *inside* states (or in a table), never as a growing pile
of `if` flags. One state owns one behavior; that is what keeps an FSM readable.

### 2. Behavior tree tick (composite nodes return a status)

```gdscript
# A node's tick() returns SUCCESS, FAILURE, or RUNNING (still working this frame).
enum Status { SUCCESS, FAILURE, RUNNING }

# Sequence: run children in order; stop at the first non-SUCCESS (logical AND).
func sequence_tick(children, agent, dt) -> int:
    for child in children:
        var s = child.tick(agent, dt)
        if s != Status.SUCCESS:
            return s                 # FAILURE or RUNNING short-circuits the sequence
    return Status.SUCCESS

# Selector: try children until one succeeds or is RUNNING (logical OR / fallback).
func selector_tick(children, agent, dt) -> int:
    for child in children:
        var s = child.tick(agent, dt)
        if s != Status.FAILURE:
            return s                 # SUCCESS or RUNNING stops the search
    return Status.FAILURE
```

A guard AI reads top-down: `Selector[ Sequence[CanSeePlayer?, Chase], Patrol ]`
— chase if visible, otherwise patrol. See `references/behavior-trees.md` for
leaf nodes, decorators (Inverter, Cooldown), and a blackboard.

### 3. Steering: seek and arrive (smooth, frame-rate independent)

```gdscript
# Seek: accelerate toward a target at full speed. Steering = desired - current.
func seek(pos, vel, target, max_speed, max_force) -> Vector2:
    var desired = (target - pos).normalized() * max_speed
    return (desired - vel).limit_length(max_force)   # a force, not a teleport

# Arrive: like seek, but ramp speed down inside slow_radius so it stops cleanly.
func arrive(pos, vel, target, max_speed, max_force, slow_radius) -> Vector2:
    var offset = target - pos
    var dist = offset.length()
    if dist < 0.001: return -vel                      # already there: kill drift
    var ramped = max_speed * min(dist / slow_radius, 1.0)
    var desired = offset / dist * ramped
    return (desired - vel).limit_length(max_force)

# Per frame: vel += steering * dt; pos += vel * dt   (always scale by dt)
```

### 4. A* heuristic must not overestimate (or paths stop being shortest)

```python
# Match the heuristic to the movement. An ADMISSIBLE heuristic (never larger
# than the true remaining cost) keeps A* optimal.
def heuristic(a, b):
    dx, dy = abs(a.x - b.x), abs(a.y - b.y)
    # return dx + dy             # Manhattan: 4-direction grids (no diagonals)
    return (dx + dy) + (1.414 - 2) * min(dx, dy)   # octile: 8-direction grids
# f(n) = g(n) + h(n): g = cost from start, h = heuristic to goal.
# Overestimating h is faster but no longer guarantees the shortest path.
```

The full A* loop (priority queue, `came_from` reconstruction, grid + waypoint
graphs) is in `references/pathfinding.md`.

## Pitfalls

- **Pathfinding every frame** tanks the frame rate. Recompute on a timer or only
  when the target moves to a new tile; follow the cached waypoints in between.
- **Steering straight to the goal** instead of to the next waypoint makes agents
  hug walls and corners. Follow the path; advance the waypoint when within radius.
- **Inadmissible A\* heuristic** (e.g. Euclidean distance scaled up, or Manhattan
  on a diagonal grid) returns fast but *non-shortest* paths. Pick the heuristic
  that matches your allowed moves.
- **Behavior tree leaves that never return RUNNING** for multi-frame actions
  (walking, playing an animation) cause the tree to restart the action every
  tick. Return RUNNING until the action completes.
- **FSM transition spaghetti**: scattering `if state == ...` checks everywhere
  recreates the mess an FSM exists to prevent. Keep transitions in the state.
- **No line-of-sight or stuck check** → agents grind into walls forever. Add a
  timeout that forces a repath or a state change.

## References

- `references/pathfinding.md` — complete A* (priority queue, reconstruction),
  grid vs waypoint graphs, when to defer to an engine navmesh.
- `references/behavior-trees.md` — node taxonomy, leaf/decorator implementations,
  blackboard, and FSM-vs-BT selection.

## Related skills

- `unity-navmesh`, `unreal-behavior-trees` — concrete engine AI/navigation APIs.
- `physics-tuning` — movement, collision response, and agent radius.
- `procedural-gen` — generating the graph/level the AI navigates.
- `tower-defense`, `fps-shooter` — genres that compose this skill.