An enemy that heads in a straight line towards the player works until there is a wall in the way. At that point it gets stuck against the obstacle, and the illusion of intelligence vanishes. To move through a level with walls, doors and corridors, characters need pathfinding: an algorithm that computes a walkable route from the starting point to the destination. On a grid, the most widely used method is A*.
The level as a graph
The first step is to represent space as a graph. On a tile map this is immediate:
- each walkable cell is a node;
- each pair of adjacent walkable cells is connected by an edge;
- each edge has a cost, for example 1 for an orthogonal step.
Different terrains can be given different costs: a swamp might cost 3, a road 1. The algorithm will look for the path with the lowest total cost, not necessarily the one with the fewest steps.
The idea behind A*
A* explores nodes starting from the origin and always picks first the one that looks most promising. For each node n it computes:
g(n): the real cost of the best path found so far from the origin ton;h(n): an estimate of the cost fromnto the destination, called the heuristic;f(n) = g(n) + h(n): the estimated total cost of going throughn.
The algorithm maintains two sets: the open list, with nodes to examine, and the closed list, with those already processed.
open = {origin}; g[origin] = 0
while open is not empty:
current = node in open with lowest f
if current == destination: rebuild the path
move current from open to closed
for each neighbour v of current not in closed:
new_g = g[current] + cost(current, v)
if v not in open or new_g < g[v]:
g[v] = new_g
parent[v] = current
add v to open with f = new_g + h(v)
The path is rebuilt by starting from the destination and following parents back to the origin.
Choosing the heuristic
The heuristic guides the search. If it never overestimates the real cost it is called admissible, and A* is guaranteed to find the optimal path. The most common on a grid:
| Allowed movement | Heuristic | Formula |
|---|---|---|
| 4 directions only | Manhattan distance | abs(dx) + abs(dy) |
| 8 directions, diagonal cost 1 | Chebyshev distance | max(abs(dx), abs(dy)) |
| 8 directions, diagonal cost √2 | Octile distance | max + (√2 − 1) · min |
| Free movement | Euclidean distance | √(dx² + dy²) |
With a heuristic of zero, A* becomes Dijkstra's algorithm: it always finds the optimal path but explores many more nodes. With an overestimating heuristic, for example multiplied by 1.5, the search is faster but the path may not be the best: in a game this is often an acceptable trade-off.
Diagonal movement and corners
If diagonals are allowed, you must prevent «cutting» wall corners: a diagonal step between two solid cells would take the character through a corner. The typical rule allows the diagonal only if both adjacent orthogonal cells are free.
Performance
The critical point is quickly finding the node with the lowest f in the open list. Scanning a list at every step is slow; a priority queue, implemented with a binary heap, cuts the cost considerably. Other tricks:
- use arrays indexed by cell instead of dictionaries for
g, parents and status; - cap the number of nodes explored per request, abandoning impossible searches;
- spread the requests of many enemies across several frames;
- recompute the path only when the destination moves significantly, not at every step.
More natural paths
A grid path tends to be jagged, with obvious zigzags. Two corrections improve the result a great deal:
- smoothing: remove intermediate points when there is a clear line of sight between two non-consecutive points;
- path following: the character does not jump from cell to cell but heads for a point a few steps further along the path, moving fluidly.
Many units, one destination
In strategy games or games with hordes of enemies, running A* for each unit towards the same goal is wasteful. A flow field solves the problem in reverse: a single search is run starting from the destination, assigning each cell its distance from the goal. Each unit then looks at its own cell and moves towards the neighbour with the lowest distance. The cost no longer depends on the number of units.
Beyond the grid
In 3D games or maps not built from tiles, navigation meshes are used: convex polygons covering the walkable areas. A* operates on the polygons instead of cells, with far fewer nodes. The main engines provide tools to generate them automatically from the level geometry.
In short
- Pathfinding turns the level into a graph of nodes and edges with costs.
- A* always picks the node with the lowest estimated total cost.
- An admissible heuristic guarantees the optimal path; overestimating speeds up the search.
- Priority queues, limits and infrequent recalculation keep performance good.
- Flow fields and navigation meshes extend the ideas to many units and 3D worlds.
