Interactive lab
Routes: a maze lab
This lab carves a maze on a square grid and then finds the shortest way through it. The two steps use different methods, and both can be followed on the canvas.
How the maze is made
01
Carving with a depth-first walk
The generator starts in the top left cell and moves to a random unvisited neighbor, removing the wall between them. When a cell has no unvisited neighbors left, the walk backs up to the most recent cell that still has one. Every cell is visited exactly once, so the finished maze has no loops.
02
Solving with a breadth-first search
The solver starts at the entrance and works outward in rings. Every cell one step away is checked before any cell two steps away. The first time the search reaches the exit, the path it followed is the shortest one, because every shorter path has already been ruled out.
03
Reading the numbers
Route steps count the moves between cells from the top left cell to the bottom right cell. Explored cells count the cells the search removed from its queue before it stopped. Neither number is a score. Both describe the work the method had to do on one particular maze.
The lab
This lab needs JavaScript. With scripts turned off, the explanation above and the fixed sample below still describe the method.
Choose a grid size and generate a maze. Solve the route to draw the path in green. Turn on shading to see which cells the search examined before it reached the exit.
Preparing the first maze.
Each control is a native button, select, or checkbox. Tab moves between them, Enter or Space presses a button or toggles the checkbox, and the arrow keys move through the grid size options. Choosing a new size generates a new maze.
A fixed sample
If scripts are off, the lab is hidden and this five by five sample shows the same method. Solid lines are walls. The green line is the route from the top left entrance to the bottom right exit, the route a breadth-first search finds.
The maze has no loops. Every cell can be reached, and there is exactly one path between any two cells, so the search never has to choose between two routes of the same length.