How Do Games Build a New Maze Every Time?

Press Step a few times, then Grow a maze, and watch the amber thread.

• It always goes into a room it has never been to. It never knocks through into a room it has visited before.
• When it is in a room with no new room beside it, it steps back along the thread, one room at a time, until it finds a room that does have a new neighbor. Then it sets off again from there.
• It stops when the thread has wound all the way back to the top left room.

Pieces counts the groups of rooms joined to each other but not to the rest: 100 at the start, 1 at the end.

A second way: random walls

Now press Random walls. This method doesn’t walk at all. It takes the 180 inner walls one at a time, in a random order, and for each it asks: are the rooms on the two sides already joined? Rooms that are joined share a color.

• If the two rooms are in different pieces (different colors, or one still plain), it knocks the wall down, and the two pieces join into one.
• If they are already in the same piece, it leaves the wall standing (the wall flashes red).

Two kinds of corridor

Grow a few mazes with each method and look at their shapes. Then press Way out: it finds the way from the top left room to the bottom right and counts the rooms on it. Press Tree too, which draws a dot for each room and a line for each opening.

Look at a maze as Grade 10 looked at a map of roads. Each room is a node, and each opening (a wall knocked down) is an edge joining two rooms. A maze is a graph.

A perfect maze is one where every room can be reached and there is exactly one way between any two rooms: no loops, and nothing cut off. In Grade 10’s words, that is a graph that is joined up and has no loops: a tree Grade 10: Trees. Pick the way in as the root, and the maze hangs from it like a family tree.

Grade 10 showed that a tree with n nodes always has exactly n − 1 edges: every node except the root has one edge up to its parent. So every perfect maze of 100 rooms has exactly 99 openings, and every perfect maze of 9 rooms, like the one in Figure 6.1, has 8. The number doesn’t depend on the method or on luck. Only the shape changes.

Each method makes a tree in its own way.

• The random walk knocks a wall down only to go into a room it has never visited. Each knock adds one new room to the part already made, joined by one opening. That can’t make a loop, since the new room had no other way in. The first room needs no knock, and each of the other 99 needs exactly one: 99 openings.
• Random walls knocks a wall down only between two different pieces. Each knock turns two pieces into one, so the count of pieces goes down by exactly one: from 100 to 1 takes exactly 99 knocks. A knock inside one piece would make a loop, and that is the one it never makes.

The thread is a stack of calls

The thread is how the walk knows where to step back to. A program keeps it, without drawing it, by a function that calls itself. To carve from a room:

1. Mark the room as visited.
2. Take the four directions in a random order. For each one: if the room that way is inside the maze and not yet visited, knock down the wall to it, and carve from that room.
3. When all four directions are done, stop.

Step 2 asks carve to do the same job again from the next room: carve is recursive. Each open call is a room on the thread. When a call finishes, the program goes back to the call that made it, the room before on the thread, and tries that room’s next direction: the step back. Grade 11 calls the open calls the call stack; the amber line shows it. A search that goes as deep as it can before stepping back is a depth-first search, which Grade 10 met in a careful box (pop(), not pop(0)).

You will build a maze maker and a maze solver in five steps, each running here on the page.

Step 1: a maze as a picture

A maze can be stored as a picture of squares, the way Grade 10 stored a temple for its flood fill: # for rock, . for floor. A maze of 3 × 3 rooms is a picture 7 × 7 squares. The rooms are the squares in the odd rows and odd columns (1, 3, 5); between two rooms is a square that is # for a wall or . for an opening. The squares in even rows and even columns are corner posts, and are always rock.

This is the maze of Figure 6.1, with A in the top left corner and I in the bottom right:

