RoboticsBuild a Robot Brain · Week 4 · Lesson 6

Finding the way: BFS and A*

Robo-Helper knows where it is and where the bin is. Now it needs a route that doesn't go through walls, and the shortest one. You'll build breadth-first search, which explores like a ripple on a pond, then A*, which aims the ripple at the goal.

Time2–4 hours, plus the challenge
You'll needPython 3, Lesson 1 finished, squared paper and a pencil
New wordssearch, queue, frontier, breadth-first search (BFS), heuristic, A*, priority queue
Project pieceRoute planning

Start here

To find the shortest route, explore every square 1 step away, then every square 2 steps away, and so on, remembering where you came from. A* does the same but tries the squares that look closer to the goal first.

The problem

Robo-Helper is in the top-left corner of the room at (1, 1). Someone says "put this in the bin". The bin is at (7, 6), and there are walls in between. The robot can step north, south, east or west, one square at a time. Which steps, in which order? It needs a plan before it moves, and the plan should be as short as possible, because every step costs battery.

The idea in one picture

Drop a stone in a pond. The ripple spreads out in rings: everything 1 metre away gets wet at the same moment, then everything 2 metres away. The first ring to touch the goal tells you its distance, and the ripple went around obstacles by itself. That's breadth-first search. A* is like tilting the pond toward the goal so the water runs mostly that way.

Words to know

Search
Systematically trying possibilities until you find one that works.
Queue
A waiting line: first in, first out, like at a shop.
Frontier
The squares we've found but haven't explored from yet: the edge of the ripple.
BFS (breadth-first search)
Explore all squares at distance 1, then 2, then 3… using a queue. It always finds a shortest route.
Heuristic
A quick guess. Here: the Manhattan distance to the goal, ignoring walls.
A* ("A-star")
Search that always explores the square with the smallest "steps so far + guess of steps left".
Priority queue
A waiting line where the smallest number always goes first, like a hospital A&E where the most urgent case is seen next.

The rest is the full lesson: the problem in detail, both algorithms built step by step on the real room, a demo that shows which squares each one explores, the homework, and a challenge in your own home.

1. The problem

Here's the room from world.py. # is wall, . is floor, R is the robot, B is the bin:

  x: 0123456789
y=0  ##########
y=1  #R.......#
y=2  #..##....#
y=3  #..#.....#
y=4  #....##..#
y=5  #........#
y=6  #.#....B.#
y=7  ##########

The obvious approach is "always step toward the goal". It works in an empty room. But try it on this small map, where a wall sits between S and the goal G:

#######
#S.#..#        Greedy: only take steps that get closer to G.
#..#.G#        From S (1,1): east to (2,1), south to (2,2).
#..#..#        At (2,2): east is a wall. North, south, west all
#.....#        go FURTHER from G. Stuck, forever.
#######

The real route goes down and around, which means moving away from the goal for a while. Greedy can't do that. We need a method that is guaranteed to find the shortest route whenever one exists.

2. First principles

Step 1: neighbours

From any square, the possible next squares are its 4 neighbours (north, south, east, west) that aren't walls. Using Lesson 1's move: from (1, 1), north is (1, 0), a wall. South is (1, 2), free. East is (2, 1), free. West is (0, 1), a wall. So neighbors(ROOM, (1, 1)) is [(1, 2), (2, 1)], in the order N, S, E, W. The order matters: it decides which of several equally short routes we find.

Step 2: rings (breadth-first search)

Write 0 on the start. Write 1 on its free neighbours. Write 2 on their unnumbered neighbours. Keep going. This is the whole room, numbered:

## ## ## ## ## ## ## ## ## ##
##  0  1  2  3  4  5  6  7 ##
##  1  2 ## ##  5  6  7  8 ##
##  2  3 ##  7  6  7  8  9 ##
##  3  4  5  6 ## ##  9 10 ##
##  4  5  6  7  8  9 10 11 ##
##  5 ##  7  8  9 10 11 12 ##
## ## ## ## ## ## ## ## ## ##

The bin at (7, 6) got the number 11. So the shortest route is 11 steps. Look at (4, 3): it says 7, even though it's only 3 squares right of the start, because the ripple had to go around the wall.

To do the numbering in code, use a queue. Take the square at the front, add its new neighbours to the back. Because squares join the back of the line, all the 1s are handled before any 2, all the 2s before any 3. Here are the first three turns:

queue: [(1,1)]
take (1,1) → neighbours (1,2), (2,1) are new     queue: [(1,2), (2,1)]
take (1,2) → (1,1) seen; (1,3), (2,2) are new    queue: [(2,1), (1,3), (2,2)]
take (2,1) → (2,2) seen; (3,1) is new            queue: [(1,3), (2,2), (3,1)]

Step 3: remember where you came from

