Game dev
Saved & recent

Pathfinding

Related terms: A*, navmesh, navigation

Finding a route from A to B around obstacles. A* (A-star) is the classic algorithm. It explores a graph of positions, always expanding the one that looks closest to the goal, and returns the shortest path.

In 2D the graph is often a grid. In 3D it is usually a navmesh: a simplified mesh of the walkable floor, built from the level geometry.

Further reading
Peter Hart, Nils Nilsson and Bertram Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths
start goal shortest route expanded cells
A* searches four-way steps on the floor. Pale violet cells are the cells it expanded. The dark route reaches the goal using the fewest steps around the walls.

View in the full Game dev collection