Advanced 13 min · March 06, 2026

A* Search — When Heuristic Multipliers Break Optimality

A 1.

N
Naren · Founder
Plain-English first. Then code. Then the interview question.
About
 ● Production Incident 🔎 Debug Guide
⚡Quick Answer
  • A* finds shortest paths by combining actual cost g(n) with heuristic estimate h(n) via f(n) = g(n) + h(n)
  • Admissible heuristics (never overestimate) guarantee optimal paths — violate admissibility and you get wrong answers with no error signal
  • A* degenerates to Dijkstra when h=0, and to greedy best-first search when g is ignored
  • Priority queue keyed by f, lazy deletion for stale entries, closed set for visited nodes
  • Checking goal at insertion time instead of pop time silently returns suboptimal paths on weighted graphs — this is the most common production bug
  • Worst-case O((V+E) log V) but heuristic quality determines practical speedup over Dijkstra — a perfect heuristic expands only nodes on the optimal path
Plain-English First

Imagine you are navigating a city to reach a friend's house. You could wander every street blindly — that is Breadth-First Search. Or you could always take the road that feels closest to the destination without caring how far you have already walked — that is Greedy Best-First Search, and it will send you down dead ends. A* does something smarter: it keeps a running score that combines 'how far I have already walked from the start' with 'my best estimate of how far I still need to go', and always takes the step with the lowest combined score. It never forgets where it came from, and it never chases shortcuts that ignore the path already traveled. That is why navigation apps find your route in milliseconds — they are not checking every road, just the ones that genuinely look promising given both signals at once.

Every time a game character finds a path around an obstacle, a delivery drone picks the fastest route between warehouses, or a robot arm plans its motion through 3D space, there is a good chance A is doing the heavy lifting. It is one of those algorithms that genuinely earns its place in production systems — not because it is the simplest, but because it hits the sweet spot between speed and correctness that Dijkstra's and greedy search both miss in opposite directions. Understanding A at a deep level separates engineers who can implement pathfinding from engineers who can tune, scale, and debug it under real production constraints.

The core problem A solves is informed shortest-path search. Dijkstra's algorithm is optimal but blind — it expands nodes in every direction equally, wasting effort on paths that lead away from the goal. Pure greedy search races toward the goal but ignores accumulated cost, so it often finds a fast-looking but suboptimal route through terrain that happened to have low heuristic values. A threads the needle by combining both signals into a single evaluation function f(n) = g(n) + h(n), where g(n) is the exact cost from start to node n, and h(n) is a heuristic estimate of the remaining cost to the goal. When h(n) never overestimates the true remaining cost — the admissibility condition — A is provably optimal. When h(n) is also consistent — satisfying the triangle inequality across neighboring nodes — A never needs to reopen a closed node, making it strictly more efficient.

By the end of this article you will understand exactly why admissibility guarantees optimality, how to choose and design heuristics for different problem domains, why tie-breaking is the silent performance killer in grid-based A, how weighted A trades bounded suboptimality for speed, and what production engineers do differently from textbook implementations. You will walk away with complete, production-quality Java code and the mental model to answer every A* question an interviewer can reasonably ask.

What is A* Search — Plain English Before the Formulas

A* (pronounced A-star) finds the shortest path from a start node to a goal node in a weighted graph by using a heuristic — an estimate of the remaining distance to the goal — to prioritize which nodes to explore next. It does not wander randomly. It does not blindly explore every direction. It specifically focuses exploration on the nodes that look most promising given both how far you have already traveled and how far you probably still need to go.

Dijkstra's algorithm explores nodes by their actual cost from the start — it knows exactly how far each node is but has no idea which direction the goal is. It expands outward like a ripple in every direction, which is optimal but wasteful when you have a specific destination. Greedy best-first search goes to the opposite extreme — it only looks at the estimated cost to the goal and ignores how far it has already walked. This can lead it straight into a dead end because it chases the heuristic without accounting for the actual terrain cost.

A threads the needle between both approaches. Its evaluation function is f(n) = g(n) + h(n), where g(n) is the exact accumulated cost from start to node n, and h(n) is the heuristic estimate from n to the goal. By always expanding the node with the lowest f(n), A balances what it knows for certain (g) with what it estimates (h). When the heuristic never overestimates the true remaining cost — the admissibility condition — A* is mathematically guaranteed to find the optimal path while exploring dramatically fewer nodes than Dijkstra on graphs with a clear spatial structure.

The Three Algorithms as Exploration Strategies
  • Dijkstra opens the door closest to where you started, measured by actual walking distance (g only). Optimal — never misses the shortest path. Slow — explores in every direction equally with no goal awareness.
  • Greedy opens the door that feels closest to the exit, measured by straight-line guess (h only). Fast — heads toward the goal immediately. Unreliable — ignores terrain cost and gets fooled by dead ends.
  • A* opens the door with the lowest total estimated trip cost — actual distance walked plus estimated distance remaining (g + h). Optimal AND goal-focused — explores far fewer nodes than Dijkstra without sacrificing correctness.
  • When h=0 for all nodes, A* collapses to Dijkstra — the heuristic contributes nothing and pure cost drives expansion.
  • When g is ignored, A* collapses to greedy — cost is abandoned and the heuristic races toward the goal unchecked.
  • Admissibility is what keeps A* honest. Without it, you have speed but not correctness — and wrong paths with no error message.
Production Insight
Dijkstra explores every direction equally — on a 1000x1000 grid navigating from corner to corner, it may expand close to one million nodes.
A* with Manhattan distance on the same grid typically expands tens of thousands — an order-of-magnitude improvement that matters enormously in games, robotics, and real-time routing.
Rule: use A* when you have a single target and a valid admissible heuristic. Fall back to Dijkstra when you need shortest paths to all nodes, or when no meaningful heuristic exists for your domain.
Key Takeaway
A* combines Dijkstra's correctness with greedy's goal-directedness via f(n) = g(n) + h(n).
The heuristic is the dial between the two extremes — h=0 gives Dijkstra, g=0 gives greedy.
Admissibility is the non-negotiable condition that keeps A* optimal — violate it and you get wrong answers with no runtime signal.

