How Pathfinding AI Moves NPCs

An NPC that walks from a village to a distant castle, weaving around trees and buildings without ever getting stuck, is not improvising a route the way a person does. It is running a graph search algorithm over an invisible network of connected points laid across the game world, calculating a full route before the character takes a single step. The technique traces directly back to a 1959 shortest-path algorithm from computer scientist Edsger Dijkstra and a 1968 heuristic-guided refinement of it, published by three researchers working on one of the first mobile robots ever built.

Turning a map into something a computer can search

Before any character can find a path, someone or something has to convert the walkable parts of a level into a data structure a search algorithm can actually operate on. A computer does not perceive floor space, walls, or slopes the way a player does. It needs the level reduced to a graph: a set of nodes, meaning discrete points that represent locations, connected by edges, meaning the possible routes between those points, each edge carrying a cost that usually stands in for distance, difficulty of movement, or both.

Early 3D games commonly used a grid, dividing the entire level into uniform square or hexagonal cells and marking each one walkable or blocked. Grids are simple to generate and easy to reason about, but they waste a lot of structure. A wide-open field gets chopped into thousands of identical cells that do not need to be searched individually, and diagonal movement across a grid can produce paths that look artificially jagged unless the engine adds extra smoothing logic.

Most modern engines instead use a navigation mesh, usually shortened to navmesh, which is a set of irregular polygons that cover only the actual walkable floor of a level, hugging the true shape of the terrain rather than forcing it into a grid. A large open plaza might be represented by a single big polygon, while a cluttered room full of furniture becomes dozens of small ones, each connected to its neighbors by a shared edge. Unity's NavMesh system and Unreal Engine's Navigation Mesh system, both extensively documented in their public developer references, generate this polygon layout automatically from level geometry, then let designers mark specific areas as off-limits, expensive to cross, or walkable only by certain character types.

This graph-building step matters as much as the search algorithm that runs on top of it. A search algorithm can only be as good as the map it is given. If the navmesh has a gap, a stray polygon that does not connect to its neighbor, or an area that was walkable at level design time but is not walkable anymore because something changed at runtime, no algorithm, however elegant, can produce a correct path across it.

Dijkstra's algorithm and the heuristic that made A* practical

The foundational algorithm behind essentially all modern game pathfinding is Dijkstra's algorithm, published by Dutch computer scientist Edsger W. Dijkstra in 1959 under the modest title "A Note on Two Problems in Connexion with Graphs" in the journal Numerische Mathematik. Dijkstra reportedly devised the algorithm's core idea in about twenty minutes while sitting at a café with his fiancée, thinking through how to demonstrate the capabilities of a new computer at the Mathematical Center in Amsterdam, and later implemented it to compute the shortest route across a simplified 64-city map of the Netherlands.

Dijkstra's algorithm guarantees it will find the mathematically shortest path between two points on a graph, and it does this by exploring outward from the start node in every direction, always expanding whichever unvisited node currently has the lowest known cost from the start. Visualize dropping a stone into still water: the ripple spreads outward evenly in all directions at once, with no sense of where the target actually is. The algorithm is correct and complete, but it wastes enormous effort exploring parts of the map that have nothing to do with where the character is actually trying to go.

A* — pronounced "A-star," is a graph search algorithm that extends Dijkstra's method by adding a heuristic, an estimate of the remaining distance to the goal, so the search can prioritize nodes that appear to be heading in the right direction rather than exploring uniformly in every direction. A* was first published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael in "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," in IEEE Transactions on Systems Science and Cybernetics, volume 4. The three researchers were affiliated with the Stanford Research Institute's Shakey the Robot project, one of the earliest mobile robots capable of reasoning about its own actions and planning routes through a room full of obstacles, and A* was developed specifically to let Shakey plan a route without exhaustively searching its entire known environment.

The heuristic in A* is typically a simple estimate, such as straight-line ("as the crow flies") distance to the goal, that never overestimates the true remaining cost. As long as that condition holds (a property formally called admissibility), A* is mathematically guaranteed to still find the shortest possible path, exactly like Dijkstra's algorithm, while typically examining a fraction of the nodes Dijkstra's algorithm would need to check. Returning to the water-ripple image, A* behaves like a ripple that has been given a magnet pulling it toward the goal: it still expands outward and still respects real obstacles, but it stretches preferentially toward the destination instead of wasting energy on nodes moving away from it. That single addition, a numeric hint about which direction is promising, is the entire reason a search technique from 1968 remains fast enough to run for dozens of characters simultaneously in a modern real-time game.

