Source: https://mokxi.com/teachers/plans/algorithms-pathfinding
Updated: 2026-11-19

Lesson plan

# Graphs and pathfinding lesson plan

Guide a Mars rover with the algorithms behind every map app and game: graphs as data, BFS, DFS, Dijkstra and A* written from scratch, mazes carved and solved, and a rover console that plans around rocks on a Raspberry Pi.

4 chapters, 7 lessons, about 6 hours, on the Raspberry Pi 4 Model B. Every lesson runs in the browser, with nothing to install.

Start a class from this course

The unit

## Objectives and materials

### By the end, students can

- Stations, roads and terrain maps as data a program can search.
- Breadth first and depth first: rings, dives and what each one is for.
- Cheapest routes with Dijkstra, then A* with a sense of direction.
- Carve and solve mazes, then run Rover 7 through one.

### Materials for the whole unit

- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module

Every part is already on the simulator’s bench, so there is nothing to buy or hand out. The counts are the most any one lesson uses, if you build it on real breadboards too.

Chapter 1. About 55 min

## Graphs

Stations, roads and terrain maps as data a program can search.

Lesson | Time | What students do

Graphs as data A Mars rover's road map as a graph: stations and roads in a dict of lists, degrees and the busiest hub, a checker that finds a one-way road, counting edges, and a terrain map turned into a graph of cells. | 55 min

- Stations and roads
- Degree and the busiest hub
- Find the one-way road
- Fix it and count the edges
- A map is a graph too
- How big is the map graph?

### Materials

- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module

### Check for understanding

Each student finishes "Graphs as data" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "How big is the map graph?".

Chapter 2. About 1 h 50 min

## Search

Breadth first and depth first: rings, dives and what each one is for.

Lesson | Time | What students do

Breadth-first search (BFS) Breadth-first search with a deque: the order it visits stations, distance in hops, parents that rebuild the route, the same function on the rover's grid, the path drawn on the map, and a red lamp when a rock walls the goal in. | 55 min

- Search in rings
- Distance in hops
- Rebuild the route
- The same BFS on the map
- Draw the route
- Walled in

Depth-first search (DFS) Depth-first search, recursive and with a stack: the order it dives, which stations a dust storm cuts off, why its first path on the map is not the shortest, and the recursion limit a big field runs into. | 55 min

- Dive first
- DFS with a stack
- Cut off by a dust storm
- Not the shortest
- Too deep
- Your own stack never runs out

### Materials

- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module

### Check for understanding

Each student finishes "Depth-first search (DFS)" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Your own stack never runs out".

Chapter 3. About 1 h 30 min

## Costs and guesses

Cheapest routes with Dijkstra, then A* with a sense of direction.

Lesson | Time | What students do

Dijkstra When roads have costs, fewest roads is not fastest: drive times as edge weights, heapq as a priority queue, Dijkstra's algorithm on the stations and then on terrain with soft sand, and a count of the squares it had to look at. | 45 min

- Fewest roads is not fastest
- A priority queue with heapq
- Dijkstra's algorithm
- Soft sand
- How much did it look at?

A* search Dijkstra with a sense of direction: a heuristic, Manhattan distance, the f = g + h priority, the same best route for far fewer squares, a big plain where the saving is huge, and what an overconfident heuristic costs. | 45 min

- Dijkstra with a hook
- Manhattan distance
- A* finds the same route, faster
- A big plain
- An overconfident guess

### Materials

- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module

### Check for understanding

Each student finishes "A* search" on their own, without opening the hints. The simulator checks 5 of its 5 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "An overconfident guess".

Chapter 4. About 1 h 50 min

## Mazes and the boss

Carve and solve mazes, then run Rover 7 through one.

Lesson | Time | What students do

Mazes Make mazes with a randomized DFS, prove they are perfect by counting passages, solve them with BFS, draw the solution, count dead ends, and change the seed for a new maze every time. | 55 min

- Carve a maze with DFS
- A perfect maze
- Solve it with BFS
- Draw the solution
- Count the dead ends
- A new maze

Boss: a robot that solves a maze Rover 7's console: a maze, A* planning on command, status lamps for planning, route and walled in, drive commands with turns, rocks typed in live that force a re-plan, and a drive to the goal. | 55 min

- Rover 7 online
- Status lamps
- Drive commands
- Rocks
- Walled in
- Drive to the goal

### Materials

- Pushbutton
- Raspberry Pi 4 Model B
- Traffic light module

### Check for understanding

Each student finishes "Boss: a robot that solves a maze" on their own, without opening the hints. The simulator checks 6 of its 6 steps as they go.

Then ask each one to explain, in a sentence or two, the last thing it asked of them: "Drive to the goal".

Your class

## Teach this unit as a class

Start a class from this course and its 7 lessons are assigned in one go, in order. Students join with a six-character code or printed login cards, and each one’s work comes back to you.

The class tools are free for 30 days for one class of up to 20 students, with no card. The lessons themselves are free either way.

Start a class from this course See the demo class

More units

## Other lesson plans

Electronics basics 20 lessons, about 10 h. Embedded on the Arduino Uno 16 lessons, about 12 h. Embedded on the ESP32-C3 13 lessons, about 11 h. Embedded on the Raspberry Pi Pico 7 lessons, about 6 h. Build your own fight stick 5 lessons, about 4 h. Embedded on the STM32F411 6 lessons, about 6 h. C++ on a board 13 lessons, about 10 h. Digital logic and memory 4 lessons, about 4 h. Interactive devices on the Uno 9 lessons, about 8 h. From gates to a computer 23 lessons, about 16 h. Build a claw machine 8 lessons, about 6 h. Every unit All the courses as ready-made units, on the teachers page.
