Interactive demo
Greedy Best-First Search
Greedy best-first search always continues from the cell that seems closest to the goal. It ignores how far it has already come, which makes it fast in open space and short-sighted in front of walls.
Draw walls or mud on the grid and drag the start and the goal. Once a search is finished, every change is searched again right away. Draw a wall shaped like a cup between start and goal, open towards the start: the search runs into the cup and only then finds its way around.
Playback
- Expanded
- –
- Frontier (max.)
- –
- Path cost
- –
Press Play or Next Step to start the search.
Grid
Options
Legend
- Start (drag to move)
- Goal (drag to move)
- Wall
- Mud
- Frontier (open list)
- Visited (closed list)
- Expanded right now
- Path
Properties
Optimal
No
It only looks ahead, never at the cost so far, so its paths can be much longer than needed.
Weighted cells
No
The costs do not change the order, so it walks straight through mud.
Heuristic
Yes
Only the estimated distance to the goal decides.
Any angle
No
Moves from cell to cell, straight or diagonally.
All 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 this page | 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 |
1. Only the estimate counts
The priority of a cell is h, its estimated distance to the goal. As long as nothing is in the way, the search goes straight to the goal and expands hardly more cells than the path is long.
2. Fooled by obstacles
Behind a wall, cells close to the goal look best even when they lead into a dead end. The search fills the pocket before it tries the way around, and the path it reports keeps the detour.
3. The estimates
Manhattan counts straight steps, octile allows diagonal steps, Euclidean is the straight line and Chebyshev counts a diagonal step as 1. For greedy search the choice changes the shape of the path, not whether it is optimal: it never is.