The numbers tell you the distance but not the route. So every time a square is discovered, write down which square discovered it, in a dictionary came_from. For example came_from[(1, 2)] = (1, 1). The start gets None. When you reach the goal, follow came_from backwards to the start, then reverse the list:

(7,6) ← (6,6) ← (5,6) ← (4,6) ← (3,6) ← (3,5) ← (2,5) ← (1,5) ← (1,4) ← (1,3) ← (1,2) ← (1,1)

Twelve squares, eleven steps. As commands: SSSSEESEEEE. The same came_from dictionary also works as the "already seen" list: if a square is in it, don't add it again.

Predict first: the room has 42 free squares (including the bin). How many does BFS take off the queue before it reaches the bin?

40. The bin is one of the farthest squares from the start. Only (8, 5), also 11 steps away, and (8, 6), 12 steps away, are never taken off the queue. BFS doesn't know where the bin is; it just explores everything closer first. That's thorough, but wasteful when the goal is in an obvious direction.

Step 4: aim the ripple (A*)

BFS explores in every direction equally, even away from the goal. Let's give it a hint: the Manhattan distance from Lesson 1, |x1 − x2| + |y1 − y2|. It ignores walls, so it's never more than the true number of steps left. It's an optimistic guess.

For every square we track g = steps taken so far, and h = the Manhattan guess of steps left. Then:

f = g + h      "the best this route could possibly be, if it goes through here"

