Skip to main content

Lesson 5-4 · The Pathfinding Functions

Module 5 · Pathfinding Around Obstacles

Lesson 5-4 · The Pathfinding Functions

45 minFunction toolkitsTwo rules for plannersSlides (PowerPoint)
👩‍🏫

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

Now the concept becomes code, in stages. GRID GRAPH becomes a toolkit like Module 2's sensor code: a shared blocked list, a function that adds to it, and a rewrite of build_grid_graph() that builds around the list. A new BFS PLANNER section opens with a placeholder compute_bfs_path(), which Lesson 5-5 fills in.

Learning Objectives

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

  • Write add_blocked(intersection) so an intersection is recorded once, even if told twice
  • Rewrite build_grid_graph() as build_graph(rows, cols, blocked): blocked intersections are neither keys nor neighbors
  • State the two planner rules: the position is passed in; the path leaves the start out
  • Explain why the blocked list is shared at the top of the section, and why the graph is rebuilt from it on every call

Where does the robot keep what it has learned?​

Three lessons from now the robot will see an obstacle with its rangefinder while driving, and have to plan around it. Where does it write down that the obstacle is there?

"Pass the blocked list to the function" is half right. The robot learns about obstacles one at a time, while driving, so the list has to last between one path and the next. It goes at the top of the section, where every function can see it, like ROWS and COLS:

BLOCKED = [] # intersections the robot must not drive through

Capitals, like THRESHOLD, because it is a setting. It grows only through one function.

Three sources, a paper test in Lesson 5-6, the rangefinder in Lesson 5-7 and you typing in a list in Lesson 5-8, all call add_blocked(x), which appends to one list, BLOCKED, at the top of the GRID GRAPH section. compute_bfs_path() builds the graph from BLOCKED on every call.
One list, three ways in, one way out: every plan builds its graph from BLOCKED as it stands right now.

Two rules we will never break​

Every planner in this course follows these two rules.

Rule 1 — the planner is told where the robot is. Every planner looks like compute_something_path(start, destination) and never remembers the position. The driving code owns it. A second copy in the planner could disagree, and the planner would plan from the wrong place. One owner.

Rule 2 — the path is the list of intersections to drive to. The start is not in it, so len(path) is the number of steps and "already there" is [].

Module 4's planner already follows both: compute_manhattan_path((0, 0), (0, 2)) returns [(0, 1), (0, 2)], two steps, no start.

Knowledge Check

Why must a planner be TOLD the robot's position instead of remembering it?

This lesson's skeleton​

Two pastes and one rewrite. Paste the first at the end of GRID GRAPH, under your Lesson 5-3 test:

# --- Lesson 5-4: the blocked list ---
# BLOCKED is the one record of where the robot must not go.
# add_blocked() is the one way in: tests, the rangefinder and
# you all use it. build_graph() builds AROUND the list, so a
# blocked intersection is never a key and never a neighbor.
BLOCKED = [] # intersections the robot must not drive through

def add_blocked(intersection):
"""Record intersection in BLOCKED, once, even if told twice."""
pass

def clear_blocked():
"""Empty BLOCKED in place, so a test can start fresh."""
pass

The second opens a new section, because a planner is different work from a graph. Paste it after GRID GRAPH, above RUN. The placeholder body is given; Lesson 5-5 replaces it.

# ===== BFS PLANNER =====
# The second planner. compute_bfs_path(start, destination)
# has the same shape as the MANHATTAN PLANNER's function and
# keeps the same two promises (told the position; the path
# leaves the start out), but it numbers the GRID GRAPH as a
# wave from the destination, so it routes AROUND whatever is in BLOCKED. Pure
# dictionary work: every test here runs with the robot still.

def compute_bfs_path(start, destination):
"""Shortest path from start to destination around
BLOCKED, as the list of intersections to drive to."""
graph = build_graph(ROWS, COLS, BLOCKED) # rebuilt every call
print("compute_bfs_path is not written yet!")
return []

The rewrite of build_grid_graph() is Step 2.

Activity · Build the toolkit​

Step 1 · add_blocked()​

The one way to tell the planner about an obstacle: an if and an append that add the intersection to BLOCKED only if it isn't already there. The robot may see the same wall twice.

Does this need global BLOCKED? In Lesson 2-7, set_threshold() needed global THRESHOLD. The difference is what each function does to the name:

