game-ai

# 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