from pixels import show_grid maze = [    "#######",    "#.#...#",    "#.#.###",    "#.....#",    "#####.#",    "#.....#",    "#######",] rooms = 0openings = 0for r in range(1, len(maze) - 1):    for c in range(1, len(maze[0]) - 1):        if r % 2 == 1 and c % 2 == 1:            rooms = rooms + 1        elif maze[r][c] == "." and (r + c) % 2 == 1:            openings = openings + 1print("Rooms:", rooms, " Openings:", openings)show_grid(maze, {"#": "black", ".": "white"})

Rooms: 9  Openings: 8

Picture

A square between two rooms has one odd and one even number (row 1, column 2, say), so r + c is odd (line 19). pixels is this page’s own module for small pictures; on a computer you would use a library such as Pillow.

Step 2: the random walk

Now the program grows its own maze. It starts with every square rock (line 5), and carve(r, c) does what the steps above say. Rooms are counted 0 to 9 in each direction, so room (r, c) is the square at row 2 * r + 1, column 2 * c + 1; the wall between it and the next room in direction (dr, dc) is one square that way (line 15).

import randomfrom pixels import show_grid def make_maze(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]     def carve(r, c):        grid[2 * r + 1][2 * c + 1] = "."        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]        random.shuffle(moves)        for dr, dc in moves:            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols:                if grid[2 * nr + 1][2 * nc + 1] == "#":                    grid[2 * r + 1 + dr][2 * c + 1 + dc] = "."                    carve(nr, nc)     carve(0, 0)    return ["".join(row) for row in grid] def openings(maze):    count = 0    for r in range(1, len(maze) - 1):        for c in range(1, len(maze[0]) - 1):            if maze[r][c] == "." and (r + c) % 2 == 1:                count = count + 1    return count random.seed(2083)maze = make_maze(10, 10)print("Rooms:", 10 * 10, " Openings:", openings(maze))show_grid(maze, {"#": "black", ".": "white"})

Rooms: 100  Openings: 99

Picture

A room is unvisited while its square is still # (line 14): the picture is the walk’s memory. carve is written inside make_maze, so it can use grid, rows and cols. random.seed(2083) makes the same “random” choices every run, so you get the maze in the picture; take it out for a new maze each run.

The board below asks your program for mazes: each Grow a maze calls your make_maze(10, 10) from the program above (press Edit there to change it), draws the picture and checks it: are all the rooms in one piece, and are there any loops?

Step 3: watch it grow

This version keeps a picture after every change, and shows them as steps. A room or opening on the thread is o (orange) while its call is open, and becomes floor when the call finishes and the walk steps back.

import randomfrom pixels import show_frames def maze_frames(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]    frames = []     def carve(r, c):        grid[2 * r + 1][2 * c + 1] = "o"        frames.append(["".join(row) for row in grid])        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]        random.shuffle(moves)        for dr, dc in moves:            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols:                if grid[2 * nr + 1][2 * nc + 1] == "#":                    grid[2 * r + 1 + dr][2 * c + 1 + dc] = "o"                    carve(nr, nc)                    grid[2 * r + 1 + dr][2 * c + 1 + dc] = "."        grid[2 * r + 1][2 * c + 1] = "."        frames.append(["".join(row) for row in grid])     carve(0, 0)    return frames random.seed(2083)frames = maze_frames(10, 10)print(len(frames), "pictures")show_frames(frames, {"#": "black", ".": "white", "o": "orange"})

200 pictures

Picture

Press Play under the pictures. The orange line is exactly the open calls of carve: a picture when each call starts (line 10) and when it finishes (line 21), 100 calls, 200 pictures.

Step 4: the way out

To solve a maze, use Grade 10’s breadth-first search on the squares of the picture, as its flood fill did, and remember where each square was reached from Grade 10: Remembering the way. The way in is the top left room, the way out the bottom right.

