Lesson 5-4 · The Pathfinding Functions
Lesson 5-4 · The Pathfinding Functions
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()asbuild_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.
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.
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.
Write both bodies. Step 2 gives you the test.
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:
- If
(x, y)is inblocked, skip it. It never becomes a key. - 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.
(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:
- Block
(1, 1)withadd_blocked()and build the graph. - Print the blocked list, the number of intersections, whether
(1, 1)is in the graph, and the neighbors of(0, 1). - Call
add_blocked((1, 1))again and print the list. - 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
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.
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.
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
globalinadd_blocked()? (Appending changes the list; it doesn't reassign the name.)