Skip to main content

Lesson 5-1 · Finding a Way Around

Module 5 · Pathfinding Around Obstacles

Lesson 5-1 · Finding a Way Around

50–55 minNo codingThe idea first
👩‍🏫

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

Your Manhattan robot has no way around a blocked intersection. Today you find a way around one by eye, then work out, as a class, a method that never guesses. It's called breadth-first search. No code today, just paper.

Learning Objectives

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

  • Explain why the Manhattan algorithm can't handle a blocked intersection
  • Explain why "look at the grid and guess" isn't a method a computer can use
  • Number every intersection with its distance to the destination, one step further out at a time, around blocked intersections
  • Explain why the number on the start is the shortest path length

Why Manhattan isn't enough​

When your usual route to school is closed, your GPS finds a detour. The robot needs to do the same. The Manhattan algorithm from Module 4 knows one strategy, across first, then up or down. It has no concept of an obstacle, so it drives right into a blocked intersection.

A maps app solves the same puzzle: a closed road is blocked, and heavy traffic makes some streets slower. This module and the next build the ideas those apps use:

  • This module, breadth-first search, finds a route around blocked intersections.
  • Module 6, Dijkstra's algorithm, finds the fastest route when some streets are slow. Real apps use faster descendants of it (A* is the best known), but the core idea is the one you'll write.
A drawing of a smartphone running a generic maps app. The map shows a grid of city streets, a park, a river and a highway. A blue route runs from the blue dot of your location to a red pin at school. One street has a road-closed barrier, labeled as an obstacle, Module 5; another is colored red for heavy traffic, labeled as a slow street, Module 6. The blue route turns along the streets to go around both. A card at the bottom reads 14 min, fastest route, avoids a closed road, with a Start button.
A maps app solving this module's problem and the next one's: go around the closed road, and avoid the slow street.
Knowledge Check

Why can't the Manhattan algorithm route around a blocked intersection?

Activity · Finding a path around​

On a 3×3 grid, block (1,0) and find the shortest path from (0,0) to (2,0). A blocked intersection is out of play: the robot can't stop on it or drive through it.

A 3 by 3 grid with (1, 0) blocked and its lines removed. S is (0, 0) and D is (2, 0). A red dashed arrow shows Manhattan trying to go straight across to the right through (1, 0), which is blocked.
Straight across is closed. Find the way around before you open the answer.

Manhattan's straight line goes through (1,0), so it fails. Trace a way around with your finger and count the steps.

Without the obstacle the path is 2 steps: the steps across plus the steps up or down. That count is the Manhattan distance. Obstacles make paths longer, so the Manhattan distance is only a lower bound.

Knowledge Check

With (1,0) blocked, the shortest path from (0,0) to (2,0) is 4 steps, but the Manhattan distance is 2. What does that tell you?

Activity · Explain your method to a computer​

You found that path by looking at the whole grid. A computer can't: it only sees one intersection and which of its neighbors are open. Write your rule, in numbered steps, for someone who can only see that much. Your rule must get them to the destination by a shortest path, every time, on any grid.

Give it two minutes, then test your rule on this one:

A 4 by 4 grid. S is the bottom-left intersection, (0, 0); D is (3, 0), straight across the bottom row, y = 0. Intersections (1, 0) and (1, 1) are blocked and crossed out, with their lines removed.
Your rule can only look at one intersection and its open neighbors at a time.

Start at S (0,0), destination D (3,0), straight across the bottom row, with a wall at (1,0) and (1,1).

Discuss · How far away is everything?​

Draw a 4×4 grid. Mark the start, S, in the bottom-left corner, (0,0), and the destination, D, in the far corner, (3,3). No obstacles yet. This time, work from the destination. Answer each question before you go on to the next.

  1. On our grid, what does "shortest" mean?
  2. Forget S for a moment. Which intersections are exactly 1 step from D? Write a 1 on each.
  3. Which are exactly 2 steps from D? Write a 2 on each. How did you find them?
  4. Keep going until S gets a number. Could there be a shorter way from S to D than S's number says?
  5. Now put back the wall from the last activity, (1,0) and (1,1) blocked, with D at (3,0) and S at (0,0), and number the grid again from D. Do you need a new rule for the blocked intersections?

What you found: a wave​

Here is the method the class just worked out:

  1. Write 0 on the destination.
  2. Every intersection one step away gets a 1.
  3. Every intersection one step from a 1 that doesn't have a number yet gets a 2.
  4. Keep going, finishing every intersection at one distance before you start the next, until the start has a number.
Left: a 3 by 3 grid with the destination D numbered 0 at the top-right, its two neighbors 1, the next two 2, the next two 3, and the start S at the bottom-left 4; the center intersection is crossed out with no number. Right: the same numbers, with the walk from S highlighted in red: from 4 right to 3, to 2, up to 1, to 0 at D, each step to a neighbor one less.
The numbers spread out from the destination like a wave, around a blocked intersection. Each number is the steps to D. The red walk on the right is next lesson's idea.

Think of dropping a stone in a pond, right on the destination. A wave spreads out from that one point, the same distance in every direction, and flows around anything in its way, the way the numbers flow around a blocked intersection. The wave front, the intersections just numbered, moves out one step at a time, so everything closer is reached first and each number is the shortest distance to the destination. That's why this search is called breadth-first (it goes wide before it goes deep), and on a grid a wavefront algorithm. It never looks at where the start is, so a wall that forces you away from the destination is no problem.

Knowledge Check

An intersection already has a 2 on it. Later, while looking around an intersection with a 3, you find it's a neighbor. What do you write on it?

Knowledge Check

The start has just been given a 5. Could a shorter way from the start to the destination still turn up?

The wave on a bigger grid​

A 3×3 is small enough to trace by hand, but too small to show the shape of breadth-first search. Here is the same rule on an 8 by 6 grid with a wall across the middle.

An animation of breadth-first search on a grid of 8 by 6 intersections with a wall of four blocked intersections at x = 3, from y = 1 to y = 4. S is (0, 4) and D is (7, 4), on the other side of the wall. The wave starts at D: each intersection lights up with its number of steps to D when the wave first reaches it, so the numbers spread out from D, flow around both ends of the wall, and fill the grid. Then the path from S is drawn in red, always stepping to a neighbor one less: up, along the top past the wall, and down to D, 9 steps.
Same rule as your grid: every intersection one step from D is numbered before any two steps away. Press Step to move the wave out one step at a time, or Play to watch it spread and bend around the wall.

The wave spreads evenly in every direction, even away from S: it never looks at where the start is. Here it fills the whole grid. The red line at the end is next lesson's idea.

Real-world connections​

Maps

GPS routing

Rerouting around a closed road is this problem. Route planners spread a wave of distances through the street map, just like your numbers.

Social

Degrees of separation

"Friends of friends" are the people two steps out in a breadth-first search over a friend network.

Games

Enemy AI

Game characters find their way around walls with graph search, many times a second.

Wrap-up​

  • Why can't Manhattan handle a blocked intersection? (One fixed route, no idea of obstacles.)
  • What does the number on an intersection mean? (Its distance to the destination, in steps.)
  • Do blocked intersections need a special rule? (No: they never get a number, and the wave flows around them.)
  • Why is the number on the start the shortest distance? (Everything closer to the destination was numbered first.)

Resources​