THRESHOLD = new_value # Lesson 2-7: REASSIGNS the name -- needs global
BLOCKED.append(intersection) # today: CHANGES the list -- no global needed

global is only for reassigning a module-level name. append changes the list BLOCKED already names. clear_blocked() empties the list in place, with pop() until len(BLOCKED) is zero, so tests can start fresh. BLOCKED = [] inside it would reassign the name and need global.

Left, BLOCKED.append((1, 1)): the name BLOCKED still points at the same list, which now has one more item, so no global is needed. Right, BLOCKED = [] inside a function: this makes a new local name pointing at a new empty list, gone when the function returns, while the real BLOCKED list is untouched; that is the case that needs global.
append changes the list the name points at. = points a name at something else, and inside a function that name is a new local.

Write both bodies. Step 2 gives you the test.

Knowledge Check

Why does add_blocked() not need `global BLOCKED`, when set_threshold() in Lesson 2-7 needed `global THRESHOLD`?

Step 2 · build_graph() — the graph learns about blocked intersections​

In Lesson 5-3, build_grid_graph() built the open grid. Now it has to leave the blocked intersections out, both halves of blocking a node: not a key, and not anyone's neighbor. In GRID GRAPH, change the def line to

def build_graph(rows, cols, blocked):
"""Return the grid as a dictionary, leaving out every
intersection in blocked: not a key, not anyone's neighbor."""

and make two changes to the body:

  1. If (x, y) is in blocked, skip it. It never becomes a key.
  2. Each of the four neighbor checks also needs the neighbor not in blocked. This keeps a blocked intersection out of every other intersection's neighbor list. Miss it and the graph still has edges into the wall.

Keep the directions in the order left, right, down, up: the order Lesson 5-1's trace checked neighbors, which is why its printed path matched the table.

The old name is gone, the way SETPOINT disappeared in Lesson 2-6, so fix test_grid_graph() to build with build_graph(ROWS, COLS, BLOCKED) and set the run line to it. With nothing blocked, the output matches Lesson 5-3: 16, four neighbors, two neighbors, then the whole graph. Don't go on until it does.

Knowledge Check

(1,1) is blocked. Someone wrote build_graph with the first `in blocked` check but forgot the second. What is wrong with the result?

Step 3 · The placeholder, and a test with a wall in it​

The placeholder compute_bfs_path() builds the graph itself, from BLOCKED, on every call. Why not once at the top of the file? Because a wall found at step 3 must be gone from the graph that plans step 4. Rebuilding every call makes that automatic: no "forgot to rebuild" bug. On a 4×4 grid it takes no time worth measuring.

Now write test_blocked_graph() to exercise all three functions, and set the run line to it:

  1. Block (1, 1) with add_blocked() and build the graph.
  2. Print the blocked list, the number of intersections, whether (1, 1) is in the graph, and the neighbors of (0, 1).
  3. Call add_blocked((1, 1)) again and print the list.
  4. Print what compute_bfs_path((0, 0), (3, 3)) returns.

It should show:

Blocked: [(1, 1)]
Number of intersections: 15
(1,1) in graph? False
Neighbors of (0,1): [(0, 0), (0, 2)]
Blocked after adding (1,1) again: [(1, 1)]
compute_bfs_path is not written yet!
Path: []

Check: fifteen keys, (1, 1) not one of them and gone from (0, 1)'s neighbors, and the list still one entry long after the second add_blocked(). The empty path is the placeholder's.

Before you leave, write down (don't run) what these should return once Lesson 5-5 is done, with nothing blocked:

  • compute_bfs_path((0, 0), (0, 2))
  • compute_bfs_path((2, 2), (2, 2))

Real-world connections​

Maps

Road closures

A navigation app keeps one shared list of closed roads and rebuilds its routing graph from it — exactly this toolkit, at city scale.

Software

One owner per fact

Rule 1 is a general principle: keep one copy of each piece of state, and tell everything else. Copies drift apart.

Robotics

Maps that grow

A robot vacuum's map starts empty and fills in as bumps and sensors report walls — the robot's BLOCKED list, with thousands of entries.

Wrap-up​

  • What are the two planner rules? (Told the position; path excludes the start.)
  • Who calls add_blocked()? (A paper test in 5-6, the rangefinder in 5-7, and you in 5-8, typing in what the last run found.)
  • Why is the graph rebuilt on every call? (So a just-found obstacle is already missing from it.)
  • Why no global in add_blocked()? (Appending changes the list; it doesn't reassign the name.)

Resources​