When a guard in Skyrim rounds a corner, dozens of computations fire in a single frame to keep the chase seamless. Behind every smoothly chasing enemy in a shooter, every escort quest in a role-playing game, and every zerg rush in a real-time strategy title sits a graph search running dozens or thousands of times per second. The character’s path is rarely a straight line because the world is full of walls, ramps, water, allies, and doors that just opened.
This article explains how game developers turn A*, NavMesh, and dynamic re-planning into the believable enemy movement players notice but rarely question.
Why Random Movement and Straight-Line Paths Fail
Before any clever algorithm shows up, developers almost always try the dumb approaches first. Random walks, straight-line motion, and wall-sliding hacks are tempting because they cost almost nothing to implement. They also fall apart within minutes of playtesting, and your immersion pays the price.
The cost of looking stupid
- Random walks read as bugs: a character that picks a new direction every few frames looks drunk, and players stop reading it as an opponent.
- Straight lines clip geometry: the NPC walks face-first into a crate, slides along it, and punches through a corner the designer never meant as a passage.
- Wall-sliding stalls in tight spaces: brute-force sliding can reach the player, but the path looks robotic and loops on convex shapes.
Warning: if your enemy path traces visible zigzag lines along walls, players will notice long before they notice your lighting or your weapon sound design.
The deeper problem is that none of these methods know anything about the world. They treat every direction as equally good, so they ignore ramps, jump links, ladders, and the fact that a doorway is narrower than the room on either side. Real pathfinding needs a model of where a character is allowed to step, then a search over that model for a route that actually makes sense.
Once you accept that, the most natural way to represent stepping rules is the graph.
Graphs, Nodes, and the Language of Search
Once you accept that the world must be modeled, the next step is to pick a model. Every pathfinding algorithm in modern games runs on the same foundation: a graph. A pathfinding graph collapses the world into walkable points, called nodes, and the connections between them, called edges. Search the graph for a sequence of edges from start to goal, and you have a path.
Three ways to build the graph
- Uniform grids: tile the world into squares or hexes; each walkable tile is a node, and each edge connects to a neighbor. Easy to reason about, great for tactical and roguelike games.
- Waypoint graphs: place hand-authored nodes at key intersections, doorways, and cover spots. Cheap to search, but tedious to maintain as levels grow.
- Navigation meshes: represent walkable surfaces as convex polygons. One node can cover an entire courtyard, so the search stays fast even in huge spaces.
From a tabletop dungeon to a 4K open world, the rule is the same. You discretize the world, connect the dots, and hand the graph to a search algorithm. Skip the graph and try to search raw geometry, and you’re running a different (and much slower) kind of math, usually some form of sampling or optimization that game teams use only when standard graph search won’t fit.
Those formal methods sit behind every mainstream search algorithm, so it’s worth comparing them head-to-head before anything fancier.
BFS, Dijkstra, and A* Compared on the Same Map
With a graph in hand, the question becomes which search to run. Three classics cover the spectrum, and the differences show up clearly on the same map. This is also where most video game AI navigation algorithms earn (or lose) their reputation.
Breadth-first and Dijkstra’s algorithm
Breadth-first search (BFS) expands outward in uniform rings and treats every edge as cost 1. It will find a path, but it ignores that walking across a muddy field should cost more than walking down a sidewalk. Dijkstra’s algorithm fixes that by accepting weighted edges, at the cost of still exploring uniformly in every direction until it finds the goal. On an open map with many destinations, Dijkstra wastes time checking nodes the goal has nothing to do with.
A* and the power of a heuristic
A* adds a heuristic, an estimate of the remaining distance to the goal, and uses that estimate to bias which node to expand next. Common choices are Manhattan distance for grids and Euclidean distance for free-form meshes. With a good heuristic, A* marches almost in a straight line toward the goal while still guaranteeing an optimal path, assuming the heuristic never overestimates the true cost. A* is the default for NPC pathfinding in games for that reason, and it’s the algorithm most engines ship out of the box.
| Algorithm | Edge cost | Search shape | Best for |
|---|---|---|---|
| BFS | Uniform (1) | Expanding rings | Small grids, unweighted puzzles |
| Dijkstra | Weighted | Uniform expansion to goal | Multi-destination queries, terrain costs |
| A* | Weighted | Heuristic-biased toward goal | Single-source, single-goal NPC routes |
| Greedy best-first | Ignored | Heads straight at goal | Fast, non-optimal hints, visual approximation |
A poor heuristic can sabotage A*. If your estimate routinely overshoots the real cost, A* may skip over the optimal route and return a longer one, or expand more nodes than Dijkstra would have. The remedy is a heuristic that is admissible (never overestimates) and consistent (the estimate shrinks as you get closer). For anyone doing a pathfinding algorithm comparison in games, this admissibility rule is the single biggest separator between a fast A* and a slow one.
Navigation Meshes and Why Modern 3D Games Use Them
Grids work, but a 1-meter tile on a 2-kilometer world map means 4 million cells, and most of them are empty space. That’s why 3D games from Halo onward switched to navigation meshes (NavMeshes), which collapse every walkable patch of floor into a convex polygon. A single node then covers a hallway, a courtyard, or a roof, and the search graph shrinks by orders of magnitude.
Recast and Detour in practice
Recast, an open-source library by Mikko Mononen, voxelizes the level geometry, erodes walls, and walks the walkable surface to spit out a polygon mesh. Detour, the companion library, then handles the actual path queries, funnel algorithm smoothing, and tile-based loading for streaming worlds. Unity and Unreal Engine both ship Detour as their default navigation backend, and most third-party engines use it too.
Tip: when prototyping, hand-author a small mesh in your editor and you can validate gameplay before the full Recast bake finishes. It also teaches you what Recast is doing when it fails.
A NavMesh also handles the awkward cases that grids handle badly. Ramps become thin slivers linking two flat polygons, irregular terrain turns into triangles that match the ground, and you can mark polygons as “jump from here to there” to support ledge links without writing a separate graph layer.
Static navmeshes cover the floor, but the moment a crate or another NPC enters the scene the route is already stale.
Dynamic Obstacles, Re-Planning, and Crowd-Scale Movement
Pathfinding for a single NPC in a static room is the easy part. Production games deal with doors that open, covers that blow up, allies that walk into the hallway, and hundreds of units that all want the same ladder. The same A* query, run naively, will fail or freeze the game in any of those cases.
Reactive re-pathing and D* Lite
When the world changes, a planner either patches the existing path (local repair) or throws it out and re-searches (global re-plan). D* Lite is the classic algorithm for local repair: it remembers which way it expanded and re-uses that work, so updating a path after one wall moves is dramatically cheaper than starting from scratch. Most AAA shooters blend the two, doing a local repair on the next waypoint and a full re-plan only when the goal itself moves or the path is fully blocked.
Hierarchical search and flow fields
Long-distance queries over huge maps still get expensive. Hierarchical pathfinding clusters the world into regions and precomputes inter-region paths, so a cross-map query skips most of the graph and only refines the start and end clusters. Flow fields take a different tack: instead of running a per-unit search, you run one search per goal, paint a direction onto every node, and have every unit read its current cell. RTS games with hundreds of units, such as Supreme Commander and They Are Billions, lean on flow fields because the per-unit cost stays near zero.
Steering and the “feel” layer
A perfect grid path still looks terrible without steering. Steering behaviors, the family of local rules popularized by Craig Reynolds’ Boids work, take the path as input and add separation (don’t pile on top of neighbors), arrival (slow down near the goal), and obstacle avoidance (sidestep before you clip). Pathfinding answers “where to go”; steering answers “how to actually walk there without bumping into your friends.”
Choosing and Optimizing a Pathfinding System for Your Game
Picking the right pathfinding setup is less about memorizing algorithms and more about matching the search to your grid size, unit count, and how often the world changes. The wrong choice shows up as frame drops; the right choice stays invisible.
Match the algorithm to your scale
A small tactics game on a 20×20 grid runs BFS in microseconds and gains nothing from A*. A 3D action game with streaming terrain and a few dozen enemies wants A* over a baked NavMesh. An RTS with 500 units moving to the same base point wants a flow field, not 500 independent A* calls. And a heavily dynamic world (a destructible cover shooter, a sandbox with player-built walls) wants D* Lite or its modern cousins so re-plans stay cheap.
Budget the queries, profile early
Even A* has a CPU cost, and one unthrottled query on a dense NavMesh can spike a frame budget for hundreds of units. The standard fix is to tick only a small slice of agents per frame (say, 8% of the crowd) and round-robin the rest. Profile on your worst-case map, not your demo level, because pathfinding cost scales with node count, and shipping maps are always bigger than you planned. The cheapest pathfinding bug is the one you find at 30 FPS in QA, not at 5 FPS in a streamer review.
Pro tip: jump point search (JPS) can cut A‘s expansions by an order of magnitude on uniform grids with no obstacles, but it falls back to plain A the moment you add weighted or non-uniform costs.
Finally, treat pathfinding as part of your gameplay budget. Cache paths when the goal and world haven’t changed, share partial results across agents moving to nearby goals, and prefer local steering fixes over full re-plans. Your NPCs should look like they know where they’re going, and the framerate should look like the pathfinder never existed.
Key Takeaways
- Pathfinding is graph search: every technique, from BFS to A* to D* Lite, runs over nodes and edges that model the walkable world.
- A* is the default: a good admissible heuristic gives optimal paths with far fewer node expansions than Dijkstra.
- NavMeshes beat grids at scale: one polygon replaces thousands of tiles, and Recast/Detour ship in Unity, Unreal, and most third-party engines.
- Dynamic worlds need re-plans: D* Lite for local repair and flow fields for crowds keep re-planning costs bounded.
- Steering sells the illusion: separation, arrival, and obstacle avoidance turn a math path into believable movement.
FAQ
What is the best pathfinding algorithm for video games?
For most 3D games, A* over a baked navigation mesh is the best default because it balances optimal routes with fast queries. Greedy best-first search is faster but not optimal, while Dijkstra’s algorithm shines when many units need paths from one source. Match the algorithm to your world’s size and how often the geometry changes.
How do games calculate NPC paths in real time?
Games run a graph search, usually A*, against a baked or streamed navigation mesh, then smooth the result with a funnel algorithm so the path hugs corners instead of zigzagging. For crowds, a single flow-field search can replace hundreds of per-unit queries without losing believability.
What is the difference between A* and Dijkstra in game AI?
Dijkstra expands uniformly outward and guarantees the cheapest path from one source to every reachable node. A* adds a heuristic estimate of the distance to the goal and uses it to expand fewer nodes, giving the same optimal path faster when the heuristic is admissible.
How do navmeshes work in game engines like Unity and Unreal?
Unity and Unreal bake level geometry into a navigation mesh at edit time, marking walkable polygons and the connections between them. At runtime, the engine runs A* (or a variant) over that mesh whenever an NPC needs a new path, and the standard backend is the open-source Recast and Detour libraries.
Why do game characters sometimes get stuck on geometry?
Stuck states usually come from a mismatch between the pathfinding graph and the physics collider, or from an agent that is too wide for the gap it was told to walk through. Tightening the agent radius, shrinking the NavMesh near doorways, and adding steering obstacle avoidance are the usual fixes.
How is pathfinding optimized for large open worlds?
Open worlds tile the NavMesh into chunks, stream them with the player, and use hierarchical search so long routes skip whole regions. Caching, time-sliced queries, and flow fields for crowds keep the per-frame cost bounded even when hundreds of agents are on screen.
