Java A* on a unit grid: an admissible Manhattan bound

Last updated: 30 Sept 20264 min read

tutorial

A* orders candidate grid cells by distance-so-far plus a lower bound to the goal; on a four-neighbor unit-cost grid, Manhattan distance is such a bound.

Keep the cost and heuristic separate

Each open cell move costs one. The fixture blocks the center of a three-by-three grid, so a route from the upper-left to the lower-right takes four moves. A second fixture blocks both exits from the start and returns -1. The priority queue may contain stale entries; the code skips an entry when its stored cost no longer matches the best known distance.

Manhattan distance stops being a valid lower bound if the graph admits a cheaper diagonal or teleport move. For zero heuristic, this becomes a Dijkstra-style search. Dijkstra covers weighted edges without a spatial bound.

A shortest length is not a path

This page returns distance only. To show the actual route, record a predecessor for each improvement and reconstruct it after reaching the goal. A map service also needs movement rules and blocked-cell data that do not change halfway through a search.

Working program

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class ReviewGridRoute {
    static final class Step {
        final int row, col, cost, score;
        Step(int row, int col, int cost, int score) {
            this.row = row; this.col = col; this.cost = cost; this.score = score;
        }
    }
    static int shortest(boolean[][] blocked) {
        if (blocked == null || blocked.length == 0 || blocked[0] == null || blocked[0].length == 0)
            throw new IllegalArgumentException("nonempty grid");
        int rows = blocked.length, cols = blocked[0].length;
        for (boolean[] line : blocked)
            if (line == null || line.length != cols) throw new IllegalArgumentException("rectangular grid");
        if (blocked[0][0] || blocked[rows - 1][cols - 1]) return -1;
        int[][] best = new int[rows][cols];
        for (int[] line : best) Arrays.fill(line, Integer.MAX_VALUE);
        best[0][0] = 0;
        PriorityQueue<Step> open = new PriorityQueue<>(Comparator.comparingInt(step -> step.score));
        open.add(new Step(0, 0, 0, rows + cols - 2));
        int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!open.isEmpty()) {
            Step current = open.remove();
            if (current.cost != best[current.row][current.col]) continue;
            if (current.row == rows - 1 && current.col == cols - 1) return current.cost;
            for (int[] move : moves) {
                int row = current.row + move[0], col = current.col + move[1];
                if (row < 0 || row >= rows || col < 0 || col >= cols || blocked[row][col]) continue;
                int next = current.cost + 1;
                if (next < best[row][col]) {
                    best[row][col] = next;
                    int bound = Math.abs(rows - 1 - row) + Math.abs(cols - 1 - col);
                    open.add(new Step(row, col, next, next + bound));
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        System.out.println(shortest(new boolean[][]{{false, false, false},
            {false, true, false}, {false, false, false}}));
        if (shortest(new boolean[][]{{false, true}, {true, false}}) != -1)
            throw new AssertionError("blocked exits");
    }
}

Output

Costs and boundaries

For V cells and at most four neighbors per cell, the priority queue and best-distance array take O(V) stored states in the usual simple-grid case; queue operations give O(V log V) time. This fixture rejects empty and ragged grids but does not support weighted or diagonal movement, map changes, or large-grid memory pressure.

Common Mistakes

Do not reuse Manhattan distance when cheaper diagonal or teleport edges exist.
Do not process stale queue entries as new shortest paths.
Do not report a distance as if the actual route was reconstructed.
Do not accept a ragged grid and index it as if every row had the same length.