How A* Works — The Algorithm Built from First Principles

Rather than treating A* as a black-box procedure to memorize, derive each step from the problem it solves.

You want to find the minimum-cost path from start to goal. At any point during the search, you have a set of candidate nodes worth exploring — nodes you know how to reach but have not yet fully expanded. For each candidate n, you know g(n) exactly (the best path found so far from start to n), and you estimate h(n) (some lower bound on the remaining cost to goal). The combined f(n) = g(n) + h(n) is your best possible total path cost through n. You should always explore the candidate with the lowest f(n) first — that is the most promising path.

Algorithm: 1. Initialize: open_set = priority queue containing (f(start), start). Set g[start] = 0. All other nodes have g = infinity. 2. While open_set is not empty: a. Pop node n with minimum f(n). b. If n is the goal: return the reconstructed path. The g-value at this moment is the proven optimal cost. c. Mark n as closed — its g-value is now final and optimal. d. For each neighbor nb of n with edge cost cost(n, nb): i. If nb is already in closed_set: skip — its g-value is already optimal. ii. Compute tentative_g = g[n] + cost(n, nb). iii. If tentative_g < g[nb]: this is a better path to nb. Update g[nb] = tentative_g. Record parent[nb] = n. Push (g[nb] + h(nb), nb) into open_set. 3. If open_set empties without reaching the goal: no path exists.

Why does this work? When n is popped with minimum f(n), any alternative path through a node still in the open set has f >= f(n). Since h is admissible (never overestimates), that alternative path's true cost is at least f(n). Therefore g(n) as computed is the true optimal cost to n. This is the formal argument for why pop-time goal checking is correct and insertion-time goal checking is not.

Common heuristics
  • Manhattan distance |goal_r
  • n_r| + |goal_c
  • n_c|: admissible and consistent for 4-directional grids.
  • Chebyshev distance max(|goal_r
  • n_r|, |goal_c
  • n_c|): admissible and consistent for 8-directional grids.
  • Euclidean distance sqrt((goal_x
  • n_x)^2 + (goal_y
  • n_y)^2): admissible for any spatial graph, consistent for continuous spaces.
  • Domain-specific precomputed tables: offline Dijkstra runs that provide tight lower bounds without overestimating.
Goal Check Timing Is the Most Common Production Bug
Check for the goal AFTER popping from the priority queue — never at insertion time. Insertion-time goal checking works on unweighted graphs where all edges cost 1, because every node at the same BFS depth has the same g-value. On weighted graphs it fails silently: when you insert the goal node into the open set, its g-value is a candidate — a good path found so far, not the proven optimal. A shorter path through a different node may still be in the open set waiting to be explored. This bug passes every unweighted unit test. It fails in production the moment terrain costs vary — which they always do in real routing problems. The returned path has the correct start and end points. The total cost is just wrong.
Production Insight
Pop-time goal checking is not a preference — it is the only correct implementation for weighted graphs.
The formal reason: when goal is popped, f(goal) = g(goal) + h(goal). Since h(goal) = 0 by definition (you are already at the goal), f(goal) = g(goal), which is proven optimal by the admissibility argument.
Rule: if you inherited a codebase with A*, the first thing you check is where the goal condition appears relative to the heap pop. If it appears before, the implementation is wrong for weighted graphs.
Key Takeaway
A* is a priority queue loop: pop minimum-f node, expand neighbors, update g-values, push improvements.
Goal detection must happen at pop time — this is the correctness guarantee, not a style choice.
Closed set prevents re-expansion of nodes whose optimal cost is already proven. G-value check prevents pushing worse paths to nodes already found via a cheaper route.

Diagonal Distance Heuristic for 8-Directional Movement

When movement allows diagonal steps (8-directional), Manhattan distance underestimates the true path cost because it assumes you must take separate horizontal and vertical steps. For grids where diagonal moves are allowed, a tighter admissible heuristic is the diagonal distance (also called octile distance).

The formula for diagonal distance depends on the cost of diagonal moves relative to cardinal moves. Let D be the cost of a cardinal step and D2 be the cost of a diagonal step (often D=1, D2=√2 for Euclidean metric). Then:

h(n) = D (|Δx| + |Δy|) + (D2 - 2D) * min(|Δx|, |Δy|)

When D = D2 (diagonal costs same as cardinal), this simplifies to Chebyshev distance: h(n) = max(|Δx|, |Δy|).

When D2 > D (the common case), the formula accounts for the fact that diagonal steps are cheaper than two cardinal steps. The expression effectively counts the number of diagonal steps as min(|Δx|,|Δy|) and the remaining cardinal steps as |Δx|+|Δy| - 2*min(|Δx|,|Δy|).

Use diagonal distance whenever your grid allows 8-directional movement and you want an admissible heuristic that avoids the underestimation of Manhattan. It is consistent as long as edge costs satisfy the triangle inequality (e.g., D2 ≤ 2D). For games and robotics planning on 8-connected grids, this heuristic provides significant performance improvements over Manhattan.

Production Insight
Switching from Manhattan to diagonal distance on an 8-directional grid can reduce node expansions by 30–50% because the heuristic better matches the true path cost. Always match the heuristic to the allowed movement directions and edge costs.
Key Takeaway
Diagonal distance (octile) heuristic is the correct admissible choice for 8-directional grids. Use the formula that accounts for diagonal step cost differences, and fall back to Chebyshev when D = D2.

Why Greedy Best-First Search Fails — The Perils of Heuristic-Only Navigation

