skip to content

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.