Gamedev Pathing

Game AI navigation & pathfinding

Move agents through a level intelligently and per-engine-correctly: pick a world representation, run the right search, then follow the result with steering + local avoidance. This skill owns the navigation stack; it stops where physics collision response and high-level behaviour design begin.

Version targets & the API ban-list (read first)

Navigation APIs were renamed hard between engine generations. Emitting an old name compiles into nothing or silent breakage. Target these versions; never emit the banned column.

The two-layer mental model (center of gravity)

The single most common navigation bug is collapsing two jobs into one. Keep them separate:

1. Global pathfinding — where to go. A discrete search (A* / navmesh query) over a static-ish representation, run occasionally (on new goal, or throttled), returns a corridor of waypoints.
2. Local steering + avoidance — how to move this frame. A cheap per-frame vector: follow the corridor, dodge other agents and dynamic obstacles, respect acceleration. Runs every frame.

Path for the map, steering for the moment. Symptoms of merging them: re-running A* every frame (CPU melts), or agents that walk the path but pile into each other (no local avoidance). Every engine's NavMeshAgent / NavigationAgent bundles both — know which layer you are configuring.

Choosing a representation

Rule: navmesh for free-roaming characters, grid for tile-locked/destructible worlds, waypoint graph only for constrained routes. Detail & path-smoothing (funnel algorithm) → references/search-algorithms.md.

Search algorithms (essentials)

• A* — the default. Dijkstra + a heuristic h(n) that estimates remaining cost. Admissible h (never over-estimates) ⇒ optimal path; use octile distance on 8-connected grids, Euclidean on navmesh/any-angle. h must also stay ≤ true edge costs (consistency) to skip re-expansions.
• Dijkstra — A* with h=0. Use when there is no single goal (nearest of many exits) or you need the full cost field (see flow fields). Slower than A* to one target.
• Weighted / greedy — inflate h (f = g + w·h, w>1) for faster, slightly suboptimal paths when frame budget beats optimality.
• JPS (Jump Point Search) — A* speedup for uniform-cost grids only; skips symmetric paths, often 10×+ fewer expansions. Not for weighted terrain or navmeshes.
• Hierarchical / HPA* — for huge maps: partition into clusters, path cluster-to-cluster, refine locally. Reach for it when a single flat A* blows the frame budget or you have thousands of tiles.

Always run search off a binary-heap open set and a closed set. Pseudocode, tie-breaking, any-angle (Theta*), and the funnel string-pull → references/search-algorithms.md.

Navmesh workflow (essentials)

1. Bake the walkable surface from level geometry. Key params: agent radius (how far the mesh is shrunk from walls — the #1 knob), agent height, max step/climb, max slope, cell size.
2. One navmesh per agent size. A tank and a rat need different bakes; do not share one mesh and hope.
3. Regions / areas + costs — tag surfaces (water, mud, road) with a traversal cost so paths prefer roads and avoid hazards, rather than deleting the area outright.
4. Off-mesh / nav links — explicit edges for jumps, ladders, teleporters, doors: places agents move but no polygon connects. Godot NavigationLink, Unity NavMeshLink, Unreal NavLinkProxy.
5. Dynamic obstacles — two tools, do not confuse them:
   • Carving obstacle (Unity NavMeshObstacle carving, Godot NavigationObstacle, Unreal NavModifier): punches a hole so global paths route around a placed prop. Costs a re-carve on move.
   • Local avoidance (RVO/ORCA): agents dodge without touching the mesh — for other moving agents.
6. Re-baking — full rebake is expensive; prefer tile/partial rebake or carving for runtime changes. Bake offline for static levels. Full param table + per-engine baking → references/navmesh-workflow.md.

Steering & local avoidance (essentials)

Steering = a desired-velocity vector combined and clamped to max force/speed. Primitives:

• Seek / Flee — accelerate toward / away from a target point.
• Arrive — seek that ramps speed down inside a slowing radius (no overshoot/jitter at the goal).
• Pursue / Evade — seek/flee the target's predicted future position, not its current one.
• Wander — smoothed random heading for idle/ambient motion.
• Path following — steer toward a look-ahead point along the A*/navmesh corridor, not the far goal.
• Flocking = separation + alignment + cohesion (Reynolds boids) for groups.

Combine either as a weighted sum (simple) or priority/arbitration (avoidance wins over cohesion).

Local avoidance (RVO / ORCA): each agent picks a velocity that is collision-free assuming neighbours share the burden (reciprocal — hence no oscillating "dance"). This is avoidance, not collision response: it changes intended velocity before moving; the physics/collision solver is a separate, last-resort backstop (→ gamedev-physics). For dense crowds use the engine's crowd/avoidance system.

Flow fields — for many agents → one (or few) goals (RTS swarm, tower-defense creeps): run one Dijkstra from the goal over the grid to build a cost/integration field, derive a per-cell direction vector once, then every agent just samples its cell. O(1) per agent vs one A* each. Full derivation, boids weights, and RVO intuition → references/steering-and-avoidance.md.

Per-engine mapping

Godot 4.x (NavigationAgent3D — 2D is identical with 2D suffix)

extends CharacterBody3D
@onready var agent: NavigationAgent3D = $NavigationAgent3D
@export var speed := 4.0

func _ready() -> void:
    agent.avoidance_enabled = true                       # RVO local avoidance
    agent.velocity_computed.connect(_on_velocity_computed)

func set_goal(p: Vector3) -> void:
    agent.target_position = p                            # property, NOT set_target_location()

func _physics_process(_delta: float) -> void:
    if agent.is_navigation_finished():
        return
    var next := agent.get_next_path_position()           # 4.x name (was get_next_location)
    var desired := global_position.direction_to(next) * speed
    agent.set_velocity(desired)                          # feed RVO; result via signal

func _on_velocity_computed(safe: Vector3) -> void:       # only fires while avoidance enabled
    velocity = safe
    move_and_slide()

One-off query without an agent: NavigationServer3D.map_get_path(map_rid, from, to, true). Rebake a region at runtime: $NavigationRegion3D.bake_navigation_mesh(). Off-mesh: NavigationLink3D. If avoidance is off, skip the signal and move_and_slide() with desired directly.