Greedy best-first search (GBFS) prioritizes nodes using only the heuristic h(n) — it ignores the accumulated cost g(n). In every iteration, it expands the node that appears closest to the goal, regardless of how expensive the path to that node was. This can produce fast initial progress but often leads to suboptimal or even catastrophic results.

Consider a 2D grid with obstacles and varied terrain costs. GBFS charges toward the goal using the heuristic (e.g., Euclidean distance). If a direct route passes through a high-cost swamp (cost 10 per step), GBFS will greedily enter the swamp because the heuristic value is small — the goal looks close. Dijkstra would avoid the swamp and take a longer but cheaper route around it. A* would balance the cheap detour cost against the heuristic, eventually finding the optimal path. GBFS fails because it lacks the exact cost component: it has no memory of how much it has already spent.

Another failure mode: dead ends. If a heuristic falsely suggests a short path through a cul-de-sac, GBFS rushes in and then must backtrack extensively. Dijkstra and A* would never enter such regions in the first place because their cost-aware expansion would have already ruled them out.

In production, GBFS is rarely used alone. It may appear as a component in anytime algorithms or for very rough approximations where path optimality is irrelevant (e.g., a quick visual guide). But for any system that requires predictable, correct routing, GBFS is unreliable — use A* instead.

GBFS Can Produce Paths with Arbitrarily High Cost
There is no bound on how suboptimal a greedy best-first path can be. On certain graphs, GBFS may return a path that is orders of magnitude worse than optimal. A* with an admissible heuristic guarantees optimality; GBFS guarantees nothing.
Production Insight
GBFS is sometimes used in real-time strategy games for unit movement when many agents need pathfinding simultaneously and a quick approximate route suffices for the first frame, corrected later. But for turn-by-turn navigation, GPS routing, or drone delivery, GBFS is too risky — stick with A or weighted A with a logged bound.
Key Takeaway
Greedy best-first search sacrifices optimality by ignoring actual path cost. It is only suitable when speed is critical and suboptimal paths with no bound are acceptable. Always prefer A* for production systems that need correct answers.

The progression from uninformed to informed search helps understand why A* is the right choice for most pathfinding problems. Each step adds a new piece of information:

AlgorithmUses actual cost g(n)?Uses heuristic h(n)?Optimal?Typical use case
Breadth-First Search (BFS)No (only step count)NoYes (unweighted)Unweighted graphs, shortest path in number of edges
DijkstraYesNoYesWeighted graphs, all-pairs shortest paths
Greedy Best-First SearchNoYesNoVery fast approximations, no optimality required
A* SearchYesYesYes (with admissible h)Single-target weighted graphs, real-world routing

BFS treats all edges as unit cost and expands level by level. Dijkstra adds cost tracking, making it optimal for weighted graphs but blind to the goal location. Greedy adds goal-awareness through the heuristic but discards cost, losing optimality. A* combines both: it tracks exact cost like Dijkstra and uses goal-awareness like greedy, achieving optimality and efficiency simultaneously.

This progression shows that A is not a fundamentally different algorithm — it is the natural integration of cost tracking and heuristic guidance. Each predecessor is a special case of A (h=0 gives Dijkstra; g ignored gives greedy; h=0 and g step count gives BFS).

Production Insight
When designing a routing system, start by considering whether you need optimality (use A), have no heuristic (use Dijkstra), or can tolerate unbounded suboptimality (use Greedy). In practice, A with a well-chosen heuristic almost always wins.
Key Takeaway
A* is the culmination of adding cost tracking (Dijkstra) and heuristic guidance (greedy). Understanding this progression helps choose the right tool for each problem.

Worked Example — A* on a 4x4 Grid with Full Node Expansion Trace

Grid (S = start at (0,0), G = goal at (3,3), X = obstacle, . = open cell):

S . . . . X X . . X . . . . . G

Heuristic: Manhattan distance h(r,c) = |3-r| + |3-c|. Edge cost: 1 per step. g(start)=0, h(start)=6, f(start)=6.

All node states shown as (r,c) g=X h=Y f=Z.

Initial open set: {(0,0) g=0 h=6 f=6}

Step 1 — Pop (0,0) f=6. Mark closed. Neighbors: (0,1) and (1,0). Both open. (0,1): tentative_g=1, h=5, f=6. Push. (1,0): tentative_g=1, h=5, f=6. Push. Open set: {(0,1) f=6, (1,0) f=6}

Step 2 — Pop (0,1) f=6 (tie broken arbitrarily). Mark closed. Neighbors: (0,0) closed skip. (0,2) open. (1,1) obstacle skip. (0,2): tentative_g=2, h=4, f=6. Push. Open set: {(1,0) f=6, (0,2) f=6}

Step 3 — Pop (1,0) f=6. Mark closed. Neighbors: (0,0) closed skip. (2,0) open. (1,1) obstacle skip. (2,0): tentative_g=2, h=4, f=6. Push. Open set: {(0,2) f=6, (2,0) f=6}

Step 4 — Pop (0,2) f=6. Mark closed. Neighbors: (0,1) closed skip. (0,3) open. (1,2) obstacle skip. (0,3): tentative_g=3, h=3, f=6. Push. Open set: {(2,0) f=6, (0,3) f=6}

Step 5 — Pop (2,0) f=6. Mark closed. Neighbors: (1,0) closed skip. (3,0) open. (2,1) obstacle skip. (3,0): tentative_g=3, h=3, f=6. Push. Open set: {(0,3) f=6, (3,0) f=6}

Step 6 — Pop (0,3) f=6. Mark closed. Neighbors: (0,2) closed skip. (1,3) open. (1,3): tentative_g=4, h=2, f=6. Push. Open set: {(3,0) f=6, (1,3) f=6}

Step 7 — Pop (3,0) f=6. Mark closed. Neighbors: (2,0) closed skip. (3,1) open. (3,1): tentative_g=4, h=2, f=6. Push. Open set: {(1,3) f=6, (3,1) f=6}

