Skip to main content

Lesson 5-5 · Implementing compute_bfs_path()

Module 5 · Pathfinding Around Obstacles

Lesson 5-5 · Implementing compute_bfs_path()

50–60 minThe algorithm in codeBuild in two stagesSlides (PowerPoint)
👩‍🏫

Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right) to preview the student view.

This is the heart of Module 5: the algorithm you reviewed at the end of Lesson 5-2 becomes about twenty lines of Python, each one a step you've done with a pencil. It comes in two functions, one for each part of the review: bfs_distances() numbers the grid from the destination, and compute_bfs_path() walks downhill from the start. Build and test them in that order; every test prints, and the robot stays on the desk.

Learning Objectives

By the end of this lesson you will be able to:

  • Match each line of bfs_distances() and compute_bfs_path() to a step of the paper method
  • Explain why to_visit.pop(0) (oldest first) matters, and what pop() would do instead
  • Explain why if neighbor not in distance is the whole "numbered once" rule
  • Write the walk downhill so the path leaves the start out, and return [] when the start can't be reached

This lesson's skeleton​

In the BFS PLANNER section, replace the placeholder compute_bfs_path() with these outlines: the algorithm from Lesson 5-2's review, one numbered step per comment. print_grid(), at the bottom, is given.

def bfs_distances(destination):
"""Steps from every reachable intersection to
destination, as a dictionary: the wave of numbers."""
# Program only, not a step of the algorithm: build the
# graph from BLOCKED; return {} if destination is not in it.
#
# Number the grid from the destination (Lesson 5-2):
# 1. Write 0 on the destination.
# 2. Put the destination on the to-visit list.
# 3. While the to-visit list is not empty:
# 4. Take the oldest one off the front. Call it current.
# 5. For each open neighbor of current:
# 6. If that neighbor has no number yet:
# 7. Give it one more than current's number.
# 8. Add it to the end of the to-visit list.
# 9. Return the numbers.
pass

def compute_bfs_path(start, destination):
"""Shortest path from start to destination around
BLOCKED, as the list of intersections to drive to."""
# Program only: build the graph from BLOCKED.
#
# Walk downhill from the start (Lesson 5-2):
# 1. Number the grid: call bfs_distances(destination).
# 2. If the start has no number, there is no path.
# 3. Start with an empty path, standing on the start.
# 4. Until you are standing on the destination:
# 5. Find the open neighbor whose number is one less
# 6. and step onto it.
# 7. Add where you are standing to the path.
# 8. That path is the answer.
pass

def print_grid(rows, cols, blocked, numbers):
"""Draw the grid the way it lies in front of you: the top
line is the far row, y = 0 is the bottom line. Each
intersection shows its entry in numbers, X if it is
blocked, . if it has no entry."""
for i in range(rows):
y = rows - 1 - i
line = " " + str(y) + " | "
for x in range(cols):
if (x, y) in blocked:
cell = "X"
elif (x, y) in numbers:
cell = numbers[(x, y)]
else:
cell = "."
line = line + "{:>3}".format(cell)
print(line)
print(" " + "-" * (3 * cols + 1))
footer = " "
for x in range(cols):
footer = footer + "{:>3}".format(x)
print(footer)

print_grid() is given: it's formatting, not pathfinding, and Module 6 uses it unchanged. It prints the far row first, so the picture lies the way the grid does in front of you. "{:>3}".format(cell) is "this value, right-aligned in three spaces."

Every line is a pencil step​

Under each numbered comment you write the Python that does what the step says, usually one line. Use the names from Lesson 5-3: distance for the numbers, a dictionary, and to_visit for the list. Step 1 of bfs_distances() makes distance with one entry: the destination, numbered 0.

Eight lines of code matched to the pencil method from Lessons 5-1 and 5-2. distance = {destination: 0} writes 0 on the destination. to_visit = [destination] is the to-visit list beside the grid. current = to_visit.pop(0) takes the oldest one, from the front. if neighbor not in distance means it has no number yet, so it is numbered once. distance[neighbor] = distance[current] + 1 gives it one more than current. to_visit.append(neighbor) adds it to the end of the list. while current != destination walks until it reaches the destination, and distance[neighbor] == distance[current] - 1 finds a neighbor one less to step onto.
Nothing in the code is new: each line is a step you already did with a pencil.

An intersection gets an entry in distance only when the wave reaches it, so "is a key in distance" means "has a number." That's why if neighbor not in distance is the whole numbered-once rule.

