Pathfinding Algorithm
Greedy Best-First Search
“The Impatient Optimist”
History
Greedy Best-First Search comes from the early days of AI, where researchers experimented with pure heuristics. It operates on a simple philosophy: "That looks like the right direction, so I'm going that way."
It represents the extreme end of the heuristic spectrum. While A* balances the past (cost so far) and future (estimated cost), Greedy BFS ignores the past entirely and focuses solely on the destination.
How It Works
Greedy BFS is A* with amnesia. It drops the component and makes decisions solely based on (the estimated distance to the goal).
The Algorithm Step-by-Step
- Initialize: Put start node in the priority queue.
- Pick: Choose the node that *looks* closest to the goal.
- Check: Is it the goal?
- Push: Add neighbors to the queue based on their heuristic distance.
- Repeat.
The Trap
Because it ignores the cost of the path taken so far, Greedy BFS can get fooled easily. If there is a U-shaped wall, it will run straight into the center of the U, hit the wall, and be forced to search effectively random neighbors until it finds a way around.
It uses a Priority Queue like A*, but typically runs much faster because it beelines for the target. However, it can degenerate into a slow search in complex mazes.
Stores the frontier of nodes. similar to A*.
The core data structure powering Greedy Best-First Search.
How this algorithm appears during visualization.
Code Walkthrough
Real implementations in multiple programming languages. Select a language to view idiomatic code.
1import heapq23def heuristic(a: tuple[int, int], b: tuple[int, int]) -> int:4 """Manhattan distance heuristic."""5 return abs(a[0] - b[0]) + abs(a[1] - b[1])67def greedy_best_first(grid: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]] | None:8 """Greedy best-first search using only heuristic. Does NOT guarantee shortest path."""9 rows, cols = len(grid), len(grid[0])10 parents = {start: None}11 open_set = [(heuristic(start, end), start)]12 visited = set()13 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]1415 while open_set:16 _, current = heapq.heappop(open_set)1718 if current in visited:19 continue20 visited.add(current)2122 if current == end:23 path = []24 while current:25 path.append(current)26 current = parents[current]27 return path[::-1]2829 row, col = current30 for dr, dc in directions:31 neighbor = (row + dr, col + dc)32 nr, nc = neighbor3334 if (0 <= nr < rows and 0 <= nc < cols35 and grid[nr][nc] == 036 and neighbor not in visited):37 if neighbor not in parents:38 parents[neighbor] = current39 h = heuristic(neighbor, end)40 heapq.heappush(open_set, (h, neighbor))4142 return NoneReal World Use Cases
- 1Fast prototyping where optimality doesn't matter
- 2Games where 'good enough' movement is acceptable
- 3Scenarios with very few obstacles
- 4AI behaviors that simulate impulsiveness
- 5Web crawling with specific target topics
- 6Heuristic testing
Key Insights
- It is incredibly fast in open spaces.
- It does NOT guarantee the shortest path.
- It can find drastically suboptimal paths (the 'long way around').
- It is susceptible to getting stuck in local optima.
- It demonstrates the danger of relying purely on heuristics.
When to Use
Use Greedy BFS when you need raw speed and don't care if the path is slightly inefficient. It's great for simple movement logic in games with open maps.
When NOT to Use
Do not use this for navigation apps or logistics. Sending a user on a route that is 50% longer just because it looked good at the start is a bad user experience.