import randomfrom pixels import show_grid def make_maze(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]     def carve(r, c):        grid[2 * r + 1][2 * c + 1] = "."        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]        random.shuffle(moves)        for dr, dc in moves:            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols:                if grid[2 * nr + 1][2 * nc + 1] == "#":                    grid[2 * r + 1 + dr][2 * c + 1 + dc] = "."                    carve(nr, nc)     carve(0, 0)    return ["".join(row) for row in grid] def way_out(maze):    start = (1, 1)    goal = (len(maze) - 2, len(maze[0]) - 2)    came_from = {start: None}    to_visit = [start]    while len(to_visit) > 0:        square = to_visit.pop(0)        if square == goal:            route = []            while square is not None:                route.append(square)                square = came_from[square]            route.reverse()            return route        r, c = square        for nxt in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:            if maze[nxt[0]][nxt[1]] == "." and nxt not in came_from:                came_from[nxt] = square                to_visit.append(nxt)    return None random.seed(2083)maze = make_maze(10, 10)route = way_out(maze)rooms_on_route = [sq for sq in route if sq[0] % 2 == 1 and sq[1] % 2 == 1]print("The way out goes through", len(rooms_on_route), "rooms")drawn = [list(row) for row in maze]for r, c in route:    drawn[r][c] = "o"show_grid(drawn, {"#": "black", ".": "white", "o": "red"})

The way out goes through 47 rooms

Picture

No square on the edge of the picture is ever floor, so nxt never falls off it (line 37). In a tree there is only one way out to find; in any maze, breadth-first search finds the shortest.

Step 5: random walls

Here is the second method, in Python. piece is a dictionary from each room to the number of its piece; every room starts as a piece of its own (line 11). The walls between neighboring rooms go into a list, which is shuffled. For each wall, if the rooms on its two sides have different piece numbers, the wall goes, and every room of the second piece takes the first one’s number (lines 24–26).

import randomfrom pixels import show_grid def random_walls(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]    piece = {}    walls = []    for r in range(rows):        for c in range(cols):            grid[2 * r + 1][2 * c + 1] = "."            piece[(r, c)] = r * cols + c            if r + 1 < rows:                walls.append((r, c, r + 1, c))            if c + 1 < cols:                walls.append((r, c, r, c + 1))    random.shuffle(walls)    knocked = 0    for r1, c1, r2, c2 in walls:        a = piece[(r1, c1)]        b = piece[(r2, c2)]        if a != b:            grid[r1 + r2 + 1][c1 + c2 + 1] = "."            knocked = knocked + 1            for room in piece:                if piece[room] == b:                    piece[room] = a    print(len(walls), "walls looked at,", knocked, "knocked down")    return ["".join(row) for row in grid] random.seed(2083)maze = random_walls(10, 10)show_grid(maze, {"#": "black", ".": "white"})

180 walls looked at, 99 knocked down

Picture

The square between rooms (r1, c1) and (r2, c2) is at row r1 + r2 + 1, column c1 + c2 + 1 (line 22): for rooms side by side, that is one square past the first room. Joseph Kruskal published this method in 1956, as a way to find the shortest network of links that joins a set of points (taking the links shortest first); with the walls in a random order instead, it makes mazes.

So far you have one maze from each method. This program makes 100 of each and checks every one: the openings, whether every room is reached, and the number of different ways from the top left room to the bottom right. count_ways tries every path that never visits a square twice, a recursive search like carve, and adds up those that reach the goal.

