Solution
Hints
- A maze with exactly one solution isn't placed randomly wall-by-wall -- it's grown one passage at a time, and the grower never revisits a cell.
- Think about how a robot vacuum finds the shortest way across a room it has never seen before -- it checks everything one step away before it checks anything two steps away.
- A "Start" button's click function shouldn't move the mouse all the way to Finish in one call -- it should move one cell, then schedule itself to run again a moment later.
Steps
- Grid model: a Cell class (or a dictionary keyed by (row, col)) stores each of the 32x32 grid's cells and which of its four walls -- north, south, east, west -- are still standing.
- Maze generation algorithm: carve_maze(grid) uses randomized depth-first search, also called the "recursive backtracker" algorithm, with an explicit stack of visited cells. Removing a wall only between the current cell and an unvisited neighbor is what guarantees exactly one path between any two cells.
- Drawing: draw_maze(grid) and draw_cell_walls(cell) use the turtle module to draw a line for every wall still standing, plus a green square for Start and a black-and-white flag shape for Finish.
- Pathfinding algorithm: solve_maze(grid, start, finish) runs breadth-first search (BFS) with a queue of cells to visit next. BFS is used instead of depth-first search because BFS always finds the shortest path first on an unweighted grid like this one. It returns the path as a list of (row, col) coordinates.
- Animation: animate_mouse(path) moves the mouse one cell per call, then uses turtle.ontimer() to schedule its own next call -- this is what makes the mouse glide through the maze instead of jumping straight to Finish.
- Interaction: create_start_button() adds a clickable "Start" button (turtle's screen supports a tkinter Button, or a second turtle used as a clickable shape) whose on-click callback calls animate_mouse(path) exactly once.
See also: The draw-a-square-turtle card and Chapter 14's Turtle Graphics and Algorithm Design sections.