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
- 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.
- Separate decision from motion. The decision layer outputs an intent
(target position, action). Steering or pathfinding turns intent into motion.
- 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.
- Steer along the path, not straight to the goal — follow the next waypoint,
advancing when close, so agents round corners.
- 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.
- 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)
# Godot 4.7, one class per file.
# state.gd: each state is a small object with enter/update/exit.
class_name State extends RefCounted
func enter(_agent) -> void: pass
func update(_agent, _dt: float) -> State: return null # return a state to transition
func exit(_agent) -> void: pass
# chase.gd: returns Patrol when the player escapes sight range.
class_name Chase extends State
func update(agent, dt: float) -> State:
if not agent.can_see(agent.target):
return Patrol.new() # transition by returning the next state
agent.move_toward(agent.target.position, dt)
return null # null = stay in this state
# enemy.gd: the agent owns `current` and ticks it once per frame.
var current: State = Patrol.new() # call current.enter(self) in _ready()
func tick(dt: float) -> void:
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)
# 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)
# 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).limit_length(max_force) # already there: brake
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)
# Match the heuristic to the movement. An ADMISSIBLE heuristic (never larger
# than the true remaining cost) keeps A* optimal.
def heuristic(a, b): # a, b are (x, y) grid cells
dx, dy = abs(a[0] - b[0]), abs(a[1] - b[1])
# 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
ai-behavior-trees-utility-ai — deeper behavior-tree and utility-AI design.
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.
1---2name: game-ai3description: >4 Design NPC and enemy decision-making with finite state machines, behavior5 trees, steering behaviors, and A* pathfinding — engine-neutral algorithms6 that pair with the detected engine's navigation API. Use when building enemy7 AI, an FSM or behavior tree, steering/flocking, or pathfinding, or when the8 user mentions state machine, behavior tree, blackboard, A*, navmesh, seek, or9 patrol/chase.10metadata:11 source: https://skillmd.com/skills/junmystery/game-ai12---1314# Game AI: decisions, steering, and pathfinding1516Build believable NPC behavior from three separable layers: **decide** (what to17do), **steer** (how to move there), and **path** (how to route around the map).18Keep them decoupled — a behavior tree picks a target, the pathfinder produces19waypoints, steering follows them. This skill teaches the engine-neutral20algorithms; bind them to your engine via the related skills below.2122## When to use2324- Use when implementing enemy/NPC logic: patrols, chase/flee, guard states,25 group movement, or "find a path to the player".26- Use to choose between an **FSM** (few clear states), a **behavior tree** (many27 reactive behaviors with priorities), or **steering** (smooth local movement).28- Use when integrating pathfinding: A* on a grid/graph, or driving an engine29 navmesh agent.3031**When *not* to use:** for the engine's concrete navmesh/agent API and baking,32use `unity-navmesh`, `unreal-behavior-trees`, or Godot's `NavigationAgent2D/3D`33(see that engine skill). For movement/collision feel, use `physics-tuning`. For34spawning waves along lanes, see the `tower-defense` genre skill.3536## Core workflow37381. **Pick the decision model by complexity.** 2–5 states with obvious39 transitions → FSM. Many behaviors, priorities, interruption, reuse → behavior40 tree. Continuous "how strongly do I want each option" → utility scoring.412. **Separate decision from motion.** The decision layer outputs an *intent*42 (target position, action). Steering or pathfinding turns intent into motion.433. **Path on the right graph.** Grid tiles, waypoint graph, or a baked navmesh.44 Fewer nodes = faster A*. Prefer the engine's navmesh for 3D; A* on a grid for45 tile games.464. **Steer along the path**, not straight to the goal — follow the next waypoint,47 advancing when close, so agents round corners.485. **Recompute paths sparingly.** Pathfind on a timer or when the goal moves a49 tile, not every frame. Cache the path; only the waypoint index advances.506. **Verify by observation.** Watch the agent: does it reach the goal, get stuck51 on corners, oscillate between states? Draw the path and current state on52 screen while tuning.5354## Patterns5556### 1. Finite state machine (one state object, explicit transitions)5758```gdscript59# Godot 4.7, one class per file.60# state.gd: each state is a small object with enter/update/exit.61class_name State extends RefCounted62func enter(_agent) -> void: pass63func update(_agent, _dt: float) -> State: return null # return a state to transition64func exit(_agent) -> void: pass6566# chase.gd: returns Patrol when the player escapes sight range.67class_name Chase extends State68func update(agent, dt: float) -> State:69 if not agent.can_see(agent.target):70 return Patrol.new() # transition by returning the next state71 agent.move_toward(agent.target.position, dt)72 return null # null = stay in this state7374# enemy.gd: the agent owns `current` and ticks it once per frame.75var current: State = Patrol.new() # call current.enter(self) in _ready()7677func tick(dt: float) -> void:78 var next := current.update(self, dt)79 if next != null:80 current.exit(self)81 next.enter(self)82 current = next83```8485Keep transition logic *inside* states (or in a table), never as a growing pile86of `if` flags. One state owns one behavior; that is what keeps an FSM readable.8788### 2. Behavior tree tick (composite nodes return a status)8990```gdscript91# A node's tick() returns SUCCESS, FAILURE, or RUNNING (still working this frame).92enum Status { SUCCESS, FAILURE, RUNNING }9394# Sequence: run children in order; stop at the first non-SUCCESS (logical AND).95func sequence_tick(children, agent, dt) -> int:96 for child in children:97 var s = child.tick(agent, dt)98 if s != Status.SUCCESS:99 return s # FAILURE or RUNNING short-circuits the sequence100 return Status.SUCCESS101102# Selector: try children until one succeeds or is RUNNING (logical OR / fallback).103func selector_tick(children, agent, dt) -> int:104 for child in children:105 var s = child.tick(agent, dt)106 if s != Status.FAILURE:107 return s # SUCCESS or RUNNING stops the search108 return Status.FAILURE109```110111A guard AI reads top-down: `Selector[ Sequence[CanSeePlayer?, Chase], Patrol ]`112— chase if visible, otherwise patrol. See `references/behavior-trees.md` for113leaf nodes, decorators (Inverter, Cooldown), and a blackboard.114115### 3. Steering: seek and arrive (smooth, frame-rate independent)116117```gdscript118# Seek: accelerate toward a target at full speed. Steering = desired - current.119func seek(pos, vel, target, max_speed, max_force) -> Vector2:120 var desired = (target - pos).normalized() * max_speed121 return (desired - vel).limit_length(max_force) # a force, not a teleport122123# Arrive: like seek, but ramp speed down inside slow_radius so it stops cleanly.124func arrive(pos, vel, target, max_speed, max_force, slow_radius) -> Vector2:125 var offset = target - pos126 var dist = offset.length()127 if dist < 0.001: return (-vel).limit_length(max_force) # already there: brake128 var ramped = max_speed * min(dist / slow_radius, 1.0)129 var desired = offset / dist * ramped130 return (desired - vel).limit_length(max_force)131132# Per frame: vel += steering * dt; pos += vel * dt (always scale by dt)133```134135### 4. A* heuristic must not overestimate (or paths stop being shortest)136137```python138# Match the heuristic to the movement. An ADMISSIBLE heuristic (never larger139# than the true remaining cost) keeps A* optimal.140def heuristic(a, b): # a, b are (x, y) grid cells141 dx, dy = abs(a[0] - b[0]), abs(a[1] - b[1])142 # return dx + dy # Manhattan: 4-direction grids (no diagonals)143 return (dx + dy) + (1.414 - 2) * min(dx, dy) # octile: 8-direction grids144# f(n) = g(n) + h(n): g = cost from start, h = heuristic to goal.145# Overestimating h is faster but no longer guarantees the shortest path.146```147148The full A* loop (priority queue, `came_from` reconstruction, grid + waypoint149graphs) is in `references/pathfinding.md`.150151## Pitfalls152153- **Pathfinding every frame** tanks the frame rate. Recompute on a timer or only154 when the target moves to a new tile; follow the cached waypoints in between.155- **Steering straight to the goal** instead of to the next waypoint makes agents156 hug walls and corners. Follow the path; advance the waypoint when within radius.157- **Inadmissible A\* heuristic** (e.g. Euclidean distance scaled up, or Manhattan158 on a diagonal grid) returns fast but *non-shortest* paths. Pick the heuristic159 that matches your allowed moves.160- **Behavior tree leaves that never return RUNNING** for multi-frame actions161 (walking, playing an animation) cause the tree to restart the action every162 tick. Return RUNNING until the action completes.163- **FSM transition spaghetti**: scattering `if state == ...` checks everywhere164 recreates the mess an FSM exists to prevent. Keep transitions in the state.165- **No line-of-sight or stuck check** → agents grind into walls forever. Add a166 timeout that forces a repath or a state change.167168## References169170- `references/pathfinding.md` — complete A* (priority queue, reconstruction),171 grid vs waypoint graphs, when to defer to an engine navmesh.172- `references/behavior-trees.md` — node taxonomy, leaf/decorator implementations,173 blackboard, and FSM-vs-BT selection.174175## Related skills176177- `ai-behavior-trees-utility-ai` — deeper behavior-tree and utility-AI design.178- `unity-navmesh`, `unreal-behavior-trees` — concrete engine AI/navigation APIs.179- `physics-tuning` — movement, collision response, and agent radius.180- `procedural-gen` — generating the graph/level the AI navigates.181- `tower-defense`, `fps-shooter` — genres that compose this skill.