DSA Advanced

A* Search Algorithm — Heuristic-Guided Shortest Path

Q: What does admissible heuristic mean and why does it matter?

An admissible heuristic never overestimates the true remaining cost to the goal — h(n) <= true_cost(n, goal) for every node n. This condition is what guarantees A* finds the optimal path. When A* closes a node, admissibility ensures that no undiscovered path through that node can be cheaper than what A* already knows. If h overestimates, A* may prematurely abandon a cheap path because f(n) looks inflated, returning a suboptimal route with no error or warning. Common admissible heuristics: Manhattan distance for 4-directional grids, Euclidean distance for spatial graphs, Chebyshev distance for 8-directional grids. Never multiply these by a factor greater than 1.0 unless you explicitly intend weighted A*.

Q: How does A* differ from Dijkstra's algorithm?

Dijkstra expands nodes by g(n) — actual cost from start — with no awareness of where the goal is. It explores uniformly in all directions. A* expands by f(n) = g(n) + h(n), using the heuristic to bias expansion toward the goal. When h(n) = 0 for all nodes, A* is exactly Dijkstra. When h is tight (close to the true remaining cost), A* expands only the nodes on or near the optimal path and ignores most of the graph. The algorithm structure is identical — both use a priority queue and a closed set. Only the priority ordering differs.

Q: What is a consistent heuristic and should I care about it?

A consistent heuristic satisfies h(n) <= cost(n, nb) + h(nb) for every node n and neighbor nb — the triangle inequality. Consistency implies admissibility. The practical benefit is that a consistent heuristic guarantees A* never needs to reopen a closed node — the first expansion of any node produces its final optimal g-value. This makes consistent heuristics strictly more efficient than merely admissible ones and simplifies implementation. Manhattan distance for 4-directional grids is consistent. Euclidean distance is consistent for spatial graphs. If you are designing a custom heuristic, checking consistency is worth the effort — it is a stronger property and easier to verify than checking admissibility alone.

Q: When should I use weighted A* instead of standard A*?

Use weighted A* when the pathfinding must complete within a tight latency budget and a slightly suboptimal path is acceptable. Weighted A* uses f = g + w*h with w > 1.0, inflating the heuristic's influence to reduce node expansions. The formal guarantee is that the returned path costs at most w times the optimal path cost. A weight of 1.5 is a common production choice — paths are within 50% of optimal and expansions typically drop by 60 to 80 percent. Always log the weight as an explicit parameter so operators know the optimality bound being applied. Never silently use w > 1.0 without documenting and monitoring it.

📅 March 06, 2026 ⏱ 10 min read 🎯 Advanced

Where developers are forged. · Structured learning · Free forever.

📍 Part of: Graphs → Topic 14 of 17

Master A* search: find the shortest path using a heuristic function to guide exploration, combining Dijkstra's correctness with greedy speed.

🔥 Advanced — solid DSA foundation required

In this tutorial, you'll learn

Master A* search: find the shortest path using a heuristic function to guide exploration, combining Dijkstra's correctness with greedy speed.

A* combines exact cost g(n) and heuristic estimate h(n) via f(n) = g(n) + h(n) to find the optimal path while exploring dramatically fewer nodes than Dijkstra on spatial graphs.
Admissible heuristics — h(n) never overestimates the true remaining cost — guarantee A* finds the optimal path. Violate admissibility and you get wrong answers with no runtime signal.
A* degenerates to Dijkstra when h=0 and to greedy best-first search when g is ignored. The heuristic is the dial between correctness and goal-directedness.

✦ Plain-English analogy ✦ Real code with output ✦ Interview questions

⚡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

🚨 START HERE

A* Performance and Correctness Quick Diagnosis

Symptom-to-fix commands for production A* pathfinding failures.

🟡Path is suboptimal — longer than Dijkstra's result on the same graph

Immediate ActionVerify 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 NowEnsure 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 ActionCheck 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 NowAfter every poll(), add: if (closed.contains(key)) continue; This single check prevents stale entries from being expanded. Log the expansion count before and after to verify improvement.