A* always explores the square with the smallest f next. To find the smallest quickly, it uses a priority queue (Python's heapq). Worked example from the start, with the bin at (7, 6):

start (1,1):  g = 0, h = |1−7| + |1−6| = 6 + 5 = 11, f = 11
  (1,2):      g = 1, h = 6 + 4 = 10,               f = 11
  (2,1):      g = 1, h = 5 + 5 = 10,               f = 11
  (4,3) later: reached in g = 7, h = 3 + 3 = 6,    f = 13   ← worse than 11, try it last

Any square where moving there means heading away from the bin gets a bigger f, so A* puts it off. Because h never overestimates, A* still always finds a shortest route. (If the guess were sometimes too big, A* could skip the real best route.)

One more detail: the same square can enter the priority queue twice, with different g. When you take one out and its g is bigger than the best known cost for that square, it's an out-of-date entry. Skip it, and don't count it.

Predict first: BFS took 40 squares off the queue. How many does A* take, for the same 11-step route?

35, a saving of only 5. Surprised? The robot is in one corner and the bin is in the opposite one, so almost every square is on some 11-step route (any mix of south and east moves). A* skips just (8, 1), (8, 2), (8, 3), (8, 4) and (4, 3). Start the robot at (4, 1) instead, and BFS takes 35 squares while A* takes only 13. A* helps most when the goal is in a clear direction and lots of the map is behind you.

3. Play with it

Interactive: BFS vs A* on the real room

The room from world.py. Press a search and watch which squares it takes off the queue, numbered in order. Shaded squares are still waiting in the frontier. The final route is drawn as a line. Click a floor square to drop a box there (a surprise obstacle), or switch the click mode to move the robot.

Click to:

Algorithm
–
Squares expanded
–
Route length
–
Commands
–

Things to try: run BFS, then A*, from the start corner (40 vs 35). Move the robot to (4, 1) and compare again. Drop a box at (1, 5) and watch both find a different 11-step route. Box the robot in completely: both should report no route.

4. Homework

Open project/homework/lesson06_paths.py. It imports move and manhattan from your Lesson 1 file, so finish that first. Write these four, in order:

4.1 neighbors(room, pos, blocked=())

Return the free squares one step N, S, E, W of pos, in that order, skipping any in blocked. Example: neighbors(ROOM, (1, 1)) → [(1, 2), (2, 1)]; with blocked={(2, 1)} → [(1, 2)].

Hint 1

You already have move(pos, direction) from Lesson 1 and is_free(room, pos) from world.py.

Hint 2

A string is a sequence: for d in "NSEW": loops over the four directions in the right order.

Hint 3

Make an empty list. For each direction d in "NSEW": p = move(pos, d); if p is free and p not in blocked, append it. Return the list.

4.2 bfs_path(room, start, goal, blocked=())

Breadth-first search with a deque and a came_from dictionary. Return the list of squares from start to goal (both included), or None if the goal can't be reached. Example: from ROBOT_START to the bin, the list has 12 squares (11 steps).

Hint 1

deque([start]) makes a queue holding the start. queue.popleft() takes from the front, queue.append(x) adds to the back. Set came_from = {start: None}.

Hint 2

Loop while queue:. Take the front square. If it's the goal, build the path. Otherwise, for each neighbour not yet in came_from, record where it came from and add it to the queue. If the loop ends without finding the goal, return None.

Hint 3

To build the path: start with an empty list and cur = goal. While cur is not None: append cur, then cur = came_from[cur]. That list runs goal → start, so return it reversed (path[::-1]).

4.3 astar_path(room, start, goal, blocked=())

Like BFS, but use a priority queue of (f, g, square) tuples with heapq, and keep a cost dictionary of the best g found for each square. Return (path, expanded), where expanded counts the squares you took off the queue (not counting out-of-date ones). Example: from the start to the bin, the path is 11 steps and expanded is 35.

Hint 1

heapq.heappush(frontier, (f, g, square)) adds; heapq.heappop(frontier) removes the tuple with the smallest f (ties broken by g, then by the square). Start the frontier as [(manhattan(start, goal), 0, start)] and cost = {start: 0}.

Hint 2

After popping (_, g, cur): if g > cost[cur], skip it with continue. Otherwise add 1 to expanded, check for the goal, and look at neighbours.

Hint 3

For each neighbour nxt: new_g = g + 1. If new_g is smaller than cost.get(nxt, infinity): set cost[nxt] = new_g, came_from[nxt] = cur, and push (new_g + manhattan(nxt, goal), new_g, nxt). If the frontier runs out, return (None, expanded).

4.4 path_to_commands(path)

Turn a list of squares into a string of letters. Example: [(1, 1), (2, 1), (2, 2), (1, 2)] → "ESW".

Hint 1

Look at each pair of neighbouring squares in the path. zip(path, path[1:]) gives you (a, b) pairs.

Hint 2

The change from a to b is (b[0] − a[0], b[1] − a[1]), for example (1, 0). Lesson 1's DIRECTIONS maps letters to changes. You need the reverse.

Hint 3

Build a reversed dictionary {change: letter} from DIRECTIONS. For each pair, look up the change and collect the letter. Join the letters into one string.

Run it

cd homework
python3 lesson06_paths.py

What you should see (real output from the reference solution; * marks the route, r b g are the blocks):

##########
#Rr......#
#*.##....#
#*.#..b..#
#*...##..#
#g**.....#
#.#****B.#
##########
BFS steps: 11 | commands: SSSSEESEEEE
A* steps: 11 | squares expanded: 35

The route passes over the green block at (1, 5), which is drawn on top. Blocks don't block the path in this lesson; surprise obstacles do, through blocked.

Check it

cd ..
python3 check.py 6

Hints you might see:

  ✗ neighbors: neighbors of (1, 1) are (1, 2) then (2, 1), checking N, S, E, W
  ✗ bfs unreachable: a boxed-in robot should get None

5/5 passed 🎉 lesson complete! means you're done.

Stretch

5. Real-world challenge: route-plan your home

  1. Draw a map. On squared paper, draw the floor of two or three rooms of your home, one square ≈ one big step (about 50 cm). Shade furniture and walls. Leave doorways open.
  2. Pick a start and a goal, e.g. your bed and the fridge.
  3. Run BFS by hand. Write 0 on the start, 1 on its free neighbours, 2 on theirs… in pencil, until you number the goal. Count how many squares you numbered.
  4. Read the route backwards. From the goal, step to any neighbour with a number one smaller, until you reach 0. Mark the route.
  5. Run A* on a fresh copy. For each square you explore, write g + h. Always continue from the smallest. Count squares again. Which method numbered fewer?
  6. Walk it. Walk the planned route counting your steps. Does it match the number on the goal? Then put a bag in the middle of the route (a surprise obstacle) and replan from where you're standing.

What to record: your map, the BFS and A* square counts, the planned and walked step counts. What it teaches: BFS really is a ripple, the heuristic really does save work, and real routes need replanning when the world surprises you, which is exactly what Robo-Helper does in Lesson 11.

6. Your Robo-Helper so far

Robo-Helper can now plan routes. Given where it is, where it wants to go, and which squares are blocked, astar_path gives it the shortest route, and path_to_commands turns that into moves like the ones you wrote in Lesson 1.

7. Common mistakes

8. Check yourself

Why does BFS always find a shortest route?

It handles all squares at distance 1 before any at distance 2, and so on. So the first time it reaches the goal, it's through the smallest possible number of steps.

Predict: what does bfs_path(ROOM, (1, 1), (1, 1)) return?

[(1, 1)]. The first square taken off the queue is already the goal, and the path is just the start: zero steps.

What does f = g + h mean in plain words?

"Steps I've already taken to get here, plus an optimistic guess of the steps left." It's the best total this route could possibly have.

Why must the heuristic never overestimate?

If it overestimated, A* might put off the square that's actually on the best route because it looked too expensive, and finish with a longer route. Manhattan distance can't overestimate on a grid where you only move N/S/E/W.

Predict: path_to_commands([(3, 3), (3, 2), (2, 2)])?

"NW". y went from 3 to 2 (up, so N), then x went from 3 to 2 (W).

9. Go deeper (optional)