A* was developed at the Stanford Research Institute for Shakey the Robot, one of the first mobile robots able to reason about its own actions, and its 1968 publication predates the first true 3D game engines by roughly two decades. The core algorithm running most game NPCs today has not changed in its underlying logic since then.

Comparing the major pathfinding approaches

Game engines rarely rely on a single technique end to end. Instead, most production pipelines layer a broad-strokes global search over a fine-grained local movement system, and the specific combination depends heavily on how many agents need to move at once and how dynamic the environment is.

Technique	Computational cost	Guarantees shortest path?	Typical use case
Dijkstra's algorithm	High — explores uniformly outward	Yes	Precomputing distances from a single point to everywhere, static utility maps
A* (A-star)	Moderate — heuristic-guided	Yes, if heuristic never overestimates	Single-character or small-group route planning, the default in most games
Navigation mesh (navmesh) search	Moderate, scales with polygon count, not cell count	Yes, for the graph it searches	Modern 3D level traversal; the map representation A* or similar searches run on
Hierarchical pathfinding (HPA*)	Low for long routes, adds setup cost	Approximate at region boundaries	Large open-world maps where full A* every frame would be too slow
Flow fields	High upfront per goal, near-zero per agent afterward	Approximate, optimized for many agents sharing one goal	Real-time strategy games moving hundreds of units to the same destination
Reciprocal velocity obstacles (RVO)	Low, per-agent, per-frame	Not applicable — local avoidance, not route planning	Crowd and formation movement, avoiding other moving agents mid-route

Games typically combine a global route planner from the top rows with a local movement or crowd-avoidance layer from the bottom rows, rather than relying on just one technique.

Why do so many games specifically use A* instead of plain Dijkstra?

Because A* returns the same guaranteed-shortest result as Dijkstra's algorithm while typically expanding far fewer nodes, thanks to its distance heuristic prioritizing promising directions. In a real-time game recalculating paths for multiple characters every few frames, that efficiency difference is the reason A* is computationally viable and pure Dijkstra generally is not, outside of precomputed, unchanging distance maps.

Why NPCs sometimes walk in ways that look robotic or wrong

A* finds the mathematically cheapest path according to the cost values assigned to the graph, and "cheapest" according to the algorithm is not automatically the same as "natural-looking" to a human watching the screen. If every edge in the navmesh graph carries an identical cost regardless of terrain, an NPC can walk in a perfectly straight, robotic-looking line, or take a technically shorter route that clips uncomfortably close to a ledge or a hazard, because the algorithm has no built-in concept of what looks natural. It only knows what is numerically cheapest given the inputs it was handed.

This is similar to how a car navigation app sometimes suggests a route that is technically fastest according to its traffic-and-distance model but feels wrong to a local driver who knows that intersection has a confusing merge lane the app's cost model does not weight heavily enough. The route-finding logic underneath is not broken; the mismatch comes from what the cost function does or does not account for, not from a flaw in the search itself. Designers routinely close this gap by hand-tuning cost penalties: raising the cost of open ground near likely player sightlines so stealth-game guards avoid exposing themselves, or raising the cost of areas near ledges so companion characters do not walk uncomfortably close to a drop.

Character animation is a second, separate source of "unnatural" movement that has nothing to do with the pathfinding algorithm itself. A* produces a sequence of waypoints, essentially straight-line segments between key points on the navmesh, and a naive implementation that snaps a character directly onto that polyline will produce sharp, unrealistic turns at each waypoint. Better implementations run the raw A* output through a smoothing or string-pulling step, most commonly the funnel algorithm, which straightens the path within the navmesh corridor the search already found, and then feed that smoothed path into a steering or locomotion system that blends turning animations. Correcting this is largely a rendering and animation-layer fix, not a change to the underlying route search.

Why NPCs get stuck, walk into walls, or freeze mid-route