Step 8 — Pop (1,3) f=6. Mark closed. Neighbors: (0,3) closed skip. (2,3) open. (2,3): tentative_g=5, h=1, f=6. Push. Open set: {(3,1) f=6, (2,3) f=6}

Step 9 — Pop (3,1) f=6. Mark closed. Neighbors: (3,0) closed skip. (3,2) open. (2,1) obstacle skip. (3,2): tentative_g=5, h=1, f=6. Push. Open set: {(2,3) f=6, (3,2) f=6}

Step 10 — Pop (2,3) f=6. Mark closed. Neighbors: (1,3) closed skip. (3,3) open. (2,2) open. (3,3): tentative_g=6, h=0, f=6. Push. (2,2): tentative_g=6, h=2, f=8. Push. Open set: {(3,2) f=6, (3,3) f=6, (2,2) f=8}

Step 11 — Pop (3,2) f=6. Mark closed. Neighbors: (3,1) closed skip. (3,3) already in open with g=6. Tentative g from (3,2) = 6. Not better — skip. (2,2): tentative from (3,2) = 6, current g=6 from step 10. Equal — skip. Open set: {(3,3) f=6, (2,2) f=8}

Step 12 — Pop (3,3) f=6. THIS IS THE GOAL. Return path.

Path reconstruction via parent map: (3,3) ← (2,3) ← (1,3) ← (0,3) ← (0,2) ← (0,1) ← (0,0)

Final path: (0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3) → (3,3) Total cost: 6. Length: 7 nodes. Optimal — this is the shortest path around the obstacles.

Nodes expanded: 12. Dijkstra on this grid would expand all 12 open cells before reaching the goal, offering no savings. On larger grids with distant goals, the savings become dramatic because A* does not expand the cells in the bottom-left quadrant that are provably not on any optimal path to the bottom-right goal.

Tie-Breaking Determines Real-World Performance More Than You Think
Every step in this example had f=6 across multiple nodes simultaneously. The tie-breaking rule determined expansion order. On this 4x4 grid the difference is small. On a 1000x1000 grid with a diagonal path, poor tie-breaking can cause A* to expand a full band of nodes across the entire grid rather than a narrow corridor along the optimal path — a 10x to 50x increase in node expansions with zero change in final path quality. Two effective tie-breaking strategies: 1. Prefer higher g-value when f is tied — this favors nodes closer to the goal by actual cost, tightening the expansion corridor. 2. Add a tiny bias epsilon × h(n) to f(n) where epsilon is on the order of 1 / (expected_max_path_length) — this breaks ties deterministically toward the goal without violating admissibility in practice. This is mentioned in almost no textbook and has massive practical impact in grid-based game engines and robotics planners.
Production Insight
On this small grid, A* provides limited advantage because the obstacles force exploration of most available cells regardless.
On sparse grids with clear lines-of-sight to the goal, A* with Manhattan distance can achieve 10x to 100x fewer node expansions than Dijkstra.
Rule: always implement tie-breaking in grid-based A*. It is free performance — one line of comparator logic that costs nothing but can halve expansion count on large open grids.
Key Takeaway
The worked trace shows that f=6 is maintained throughout the entire search on this grid — Manhattan distance is perfectly tight given the grid structure and edge cost of 1.
Tie-breaking determines which f=6 node gets expanded first and directly controls the shape of the explored region.
Path reconstruction walks the parent map backward from goal to start — verify that every node on the path has a parent entry and that the start node's parent is null.

Complete Production Implementation — A* with Lazy Deletion, Tie-Breaking, and Path Reconstruction

The implementation below is production-quality: lazy deletion instead of decrease-key, long arithmetic throughout, tie-breaking by g-value, full path reconstruction, and input validation. It handles weighted grids by accepting a cost function, making it adaptable to terrain-cost maps, road networks, and game world navigation.

io/thecodeforge/pathfinding/AStarSolver.javaJAVA
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
package io.thecodeforge.pathfinding;

import java.util.*;

/**
 * Production A* pathfinder for 2D grids.
 *
 * Design decisions:
 *   - Lazy deletion: push new entries to the heap and skip stale ones on pop.
 *     Simpler than decrease-key, nearly as fast in practice.
 *   - Tie-breaking by g-value: when f is equal, prefer higher g (closer to goal\\n *     by actual cost). Reduces expansion count on large open grids significantly.
 *   - Long arithmetic: prevents silent overflow on large grids with high-cost terrain.
 *   - Pop-time goal check: g(goal) is proven optimal the moment goal is popped.
 *     Insertion-time check is WRONG for weighted graphs.
 *   - Weighted A* support: set weight > 1.0 to trade optimality for speed.
 *     A result is guaranteed within (weight * optimal_cost).
 */
public class AStarSolver {

    private static final int[][] DIRS_4 = {{-1,0},{1,0},{0,-1},{0,1}};
    private static final int[][] DIRS_8 = {
        {-1,0},{1,0},{0,-1},{0,1},
        {-1,-1},{-1,1},{1,-1},{1,1}
    };