🔴OutOfMemoryError or heap size growing unbounded during pathfinding on large graphs

Immediate ActionLocate 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 NowWrap 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.

Production IncidentDelivery Drone Routes 23% Longer Than Optimal — Inadmissible Heuristic in ProductionA last-mile delivery platform's drone fleet was consistently generating routes 23% longer than optimal, causing battery drain and missed delivery windows across three cities over two months before the root cause was identified.

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

AssumptionThe 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 causeThe 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.

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

Returned path is valid but consistently 10 to 30 percent longer than the optimal route→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.

Path is optimal on unweighted test graphs but suboptimal on weighted production graphs→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.

A* runs slower than Dijkstra despite having a heuristic that should reduce expansions→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.

Memory usage grows unbounded on large graphs — heap size keeps increasing during a single pathfinding call→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.

Path reconstruction returns an incorrect or empty path even though the algorithm reports finding the goal→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.

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.

Mental Model

The Three Algorithms as Exploration Strategies

Think of pathfinding as deciding which door to open next in a large maze — each algorithm uses a different piece of information to make that decision.

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.

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.java · JAVA

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250

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
 *     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) {

        validateInputs(grid, start, goal);
        int rows = grid.length;
        int cols = grid[0].length;

        // g-scores: best known cost from start. Long.MAX_VALUE = unvisited.
        long[][] gScore = new long[rows][cols];
        for (long[] row : gScore) Arrays.fill(row, Long.MAX_VALUE);
        gScore[start[0]][start[1]] = 0L;

        // parent tracking for path reconstruction
        // encoded as flat index: row * cols + col, -1 = no parent
        int[] parent = new int[rows * cols];
        Arrays.fill(parent, -1);

        // closed set: nodes whose optimal g-score is finalized
        boolean[][] closed = new boolean[rows][cols];

        // 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) {

        List<int[]> path = new ArrayList<>();
        int curr = goal[0] * cols + goal[1];
        int startIdx = start[0] * cols + start[1];

        while (curr != startIdx && curr != -1) {
            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.

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.

Mental Model

The Admissibility Contract Is a Promise to Every Future Path

When A* closes a node and stops exploring through it, it is making a bet: no undiscovered path through this node can be cheaper than what we already found. Admissibility is what makes that bet safe.

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 Insight

Tight admissible heuristics expand fewer nodes. A heuristic of h=0 is correct but expands every reachable node. A perfect heuristic (h = true_cost) expands only nodes on the optimal path. Real heuristics live between these extremes — the tighter to true_cost, the better the performance.

For road network routing, precomputed landmark distances (ALT algorithm) provide tight lower bounds and are used in production routing engines for exactly this reason.

Rule: design heuristics to be as tight as possible without overestimating. Every unit of slack in your heuristic becomes extra node expansions.

🎯 Key Takeaway

Admissibility (h never overestimates) guarantees optimal paths. Consistency (triangle inequality) additionally guarantees each node is expanded at most once.

Validate heuristic admissibility with automated tests comparing h(n) against Dijkstra-computed true costs. Do not trust intuition alone.

Multiplying a lower-bound heuristic by any factor greater than 1.0 destroys admissibility — it converts A into weighted A whether you intended that or not.

🗂 Dijkstra vs Greedy Best-First vs A* — Complete Comparison

When to use each algorithm and what you trade off. Default to A* when you have a single target and a valid heuristic.

Aspect	Dijkstra's Algorithm	Greedy Best-First Search	A* Search
Evaluation function	f(n) = g(n) — actual cost from start only	f(n) = h(n) — estimated cost to goal only	f(n) = g(n) + h(n) — actual cost plus estimate
Optimal path guaranteed?	Yes, for all non-negative edge weights	No — frequently suboptimal, can get trapped by dead ends	Yes, when h is admissible. Bounded suboptimal with weighted A*.
Heuristic required?	No — works on any weighted graph	Yes — without h the algorithm has no goal awareness	Yes — h quality determines how much faster than Dijkstra
Direction of expansion	Uniform outward in all directions from start	Directly toward goal regardless of accumulated cost	Balanced — goal-biased but accounting for actual travel cost
Nodes expanded (typical)	Most — no goal bias, expands everything within cost radius	Fewest — but often wrong paths and dead-end backtracks	Fewest among correct algorithms — heuristic focuses the search
Worst-case time complexity	O((V + E) log V)	O((V + E) log V)	O((V + E) log V) — but with far fewer V in practice on spatial graphs
Memory usage	O(V) — stores all reachable nodes in open and closed sets	O(V) — same structure	O(V) — open set, closed set, g-scores, parent map
Best production use case	All-pairs shortest paths, unknown goal location, no valid heuristic	Rapid rough navigation where suboptimal paths are acceptable	Single-target shortest path with a spatial or domain-specific heuristic
Handles negative edge weights?	No — requires Bellman-Ford for negative weights	No — heuristic-based, assumes non-negative costs	No — same limitation as Dijkstra
Weighted variant for speed?	Not applicable	Not applicable — already ignores g entirely	Weighted A: f = g + wh with w > 1.0 gives bounded suboptimality within factor w

🎯 Key Takeaways

A* combines exact cost g(n) and heuristic estimate h(n) via f(n) = g(n) + h(n) to find the optimal path while exploring dramatically fewer nodes than Dijkstra on spatial graphs.
Admissible heuristics — h(n) never overestimates the true remaining cost — guarantee A* finds the optimal path. Violate admissibility and you get wrong answers with no runtime signal.
A* degenerates to Dijkstra when h=0 and to greedy best-first search when g is ignored. The heuristic is the dial between correctness and goal-directedness.
Goal detection must happen at pop time, not insertion time. Insertion-time checking is wrong for weighted graphs — it returns a valid but non-optimal path and passes all unweighted unit tests.
Tie-breaking by g-value when f is equal significantly reduces node expansions on large open grids — it is free performance that textbooks consistently omit.
Weighted A (f = g + wh, w > 1) provides a bounded suboptimality guarantee of w times optimal. Use it for latency-sensitive applications and log the weight as an explicit optimality bound.

⚠ Common Mistakes to Avoid

✕Using an inadmissible heuristic — most commonly by multiplying a lower-bound heuristic by a safety factor

Symptom

The algorithm returns a valid path every time — correct endpoints, no exception, no log line. The path is just not the shortest one. The discrepancy is 10 to 30 percent longer than optimal and is consistent enough to look like a systematic bias, which it is.

Fix

Never multiply a base lower-bound heuristic by any factor greater than 1.0 and call the result admissible. A factor of 1.3 on Euclidean distance produces an overestimating heuristic by definition. If you want to account for real-world path lengthening due to constraints like no-fly zones, compute a proper lower bound from precomputed data rather than inflating a geometric estimate. Write a test that computes true_cost via Dijkstra for every node in your test graph and asserts h(n) <= true_cost(n, goal). Run it in CI.

✕Checking for the goal at insertion time instead of pop time

Symptom

Returns a path with correct start and end nodes but non-minimum total cost on weighted graphs. Passes all unit tests written on unweighted grids because BFS and A* produce equivalent g-values at equal depth on unit-cost graphs. Fails in production the moment terrain costs vary.

Fix

Move the goal condition to immediately after polling from the priority queue. The single line if (r == goal[0] && c == goal[1]) return reconstructPath(...) belongs after poll(), not inside the neighbor loop. When the goal node is popped, its g-value is the proven optimal cost. Before that moment, g(goal) is a good candidate, not a proven minimum.

✕Not implementing lazy deletion — allowing stale priority queue entries to be expanded

Symptom

Algorithm produces correct paths but runs significantly slower than expected. Node expansion count is higher than the number of nodes in the graph, which is impossible unless nodes are being expanded multiple times. Memory usage is higher than O(V) because the heap accumulates duplicate entries.

Fix

After every poll(), immediately check if the popped node is already in the closed set and skip it if so: if (closed[r][c]) continue. This one check, placed before any neighbor expansion, eliminates all duplicate expansions caused by stale heap entries. Log the expansion count before and after adding this check to confirm the improvement.

✕Using String concatenation for node keys in performance-critical pathfinding

Symptom

A* runs noticeably slower than expected on large grids despite correct implementation. Profiling shows high GC pressure and significant time spent in String.format or string concatenation operations inside the hot loop.

Fix

Replace string key encoding with flat integer indexing: key = row * cols + col. This encodes any (row, col) pair as a unique int with zero allocation overhead. Use boolean[][] for the closed set and long[][] for g-scores — direct array access is several times faster than HashMap lookup inside a tight loop that runs millions of times on a large grid.

Interview Questions on This Topic

QWhat is the f(n) function in A* and what do each of its components represent?JuniorReveal
f(n) = g(n) + h(n). Each component represents a different kind of knowledge. g(n) is the exact accumulated cost from the start node to node n along the best path found so far. It is known precisely — computed from actual edge costs traversed. It represents 'how much have I already spent getting here.' h(n) is the heuristic estimate of the remaining cost from n to the goal. It is an approximation — the algorithm does not know the true remaining cost without completing the search. It represents 'how much do I estimate I still need to spend.' f(n) = g(n) + h(n) is therefore the estimated total cost of the cheapest path through n. A* always expands the node with the minimum f(n), which ensures it is always working on the most promising candidate path — the one with the lowest estimated total cost from start to goal through the current node.
QWhat makes a heuristic admissible, and what happens if it is not?Mid-levelReveal
A heuristic h(n) is admissible if h(n) <= true_cost(n, goal) for every node n in the graph. It never overestimates the true remaining cost to the goal. Why admissibility guarantees optimality: when A is about to close a node n and commit to its g-value, every node remaining in the open set has f >= f(n). Since h is admissible, f is a lower bound on the true path cost through any open node. No undiscovered path can be cheaper than g(n) + h(n), so g(n) is proven optimal. What happens without admissibility: A may evaluate a node and see f(n) = g(n) + h(n) appears high. If h overestimates, f is inflated — the node looks expensive but is not. A* may skip or defer that node in favor of another with a lower (but falsely optimistic) f-value. The result is a suboptimal path returned with complete confidence and no error signal. Common admissible heuristics: Manhattan distance for 4-directional grids with unit costs, Euclidean distance for any spatial graph where edge costs match physical distance, Chebyshev distance for 8-directional grids. Any heuristic derived from relaxing constraints of the original problem is admissible by construction.
QHow does A compare to Dijkstra's algorithm, and when does A reduce to Dijkstra?Mid-levelReveal
Both algorithms find optimal shortest paths using a priority queue. The difference is what drives the queue ordering. Dijkstra expands nodes in order of g(n) — actual cost from start. It has no goal awareness and expands outward uniformly in all directions. On a grid navigating from corner to corner, Dijkstra may expand the entire grid before reaching the goal. A expands nodes in order of f(n) = g(n) + h(n) — actual cost plus heuristic estimate of remaining cost. The heuristic biases expansion toward the goal, so A typically expands far fewer nodes than Dijkstra while finding the same optimal path. A reduces to Dijkstra when h(n) = 0 for all nodes. f(n) = g(n) + 0 = g(n), identical to Dijkstra's ordering. This happens when no meaningful heuristic is available — it is always safe, always correct, and never better than Dijkstra in terms of expansions. A is strictly better than Dijkstra in practice whenever h(n) > 0 and admissible — the heuristic provides information that Dijkstra does not have. The improvement is most dramatic on large sparse graphs with clear geometric structure, like road networks and game maps.
QWhat is a consistent heuristic, why does it matter for A* efficiency, and how does it relate to admissibility?SeniorReveal
A heuristic h is consistent (also called monotone) if for every node n and every neighbor nb reached via an edge of cost c: h(n) <= c + h(nb). This is the triangle inequality applied to the heuristic — the estimated cost from n to goal should not exceed the cost of going from n to nb plus the estimated cost from nb to goal. Consistency implies admissibility. Proof: for any node n, consider the path from n to goal through any sequence of nodes n1, n2, ..., goal. By repeatedly applying the consistency condition: h(n) <= c(n,n1) + h(n1) <= c(n,n1) + c(n1,n2) + h(n2) <= ... <= true_cost(n, goal). Therefore h(n) <= true_cost(n, goal), which is admissibility. Why consistency matters for efficiency: with a consistent heuristic, the sequence of f-values encountered by A is non-decreasing along any path. This means the first time A closes a node, its g-value is already optimal. No node ever needs to be reopened. Every node is expanded at most once, giving an expansion count of at most V — the tightest possible bound. With an admissible but not consistent heuristic, A* still finds the optimal path, but it may occasionally discover a better path to a closed node and need to reopen it with the updated g-value. This is rare in practice but theoretically possible and adds implementation complexity. Manhattan distance for 4-directional unit-cost grids is consistent. Euclidean distance for any spatial graph where edge costs equal physical distances is consistent. Both are safe defaults for their respective domains.

Frequently Asked Questions

What does admissible heuristic mean and why does it matter?

An admissible heuristic never overestimates the true remaining cost to the goal — h(n) <= true_cost(n, goal) for every node n. This condition is what guarantees A finds the optimal path. When A closes a node, admissibility ensures that no undiscovered path through that node can be cheaper than what A already knows. If h overestimates, A may prematurely abandon a cheap path because f(n) looks inflated, returning a suboptimal route with no error or warning. Common admissible heuristics: Manhattan distance for 4-directional grids, Euclidean distance for spatial graphs, Chebyshev distance for 8-directional grids. Never multiply these by a factor greater than 1.0 unless you explicitly intend weighted A*.

How does A* differ from Dijkstra's algorithm?

Dijkstra expands nodes by g(n) — actual cost from start — with no awareness of where the goal is. It explores uniformly in all directions. A expands by f(n) = g(n) + h(n), using the heuristic to bias expansion toward the goal. When h(n) = 0 for all nodes, A is exactly Dijkstra. When h is tight (close to the true remaining cost), A* expands only the nodes on or near the optimal path and ignores most of the graph. The algorithm structure is identical — both use a priority queue and a closed set. Only the priority ordering differs.

What is a consistent heuristic and should I care about it?

A consistent heuristic satisfies h(n) <= cost(n, nb) + h(nb) for every node n and neighbor nb — the triangle inequality. Consistency implies admissibility. The practical benefit is that a consistent heuristic guarantees A* never needs to reopen a closed node — the first expansion of any node produces its final optimal g-value. This makes consistent heuristics strictly more efficient than merely admissible ones and simplifies implementation. Manhattan distance for 4-directional grids is consistent. Euclidean distance is consistent for spatial graphs. If you are designing a custom heuristic, checking consistency is worth the effort — it is a stronger property and easier to verify than checking admissibility alone.

When should I use weighted A* instead of standard A*?

Use weighted A when the pathfinding must complete within a tight latency budget and a slightly suboptimal path is acceptable. Weighted A uses f = g + w*h with w > 1.0, inflating the heuristic's influence to reduce node expansions. The formal guarantee is that the returned path costs at most w times the optimal path cost. A weight of 1.5 is a common production choice — paths are within 50% of optimal and expansions typically drop by 60 to 80 percent. Always log the weight as an explicit parameter so operators know the optimality bound being applied. Never silently use w > 1.0 without documenting and monitoring it.

🔥

Naren Founder & Author

Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.

About Naren Get in touch

Forged with 🔥 at TheCodeForge.io — Where Developers Are Forged