Greedy best-first grid search: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

Greedy best-first grid search example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. 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": []
    }
  2. 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
      ]
    }
  3. 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
      ]
    }
  4. 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
      ]
    }
  5. 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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 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.