All paths

Graphs and pathfinding

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.

Raspberry Pi 4 Model BFree7 lessons6 h4 chapters2,766 XPCoding · Advanced+250 XP

0 of 7 done

What you will build

3 projects, built step by step

7 lessons in 4 chapters, about 6 hours on a simulated Raspberry Pi 4 Model B. Free, in your browser, every step checked by the simulator.

Chapter 2 project

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.

Open it in the simulator
Chapter 3 project

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.

Open it in the simulator
Chapter 4 project

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.

Open it in the simulator
The map

Chapter by chapter

Each lesson opens when the one before it is done, and each chapter ends in a project.

Chapter 1

Graphs

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

  1. Open288 XP

    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.

    0 of 6 steps

4 questions, graded as you go.
Chapter 2

Search

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

  1. Locked288 XP

    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.

    0 of 6 steps

  2. ProjectLocked576 XP

    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.

    0 of 6 steps

4 questions, graded as you go.
Chapter 3

Costs and guesses

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

  1. Locked250 XP

    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.

    0 of 5 steps

  2. ProjectLocked500 XP

    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.

    0 of 5 steps

5 questions, graded as you go.
Chapter 4

Mazes and the boss

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

  1. Locked288 XP

    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.

    0 of 6 steps

  2. ProjectLocked576 XP

    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.

    0 of 6 steps

4 questions, graded as you go.
Syllabus

Every lesson in the course

All 7 lessons, in order, each with what it covers. Any of them opens in the editor right away.

Chapter 1

Graphs

  1. Graphs as dataA 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.
Chapter 2

Search

  1. 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.
  2. 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.
Chapter 3

Costs and guesses

  1. DijkstraWhen 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.
  2. A* searchDijkstra 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.
Chapter 4

Mazes and the boss

  1. MazesMake 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.
  2. Boss: a robot that solves a mazeRover 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.
Kits

Build it on your bench too

Every lesson runs in the simulator with nothing to buy. When you want the real thing, these kits have the parts.

Have a kit already?

Find your kit

Pick the starter kit you own and run every lesson in its manual with the same parts on the same pins.

See every kit
Questions

About Graphs and pathfinding

Is Graphs and pathfinding free?

Yes. All 7 lessons of Graphs and pathfinding are free and run in your browser, with nothing to install and no parts to buy before you start.

Do I need a real Raspberry Pi 4 Model B?

No. Every lesson runs on a simulated Raspberry Pi 4 Model B with its parts on the canvas, and the simulator checks each step as you go. When you want to build it for real, the same wiring and code work on a real board.

How long does Graphs and pathfinding take?

About 6 hours: 7 lessons in 4 chapters, each one a few short steps. Your progress is kept, so you can stop after any lesson and pick up where you left off.

What will I build?

Each chapter ends in a project that puts it together: Depth-first search (DFS), A* search and Boss: a robot that solves a maze.

Where do I start?

With "Graphs as data", and each lesson builds on the one before it. New to circuits? Electronics basics is the course that starts from zero.