import random def make_maze(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]     def carve(r, c):        grid[2 * r + 1][2 * c + 1] = "."        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]        random.shuffle(moves)        for dr, dc in moves:            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols:                if grid[2 * nr + 1][2 * nc + 1] == "#":                    grid[2 * r + 1 + dr][2 * c + 1 + dc] = "."                    carve(nr, nc)     carve(0, 0)    return ["".join(row) for row in grid] def random_walls(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]    piece = {}    walls = []    for r in range(rows):        for c in range(cols):            grid[2 * r + 1][2 * c + 1] = "."            piece[(r, c)] = r * cols + c            if r + 1 < rows:                walls.append((r, c, r + 1, c))            if c + 1 < cols:                walls.append((r, c, r, c + 1))    random.shuffle(walls)    for r1, c1, r2, c2 in walls:        a = piece[(r1, c1)]        b = piece[(r2, c2)]        if a != b:            grid[r1 + r2 + 1][c1 + c2 + 1] = "."            for room in piece:                if piece[room] == b:                    piece[room] = a    return ["".join(row) for row in grid] def openings(maze):    count = 0    for r in range(1, len(maze) - 1):        for c in range(1, len(maze[0]) - 1):            if maze[r][c] == "." and (r + c) % 2 == 1:                count = count + 1    return count def rooms_reached(maze):    seen = {(1, 1)}    to_visit = [(1, 1)]    while len(to_visit) > 0:        r, c = to_visit.pop()        for nxt in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:            if maze[nxt[0]][nxt[1]] == "." and nxt not in seen:                seen.add(nxt)                to_visit.append(nxt)    return len([sq for sq in seen if sq[0] % 2 == 1 and sq[1] % 2 == 1]) def count_ways(maze, square, goal, on_path):    if square == goal:        return 1    on_path.add(square)    total = 0    r, c = square    for nxt in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:        if maze[nxt[0]][nxt[1]] == "." and nxt not in on_path:            total = total + count_ways(maze, nxt, goal, on_path)    on_path.remove(square)    return total random.seed(1)for name, method in [("Random walk", make_maze), ("Random walls", random_walls)]:    all_99 = True    all_reached = True    ways = set()    for i in range(100):        maze = method(10, 10)        if openings(maze) != 99:            all_99 = False        if rooms_reached(maze) != 100:            all_reached = False        ways.add(count_ways(maze, (1, 1), (19, 19), set()))    print(name + ": 99 openings every time:", all_99,          " every room reached:", all_reached, " ways out:", ways)

Random walk: 99 openings every time: True  every room reached: True  ways out: {1}Random walls: 99 openings every time: True  every room reached: True  ways out: {1}

Two hundred mazes, made two different ways, and in every one: 99 openings, every room reached, and exactly one way out. Your program didn’t just make mazes; it checked the claim that a perfect maze is a tree on every maze it made.

Now spoil them. This program knocks down one more wall in each of 100 mazes, a wall chosen at random from those still standing, and counts the ways out again:

import random def make_maze(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]     def carve(r, c):        grid[2 * r + 1][2 * c + 1] = "."        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]        random.shuffle(moves)        for dr, dc in moves:            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols:                if grid[2 * nr + 1][2 * nc + 1] == "#":                    grid[2 * r + 1 + dr][2 * c + 1 + dc] = "."                    carve(nr, nc)     carve(0, 0)    return ["".join(row) for row in grid] def count_ways(maze, square, goal, on_path):    if square == goal:        return 1    on_path.add(square)    total = 0    r, c = square    for nxt in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:        if maze[nxt[0]][nxt[1]] == "." and nxt not in on_path:            total = total + count_ways(maze, nxt, goal, on_path)    on_path.remove(square)    return total random.seed(1)results = {}for i in range(100):    maze = [list(row) for row in make_maze(10, 10)]    standing = []    for r in range(1, 20):        for c in range(1, 20):            if (r + c) % 2 == 1 and maze[r][c] == "#":                standing.append((r, c))    r, c = random.choice(standing)    maze[r][c] = "."    ways = count_ways(maze, (1, 1), (19, 19), set())    results[ways] = results.get(ways, 0) + 1print("Ways out, after one more opening:", results)

Ways out, after one more opening: {2: 64, 1: 36}

One wall too many, and most mazes have two ways out: the extra opening made a loop, and a way out through the loop can go round either side. In the rest, the loop is off to one side, but still there. With 99 openings and every room joined there is no room for a loop; with 100 there must be one.

So the rule that made the maze also made it perfect. That is what game makers need: a maze that is new every time and never broken, without anyone checking it by hand.

