Turtle Maze Generator

By the end of this lab you'll be able to:

• Generate a maze using the recursive backtracker (depth-first search) algorithm
• Represent a grid of cells as a 2D list and track which walls have been removed
• Draw the maze using goto() to draw wall segments

A perfect maze — every pair of cells connected by exactly one path — generated by the recursive backtracker algorithm. The algorithm carves passages by removing walls between randomly chosen unvisited neighbors.

Welcome to the Maze Generator!

Mazes are a classic use of recursive backtracking — a computer science algorithm where you explore as far as possible before backing up. Let's generate one together!

How It Works

Recursive backtracker: start at (0,0). Mark it visited. Randomly visit unvisited neighbors by removing the shared wall. When stuck, backtrack. This produces a "perfect maze" where every cell is reachable.

Sample Code

import turtle
import random
monty = turtle.Turtle()
monty.speed(0)
monty.hideturtle()
random.seed(42)

COLS, ROWS = 12, 10
cell = 25
ox = -COLS * cell / 2
oy = -ROWS * cell / 2

walls_removed = set()
visited = [[False]*COLS for _ in range(ROWS)]

def neighbors(r, c):
    result = []
    for dr, dc, direction in [(-1,0,'N'),(1,0,'S'),(0,-1,'W'),(0,1,'E')]:
        nr, nc = r+dr, c+dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and not visited[nr][nc]:
            result.append((nr, nc, direction))
    return result

def carve(r, c):
    visited[r][c] = True
    dirs = neighbors(r, c)
    random.shuffle(dirs)
    for nr, nc, d in dirs:
        if not visited[nr][nc]:
            walls_removed.add((r, c, d))
            carve(nr, nc)

import sys
sys.setrecursionlimit(5000)
carve(0, 0)

def draw_wall(x1, y1, x2, y2):
    monty.penup(); monty.goto(x1, y1)
    monty.pendown(); monty.goto(x2, y2)

monty.pencolor('navy')
monty.pensize(2)

for r in range(ROWS):
    for c in range(COLS):
        x = ox + c * cell
        y = oy + r * cell
        if r == ROWS - 1 or not (r, c, 'N') in walls_removed:
            draw_wall(x, y+cell, x+cell, y+cell)
        if c == 0 or not (r, c, 'W') in walls_removed:
            draw_wall(x, y, x, y+cell)
draw_wall(ox, oy, ox + COLS*cell, oy)
draw_wall(ox + COLS*cell, oy, ox+COLS*cell, oy+ROWS*cell)

monty.pencolor('forestgreen')
monty.goto(ox + 2, oy + 2)
monty.dot(8, 'forestgreen')
monty.goto(ox + COLS*cell - 2, oy + ROWS*cell - 2)
monty.dot(8, 'red')

What Do You Think Will Happen?

The algorithm uses random.seed(42) — the same seed always gives the same maze. Will the result look random and winding, or structured and regular? Make your guess — then click Run to find out!

Try It Now

▶ Run ↻ Reset

A random-looking but perfect maze — winding paths with no loops, guaranteed to be solvable. Were you right?

How It Works

The recursive backtracker uses the call stack to "remember" its path. When a cell has no unvisited neighbors, the function returns — backtracking to the previous cell. walls_removed records which walls were carved away so the drawing step knows which walls to skip.

Explanation Table

Line	What it does
walls_removed = set()	Track which walls have been carved
random.shuffle(dirs)	Randomize order of neighbor exploration
carve(nr, nc)	Recursive DFS — explore the chosen neighbor
if (r,c,'N') not in walls_removed	Only draw walls that haven't been carved

Learning Check

Your Turn — Change the Seed

Change random.seed(42) to random.seed(7). A completely different maze will be generated from the same algorithm. Predict: will it look similar or completely different?

▶ Run ↻ Reset

A completely different maze from seed 7 — but still perfectly connected with exactly one path between any two cells.

Experiments

1. Make it larger. Change to COLS=20, ROWS=16 and cell=18. You'll know it worked when a bigger, more complex maze appears.

2. Add entrance and exit openings. Remove the bottom-left and top-right boundary walls. You'll know it worked when the maze has a clear start and end opening.

3. Show the solution. After generating the maze, find a path from (0,0) to (ROWS-1, COLS-1) using BFS and draw it in red. You'll know it worked when a red path shows the solution.

4. Use different cell shapes. Draw small circles at each cell center instead of wall lines. You'll know it worked when the maze looks like a node-based network.

Generated a Maze!

You implemented depth-first search to generate a perfect maze! This algorithm is used in game level generation, network routing, and puzzle design. Up next: Parametric Surface Projection — 3D math projected onto 2D.