A* pathfinding explained
How A* finds the shortest route: g, h and f = g + h, the priority queue, and why the heuristic must never overestimate. Watch it search a mat with two walls, compare it with Dijkstra, then see a robot drive the route. With A* in Python.
A* (said "A star") finds the shortest route from one place to another on a map, and it usually does it while looking at much less of the map than simpler searches. It moves characters round game levels, plans routes for warehouse robots, and sits inside route planners. On this page a small robot plans a route across a 2 metre mat with two walls in the way, and each demo below is a real program you can change and run.
On the mat, blue squares are cells the search has finished with, yellow squares are the frontier (cells it has found but not yet dealt with), and the red line is the route it chose. The chart counts the cells the search has expanded. Fewer is better, as long as the route is still the shortest.
The idea in one line
f = g + h
- g is the cost so far: the length of the best route found from the start to this cell.
- h is the heuristic: a guess at the cost still to go from this cell to the goal, worked out from where the cell is, without searching.
- f is the guess at the whole trip, start to goal, through this cell.
A* keeps the frontier in a priority queue and always takes out the cell with the smallest f. It works out g for each of that cell's neighbours, and puts any neighbour that is new, or that it has now reached more cheaply, into the queue. Taking a cell out and doing this is called expanding it. When the goal comes out of the queue the search stops, and the route is read backwards from the goal, following which cell each one was reached from.
The mat as a graph
A search works on a graph: points joined by edges, each edge with a cost. Here the mat is cut into a 40 by 40 grid of 5 cm cells. Each cell is a point, joined to its eight neighbours. A straight step costs 5 (centimetres) and a diagonal step costs 5 × √2, about 7.07. The walls are grown by 10 cm and any cell whose centre falls inside them is left out, so a route through the cells that remain keeps the robot's body clear of the walls. That leaves 1,020 cells the robot can reach.
The heuristic is the octile distance: the length of the route to the goal if there were no walls, made of diagonal steps and straight steps. In the code it is max(dx, dy) + 0.414 × min(dx, dy) cells. 0.414 is √2 − 1 rounded down, so the guess stays just under the truth.
A* on the mat
The robot starts at the bottom left and the goal is the green corner at the top right. The first wall blocks the way up the middle and the second blocks the way along the top, so every route has to go up, over the first wall, down between the two, under the second and up again.
The program
from bugbot import *
import heapq
import math
connect()
# change W and press Run
# 1: A* 0: Dijkstra above 1: guesses high
W = 1
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
GOAL = (34, 34) # the green corner
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def h(c):
# guess of the cost left: the octile distance
dx = abs(c[0] - GOAL[0])
dy = abs(c[1] - GOAL[1])
d = max(dx, dy) + 0.414 * min(dx, dy)
return W * CELL * d
def show():
seen = [cm(c) for c in done]
edge = [cm(c) for c in g if c not in done]
draw("visited", seen, "blue", "squares", 5)
draw("frontier", edge, "yellow", "squares", 5)
plot("cells expanded", len(done))
wait(0.1)
g = {START: 0} # best cost so far
came = {START: None} # the cell before
queue = [(h(START), START)]
done = set()
while queue:
f, cur = heapq.heappop(queue)
if cur in done:
continue
done.add(cur)
if cur == GOAL:
break
if len(done) % 20 == 0:
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
cost = g[cur] + CELL * math.hypot(dx, dy)
if cost < g.get(nxt, 1e9):
g[nxt] = cost
came[nxt] = cur
f = cost + h(nxt)
heapq.heappush(queue, (f, nxt))
show()
route = []
c = GOAL
while c:
route.append(cm(c))
c = came[c]
route.reverse()
draw("route", route, "red", "line", 2)
print("cells expanded:", len(done))
print("route length:", round(g[GOAL]), "cm")
A* is only as good as its guess. From the start, the octile distance to the green corner is 198 cm, but the real route is 337 cm, because the walls force a long detour. Every cell in the top left looks promising to the guess, so A* has to use them all up before it tries the way down between the walls.
Turn the guess off and you have Dijkstra
W multiplies the guess. Set it to 0 and h is 0 everywhere, so f is just g and the queue hands out the cell nearest the start. That is Dijkstra's algorithm, line for line.
The program
from bugbot import *
import heapq
import math
connect()
# change W and press Run
# 1: A* 0: Dijkstra above 1: guesses high
W = 0
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
GOAL = (34, 34) # the green corner
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def h(c):
# guess of the cost left: the octile distance
dx = abs(c[0] - GOAL[0])
dy = abs(c[1] - GOAL[1])
d = max(dx, dy) + 0.414 * min(dx, dy)
return W * CELL * d
def show():
seen = [cm(c) for c in done]
edge = [cm(c) for c in g if c not in done]
draw("visited", seen, "blue", "squares", 5)
draw("frontier", edge, "yellow", "squares", 5)
plot("cells expanded", len(done))
wait(0.1)
g = {START: 0} # best cost so far
came = {START: None} # the cell before
queue = [(h(START), START)]
done = set()
while queue:
f, cur = heapq.heappop(queue)
if cur in done:
continue
done.add(cur)
if cur == GOAL:
break
if len(done) % 20 == 0:
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
cost = g[cur] + CELL * math.hypot(dx, dy)
if cost < g.get(nxt, 1e9):
g[nxt] = cost
came[nxt] = cur
f = cost + h(nxt)
heapq.heappush(queue, (f, nxt))
show()
route = []
c = GOAL
while c:
route.append(cm(c))
c = came[c]
route.reverse()
draw("route", route, "red", "line", 2)
print("cells expanded:", len(done))
print("route length:", round(g[GOAL]), "cm")
993 of the 1,020 reachable cells: Dijkstra looked at nearly the whole mat, because the green corner is one of the furthest points from the robot. A* found a route just as short after 662. Both are guaranteed to find the shortest route. A* gets there with less work because it spends it on cells that could lead to the goal.
Where A* saves the most
The saving depends on how good the guess is. Move the goal to the top left, where nothing stands between it and the robot.
The program
from bugbot import *
import heapq
import math
connect()
# change W or GOAL and press Run
# 1: A* 0: Dijkstra above 1: guesses high
W = 1
GOAL = (6, 34) # top left, 172 cm up
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def h(c):
# guess of the cost left: the octile distance
dx = abs(c[0] - GOAL[0])
dy = abs(c[1] - GOAL[1])
d = max(dx, dy) + 0.414 * min(dx, dy)
return W * CELL * d
def show():
seen = [cm(c) for c in done]
edge = [cm(c) for c in g if c not in done]
draw("visited", seen, "blue", "squares", 5)
draw("frontier", edge, "yellow", "squares", 5)
plot("cells expanded", len(done))
wait(0.1)
g = {START: 0} # best cost so far
came = {START: None} # the cell before
queue = [(h(START), START)]
done = set()
while queue:
f, cur = heapq.heappop(queue)
if cur in done:
continue
done.add(cur)
if cur == GOAL:
break
if len(done) % 5 == 0:
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
cost = g[cur] + CELL * math.hypot(dx, dy)
if cost < g.get(nxt, 1e9):
g[nxt] = cost
came[nxt] = cur
f = cost + h(nxt)
heapq.heappush(queue, (f, nxt))
show()
route = []
c = GOAL
while c:
route.append(cm(c))
c = came[c]
route.reverse()
draw("route", route, "red", "line", 2)
print("cells expanded:", len(done))
print("route length:", round(g[GOAL]), "cm")
Here the octile distance is exactly right, so every cell on the route has the same f and A* never looks sideways. The 29 cells it expands are the 29 cells of the route. Dijkstra, with no idea where the goal is, expands 353 cells to find the same 140 cm. On open ground, or a large map where the goal is close, A* does a small fraction of Dijkstra's work.
A guess that is too high
A heuristic that never overestimates the real cost to the goal is called admissible, and with one, A* always finds the shortest route. The octile distance is admissible, because no route round walls can be shorter than the route with no walls.
Now make the guess five times too big.
The program
from bugbot import *
import heapq
import math
connect()
# change W and press Run
# 1: A* 0: Dijkstra above 1: guesses high
W = 5
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
GOAL = (34, 34) # the green corner
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def h(c):
# guess of the cost left: the octile distance
dx = abs(c[0] - GOAL[0])
dy = abs(c[1] - GOAL[1])
d = max(dx, dy) + 0.414 * min(dx, dy)
return W * CELL * d
def show():
seen = [cm(c) for c in done]
edge = [cm(c) for c in g if c not in done]
draw("visited", seen, "blue", "squares", 5)
draw("frontier", edge, "yellow", "squares", 5)
plot("cells expanded", len(done))
wait(0.1)
g = {START: 0} # best cost so far
came = {START: None} # the cell before
queue = [(h(START), START)]
done = set()
while queue:
f, cur = heapq.heappop(queue)
if cur in done:
continue
done.add(cur)
if cur == GOAL:
break
if len(done) % 20 == 0:
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
cost = g[cur] + CELL * math.hypot(dx, dy)
if cost < g.get(nxt, 1e9):
g[nxt] = cost
came[nxt] = cur
f = cost + h(nxt)
heapq.heappush(queue, (f, nxt))
show()
route = []
c = GOAL
while c:
route.append(cm(c))
c = came[c]
route.reverse()
draw("route", route, "red", "line", 2)
print("cells expanded:", len(done))
print("route length:", round(g[GOAL]), "cm")
With the guess inflated, a cell that is nearer the goal looks far better than it is, so the search follows the first way through it finds and stops as soon as it reaches the goal, without checking whether a cheaper way was left in the queue. The route kinks over the first wall where the best one runs straight.
| W | cells expanded | route |
|---|---|---|
| 0 (Dijkstra) | 993 | 337 cm |
| 1 (A*) | 662 | 337 cm |
| 1.5 | 581 | 341 cm |
| 2 | 552 | 346 cm |
| 3 | 358 | 346 cm |
| 5 | 282 | 353 cm |
| 10 | 263 | 373 cm |
The table is from this program, run with each W. Above 1, the work falls and the route gets longer. This is called weighted A*, and it is used on purpose when an answer now matters more than the best answer: with an admissible guess multiplied by W, the route is never more than W times the length of the best one. Some planners run it with a large W first, start moving, then run it again with a smaller one while there is time.
Plan, then drive
A plan is only useful if the robot can follow it. This program plans with A* and then drives the red line. The robot can move sideways as well as forwards, so it never needs to turn: it aims at a point on the route, and moves that point further along once it is within 8 cm, which smooths the grid's corners into curves.
The program
from bugbot import *
import heapq
import math
connect()
# change W and press Run, then watch it drive
# 1: A* 0: Dijkstra above 1: guesses high
W = 1
CELL = 5 # each cell is 5 cm
START = (6, 6) # the robot, at 30, 30 cm
GOAL = (34, 34) # the green corner
WALLS = [(70, 0, 8, 115), (125, 85, 8, 115)]
STEPS = [(1, 0), (-1, 0), (0, 1), (0, -1),
(1, 1), (1, -1), (-1, 1), (-1, -1)]
def cm(c):
# the centre of cell c, in cm on the mat
return (c[0] * CELL + 2.5, c[1] * CELL + 2.5)
def blocked(c):
# walls and mat edge, grown by 10 cm
x, y = cm(c)
if not (10 < x < 190 and 10 < y < 190):
return True
for wx, wy, ww, wh in WALLS:
if (wx - 10 < x < wx + ww + 10 and
wy - 10 < y < wy + wh + 10):
return True
return False
def h(c):
# guess of the cost left: the octile distance
dx = abs(c[0] - GOAL[0])
dy = abs(c[1] - GOAL[1])
d = max(dx, dy) + 0.414 * min(dx, dy)
return W * CELL * d
def show():
seen = [cm(c) for c in done]
edge = [cm(c) for c in g if c not in done]
draw("visited", seen, "blue", "squares", 5)
draw("frontier", edge, "yellow", "squares", 5)
plot("cells expanded", len(done))
wait(0.1)
g = {START: 0} # best cost so far
came = {START: None} # the cell before
queue = [(h(START), START)]
done = set()
while queue:
f, cur = heapq.heappop(queue)
if cur in done:
continue
done.add(cur)
if cur == GOAL:
break
if len(done) % 40 == 0:
show()
for dx, dy in STEPS:
nxt = (cur[0] + dx, cur[1] + dy)
if nxt in done or blocked(nxt):
continue
cost = g[cur] + CELL * math.hypot(dx, dy)
if cost < g.get(nxt, 1e9):
g[nxt] = cost
came[nxt] = cur
f = cost + h(nxt)
heapq.heappush(queue, (f, nxt))
show()
route = []
c = GOAL
while c:
route.append(cm(c))
c = came[c]
route.reverse()
draw("route", route, "red", "line", 2)
print("cells expanded:", len(done))
print("route length:", round(g[GOAL]), "cm")
# drive it: aim at a point on the route and
# move that point on as the robot comes near
i = 0
while True:
px, py = position() # cm from the start
x, y = 30 + px, 30 + py
tx, ty = route[i]
d = math.hypot(tx - x, ty - y)
if d < 8 and i < len(route) - 1:
i += 1
continue
if d < 2:
break
gx, gy = route[-1]
plot("cm from the goal",
math.hypot(gx - x, gy - y))
# a world velocity of up to 14 cm/s
s = min(14, 1 + 2 * d) / d
vx = (tx - x) * s
vy = (ty - y) * s
# turn it into the robot's own frame
a = math.radians(heading())
fwd = vx * math.sin(a) + vy * math.cos(a)
side = vx * math.cos(a) - vy * math.sin(a)
# 100 % is 20 cm/s forward, 15 sideways
turn = (heading() + 180) % 360 - 180
drive(fwd * 5, side * 6.7, -turn)
wait(0.1)
stop()
print("stopped at", round(x), round(y))
position() is the overhead camera in the simulator, so the robot always knows where it is. A real robot has to work that out from its own sensors, which is a separate problem with its own errors. The chart shows the straight-line distance to the goal. It falls from 201 cm to 94 cm, then rises to 111 cm while the robot goes down between the walls, away from the goal, then falls to about 2 cm as it stops.
A* in Python
The demos write A* out in full for the grid. Here is the same search as one function for any graph: you give it a function that lists a point's neighbours with the cost of each step, and a heuristic.
import heapq
def a_star(start, goal, neighbours, h):
# neighbours(n) gives (next, cost) pairs
# h(n) guesses the cost left from n to goal
g = {start: 0}
came = {start: None}
queue = [(h(start), start)]
done = set()
while queue:
f, cur = heapq.heappop(queue)
if cur == goal:
path = []
while cur is not None:
path.append(cur)
cur = came[cur]
return path[::-1], g[goal]
if cur in done:
continue
done.add(cur)
for nxt, cost in neighbours(cur):
new = g[cur] + cost
if new < g.get(nxt, float("inf")):
g[nxt] = new
came[nxt] = cur
heapq.heappush(queue, (new + h(nxt), nxt))
return None, None # no route
grid = ["S...#....",
".##.#.##.",
"...#...#G",
".#...#..."]
def neighbours(cell):
r, c = cell
for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
if grid[nr][nc] != "#":
yield (nr, nc), 1
goal = (2, 8)
def manhattan(cell):
return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])
path, cost = a_star((0, 0), goal, neighbours, manhattan)
print(cost, path)
It prints 14 and the 15 cells of the route, from (0, 0) to (2, 8). heapq keeps the list as a priority queue: heappop always removes the smallest f. A cell can be pushed more than once if a cheaper way to it turns up, and the older, dearer copy is skipped when it comes out, which is what done is for. The grid moves only up, down, left and right, so the heuristic is the Manhattan distance, rows apart plus columns apart.
Questions
How does A* work?
It keeps a priority queue of cells it has found, ordered by f = g + h: the cost to reach the cell plus a guess at the cost still to go. It repeatedly takes out the cell with the smallest f, adds that cell's neighbours with their costs, and stops when the goal comes out. The route is then read backwards from the goal.
What is the difference between A* and Dijkstra?
Dijkstra orders its queue by g alone, so it spreads out evenly from the start. A* adds the heuristic h, so it prefers cells that look closer to the goal, and with h = 0 the two are the same. On the mat on this page both find the same 337 cm route: Dijkstra expands 993 cells, and the heuristic cuts that to 662.
When should you use A* instead of Dijkstra?
Use A* when you want one route to one goal and you can estimate the distance to that goal, such as straight-line distance on a map. Use Dijkstra when you want the distances from one start to every point, or when there is no sensible estimate.
What makes a good heuristic?
It must never overestimate the real cost to the goal (admissible), or the search can return a route that is not the shortest. Within that, the closer it is to the real cost, the fewer cells A* expands. It must also be quick to work out. Straight-line distance, Manhattan distance for four-way grids and octile distance for eight-way grids are the usual choices.
Is A* always the shortest path?
Only if the heuristic is admissible. With an overestimating heuristic, A* can stop at a longer route: on this page, a guess five times too big found a 353 cm route where the best is 337 cm.
What are the open and closed lists in A*?
The open list is the frontier: cells that have been found but not yet expanded, kept in order of f. The closed list holds the cells that have been expanded, whose best route is settled. In the demos the open list is yellow and the closed list is blue.
How is A* different from greedy best-first search?
Greedy best-first search orders the queue by h alone and ignores the cost so far. It is quick but can return a long route. On this mat, weighting h by 1000 so that g barely counts expands 241 cells and returns a 373 cm route, against A*'s 662 cells and 337 cm.
How do you write A* in Python?
Use heapq as the priority queue, holding (f, cell) pairs. Keep a dictionary of the best g for each cell and another of the cell each one was reached from. Pop the smallest f, skip it if it is already done, stop if it is the goal, and otherwise push each neighbour whose g has improved. The function on this page does this in about 25 lines.
Is A* on the A level Computer Science specification?
Yes, in OCR's A level (H446), which lists both Dijkstra's shortest path algorithm and A*. Students trace it on a small graph, showing g, h and f for each vertex, and explain why the heuristic matters. AQA's A level (7517) includes Dijkstra's algorithm only.
Learn it step by step
These lessons build the same ideas one at a time, each with tasks the simulator marks.
- A5.8 A* search Algorithms and complexity, A level
- A5.9 Project: plan the route, then drive it Algorithms and complexity, A level
- U9.2 A grid is a graph Planning, University
- U9.4 A* and the heuristic Planning, University
- U9.7 Project: plan a route and drive it Planning, University