Because the navmesh or grid an NPC's pathfinding relies on can become outdated the instant the level changes dynamically, for example if a door closes, debris falls into a previously walkable corridor, or another structure gets built mid-match, and the character has no path-recovery logic to notice and replan. A navmesh generated once when the level loads, and never updated afterward, can leave an NPC calculating and committing to a route across ground that is no longer actually passable.

Well-built games recalculate the navmesh in the affected region, or trigger a full path recalculation, whenever something blocks a previously open route, and add periodic replanning or stuck-detection logic that notices when a character has not made meaningful progress and forces a new search. Games that skip this layer produce the exact "NPC walking in place against a wall" behavior players sometimes clip and share, and it is a well-documented category of failure in game AI development rather than an exotic edge case. Independent game AI conference proceedings and postmortems, including material published through the long-running Game AI Pro book series that collects contributed chapters from professional game AI programmers, catalog stuck-agent and navmesh-desync bugs as one of the recurring, expected failure modes any shipped pathfinding system has to defend against, not a rare accident.

A closely related and well-documented case is large-scale unit movement in real-time strategy games. In the original Supreme Commander, each unit computed and followed its own individual A* path, and when two units' paths crossed, the game's collision logic would simply stop both units and wait for the conflict to resolve rather than replanning around each other. In large battles involving hundreds of units, this produced compounding gridlock: a new path around one collision would frequently lead straight into a second and third collision, and players ended up manually managing unit movement across the map to avoid the pile-ups. Its sequel, Supreme Commander 2, replaced this per-unit A* approach with flow field pathfinding (built on techniques from the Continuum Crowds research), a fundamentally different technique that computes one shared directional map for an entire destination-bound group instead of one independent path per unit, specifically to solve this documented large-crowd gridlock problem.

Can pathfinding AI adapt if the level changes while an NPC is already mid-route?

Yes, if the engine is built to support it. Dynamic obstacle systems mark navmesh regions as temporarily blocked and trigger an automatic replan for any agent whose stored path now crosses that blocked region. Engines lacking this layer will leave the NPC committed to a path that has become invalid, which is the direct cause of most "walked into a wall and froze" behavior players notice.

Beyond one path: local avoidance and moving through crowds

Modern games rarely calculate a single static path per NPC and consider the job finished. A pathfinding system usually needs a second layer working underneath the long-range route: local obstacle avoidance, which handles moving obstacles that a precalculated path could not have anticipated, such as another character walking through the same corridor, a thrown object, or the player standing directly in the way.

Reciprocal velocity obstacles, commonly abbreviated RVO, is a widely used local avoidance technique introduced in a 2008 paper by Jur van den Berg, Ming C. Lin, and Dinesh Manocha, presented at the IEEE International Conference on Robotics and Automation. RVO lets each moving agent adjust its own immediate velocity, in real time, based on the predicted velocities of nearby agents, so a group of characters can flow around each other smoothly without every single one recalculating its entire A* route from scratch every time someone steps into its way. An extension called Optimal Reciprocal Collision Avoidance, or ORCA, refined the mathematics further and is now the basis for local-avoidance systems in several commercial crowd simulation tools.

Hierarchical pathfinding — a broad-strokes route-planning strategy that breaks a large map into big regions first, computes a cheap region-to-region path, and only calculates precise, detailed paths within the specific regions a character is currently traveling through. This is directly analogous to how a person plans a long road trip: choose the highways connecting cities first, and only worry about which specific street to turn onto once actually inside the destination city. Open-world games that need dozens of characters navigating simultaneously across enormous maps rely on hierarchical approaches like this because recalculating a full, detailed A* search across the entire map for every character, every few frames, is computationally far too expensive to sustain at a stable frame rate.

Flow fields — a pathfinding technique that computes one shared directional field pointing toward a single destination, letting an unlimited number of agents follow it simultaneously at near-zero additional cost per unit, are the technique real-time strategy games increasingly reach for specifically because they sidestep the per-agent replanning cost that made large-scale A* movement in games like the original Supreme Commander gridlock under heavy unit counts. The tradeoff is that a flow field is computed for one destination and shared by everyone heading there, so it is a poor fit for characters that each need a genuinely distinct destination or a genuinely distinct route.

Common misconceptions about how NPCs "see" a level

