skip to content

Pathfinding and Navmeshes

Search over game spaces: grid and navmesh graphs, heuristics fitted to the movement model, Jump Point Search, HPA* and the funnel algorithm. Whiteboarding it is a staple of AI interviews.

on this pageshow

explore

questions

6

How do grid, waypoint-graph and navmesh representations of walkable space differ for game pathfinding, and what does each cost?

level: juniorimportance: must knowfreq 70%

answer

  1. what one search node stands for
  2. cells vs placed points vs polygons
  3. free movement inside a convex polygon
  4. node count drives search cost

basics

~20 s

A grid splits the world into uniform cells, a waypoint graph links hand-placed points, and a navmesh covers walkable floor with convex polygons. Grids are simple but node-heavy, waypoints sparse but rail-bound, navmeshes compact but costly to build.

solid answer

~50 s

All three are graphs that the same search, usually A*, runs over; what changes is what a node means. In a **grid** each cell is a node linked to 4 or 8 neighbours: trivial to build and to edit when a wall falls, but a large map holds millions of nodes and raw paths follow 45-degree zig-zags. A **waypoint graph** is a sparse set of designer-placed points and links: cheap to search, but agents only know the links, so they walk on rails and cannot reason about the open space between points. A **navmesh** covers walkable surfaces with convex polygons; an agent can move straight between any two points inside one polygon, so a big room is one node, multi-floor levels fit naturally, and paths straighten into any-angle routes, at the price of a generation step and harder runtime edits.

go deeper

for a junior

Recall what a node is in each representation: a cell, a placed point, a convex polygon. Say that the same A* search runs over all three and only the graph changes.

for a middle

Explain why convexity lets a whole polygon be one node, how 4- and 8-connected grids differ, and why waypoint agents look as if they are on rails.

for a senior

Pick a representation for a stated game and defend it with node counts, runtime edits, multi-level geometry and the path quality players will notice.

for a principal

Treat the representation as a pipeline decision: who builds and maintains it, what it costs in content iteration, and whether a coarse layer belongs on top for long trips.

## The common shape: a graph plus a search Every pathfinding system in a game has two parts: a **graph** that describes where an agent can go, and a **search** that finds a cheap route through it. The search is almost always A* or a variant, and it does not care what the nodes mean; it only needs nodes, edges between them and a cost per edge. The real design choice is therefore the **representation of walkable space**: what one node stands for, how nodes are connected, and what an agent knows about the space between nodes. Three representations dominate. ## Grids A **grid** divides the map into equal cells, each marked walkable or blocked, sometimes with a terrain cost (road cheap, swamp expensive). - A node is a cell; edges go to the 4 orthogonal neighbours (**4-connected**) or also to the 4 diagonal ones (**8-connected**). - Building it is trivial: rasterize obstacles into cells. Editing it is just as easy: a destroyed wall flips a few cells to walkable. - The cost is size. A 2,048 by 2,048 map is about 4.2 million nodes, and a long search can touch a large share of them. - Raw paths are bound to the grid's directions, so they zig-zag at 45 or 90 degrees and need smoothing. - Grids fit flat, tile-based worlds well: strategy maps, roguelikes, top-down games. ## Waypoint graphs A **waypoint graph** is a sparse set of points, usually placed by designers or a tool, joined by links that are known to be walkable. - Few nodes means very fast searches and little memory. - Agents know only the links. Between two waypoints they follow the link as a rail; they have no description of the open floor around it, so they cannot cut a corner, step aside, or pick a different line across a courtyard. - Covering a large open area well needs many points and many links, which designers must maintain by hand as the level changes. - Waypoint graphs still suit sparse, corridor-like spaces and abstract travel networks, such as roads between towns. ## Navigation meshes A **navmesh** covers every walkable surface with **convex polygons**. Convexity is the key property: the straight segment between any two points of a convex polygon stays inside it, so an agent may walk directly between any two points of the same polygon. - A node is a polygon; an edge joins two polygons that share a side, and that shared side is a **portal** the path must cross. - A large room can be a single polygon, so node counts are small even on big levels. - Because the agent knows the whole walkable area, the polygon route can be straightened into the shortest path inside it, giving natural any-angle movement. - Surfaces at different heights, such as a bridge over a road, are separate polygons, so multi-floor 3D levels need little special handling. - The price is a generation step, usually automated from level geometry, and more work to update the mesh when the world changes at runtime. ## Side by side | Property | Grid | Waypoint graph | Navmesh | |---|---|---|---| | Node | Cell | Placed point | Convex polygon | | Node count on a large level | Very high | Very low | Low | | Knows the open space | Yes, at cell resolution | No, only links | Yes, exactly | | Raw path shape | 45/90-degree zig-zags | Along links | Corridor, then straightened | | Build | Trivial | Manual placement | Automated generation | | Runtime edits | Easy | Manual or scripted | Rebuild affected areas | | Multi-level 3D | Awkward | Possible | Natural | ## Choosing 1. If the game is played on a flat tile map and the world changes often, a grid is usually right, with a faster search on top when the map grows. 2. If agents roam a 3D level with rooms, stairs and open areas, a navmesh is the usual choice. 3. If travel is along a small known network, a waypoint graph is enough, and it can sit above a navmesh as a coarse layer for long trips. Whatever the representation, the edge costs drive the result: the search finds the cheapest route through the graph, so a representation whose costs misdescribe real travel, such as navmesh edges costed between polygon centres, returns a route that is good rather than exactly shortest.

  • Why must navmesh polygons be convex?
    Inside a convex polygon the straight segment between any two points stays inside it, so an agent can walk directly from any point to any other in the same polygon without leaving walkable space. That is what lets one polygon act as a single search node; a concave polygon would need its own internal route around the notch.
  • What is the edge cost between two navmesh polygons, and why is it approximate?
    It is usually the distance between representative points, such as polygon centres or the midpoints of the shared sides. The real path crosses each shared side wherever the straightened route needs it, so these costs only approximate travel length, and the polygon route A* picks is good but not guaranteed to contain the true shortest path.

