skip to content

As AI lead on a large streamed open world, how would you choose the navigation stack: representation, hierarchy, dynamic obstacles, agent sizes and the per-frame budget?

level: principalimportance: should knowfreq 35%

answer

  1. tiles that stream with the world
  2. a coarse graph above the tiles
  3. rebuild, toggle, or leave to avoidance
  4. few agent size classes
  5. queue, budget, level of detail

basics

~20 s

Standardise on navmesh tiles that stream with the world, a coarse tile graph for long routes, a policy per obstacle type (rebuild, toggle links, or leave to avoidance), few agent size classes, and a time-sliced queue with cheaper paths far away.

solid answer

~50 s

There is no single right answer; the lead sets the standard and its budgets. **Representation:** a navmesh in fixed-size tiles that load and unload with world streaming, built offline for static geometry and rebuilt per tile at runtime only where the world changes. **Hierarchy:** long routes search a small, always-resident graph of tiles or regions first and refine near the agent, so cross-map orders never touch the full mesh. **Dynamic obstacles:** a policy per obstacle class: long-lived blockers rebuild tiles, doors and bridges toggle links or area flags, transient props are left to local avoidance. **Agent sizes:** each radius means another mesh, so cap the classes. **Budget:** a prioritised, time-sliced request queue with level of detail, full paths near the player and coarse or simulated travel far away. The trade-offs are memory, build time in the content pipeline, and how wrong unobserved agents may look.

go deeper

for a junior

Recall that a large world is split into navmesh tiles that load with the world, and that long routes use a coarser graph first.

for a middle

Explain how tiles, a coarse graph and off-mesh links fit together, and why each agent size needs its own eroded mesh.

for a senior

Diagnose open-world navigation failures, such as agents stuck at tile seams, broken links or planning through a fallen bridge, and fix them within the existing standard.

for a principal

Choose the standard and its budgets: tile size, size classes, the obstacle policy, the request budget and level of detail, and weigh memory, build time and how wrong unobserved agents may look.

## Why this is a lead's decision On a small level, pathfinding is a component: generate a navmesh, run A*, straighten the path. On a large streamed open world it becomes a **system with budgets**: memory for navigation data, build time in every content iteration, runtime milliseconds shared with every other AI system, and a standard that designers, level builders and engineers all work to. Each choice below has several defensible answers; the lead's job is to pick one per question, write down why, and measure it. ## Representation and streaming A navmesh is the usual base for a 3D open world: compact over large open areas, natural on multi-level geometry, and straightenable into any-angle paths. The questions are about how it is cut and loaded. - **Tiles.** Build the mesh in fixed-size tiles aligned with, or nested in, the world's streaming cells, so navigation data loads and unloads with the geometry it describes. - **Offline versus runtime builds.** Static geometry is built in the content pipeline; runtime rebuilds are reserved for tiles the game actually changes. Tile size trades rebuild cost against border overhead and tile count. - **Build time is a team cost.** If changing a hillside means waiting on a full rebuild, designers stop iterating; incremental, per-tile builds keep the pipeline usable. ## Hierarchy for long routes A route across the world cannot search millions of polygons, and most of them are not even loaded. - Keep a **coarse graph** of tiles or regions, with connection costs between neighbours, resident at all times; it is small enough to hold for the whole world. - Search the coarse graph first, then run the fine search only over the next few tiles, refining as the agent advances. - Agents beyond the loaded area travel **abstractly** along the coarse graph, advancing by estimated travel time, and receive a real path when their tile loads. ## Dynamic world policy Not every change deserves the same treatment. | Obstacle | Lifetime | Policy | Cost | |---|---|---|---| | Destroyed bridge, new building | Long | Rebuild the touched tiles | Background build time | | Door, gate, drawbridge | Toggles | Enable or disable a link or area flag | Cheap, authored per object | | Parked vehicle | Medium | Mark an area as blocked or expensive | Cheap, coarse | | Kicked crate, other characters | Short | Leave to local avoidance | No navigation cost | Too much rebuilding burns budget; too little leaves agents planning through walls. The policy should be written down per obstacle class, so a new prop's behaviour is not decided ad hoc. ## Agent classes and special movement - **Size classes.** Erosion bakes one radius into a mesh, so every size class adds a mesh for the whole world: memory and build time scale with the count. Fix a small set, for example humans and large creatures, and map every new creature to one of them. - **Off-mesh links** cover movement the mesh cannot describe: jumps, ladders, vaults, doors. They need costs, animation hooks and per-class permissions, and they are a frequent source of stuck agents, so they need tooling. - **Area costs** such as roads, water or danger zones shape routes; decide who owns their values, design or AI. ## Runtime budget and level of detail 1. A **prioritised request queue**, time-sliced under a per-frame budget, with agents near the player or in combat first. 2. **Level of detail**: full fine paths and straightening near the player; coarse-graph routes for agents in loaded but distant areas; abstract travel for agents outside the loaded world. 3. **Replanning rules**: replan when the path is invalidated or the goal moves far, not every frame. 4. **Determinism**, if the game uses lockstep networking or replays, constrains threading and floating-point choices in the pathfinder. ## What to measure and standardise - Path requests per second, expansions per request, and the queue's wait time at peak. - Navigation memory per loaded area and total coarse-graph size. - Build time per tile and for a full world rebuild. - Stuck-agent reports, broken off-mesh links and tile seams, collected by automated runs. The resulting standard is a set of trade-offs the lead owns: how much memory navigation gets, how long content builds may take, how many agent sizes the game supports, and how wrong an unobserved agent is allowed to be.

  • How would you route an agent to a goal in a part of the world that is not loaded?
    Search the always-resident coarse graph to get a sequence of regions and an estimated travel time. Move the agent abstractly along it, updating its position by time, and only request a fine path once the tiles around it load. The coarse graph must be kept consistent with the fine meshes, or abstract travel will take routes that do not exist.
  • When should a dynamic obstacle trigger a tile rebuild rather than local avoidance?
    When it lasts long enough that agents would keep planning through it and then jam against it: a new building, a collapsed bridge, a long-lived barricade. Short-lived or moving obstacles, like characters or kicked props, change faster than a rebuild could follow, so local avoidance handles them and the mesh stays untouched.

  • Build one monolithic navmesh for the whole world, once.
  • Rebuild the navmesh whenever any physics object moves.
  • Give every NPC a full-resolution path every frame, near or far.
  • Add a new mesh for every creature size designers invent.
  • All dynamic obstacles can be left to local avoidance.