The problem in one sentence
A character stands in one spot, wants to reach another, and there are walls, crates and cliffs in between. Pathfinding is how the game finds a route that avoids those obstacles. It sounds easy because people do it without thinking, but a game character has no view of the level. It only knows the numbers the game gives it, so the level has to be turned into something a program can search.
Step one: simplify the level
The detailed art of a level, with its thousands of triangles, is useless for route planning. Games build a much simpler map of where characters can and cannot go. There are three common ways to do it.
Grids
The simplest method lays a grid over the level. Each cell is either open or blocked. A character can move between neighboring open cells, and the route is a chain of cells.
Grids are easy to understand and fit games that are already tile-based, such as tactics games and many puzzle games. The cost grows with size: a 10 by 10 grid has 100 cells, but a 1,000 by 1,000 grid has a million, and searching that many can take noticeable time. Grids can also produce stiff-looking movement if characters are limited to horizontal, vertical and diagonal steps.
Waypoints
Instead of covering everything with cells, the designer places a modest number of points at useful spots, such as doorways, corridor junctions and corners, and links the ones that have a clear path between them. A character first moves to the nearest waypoint, follows the links to the one closest to its goal, and then walks to the final spot.
This uses far fewer points than a grid, which makes searching fast. The downside is that characters tend to follow the links closely, which can make them look like they run on rails, and the designer must place points by hand or with a tool.
Navigation meshes
A navigation mesh, often shortened to navmesh, covers the walkable floor with a set of connected shapes, usually triangles or convex polygons. A character can move freely within any one shape, and the connections between shapes tell the search where it may cross.
Because each shape can be large, a navmesh needs far fewer pieces than a grid and gives smoother, more natural routes. Many engines can generate one automatically from the level, though the result still needs checking.
Step two: search
Once the level is a network of connected pieces, the game searches for a sequence that links start to goal. The most widely used method is called A-star, written A*. The idea in plain terms is to explore outward from the start but to prefer pieces that seem to lead toward the goal.
For each candidate piece, the search keeps two numbers: how far it has traveled so far, and a rough guess of how far remains. It adds them and always expands the candidate with the lowest total. The guess must never overestimate, or the method may return a longer route than necessary. On a grid, a common guess is the straight-line distance or the count of steps ignoring walls.
A tiny hypothetical case: on a grid with no obstacles, a character at the bottom-left needs to reach a cell 3 steps right and 2 steps up. With diagonal movement allowed, the shortest route is 3 steps (two diagonal and one straight). Move in only four directions, and the shortest route is 5 steps (3 plus 2). The path found depends on which movements the game allows.
If the grid contains a wall, the search still prefers cells toward the goal but will back up and explore alternatives when it hits the wall, which is why it finds a way around instead of getting stuck.
Step three: follow the route smoothly
A raw route from a grid or waypoint search can zigzag. Games usually smooth it. One common trick is to check whether the character can walk straight from its current position to a point further along the route, and skip the points in between if so. Another is to steer along the route with gentle turns instead of snapping from point to point. Because the character must also avoid bumping into walls while it moves, this ties in with collision detection.
Why paths look strange
Players notice pathfinding mostly when it fails. Typical reasons include:
- Stuck on doorways or corners. The navigation data may be slightly too narrow, or the character’s collision shape may be wider than the walkable area the planner assumed.
- Taking an odd detour. The cheapest route by the search’s measure may not look sensible to a person, for instance if certain terrain is marked as costly.
- Stopping when the world changes. If a door closes or a bridge is destroyed after the route is planned, the character keeps following an outdated path unless the game replans.
- Crowding. Many characters may all choose the same narrow gap and block each other.
Fixes usually involve data rather than the search itself.
Keeping it affordable
Searching takes time, and every frame has a tight budget. Games reduce the load by planning for only a few characters per frame, by caching routes that are reused, by planning at coarse resolution for long trips, and by giving far-away characters simpler behavior. When a game slows down during a large battle, the cause can be a flood of route requests, which is the kind of thing performance profiling is meant to reveal.
How it fits with behavior
Pathfinding answers “how do I get there?” The character’s behavior rules decide where to go, such as “chase the player.”