The shape of the corridors

The two methods make different mazes. This program measures 100 mazes of each: how many rooms are dead ends (a room with just one opening), and how many rooms the way out passes through.

import random def make_maze(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]     def carve(r, c):        grid[2 * r + 1][2 * c + 1] = "."        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]        random.shuffle(moves)        for dr, dc in moves:            nr, nc = r + dr, c + dc            if 0 <= nr < rows and 0 <= nc < cols:                if grid[2 * nr + 1][2 * nc + 1] == "#":                    grid[2 * r + 1 + dr][2 * c + 1 + dc] = "."                    carve(nr, nc)     carve(0, 0)    return ["".join(row) for row in grid] def random_walls(rows, cols):    grid = [["#"] * (2 * cols + 1) for r in range(2 * rows + 1)]    piece = {}    walls = []    for r in range(rows):        for c in range(cols):            grid[2 * r + 1][2 * c + 1] = "."            piece[(r, c)] = r * cols + c            if r + 1 < rows:                walls.append((r, c, r + 1, c))            if c + 1 < cols:                walls.append((r, c, r, c + 1))    random.shuffle(walls)    for r1, c1, r2, c2 in walls:        a = piece[(r1, c1)]        b = piece[(r2, c2)]        if a != b:            grid[r1 + r2 + 1][c1 + c2 + 1] = "."            for room in piece:                if piece[room] == b:                    piece[room] = a    return ["".join(row) for row in grid] def dead_ends(maze):    count = 0    for r in range(1, len(maze), 2):        for c in range(1, len(maze[0]), 2):            ways = 0            for nr, nc in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:                if maze[nr][nc] == ".":                    ways = ways + 1            if ways == 1:                count = count + 1    return count def way_out(maze):    start = (1, 1)    goal = (len(maze) - 2, len(maze[0]) - 2)    came_from = {start: None}    to_visit = [start]    while len(to_visit) > 0:        square = to_visit.pop(0)        if square == goal:            route = []            while square is not None:                route.append(square)                square = came_from[square]            return route        r, c = square        for nxt in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:            if maze[nxt[0]][nxt[1]] == "." and nxt not in came_from:                came_from[nxt] = square                to_visit.append(nxt)    return None random.seed(1)for name, method in [("Random walk", make_maze), ("Random walls", random_walls)]:    ends = 0    long = 0    for i in range(100):        maze = method(10, 10)        ends = ends + dead_ends(maze)        long = long + (len(way_out(maze)) + 1) // 2    print(f"{name}: {ends / 100:.1f} dead ends, way out through {long / 100:.1f} rooms")

Random walk: 11.8 dead ends, way out through 46.2 roomsRandom walls: 30.6 dead ends, way out through 25.0 rooms

About 12 rooms in 100 are dead ends in the random walk’s mazes, and the way out wanders through 46 rooms; random walls makes about 31 dead ends and a way out through 25. (A route of s squares passes (s + 1) ÷ 2 rooms: rooms and openings take turns.) The walk’s mazes are a few long corridors whose wrong turns go a long way; random walls’ are bushy, with many short ones. Walter Pullen’s list of maze methods gives about 10% and 30% dead ends for big mazes made these two ways. A game maker picks the method for the feel they want.

Bigger mazes, without recursion

Make a maze of 50 × 50 rooms with make_maze, and it will usually stop with RecursionError: maximum recursion depth exceeded. The thread gets long: in a 50 × 50 maze it usually passes through more than a thousand rooms at once, each an open call, and Python allows only about a thousand open calls Grade 11: When recursion goes wrong.

Which mazes can each method make?

How many different perfect mazes of 3 × 3 rooms are there? A 3 × 3 maze has 12 inner walls, and a perfect one opens exactly 8 of them. A program can try every set of 8 and keep those that join all 9 rooms. And does each method make every one of them, equally often?