    /**
     * Solves A* on a 2D grid using Manhattan distance heuristic (4-directional).
     *
     * @param grid     2D array: 0 = traversable, 1 = obstacle
     * @param start    {row, col} of start position
     * @param goal     {row, col} of goal position
     * @param weight   heuristic weight: 1.0 = standard A*, >1.0 = weighted A*
     *                 (higher weight = faster but potentially suboptimal)
     * @return shortest path as ordered list of {row, col} pairs, or null if unreachable
     */
    public static List<int[]> solve(
            int[][] grid, int[] start, int[] goal, double weight) {\\n\\n        validateInputs(grid, start, goal);\\n        int rows = grid.length;\\n        int cols = grid[0].length;\\n\\n        // g-scores: best known cost from start. Long.MAX_VALUE = unvisited.\\n        long[][] gScore = new long[rows][cols];\\n        for (long[] row : gScore) Arrays.fill(row, Long.MAX_VALUE);\\n        gScore[start[0]][start[1]] = 0L;\\n\\n        // parent tracking for path reconstruction\\n        // encoded as flat index: row * cols + col, -1 = no parent\\n        int[] parent = new int[rows * cols];\\n        Arrays.fill(parent, -1);\\n\\n        // closed set: nodes whose optimal g-score is finalized\\n        boolean[][] closed = new boolean[rows][cols];\\n\\n        // Priority queue entries: {f_scaled, g_negated_for_tiebreak, row, col}
        // f_scaled = (long)(f * SCALE) to avoid floating-point comparisons
        // Tie-breaking: when f equal, prefer higher g (lower -g)
        // Using long[] for cache efficiency on large grids
        final long SCALE = 1_000_000L;
        PriorityQueue<long[]> openSet = new PriorityQueue<>(
            Comparator.comparingLong((long[] e) -> e[0])
                      .thenComparingLong(e -> e[1])  // tie-break: higher g wins
        );

        long startH = manhattan(start[0], start[1], goal);
        long startF = (long)(startH * weight * SCALE);
        openSet.offer(new long[]{startF, 0L, start[0], start[1]});

        while (!openSet.isEmpty()) {
            long[] curr = openSet.poll();
            int r = (int) curr[2];
            int c = (int) curr[3];

            // Lazy deletion: skip if this entry is stale
            if (closed[r][c]) continue;
            closed[r][c] = true;

            // Goal check at POP time — g[r][c] is now the proven optimal cost
            if (r == goal[0] && c == goal[1]) {
                return reconstructPath(parent, start, goal, cols);
            }

            long currentG = gScore[r][c];

            for (int[] dir : DIRS_4) {
                int nr = r + dir[0];
                int nc = c + dir[1];

                // Bounds check
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                // Obstacle check
                if (grid[nr][nc] == 1) continue;
                // Already optimally explored
                if (closed[nr][nc]) continue;

                // Edge cost: 1 for uniform grid; adapt here for terrain costs
                long edgeCost = 1L;
                long tentativeG = currentG + edgeCost;

                // Only push if this is a strictly better path to (nr, nc)
                if (tentativeG < gScore[nr][nc]) {
                    gScore[nr][nc] = tentativeG;
                    parent[nr * cols + nc] = r * cols + c;

                    long h = manhattan(nr, nc, goal);
                    // f = g + weight * h
                    // weight > 1.0 inflates h, trading optimality for speed
                    long f = (long)((tentativeG + weight * h) * SCALE);
                    // Tie-break entry: negate tentativeG so higher g sorts first
                    openSet.offer(new long[]{f, -tentativeG, nr, nc});
                }
            }
        }

        return null; // no path exists
    }

    /**
     * Convenience overload: standard A* (weight = 1.0, admissible, optimal).
     */
    public static List<int[]> solve(int[][] grid, int[] start, int[] goal) {
        return solve(grid, start, goal, 1.0);
    }

    // ----------------------------------------------------------------
    // Heuristics
    // ----------------------------------------------------------------

    /**
     * Manhattan distance — admissible and consistent for 4-directional grids.
     * Never overestimates when edge cost >= 1.
     */
    private static long manhattan(int r, int c, int[] goal) {
        return Math.abs(goal[0] - r) + Math.abs(goal[1] - c);
    }

    /**
     * Chebyshev distance — admissible and consistent for 8-directional grids.
     * Use this when diagonal moves have the same cost as cardinal moves.
     */
    public static long chebyshev(int r, int c, int[] goal) {
        return Math.max(Math.abs(goal[0] - r), Math.abs(goal[1] - c));
    }

    /**
     * Euclidean distance — admissible for any spatial graph.
     * Tighter lower bound than Manhattan for 8-directional movement.
     */
    public static long euclidean(int r, int c, int[] goal) {
        double dr = goal[0] - r;
        double dc = goal[1] - c;
        return (long) Math.sqrt(dr * dr + dc * dc);
    }

    // ----------------------------------------------------------------
    // Path reconstruction
    // ----------------------------------------------------------------

    private static List<int[]> reconstructPath(
            int[] parent, int[] start, int[] goal, int cols) {\\n\\n        List<int[]> path = new ArrayList<>();\\n        int curr = goal[0] * cols + goal[1];\\n        int startIdx = start[0] * cols + start[1];\\n\\n        while (curr != startIdx && curr != -1) {\\n            path.add(new int[]{curr / cols, curr % cols});
            curr = parent[curr];
        }
        path.add(start);
        Collections.reverse(path);
        return path;
    }

    // ----------------------------------------------------------------
    // Input validation
    // ----------------------------------------------------------------

