Interactive demo
Pathfinding Algorithms
How do you get from A to B? Eight search algorithms find their way through walls and mud, step by step. Each one makes a different trade-off between speed, the quality of the path and what it needs to know.
Uninformed search
Breadth-First Search
Spreads in rings of equal step count from the start. Finds the path with the fewest steps, but ignores what a step costs.
Optimal: ConditionallyWeighted cells: No
Depth-First Search
Follows one direction as far as it can and only backtracks at dead ends. Finds a path, but rarely a short one.
Optimal: NoWeighted cells: No
Dijkstra's Algorithm
Always expands the cheapest cell found so far. It spreads by cost and finds the cheapest path, around the mud if that is cheaper.
Optimal: YesWeighted cells: Yes
Bidirectional Search
Runs Dijkstra's algorithm from the start and from the goal at once. The two searches meet in the middle and together explore less.
Optimal: YesWeighted cells: Yes
Informed search
Greedy Best-First Search
Always expands the cell that looks closest to the goal. Very fast in open space, but easily lured into dead ends and detours.
Optimal: NoWeighted cells: No
A* Search
Adds an estimate of the remaining distance to the cost so far. With a good estimate it finds the cheapest path and explores far less than Dijkstra.
Optimal: ConditionallyWeighted cells: Yes
Grid techniques
Jump Point Search
A* for uniform grids that jumps along straight runs and only stops where the path might turn. Far fewer cells end up in the open list.
Optimal: ConditionallyWeighted cells: No
Theta*
A* that links a cell straight to its parent's parent whenever the line between them is free. Paths run at any angle and beat grid paths.
Optimal: NoWeighted cells: Conditionally
Pathfinding algorithms compared
| Algorithm | Optimal | Weighted cells | Heuristic | Any angle |
|---|---|---|---|---|
| Breadth-First Search | Without mud and diagonals | No | No | No |
| Depth-First Search | No | No | No | No |
| Dijkstra's Algorithm | Yes | Yes | No | No |
| Bidirectional Search | Yes | Yes | No | No |
| Greedy Best-First Search | No | No | Yes | No |
| A* Search | With weight 1 and an admissible heuristic | Yes | Yes | No |
| Jump Point Search | Without mud | No | Yes | No |
| Theta* | No | Shortcuts over open ground only | Yes | Yes |
The previews show every algorithm on the same map with diagonal moves: walls in light gray, mud in brown.