The number of perfect mazes grows very fast. For 4 × 4 rooms there are 100,352. For 10 × 10, a theorem of Gustav Kirchhoff’s from 1847 about electrical networks gives the count without making them; this program uses it (how it works is beyond this topic):

def count_mazes(rows, cols):    n = rows * cols    m = [[0] * n for i in range(n)]    for r in range(rows):        for c in range(cols):            a = r * cols + c            for nr, nc in [(r + 1, c), (r, c + 1)]:                if nr < rows and nc < cols:                    b = nr * cols + nc                    m[a][a] += 1                    m[b][b] += 1                    m[a][b] -= 1                    m[b][a] -= 1    m = [row[1:] for row in m[1:]]    k = len(m)    before = 1    for i in range(k - 1):        for j in range(i + 1, k):            for l in range(i + 1, k):                m[j][l] = (m[j][l] * m[i][i] - m[j][i] * m[i][l]) // before        before = m[i][i]    return m[k - 1][k - 1] for size in [3, 4, 10]:    print(f"{size} x {size} rooms:", count_mazes(size, size), "perfect mazes")

3 x 3 rooms: 192 perfect mazes4 x 4 rooms: 100352 perfect mazes10 x 10 rooms: 5694319004079097795957215725765328371712000 perfect mazes

A number of 43 digits, about 5.7 × 10⁴². A game could show you a new 10 × 10 maze every second for far longer than the universe has existed and never run out.

A question to think about: is there a method that makes every perfect maze equally often? There is: David Wilson found a fast one in 1996, a random walk that wanders until it hits the maze made so far and then wipes out any loops it walked on the way. Why would a game maker choose it, or not?

Three challenges, each checked on the page: write your function in the program above the checker (press Edit), then press Check my program. A maze is a picture as in Step 1, a list of strings of # and ., with rooms in the odd rows and odd columns. The examples show what your function should give; there are more tests you can’t see.

★ Count the dead ends

Write dead_ends(maze): the number of rooms with exactly one opening.

def dead_ends(maze):    # Give back how many rooms have exactly one opening.    return 0 maze = [    "#######",    "#.#...#",    "#.#.###",    "#.....#",    "#####.#",    "#.....#",    "#######",]print(dead_ends(maze))

★★ Is it perfect?

Write is_perfect(maze): True if every room can be reached from every other and there is exactly one way between any two, False if not. Some test mazes have a loop, some have rooms cut off, and some have both.

def is_perfect(maze):    # Give back True for a perfect maze, False otherwise.    return True maze = [    "#######",    "#.....#",    "#.#.###",    "#.....#",    "#####.#",    "#.....#",    "#######",]print(is_perfect(maze))

★★★ The two rooms farthest apart

A game wants its way in and its way out as far apart as the maze allows. Write farthest(maze): the most steps it takes to walk from one room to another in a perfect maze, choosing the two rooms that are farthest apart (a step is from a room to the room next to it, through an opening). Some test mazes have 1,600 rooms, so trying a search from every room is too slow.

def farthest(maze):    # Give back the most steps between two rooms of the maze.    return 0 maze = [    "#######",    "#.#...#",    "#.#.###",    "#.....#",    "#####.#",    "#.....#",    "#######",]print(farthest(maze))

• Grade 10, Trees: why a tree with n nodes has n − 1 edges, and one route between any two nodes.
• Grade 10, The fewest steps between two places: the breadth-first search of Step 4.
• Grade 11, Recursion: functions that call themselves, the call stack, and why a very deep one fails.
• Grade 11, One fill, a stack or a queue: depth-first and breadth-first, side by side.
• Can a Robot Get Out of Any Maze?: a rule that walks out of a maze with no map. In a perfect maze, it always works.
• How Is a Sudoku Solved in a Blink?: another search that goes forward and steps back when it is stuck.
• Can one random choice draw a maze?: a maze from a single line of code, and whether it has a way through. (Coming soon.)