A grid is graph paper, a waypoint graph is a subway map, and a navmesh is a floor plan of rooms: on the subway map you can only ride the lines, while on the floor plan you can cross any room however you like.

  • A navmesh needs a different search algorithm than a grid.
  • Agents on a waypoint graph can move freely through the open space between waypoints.
  • Navmesh polygons must all be equal-sized triangles, like grid cells.
  • A finer grid always gives better paths at no real cost.
  • Grids are always too slow to use in a shipped game.
open as a page

For A* on a game grid, how do you choose between Manhattan, octile and Euclidean heuristics, and how does tie-breaking cut node expansions?

level: middleimportance: must knowfreq 72%

basics

~20 s

Use the heuristic that equals unobstructed travel cost under your movement rules: Manhattan for 4-way grids, octile for 8-way grids with √2 diagonals, Euclidean for any-angle movement. Break equal-f ties toward the node nearer the goal.

open as a page

How is a navmesh generated from level geometry by voxelization, and why is the walkable area eroded by the agent's radius?

level: middleimportance: should knowfreq 45%

basics

~20 s

Level triangles are rasterized into a voxel heightfield, filtered by slope, headroom and step height, shrunk by the agent radius, and split into regions whose outlines become convex polygons. Erosion lets search treat the agent as a point.

open as a page

A soldier's navmesh path zig-zags between polygon edge midpoints across an open floor, then scrapes along wall corners; what causes each, and how do you fix them?

level: seniorimportance: should knowfreq 58%

basics

~20 s

Zig-zag means waypoints sit at polygon centres or edge midpoints; string-pull the polygon corridor with the funnel algorithm. Scraping means the taut path touches vertices of a mesh not eroded by the agent's radius; erode at build time.

open as a page

In a strategy game where two hundred units request grid paths across a large map through chokepoints, how do you keep pathfinding inside the frame budget?

level: seniorimportance: should knowfreq 60%

basics

~20 s

Reject unreachable goals with precomputed connected-region labels, queue requests and time-slice them under a per-frame expansion budget, share routes, and shrink each search: Jump Point Search on uniform-cost grids, HPA* clusters for long routes, a weighted heuristic for low-priority units.

open as a page

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%

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.

open as a page