Skip to main content

Lesson 5-2 · Finding the Path

Module 5 · Pathfinding Around Obstacles

Lesson 5-2 · Finding the Path

55–60 minNo codingHand method to computer method
👩‍🏫

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

In Lesson 5-1 you labeled every intersection with its distance to the destination. That tells you how far the start is, but not the path, and the robot needs a path: a list of intersections to drive to, like the one the Manhattan planner hands it. So this lesson answers two questions. What's the path? And how would we write a compute_bfs_path() function that finds it? The lesson ends with a review of the whole algorithm in plain words, which is what you'll turn into Python in Lesson 5-5.

Learning Objectives

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

  • Walk downhill from the start to find a shortest path, and explain why the path leaves the start out
  • Explain why the wave starts at the destination
  • Explain why a computer takes intersections oldest-first, and why the numbers are all it needs
  • Carry out the algorithm exactly as a computer would, by hand, including on a grid with no path

Discuss · Where's the path?​

Start from the grid you numbered at the end of Lesson 5-1: the wall at (1,0) and (1,1), the destination D at (3,0) numbered 0, and the start S at (0,0), which got a 7.

  1. You're standing on S, a 7. Which way do you go first?
  2. Keep going. How do you choose each step, and when do you stop?
  3. Somewhere you'll find two neighbors with the same number. Which one do you pick?
  4. Why did we start the wave at D, and not at S?

Walking downhill​

Each step of the walk is an intersection the robot drives to. Written down in order, they are the path. One answer for the wall grid is

[(0, 1), (0, 2), (1, 2), (2, 2), (3, 2), (3, 1), (3, 0)]

The start is left out because the robot is already on it, as in Module 4's compute_manhattan_path, so len(path) is the number of steps: 7. A classmate who picked differently at a tie might have [..., (2, 2), (2, 1), (2, 0), (3, 0)]: also 7 steps, also right. In Lesson 5-6 you'll test the planner by checking what must be true of any correct answer, not by comparing against one list.

Knowledge Check

Walking downhill, you are on an intersection numbered 4. Its open neighbors are numbered 3, 3 and 5. Where can you step?

Discuss · Teaching it to a computer​

You numbered the grid with your eyes: you looked at the whole board and found "all the 2s" at once. A computer can't do that. It sees one intersection and its open neighbors, the same limit your own rule had in Lesson 5-1.

  1. A computer looks around one intersection at a time. In what order should it take them, so that every 1 is looked around before any 2?
  2. How can it remember that order? What does it write down, and where does each newly numbered intersection go?
  3. When is the wave finished?
  4. To walk downhill, what does the computer need to know about each intersection? Does it need anything else?

Activity · Trace it the computer's way​

Now do exactly what the computer will do. Use a 3×3 grid with the center, (1,1), blocked. The start is (0,0), the destination (2,2). Check neighbors in the order the code will use: left, right, down, up.

Each step: take the intersection at the front of the to-visit list. Every open neighbor that doesn't have a number yet gets one more than this one's number, and goes on the end of the list. Stop when the list is empty. Copy the table and fill it in; the first two rows are done for you.

StepTake off the frontNewly numberedTo-visit afterward
start—(2,2): 0(2,2)
1(2,2)(1,2): 1, (2,1): 1(1,2), (2,1)
2
3
4
5
6
7
8

Then walk downhill from (0,0) and write the path. When two neighbors tie, take the first one in the order left, right, down, up.

Here is the same trace, run one step at a time, and then the walk. Press Step to see what the computer does next and why.

A step-by-step animation of breadth-first search on the 3 by 3 grid with the center blocked, from S at (0, 0) to D at (2, 2), with the numbers written from D and a sentence for each step. D gets 0 and goes on the to-visit list. Each later step takes the oldest intersection from the front of the list; every open neighbor without a number gets the next number and a place at the back of the list. (1, 2) and (2, 1) get 1; (0, 2) and (2, 0) get 2; (0, 1) and (1, 0) get 3; S gets 4. When the list is empty, the walk downhill from S goes to (1, 0), (2, 0), (2, 1) and D, so the path is [(1, 0), (2, 0), (2, 1), (2, 2)]. The last step explains why it is the shortest: every 1 was written before any 2 and every 2 before any 3, so S's 4 is the fewest steps.
The computer's way: take from the front, add to the back, until the list is empty; then walk downhill from S.
Knowledge Check

Why does the computer take intersections from the FRONT of the to-visit list?

Review: the algorithm​

Here is breadth-first search all in one place, the way you would explain it if someone asked you how it works.

Number the grid from the destination. Write 0 on the destination and put it on a to-visit list. Then, until the list is empty: take the intersection at the front of the list, the one that has waited longest, and look at each of its open neighbors. A neighbor that doesn't have a number yet gets one more than this intersection's number, and joins the end of the list. A neighbor that already has a number is left alone. When the list is empty, every intersection the wave could reach has its number: its steps to the destination.

Because new intersections join the end and you always take from the front, everything 1 step from the destination is numbered before anything 2 steps away. That's the wave from Lesson 5-1, moving out one step at a time.

Walk downhill from the start. If the start never got a number, the wave never reached it, and there is no path. Otherwise, stand on the start and, until you're on the destination, step to an open neighbor whose number is one less, writing down each intersection you step onto. Leave the start off; the robot is already there. The intersections you wrote down, in order, are the path the robot drives.

That's all it needs: one number per intersection. And while it numbers the grid it never looks at where the start is, which is why walls in the way are no problem.

Knowledge Check

What in the algorithm makes sure no intersection is ever numbered twice?

Knowledge Check

What makes sure everything 1 step from the destination is numbered before anything 2 steps away?

Activity · Be the computer​

Work in pairs. One of you is the computer: you may look only at the intersection you're working on and its open neighbors, and you keep the to-visit list and the numbers on paper. The other reads the review above aloud, one instruction at a time, and checks that the computer does exactly that and nothing more.

Use a 3×3 grid with the whole middle column blocked: (1,0), (1,1) and (1,2). The start is (0,0), the destination (2,0).

  1. What ends the numbering, and which intersections got numbers?
  2. Did the start get a number? What does that mean?
  3. Swap jobs and run it once more, this time with only (1,1) blocked. What path do you get?

Check your paper against the computer​

Nothing goes into robot.py yet. Next lesson works out what a program has to keep track of to follow the algorithm, and by Lesson 5-5 your own file draws the grid below. For now your teacher has a demonstration program that runs the 3×3-with-(1,1)-blocked trace step by step, printing each intersection as it's numbered and the to-visit list after every step, then the walk and the grid of numbers:

2 | 2 1 0
1 | 3 X 1
0 | 4 3 2
----------
0 1 2

If your trace matches, you ran the algorithm the way the computer does.

Real-world connections​

Robotics

Wavefront planners

Many robots plan exactly this way: spread a wave of numbers out from the goal, then drive downhill from wherever they are.

Graphics

Paint-bucket fill

The fill tool in a paint program spreads out from where you click with a to-visit list, exactly like the wave from Lesson 5-1.

Puzzles

Maze solvers

A maze solver floods the maze from the exit, then walks downhill from the entrance.

Wrap-up​

  • How do you get the path from the numbers? (From the start, keep stepping to a neighbor one less until you reach 0.)
  • Why does the wave start at the destination? (So the walk starts where the robot is and the path comes out in driving order.)
  • Why does the computer take the oldest intersection first? (So the wave front moves out one step at a time.)
  • What happens when the start is walled off? (The list empties without reaching it; there is no path.)

Resources​