    private static void validateInputs(int[][] grid, int[] start, int[] goal) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            throw new IllegalArgumentException("Grid must be non-null and non-empty");
        }
        int rows = grid.length, cols = grid[0].length;
        if (start == null || start.length != 2) {
            throw new IllegalArgumentException("Start must be {row, col}");
        }
        if (goal == null || goal.length != 2) {
            throw new IllegalArgumentException("Goal must be {row, col}");
        }
        for (int[] pos : new int[][]{start, goal}) {
            if (pos[0] < 0 || pos[0] >= rows || pos[1] < 0 || pos[1] >= cols) {
                throw new IllegalArgumentException(
                    "Position out of bounds: [" + pos[0] + "," + pos[1] + "]");
            }
        }
        if (grid[start[0]][start[1]] == 1) {
            throw new IllegalArgumentException("Start position is an obstacle");
        }
        if (grid[goal[0]][goal[1]] == 1) {
            throw new IllegalArgumentException("Goal position is an obstacle");
        }
    }

    // ----------------------------------------------------------------
    // Demo and correctness validation
    // ----------------------------------------------------------------

    public static void main(String[] args) {
        int[][] grid = {
            {0, 0, 0, 0},
            {0, 1, 1, 0},
            {0, 1, 0, 0},
            {0, 0, 0, 0}
        };
        int[] start = {0, 0};
        int[] goal  = {3, 3};

        System.out.println("=== Standard A* (weight=1.0, optimal) ===");
        List<int[]> optimalPath = solve(grid, start, goal, 1.0);
        if (optimalPath != null) {
            System.out.print("Path ("+optimalPath.size()+" nodes): ");
            for (int[] p : optimalPath)
                System.out.print("("+p[0]+","+p[1]+") ");
            System.out.println();
        } else {
            System.out.println("No path found");
        }

        System.out.println();
        System.out.println("=== Weighted A* (weight=2.0, up to 2x suboptimal but faster) ===");
        List<int[]> weightedPath = solve(grid, start, goal, 2.0);
        if (weightedPath != null) {
            System.out.print("Path ("+weightedPath.size()+" nodes): ");
            for (int[] p : weightedPath)
                System.out.print("("+p[0]+","+p[1]+") ");
            System.out.println();
        }

        System.out.println();
        System.out.println("=== Unreachable goal demo ===");
        int[][] blockedGrid = {
            {0, 1},
            {1, 0}
        };
        List<int[]> noPath = solve(blockedGrid, new int[]{0,0}, new int[]{1,1});
        System.out.println("Result: " + (noPath == null ? "No path (correct)" : "Path found (wrong)"));
    }
}
Output
=== Standard A* (weight=1.0, optimal) ===
Path (7 nodes): (0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (3,3)
=== Weighted A* (weight=2.0, up to 2x suboptimal but faster) ===
Path (7 nodes): (0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (3,3)
=== Unreachable goal demo ===
Result: No path (correct)
Production Insight
The flat int[] parent array (row cols + col encoding) avoids string key allocation overhead on large grids — string concatenation for keys is one of the top hidden performance costs in naive A implementations on high-throughput game servers.
The SCALE factor converts float f-values to long for heap comparison, avoiding floating-point comparison instability without resorting to double[] arrays.
Weighted A* with w=1.5 is the standard choice for real-time game AI: paths are within 50% of optimal, node expansions drop by 60 to 80 percent, and the latency budget for pathfinding stays under the frame time budget.
Rule: default to standard A (w=1.0) for routing correctness requirements. Use weighted A with a logged optimality bound for latency-sensitive applications where approximate paths are acceptable.
Key Takeaway
Production A* uses lazy deletion — push new entries, skip stale ones on pop — rather than decrease-key operations. Simpler to implement correctly and nearly identical in performance.
Tie-breaking by g-value is implemented by sorting on -g when f is equal, which favors nodes closer to the goal by actual cost and tightens the expansion corridor on open grids.
Weighted A* is a first-class production tool for latency-sensitive applications — it is not a hack. The weight is an explicit optimality bound that should be logged and monitored.

C++ Implementation Stub for A* Pathfinding

The core A* logic translates directly to C++ with standard library containers. Below is a minimal but complete grid-based implementation using std::priority_queue with a custom comparator for tie-breaking. This stub focuses on the algorithm structure and can be extended with terrain costs and 8-directional movement.

astar_solver.cppCPP
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <vector>
#include <queue>
#include <unordered_set>
#include <functional>
#include <cmath>
#include <climits>

using namespace std;

struct Node {
    int r, c;
    long g, h;  // exact cost and heuristic
    long f() const { return g + h; }
};

struct CompareNode {
    bool operator()(const Node& a, const Node& b) {\\n        if (a.f() != b.f()) return a.f() > b.f();  // min-heap: lower f first\\n        return a.g < b.g;  // tie-break: higher g first (closer to goal)\\n    }
};

// Manhattan distance heuristic
long heuristic(int r, int c, int gr, int gc) {\\n    return abs(gr - r) + abs(gc - c);\\n}

vector<pair<int,int>> aStar(const vector<vector<int>>& grid,\\n                            pair<int,int> start, pair<int,int> goal) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<long>> gScore(R, vector<long>(C, LONG_MAX));
    vector<vector<bool>> closed(R, vector<bool>(C, false));
    vector<vector<int>> parentRow(R, vector<int>(C, -1));
    vector<vector<int>> parentCol(R, vector<int>(C, -1));

    priority_queue<Node, vector<Node>, CompareNode> openSet;
    gScore[start.first][start.second] = 0;
    openSet.push({start.first, start.second, 0,
                  heuristic(start.first, start.second, goal.first, goal.second)});

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!openSet.empty()) {
        Node cur = openSet.top(); openSet.pop();
        if (closed[cur.r][cur.c]) continue;
        closed[cur.r][cur.c] = true;

        if (cur.r == goal.first && cur.c == goal.second) {
            // Reconstruct path
            vector<pair<int,int>> path;
            int r = cur.r, c = cur.c;
            while (r != -1) {
                path.push_back({r, c});
                int pr = parentRow[r][c];
                int pc = parentCol[r][c];
                r = pr; c = pc;
            }
            reverse(path.begin(), path.end());
            return path;
        }

        for (int d = 0; d < 4; ++d) {
            int nr = cur.r + dr[d], nc = cur.c + dc[d];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            if (grid[nr][nc] == 1) continue;  // obstacle
            if (closed[nr][nc]) continue;

            long tentativeG = cur.g + 1;  // edge cost 1
            if (tentativeG < gScore[nr][nc]) {
                gScore[nr][nc] = tentativeG;
                parentRow[nr][nc] = cur.r;
                parentCol[nr][nc] = cur.c;
                openSet.push({nr, nc, tentativeG,
                              heuristic(nr, nc, goal.first, goal.second)});
            }
        }
    }
    return {};  // no path
}
Output
// Example usage:
// auto path = aStar(grid, {0,0}, {4,4});
// if (!path.empty()) { for (auto [r,c] : path) cout << r << "," << c << "\n"; }
Production Insight
In C++ game engines, std::priority_queue is the standard container. For extra performance, consider a custom bucket priority queue or a relaxed heap. The key point is that the algorithm remains unchanged across languages — only the data structure syntax differs.
Key Takeaway
C++ A* mirrors Java's logic: a priority queue with adjacency expansion, g-value checks, and pop-time goal detection. Use LONG_MAX for unvisited and always check closed after popping.

Applications — Where A* Excels in Production Systems

A is the dominant pathfinding algorithm in video games for moving NPCs and units across tactical maps, where it must compute paths for hundreds of agents per frame with <1ms per query. GPS navigation systems use A on road network graphs with heuristic based on straight-line distance or Haversine distance for long-haul routes. Robotics applications use A for arm motion planning in 3D configuration spaces, often with custom heuristics derived from precomputed distance fields. A is also used in network routing, puzzle solving, and natural language processing for word ladder problems. Its flexibility and optimality guarantee make it the go-to algorithm whenever a shortest path is needed and a meaningful heuristic exists.

Production Insight
In game engines, A is often replaced by HPA (Hierarchical A*) for large maps, which decomposes the graph into clusters and plans at multiple levels. For real-time GPS, the heuristic must be invariant to traffic conditions — use Euclidean over road distance to avoid overestimation.
Key Takeaway
A* is production-ready for any domain with a single start and goal and a lower-bound heuristic: games, navigation, robotics, and network routing all use it daily.

Admissibility and Consistency — Why the Heuristic Is Everything

The heuristic h(n) is the component that makes A faster than Dijkstra. It is also the component that can silently break correctness if designed carelessly. Understanding admissibility and consistency at a formal level is what separates an engineer who implements A from one who can certify it is correct in production.

Admissibility means h(n) <= true_cost(n, goal) for every node n in the graph. The heuristic never overestimates the remaining cost. This is the condition that guarantees A finds the optimal path. Intuition: if A is about to skip a path through node n because f(n) looks too high, admissibility guarantees that the true cost through n really is at least f(n). If we skipped it, we could not have done better through n anyway.

Consistency (also called monotonicity) is a stronger condition: h(n) <= cost(n, nb) + h(nb) for every node n and every neighbor nb. This is the triangle inequality applied to the heuristic. Consistency implies admissibility. The practical consequence of consistency is that A* with a consistent heuristic never needs to reopen a closed node — once a node is popped and marked closed, its g-value is proven optimal and no future path can improve it. This means every node is expanded at most once, giving the tightest possible worst-case bound.

The relationship: every consistent heuristic is admissible. Not every admissible heuristic is consistent. If your heuristic is admissible but not consistent, A* still finds the optimal path, but it may occasionally need to reopen a closed node when a better path to it is discovered later.

For common grid heuristics
  • Manhattan distance: consistent for 4-directional grids with uniform edge costs. Proof: moving from n to nb costs at least 1, and Manhattan distance changes by at most 1 per step, so h(n) <= 1 + h(nb) always holds.
  • Euclidean distance: consistent for any spatial graph where edge costs equal Euclidean length. Follows directly from the geometric triangle inequality.
  • Diagonal distance: consistent for 8-directional grids where diagonal moves cost sqrt(2).

How to validate your heuristic in production: 1. Run Dijkstra on your graph to compute true_cost(n, goal) for all nodes n. 2. Assert h(n) <= true_cost(n, goal) for every n. 3. Run this as a CI test on a representative graph sample, not just hand-picked cases. 4. If any assertion fails, your heuristic is inadmissible — fix it before shipping.

The Admissibility Contract Is a Promise to Every Future Path
  • h(n) <= true_cost(n, goal) means f(n) = g(n) + h(n) is a lower bound on the true cost of any path through n.
  • When A* closes the goal node, it has found a path with cost g(goal). Every other node still in the open set has f >= g(goal) >= true_optimal_cost. No alternative can be cheaper.
  • A multiplier > 1.0 on a lower-bound heuristic destroys admissibility immediately. 1.3 × euclidean is not a conservative estimate — it is an overestimate by definition.
  • Consistent heuristics give you an additional guarantee: the first time a node is expanded, its g-value is final. No reopening needed.
  • Zero heuristic (h=0) is trivially admissible and consistent — it makes A* exactly Dijkstra. It is the safe fallback when you cannot design a meaningful heuristic.
● Production incidentPOST-MORTEMseverity: high

Delivery Drone Routes 23% Longer Than Optimal — Inadmissible Heuristic in Production

Symptom
Drone completion times exceeded simulation estimates by 15 to 25 percent. Battery consumption per delivery was running 20 percent above projections. No crashes, no exceptions, no alerts — the routing service ran silently and returned routes that looked perfectly plausible. The only signal was an operations dashboard showing rising cost-per-delivery, which was initially attributed to wind conditions.
Assumption
The operations team blamed wind modeling inaccuracies and GPS drift for the extra flight time. Engineering spent the first week investigating race conditions in the route cache invalidation logic, suspecting that stale routes from a previous airspace configuration were being served. Both teams were wrong.
Root cause
The A heuristic used Euclidean distance as a base but applied a 1.3x safety multiplier to account for no-fly zones — the reasoning being that actual flight paths would be longer than straight-line distance due to restricted airspace. This made h(n) = 1.3 × euclidean(n, goal), which consistently overestimates the true remaining cost whenever no-fly zones are sparse or not directly in the path. An overestimating heuristic violates admissibility. A with an inadmissible heuristic prematurely commits to paths that appear cheap under the inflated heuristic but are actually longer in reality — exactly the failure mode admissibility is designed to prevent. The 1.3x factor felt conservative and safe. It was neither.
Fix
1. Removed the 1.3x multiplier entirely. Replaced it with a precomputed lower-bound lookup table that accounts for no-fly zone geometry without ever overestimating — derived from offline Dijkstra runs on a coarse grid of the airspace. 2. Added a daily validation job that compares A output against Dijkstra on a randomly sampled 5% of route requests. Any route where A is longer than Dijkstra triggers an alert and a heuristic audit. 3. Implemented weighted A* (w=1.5) as a separate real-time variant for latency-sensitive requests, with an explicit optimality bound of 1.5x logged to the monitoring dashboard so operations can see the trade-off being made. 4. Added a unit test suite that iterates every node in the test graph and asserts h(n) <= true_cost(n, goal) computed by Dijkstra. This test runs on every CI build.
Key lesson
  • An inadmissible heuristic produces wrong answers silently — no crash, no exception, no log line. Just suboptimal paths that look plausible because they are valid paths, just not optimal ones.
  • Never multiply heuristic values by a safety factor without formally proving that admissibility is preserved. A factor greater than 1.0 on a lower-bound heuristic always violates admissibility.
  • Always validate heuristic correctness with automated tests that compare A* output against Dijkstra on a representative sample of graphs. If Dijkstra ever finds a shorter path, your heuristic is inadmissible.
  • Separate the real-time routing path from the optimal routing path in your architecture. Use weighted A with a logged optimality bound when latency matters, and standard A when correctness is non-negotiable.
Production debug guideCommon symptoms when A* returns suboptimal paths or performs unexpectedly in production. Most of these produce no error — just wrong or slow results.5 entries
Symptom · 01
Returned path is valid but consistently 10 to 30 percent longer than the optimal route
→
Fix
Check heuristic admissibility immediately. Run A* and Dijkstra on the same graph with the same start and goal. If Dijkstra finds a shorter path, your h(n) is overestimating somewhere. Audit every place where the heuristic value is computed or modified — look specifically for multipliers greater than 1.0 applied to a base lower-bound heuristic.
Symptom · 02
Path is optimal on unweighted test graphs but suboptimal on weighted production graphs
→
Fix
You are almost certainly checking for the goal at insertion time instead of pop time. At insertion time, the node's g-value is a candidate — not yet the proven optimum. Move the goal check to immediately after the priority queue poll. The moment the goal node is popped, its g-score is the true optimal cost.
Symptom · 03
A* runs slower than Dijkstra despite having a heuristic that should reduce expansions
→
Fix
Check for two separate issues. First, verify that lazy deletion is implemented — when you pop a node, check if it is already in the closed set and skip it if so. Without this, stale priority queue entries cause the same node to be expanded multiple times. Second, check whether the heuristic is so weak (h values near zero) that it provides no useful guidance, effectively making A* behave like Dijkstra with extra heap overhead.
Symptom · 04
Memory usage grows unbounded on large graphs — heap size keeps increasing during a single pathfinding call
→
Fix
Verify that duplicate heap entries are being controlled with the g-value check. Before pushing a neighbor to the heap, check if tentative_g is strictly less than the current best-known g[neighbor]. If not, do not push. Without this guard, every time a node is revisited with any path — even a worse one — a new entry is pushed, inflating the heap without bound.
Symptom · 05
Path reconstruction returns an incorrect or empty path even though the algorithm reports finding the goal
→
Fix
Verify that the parent map is being updated correctly and consistently with the key encoding. If you use string keys like r+','+c, verify there are no collision cases where different coordinates produce the same string. Also verify that the start node's parent is explicitly set to null or a sentinel value — a missing start-node parent entry causes the reconstruction loop to terminate prematurely.
★ A* Performance and Correctness Quick DiagnosisSymptom-to-fix commands for production A* pathfinding failures.
Path is suboptimal — longer than Dijkstra's result on the same graph−
Immediate action
Verify heuristic admissibility. The heuristic is the only component that can cause A* to return a valid but non-optimal path.
Commands
grep -n 'heuristic\|def h\|return.*Math.abs\|return.*sqrt\|\* 1\.' io/thecodeforge/pathfinding/AStarSolver.java
java -cp . io.thecodeforge.pathfinding.AStarValidator --compare-dijkstra --graph test.graph --sample-rate 0.1
Fix now
Ensure h(n) <= true_cost(n, goal) for all nodes. Euclidean distance is always a safe admissible lower bound for spatial graphs. Remove any multiplier greater than 1.0 applied to a base lower-bound heuristic.
A* is slower than Dijkstra — node expansion count is higher than expected+
Immediate action
Check whether lazy deletion is correctly implemented and whether the closed-set skip is actually being reached.
Commands
grep -n 'closed.contains\|closedSet\|visited.contains' io/thecodeforge/pathfinding/AStarSolver.java
jmap -histo <pid> | grep -i 'PriorityQueue\|long\[\]' | head -5
Fix now
After every poll(), add: if (closed.contains(key)) continue; This single check eliminates all duplicate expansions caused by stale heap entries. Log the expansion count before and after to verify improvement.
OutOfMemoryError or heap size growing unbounded during pathfinding on large graphs+
Immediate action
Locate every point where entries are pushed to the priority queue and verify the g-value guard is present.
Commands
grep -n 'offer\|add\|push' io/thecodeforge/pathfinding/AStarSolver.java
jcmd <pid> GC.heap_info
Fix now
Wrap every heap push with: if (tentativeG < gScores.getOrDefault(neighborKey, Long.MAX_VALUE)) { ... offer ... }. Without this guard, every path to a node — including worse ones — pushes a new entry.
Related Articles
Graph RepresentationIntermediateBFS — Breadth First SearchIntermediateDFS — Depth First SearchIntermediateDijkstra Shortest Path AlgorithmAdvancedBellman-Ford AlgorithmAdvancedFloyd-Warshall AlgorithmAdvanced
🔥

That's Graphs. Mark it forged?

13 min read · try the examples if you haven't

←
Previous
Strongly Connected Components
14 / 17 · Graphs
Next
Bubble Sort
→