A frequent assumption is that NPC pathfinding involves a character visually perceiving the map the way a player does and reasoning about what it sees on screen. In reality, the pathfinding AI has no visual understanding of the rendered scene at all. It queries a precomputed graph or navmesh data structure that exists entirely separately from whatever pixels are drawn to the screen, and it has no concept of lighting, camera angle, or visual clutter unless a designer has explicitly encoded that information as a cost value on specific navmesh polygons.

A second misconception is that the mathematically shortest path is always the best path for player experience, and that a well-designed game will always route characters along it. Designers routinely add deliberate cost penalties to specific navmesh regions, such as raising the cost of open ground within a likely player sightline, specifically to steer guards and other NPCs away from mathematically shorter but tactically exposed or narratively unnatural-looking routes. The algorithm is doing exactly what it is told; the design decision is in the cost values fed to it, not in the search logic itself.

A third misconception treats every visible pathfinding failure as evidence the underlying AI is unsophisticated or broken. Most of the widely mocked "the NPC got stuck" clips trace back to a stale navmesh that was never updated after the level changed, a missing local-avoidance layer, or a cost function or hierarchical setup that did not anticipate a specific edge case, all of which are failures in the supporting systems layered around the search rather than a flaw in A* itself, which remains mathematically sound and essentially unchanged in its core logic since 1968.

A fourth, more subtle misconception is assuming pathfinding and NPC decision-making are the same system. Pathfinding only answers "how do I physically get from point A to point B." A separate decision-making layer, often built on behavior trees or finite state machines, decides where an NPC should be going and why in the first place, whether to flee, patrol, or attack. The choice of destination is a distinct problem from the search that computes the route to reach it, and confusing the two is a common source of misdiagnosing which system actually caused a given piece of odd NPC behavior.

The takeaway

Pathfinding AI moves NPCs by first converting the game world into a searchable graph, most often a navigation mesh of walkable polygons, and then running a graph search algorithm, almost always A* or one of its descendants, that combines Dijkstra's guaranteed-shortest-path logic from 1959 with a distance heuristic from 1968 to find a near-optimal route while examining far less of the map than an exhaustive search would need. Strange-looking or stuck NPC behavior almost always traces back to the supporting systems around that search, an outdated navmesh, a missing local-avoidance layer, or a cost function that did not anticipate a specific situation, rather than to a flaw in the underlying algorithm itself, which remains fundamentally the same technique used to route one of the first reasoning robots ever built.

---

Read next:

• How game engines render lighting
• How matchmaking ratings work
• How procedural audio creates sound

FAQ

Q: What is A and why is it used in games?*

A* is a graph search algorithm that finds a near-shortest path between two points by combining the actual travel cost from Dijkstra's algorithm with a heuristic estimate of remaining distance. Published in 1968 by Hart, Nilsson, and Raphael for a Stanford robotics project, it remains the default game pathfinding approach because it finds good paths while exploring far fewer possibilities than exhaustive search.

Q: What is a navigation mesh?

A navigation mesh, or navmesh, is a set of connected polygons covering only the actual walkable floor space of a game level, used as the graph structure that pathfinding algorithms search across. It replaced older, less precise grid-based systems in most modern 3D engines, including Unity and Unreal Engine's built-in navmesh tools.

Q: Why do NPCs sometimes walk in unnatural, perfectly straight lines?

Because the pathfinding algorithm optimizes strictly for the lowest-cost path according to the numeric costs assigned to the graph, which does not automatically account for what looks natural to a human observer unless designers explicitly add extra cost penalties or a path-smoothing step for that purpose.

Q: How do games handle pathfinding for large crowds of NPCs efficiently?

Many games combine hierarchical pathfinding, which breaks the map into large regions for cheap high-level planning, with local avoidance techniques like reciprocal velocity obstacles (RVO), so each character adjusts its immediate movement around nearby moving obstacles without recalculating its entire route. Real-time strategy games moving hundreds of units at once, such as Supreme Commander 2, instead use flow fields, which compute one shared directional map for an entire group heading to the same destination.

Q: Why do NPCs sometimes get stuck or walk into walls?

Most commonly because the navmesh or grid the AI relies on has become outdated after the level changed dynamically, for instance a door closing or debris blocking a previously walkable path, and the character lacks the stuck-detection or replanning logic needed to notice and recalculate. This is a well-documented, recurring category of game AI failure rather than evidence the search algorithm itself is flawed.