Interactive pathfinding visualization. Click and drag on the grid to create barriers.
Overview
The problem with searching in every direction
Dijkstra’s algorithm expands outward from the source in rings of equal cost. If the goal is due east, it still explores just as far north, south and west before reaching it. On a large map that is enormous wasted effort — the algorithm has no idea where it is going.
A* adds that idea. Alongside the known cost from the start it keeps an estimate of the cost still to come, and expands whichever node looks best on the total.
Toolbox
Execution Speed
Search Space
Status: Ready
Performance
Nodes Explored0
Path Length0
Total Cost0.00
Legend
Open List
Closed List
Path
A* Pathfinding Algorithm: A Practical Guide
Dijkstra with a sense of direction. Adding an estimate of the remaining distance steers the search toward the goal instead of expanding uniformly - and if that estimate never overestimates, the path is still optimal.
f = g + h
Every node carries three numbers:
g(n) — the actual cost of the best known path from the start to n. This is exactly Dijkstra’s distance.
h(n) — the heuristic: an estimate of the remaining cost from n to the goal.
f(n) = g(n) + h(n) — the estimated total cost of a route through n.
A* is then exactly Dijkstra with the priority queue ordered by f instead of g. Set h(n) = 0 everywhere and you get Dijkstra back precisely — A* is a strict generalisation, not a different algorithm.
Admissible, consistent, and why it stays optimal
A heuristic is admissible if it never overestimates the true remaining cost. That single property is what guarantees A* finds an optimal path.
The reason: if h never overestimates, then f(n) never overestimates the cost of the best route through n. So when the goal is popped with total cost f, no unexplored node can be hiding a cheaper route — any such node would have had a smaller f and been popped first.
Overestimate, and that breaks. An inflated h can make the true best route look worse than a bad one, and A* will return the bad one. The common heuristics on a grid are admissible by construction:
Manhattan|dx| + |dy| — admissible when movement is 4-directional, because that is the exact distance with no obstacles.
Euclidean√(dx² + dy²) — admissible always, since a straight line is the shortest possible route, but weak (too low) on 4-directional grids.
Zero — admissible and useless: this is Dijkstra.
Note that Manhattan is not admissible if diagonal movement is allowed, because the diagonal route is shorter than |dx| + |dy|. That mismatch is the most common way people accidentally break optimality.
Dijkstra, pointed at the goal
Dijkstra's algorithm expands outwards in all directions, treating every unexplored node as equally worth visiting. On a map, searching from London for a route to Manchester, it spends effort exploring towards Cornwall.
A* fixes that with one change to the priority:
f(n) = g(n) + h(n)
g(n) is the known cost from the start — exactly what Dijkstra uses. h(n) is a heuristic estimate of the remaining cost to the goal. Prioritising by their sum focuses the search along promising directions.
import heapq
def a_star(start, goal, neighbours, cost, h):
g = {start: 0}
prev = {start: None}
pq = [(h(start), start)]
while pq:
_, node = heapq.heappop(pq)
if node == goal:
break
for nxt in neighbours(node):
ng = g[node] + cost(node, nxt)
if ng < g.get(nxt, float("inf")):
g[nxt] = ng
prev[nxt] = node
heapq.heappush(pq, (ng + h(nxt), nxt)) # g + h
return reconstruct(prev, goal)
The only difference from Dijkstra is ng + h(nxt) where Dijkstra pushes ng. With h = 0, A* is Dijkstra.
Admissibility: the condition for correctness
A* returns the optimal path if the heuristic is admissible — it never overestimates the true remaining cost.
The reasoning: if h underestimates, then f(n) = g(n) + h(n) is a lower bound on the true cost of any path through n. So when the goal is popped with the smallest f, no unexplored path can be shorter, and the path found is optimal.
If h overestimates, A* may pop the goal while a better path is still queued, and it returns a suboptimal route quickly. Sometimes that is an acceptable trade — deliberately inflating h ("weighted A*") gives faster, slightly worse paths, and games use it routinely.
Heuristic
Admissible for
0
Anything — this is Dijkstra
Straight-line (Euclidean) distance
Movement in any direction
Manhattan distance
Grid movement, 4 directions only
Diagonal (Chebyshev) distance
Grid movement, 8 directions
Actual remaining cost
Perfect — explores only the optimal path
A stronger property, consistency (or monotonicity), means h never decreases by more than the edge cost along any edge. A consistent heuristic guarantees each node is finalised once, so no node needs reopening — which is why standard implementations can use a closed set safely.
Choosing the heuristic is the whole design
The heuristic decides how much better than Dijkstra A* is, and getting it wrong is the usual failure.
Too weak (close to 0) and A* degenerates towards Dijkstra, exploring almost everything.
Not admissible and the result is suboptimal. The classic mistake on a 4-directional grid is using Euclidean distance: it underestimates correctly, so it is admissible — but Manhattan distance is a tighter underestimate and therefore explores far less. Conversely, using Manhattan distance when diagonal movement is allowed overestimates and breaks optimality.
Too expensive to compute and the per-node saving is lost. h is evaluated for every node examined.
The practical rule: use the tightest admissible estimate that is cheap to compute, and match it to the actual movement rules.
For road networks the straight-line distance is admissible but weak, because roads are not straight. Production routing engines use landmark-based heuristics: precompute distances from a few hundred landmark nodes, and use the triangle inequality to derive much tighter bounds. That is one of the techniques that makes continental route planning interactive.
What the heuristic buys, and the condition it must satisfy
A* is Dijkstra's algorithm plus a guess about how far the goal still is. The guess decides everything: a good one cuts the search enormously, a merely plausible one makes it return the wrong path. Both are visible on a grid you can print.
example_01.pyPython
import heapq
GRID = [
"..........",
".####.###.",
".#........",
".#.#####.#",
"...#...#..",
".###.#.##.",
".....#....",
"####.#.##.",
"......#...",
".####.....",
]
START, GOAL = (0, 0), (9, 9)
def neighbours(p):
r, c = p
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < len(GRID) and 0 <= nc < len(GRID[0]) and GRID[nr][nc] != "#":
yield (nr, nc)
def search(h):
# h = None gives Dijkstra: no guess at all
openq = [(0, 0, START, [START])]
best = {START: 0}
expanded = 0
while openq:
_, g, node, path = heapq.heappop(openq)
if node == GOAL:
return path, expanded
if g > best.get(node, float("inf")):
continue
expanded += 1
for nxt in neighbours(node):
ng = g + 1
if ng < best.get(nxt, float("inf")):
best[nxt] = ng
f = ng + (h(nxt) if h else 0)
heapq.heappush(openq, (f, ng, nxt, path + [nxt]))
return None, expanded
def manhattan(p):
return abs(p[0] - GOAL[0]) + abs(p[1] - GOAL[1])
def overestimate(p):
return manhattan(p) * 4 # never admissible: it exaggerates
print("%-28s %10s %14s" % ("heuristic", "expanded", "path length"))
for name, h in (("none (Dijkstra)", None),
("Manhattan (admissible)", manhattan),
("Manhattan x 4 (not)", overestimate)):
path, expanded = search(h)
print("%-28s %10d %14d" % (name, expanded, len(path) - 1))
# Three runs, same grid, same goal. Dijkstra expands the most cells
# because it explores outward in all directions equally. Manhattan
# distance points the search at the goal and cuts the work, and it still
# returns a shortest path.
#
# The third one is the warning. Multiplying the heuristic makes it
# ADMISSIBLE no longer -- it can claim the remaining distance is larger
# than it really is -- and A* will then happily commit to a route it
# should have kept open. It expands fewer cells still, and that speed is
# bought with correctness.
#
# Admissible means: never overestimate the true remaining cost. Manhattan
# distance on a 4-connected grid qualifies, because you must make at least
# that many moves and obstacles can only make it worse.
print()
print("checking admissibility against the true cost from each cell:")
true_cost = {}
frontier = [(0, GOAL)]
while frontier:
d, node = heapq.heappop(frontier)
if node in true_cost:
continue
true_cost[node] = d
for nxt in neighbours(node):
if nxt not in true_cost:
heapq.heappush(frontier, (d + 1, nxt))
bad_manhattan = [p for p, d in true_cost.items() if manhattan(p) > d]
bad_scaled = [p for p, d in true_cost.items() if overestimate(p) > d]
print(" cells where Manhattan overestimates: %d" % len(bad_manhattan))
print(" cells where Manhattan x 4 overestimates: %d of %d" % (
len(bad_scaled), len(true_cost)))
# Zero against most of the grid. That is the whole condition, checked
# directly, and it is the reason one of those heuristics is safe to use
# and the other is not.
#
# The path itself:
path, _ = search(manhattan)
on_path = set(path)
print()
for r, row in enumerate(GRID):
print(" " + "".join("o" if (r, c) in on_path else ch
for c, ch in enumerate(row)))
Output
Guided experiments
See the search become directional. Press Run Algorithm and watch the explored region. It stretches toward the goal rather than spreading in a circle — that elongation is h doing its job.
Turn the heuristic off. Set Heuristic to the zero or Dijkstra option and press Reset Grid, then run again. The explored area balloons into a symmetric blob. The path found is the same length; the work to find it is far greater.
Compare Manhattan against Euclidean. Run each in turn on the same grid. Manhattan is the larger estimate on a 4-directional grid, so it prunes harder and expands fewer nodes while still finding an optimal route.
Slow it down and watch the frontier choose. Set Execution Speed to 1 and run. Each expansion picks the lowest f, so the frontier repeatedly reaches toward the goal and only falls back sideways when it meets an obstacle.
What usually goes wrong
An inadmissible heuristic. Scaling h up (multiplying by 1.5, say) makes the search much faster and quietly non-optimal. That trade is sometimes worth making — weighted A* is a real technique — but it must be a decision, not an accident.
Manhattan distance with diagonal movement. Overestimates, so paths stop being optimal. Use the octile heuristic when diagonals are allowed.
Forgetting that a node’s g can improve. With a merely admissible (not consistent) heuristic, a node may be reached again more cheaply after being expanded. Either use a consistent heuristic or re-open such nodes.
An expensive heuristic. h is evaluated constantly. If computing it costs more than the expansions it saves, A* is slower than Dijkstra despite exploring fewer nodes.
What to remember
A* orders its priority queue by f = g + h, where g is the cost so far and h estimates the cost remaining, which focuses the search along the direction of the goal instead of expanding uniformly. Provided h never overestimates, the path returned is still optimal — and the better the estimate, the fewer nodes get expanded. With h = 0 it degenerates exactly to Dijkstra, which is the cleanest way to see what the heuristic is buying.
Where it is used
Game pathfinding. The default algorithm for moving units around a map, usually on a grid or navigation mesh.
Robotics. Motion planning over occupancy grids, often with variants handling continuous space.
Route planning. Real navigation systems use A* with landmark heuristics, or contraction hierarchies which precompute shortcuts.
Puzzle solving. Sliding tiles, Rubik's cube and similar, where the heuristic is a relaxation of the puzzle — for the 15-puzzle, the sum of Manhattan distances of each tile from its home.
Word ladders and state-space search generally, where the graph is generated on demand.
Automated planning in AI, where the state space is enormous and heuristics are essential.
The puzzle case illustrates a general technique for inventing heuristics: solve a relaxed version of the problem. Ignoring that tiles block each other gives the Manhattan-distance heuristic, which is admissible because the real puzzle can only be harder.
The variants
Variant
Change
Use
Weighted A*
f = g + w×h with w > 1
Faster, suboptimal by at most a factor of w
IDA*
Iterative deepening with an f-limit
Memory-constrained; puzzles
Bidirectional A*
Search from both ends
Long paths
Jump point search
Skip symmetric grid paths
Uniform-cost grids — large speed-up
D* / D* Lite
Repair the path when the map changes
Robotics with unknown obstacles
Anytime A*
Return a path quickly, improve it
Real-time constraints
Memory is A*'s real weakness. It stores every node it has seen, and on a large state space that exhausts memory long before time becomes the constraint. IDA* addresses this by using depth-first search with an increasing f-limit and O(depth) memory, at the cost of re-expanding nodes.
Jump point search is worth knowing for grid games: on a uniform-cost grid, many paths are symmetric — going right-then-up is the same cost as up-then-right — and JPS skips all but one representative. It can be an order of magnitude faster than plain A* on open maps.
Comparing the search algorithms
Algorithm
Priority
Optimal
Explores
BFS
Insertion order
Yes, unweighted
Everything within distance d
Dijkstra
g(n)
Yes
Uniformly outwards
Greedy best-first
h(n)
No
Straight at the goal
A*
g(n) + h(n)
Yes, if h is admissible
Towards the goal
Greedy best-first search is the instructive contrast: prioritising by h alone is fast and can produce badly suboptimal paths, because it ignores the cost already incurred. A* is exactly the correction — balance what the path has cost against what remains.
Questions people ask
Is A* always better than Dijkstra? When a useful heuristic exists, yes — it explores far fewer nodes for the same answer. Without one, it is Dijkstra.
What if my heuristic overestimates? The path found may be suboptimal. That is sometimes an acceptable trade for speed.
Which heuristic for a grid? Manhattan for 4-directional movement, diagonal/Chebyshev for 8-directional, Euclidean for free movement.
Why does it use so much memory? It keeps every discovered node. IDA* trades time for memory when that binds.
Can it handle negative weights? No — like Dijkstra, its correctness assumes non-negative edges.
How do I get the path, not just the cost? Record each node's predecessor when its g value improves, then walk back from the goal.
Recap in one screen
A* prioritises by g + h: cost so far plus an estimate of what remains.
With h = 0 it is Dijkstra; with a good heuristic it explores dramatically fewer nodes.
The heuristic must never overestimate (admissible) or the path may be suboptimal.
Use the tightest cheap estimate matching the movement rules — Manhattan for 4-way grids, not Euclidean.
Memory is the practical limit; IDA*, jump point search and weighted A* are the standard responses.
Run it in Python
The same grid solved twice: once by Dijkstra and once by A* with a Manhattan heuristic. Both find a shortest path; the interesting number is how many cells each one had to expand to do it.
a_star.pyPython 3
# A*: Dijkstra plus an estimate of the distance still to go.
import heapq
GRID = [
"..........#.........",
".####.....#.####....",
".#..#..####....#....",
".#..#..#..........#.",
"....#..#..####..#.#.",
".####..#.....#..#...",
".......#####.#..#.#.",
".#####.......#....#.",
".....#.#######..###.",
"..#........#........",
]
ROWS, COLS = len(GRID), len(GRID[0])
START, GOAL = (0, 0), (ROWS - 1, COLS - 1)
def neighbours(cell):
r, c = cell
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] != "#":
yield (nr, nc)
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def search(heuristic, label):
g = {START: 0} # cost from the start, known
parent = {START: None}
h0 = heuristic(START, GOAL)
heap = [(h0, h0, START)] # (f, h, cell)
seen = set()
expanded = 0
while heap:
_, _, node = heapq.heappop(heap)
if node in seen:
continue
seen.add(node)
expanded += 1
if node == GOAL:
break
for nxt in neighbours(node):
tentative = g[node] + 1 # every step costs 1
if tentative < g.get(nxt, float("inf")):
g[nxt] = tentative
parent[nxt] = node
h = heuristic(nxt, GOAL)
# f = cost so far + estimate of what is left
heapq.heappush(heap, (tentative + h, h, nxt))
path, node = [], GOAL
while node is not None:
path.append(node)
node = parent[node]
print(f"{label:>9}: path length {len(path) - 1}, cells expanded {expanded}")
return set(path)
search(lambda a, b: 0, "Dijkstra") # h = 0 is exactly Dijkstra
path = search(manhattan, "A*")
print()
for r in range(ROWS):
print(" " + "".join("*" if (r, c) in path else GRID[r][c] for c in range(COLS)))
print()
print(f"{sum(row.count('.') for row in GRID)} open cells.")
print("Same path length. A* just wasted less time looking away from the goal.")
Output
How the code works
heapq.heappush(heap, (tentative + h, h, nxt))The one line that separates A* from Dijkstra: the priority is f = g + h, cost already spent plus cost estimated to remain, instead of g alone.
(f, h, cell)The second element breaks ties. On a grid where every step costs 1 an enormous number of cells share an f value, and preferring the one nearest the goal is what turns a fan into a beeline. It changes nothing about correctness and most of the measured saving here comes from it.
search(lambda a, b: 0, "Dijkstra")With h = 0 the formula collapses to f = g, so the identical function is Dijkstra. That is the cleanest way to see that A* is a generalisation, not a different algorithm.
def manhattan(a, b):Steps are up/down/left/right and each costs 1, so the Manhattan distance can never overestimate what remains. That property — admissibility — is what keeps the answer optimal.
if tentative < g.get(nxt, float("inf")):Compares on g, never on f. The heuristic decides what to look at next; it must not be allowed to decide what the route actually cost.
expandedThe number that matters. Both runs return a shortest path of the same length, and A* gets there having opened far fewer cells — on a game map or a road network that is the entire point.
Change one thing
Multiply the heuristic by 5. It is now inadmissible: expansions drop further, and the path it returns can be longer than the shortest one.
Swap Manhattan for Euclidean (math.hypot). Still admissible on this grid, but weaker, so more cells get expanded.
Wall the goal off completely. Both searches drain the heap and the reconstructed path is nonsense — a real implementation has to check that the goal was actually reached.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Setting the heuristic to zero turns A* into:
f = g + h collapses to f = g, which is Dijkstra's priority exactly. The program runs the identical function both ways to show it.
An admissible heuristic is one that:
Overestimating lets A* commit to a route before a cheaper one is examined, so the path it returns can be longer than the shortest.
Both searches in the program return a path of the same length. What differs?
136 cells against 90 on this grid. A* is not more correct - it is the same answer reached without looking away from the goal.
Cheat sheet
A* Pathfinding Algorithm
Dijkstra’s algorithm expands outward from the source in rings of equal cost. If the goal is due east, it still explores just as far north, south and west before reaching it. On a large map that is enormous wasted effort — the algorithm has no idea where it is going.
A Formal Basis for the Heuristic Determination of Minimum Cost PathsHart, Nilsson & Raphael, IEEE Transactions on SSC 1968
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.