Published by Dimitris Kougioumtzis · Updated
Find a path from top-left to bottom-right using four-direction moves. Greedy uses only Manhattan distance and does not guarantee a shortest path.
Expand the cell closest by Manhattan estimate, without accounting for the route cost already accumulated.
When to use Greedy best-first grid search
Comparing heuristic direction with optimal search.
Choosing an alternative
A* includes route cost and finds shortest paths with the supported heuristic.
Worked example: input and state changes
Example input
0,0,0,0;1,1,0,1;0,0,0,0;0,1,1,0
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Scores are Manhattan estimates. Distance traveled does not affect priority.
State at this checkpoint
{ "values": [ 6, "∞", "∞", "∞", "×", "×", "∞", "×", "∞", "∞", "∞", "∞", "∞", "×", "×", "∞" ], "active": [], "kind": "matrix", "columns": 4, "blocked": [ 4, 5, 7, 13, 14 ], "selected": [] }Step 4: Improve cell 2: distance 2, estimate 4.
State at this checkpoint
{ "values": [ 6, 5, 4, "∞", "×", "×", "∞", "×", "∞", "∞", "∞", "∞", "∞", "×", "×", "∞" ], "active": [ 2 ], "kind": "matrix", "columns": 4, "blocked": [ 4, 5, 7, 13, 14 ], "selected": [ 0, 1 ] }Step 9: Expand cell [1,2], distance 3.
State at this checkpoint
{ "values": [ 6, 5, 4, 3, "×", "×", 3, "×", "∞", "∞", "∞", "∞", "∞", "×", "×", "∞" ], "active": [ 6 ], "kind": "matrix", "columns": 4, "blocked": [ 4, 5, 7, 13, 14 ], "selected": [ 0, 1, 2, 3, 6 ] }Step 13: Improve cell 11: distance 5, estimate 1.
State at this checkpoint
{ "values": [ 6, 5, 4, 3, "×", "×", 3, "×", "∞", 3, 2, 1, "∞", "×", "×", "∞" ], "active": [ 11 ], "kind": "matrix", "columns": 4, "blocked": [ 4, 5, 7, 13, 14 ], "selected": [ 0, 1, 2, 3, 6, 10 ] }Step 17: Path length = 6 (not guaranteed shortest).
State at this checkpoint
{ "values": [ 6, 5, 4, 3, "×", "×", 3, "×", "∞", 3, 2, 1, "∞", "×", "×", 0 ], "active": [ 0, 1, 2, 6, 10, 11, 15 ], "kind": "matrix", "columns": 4, "blocked": [ 4, 5, 7, 13, 14 ], "selected": [ 0, 1, 2, 6, 10, 11, 15 ], "path": [ 0, 1, 2, 6, 10, 11, 15 ], "result": 6 }
Expected final state
Path length = 6 (not guaranteed shortest).
Complexity and input bounds
Family: Graphs. Time complexity: O(V²).
Space complexity: O(V) frontier and parent state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Rectangular grid up to 8 × 8: 0 = free, 1 = obstacle. Start and goal must be free.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
A found route is not necessarily shortest; obstacles can make a promising estimate misleading.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | // Grid dimensions 1–8; row-major blocked values 0/1, free start and goal. Writes the path indices including endpoints; returns moves or -1. Greedy ignores distance traveled and does not guarantee shortest paths. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(blocked, rows, columns, output) { let n = rows * columns; let dist = Array(256).fill(0); let parent = Array(256).fill(0); let closed = Array(256).fill(0); for (let i = 0; i < n; i++) { dist[i] = 1000000; parent[i] = -1; } dist[0] = 0; for (let step = 0; step < n; step++) { let u = -1; let best = 1000000; for (let v = 0; v < n; v++) { let estimate = rows - 1 - Math.floor(v / columns) + columns - 1 - v % columns; let score = estimate; if (closed[v] == 0 && dist[v] < 1000000 && score < best) { best = score; u = v; } } if (u < 0) { break; } closed[u] = 1; if (u == n - 1) { break; } for (let direction = 0; direction < 4; direction++) { let v = -1; if (direction == 0 && u >= columns) { v = u - columns; } if (direction == 1 && u + columns < n) { v = u + columns; } if (direction == 2 && u % columns > 0) { v = u - 1; } if (direction == 3 && u % columns < columns - 1) { v = u + 1; } if (v >= 0 && blocked[v] == 0 && closed[v] == 0 && dist[u] + 1 < dist[v]) { dist[v] = dist[u] + 1; parent[v] = u; } } } if (closed[n - 1] == 0) { return -1; } let path = Array(256).fill(0); let count = 0; for (let v = n - 1; v >= 0; v = parent[v]) { path[count++] = v; } for (let i = 0; i < count; i++) { output[i] = path[count - 1 - i]; } return count - 1; } |
Source
Pohl provides heuristic-search research background. The heuristic-only grid search here is a bounded teaching variant, not a reproduction of every algorithm in the paper.
- Heuristic search viewed as path finding in a graph
Ira Pohl (1970). Related research paper.