The list is a queue: append() adds to the end and pop(0) takes from the front (index 0), so the wave front moves out one step at a time.

Knowledge Check

In bfs_distances(), what does `if neighbor not in distance:` mean in pencil terms?

Activity · Build it in two stages​

Build the two functions in order, running a test after each. Check every printed grid, path and step count against your traces from Lessons 5-1 and 5-2.

Step 1 · The numbers​

Write bfs_distances(). Then write test_distances(): clear the blocked list, block (1, 0) and (1, 1), and call

print_grid(ROWS, COLS, BLOCKED, bfs_distances((3, 0)))

Set the run line to it. It should print the wall grid you numbered in Lesson 5-1:

3 | 6 5 4 3
2 | 5 4 3 2
1 | 6 X 2 1
0 | 7 X 1 0
-------------
0 1 2 3

If a number is wrong, the bug is in this function, and you haven't written the walk yet, so there's only one place to look.

Step 2 · The walk downhill​

Write compute_bfs_path(). If the start has no number, the wave never reached it, so there's no path; that one check covers a blocked start, a blocked destination and a wall between them.

Steps 4 to 7 are a loop inside a loop. The outer while keeps walking until you're on the destination. The inner for looks through the neighbors for one with a number one less; when it finds one, it steps onto it and uses break to stop looking. Check that the neighbor has a number before you compare it: neighbor in distance and .... And notice when the start is left out: you add an intersection to the path only after stepping onto it, so the start never goes in, and "already there" comes free: when start == destination, the loop never runs and the path is [].

Knowledge Check

A classmate's walk adds current to the path BEFORE stepping. Their straight-line test, (0,0) to (0,3), prints Steps: 3, but the path is [(0, 0), (0, 1), (0, 2)]. What's wrong?

Run the five paper tests​

Five cases, all grids you traced by hand. Write test_bfs_open() for three open-grid cases: (0, 0) to (3, 3), (0, 0) to (0, 3), and (2, 2) to (2, 2); start it with clear_blocked() so the test means the same whatever ran before it. Then write test_bfs_walls() for the two with walls: add_blocked() the two wall intersections and plan (0, 0) to (3, 0); then block the rest of the column at x = 1 and plan again. Print each path and len(path) next to the step count you expect, and the blocked list before each wall test. Step counts must match; the exact path may differ from yours and still be right.

=== Test 1: no obstacles, (0,0) to (3,3) ===
Path: [(1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]
Steps: 6 (expect 6)

=== Test 2: straight line, (0,0) to (0,3) ===
Path: [(0, 1), (0, 2), (0, 3)]
Steps: 3 (expect 3)

=== Test 3: already there, (2,2) to (2,2) ===
Path: []
Steps: 0 (expect 0)

=== Test 4: wall across the grid, (0,0) to (3,0) ===
Blocked: [(1, 0), (1, 1)]
Path: [(0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0)]
Steps: 7 (expect 7 -- around the wall)

=== Test 5: destination walled off ===
Blocked: [(1, 0), (1, 1), (1, 2), (1, 3)]
Path: []
Steps: 0 (expect 0 -- no way through)

Tests 3 and 5 both return []: one because the start is already the destination, the other because the start never got a number. Next lesson's harness tells them apart.

Activity · Break it on purpose​

Once all five pass, break bfs_distances() two ways. Put each back before the next.

  1. Change pop(0) to pop(). Run Test 4 and count the steps: more. pop() takes the newest intersection, so the wave no longer moves out one step at a time and the numbers stop being shortest distances. The walk downhill trusts the numbers, so it follows them on a longer route. Run test_distances() too and compare the grid with yours.
  2. Delete if neighbor not in distance: (keep the two lines under it, one indent level out). Run Test 1. Every neighbor goes back on the list every time, so the list never empties and the program hangs. Press Ctrl-C. That one line is the numbered-once rule.
Knowledge Check

You change pop(0) to pop() in bfs_distances() and Test 4, the wall test, prints Steps: 9 instead of 7. What changed?

Do this after your functions version works on the robot. It is not graded; it is for when there is time. Once it works, use it from here on.

Wrap-up​

  • Which line is "take the oldest one"? (to_visit.pop(0).) What would pop() do? (Newest first — depth-first, not shortest.)
  • Which line is "numbered once"? (if neighbor not in distance.)
  • Why does the walk add an intersection only after stepping onto it? (So the start is never in the path — Rule 2.)
  • Two cases return []. What are they? (Already there; the start never got a number.)

Resources​