Notebook

Peter Norvig
13 March 2018

Maze Generation¶

Let's make some mazes! I'm thinking of mazes like this one, which is a rectangular grid of squares, with walls on some of the sides of squares, and openings on other sides:

The main constraint is that there should be a path from entrance to exit, and it should be *fun* to solve the maze with pencil, paper, and brain power—not too easy, but also not impossible.

As I think about how to model a maze on the computer, it seems like a graph is the right model: the nodes of the graph are the squares of the grid, and the edges of the graph are the openings between adjacent squares. So what properties of a graph make a good maze?

There must be a path from entrance to exit.
There must not be too such many paths; maybe it is best if there is only one.
Probably the graph should be singly connected—there shouldn't be islands of squares that are unreachable from the start. And maybe we want exactly one path between any two squares.
The path should have many twists; it would be too easy if it was mostly straight.

I know that a tree has all these properties except the last one. So my goal has become: Superimpose a tree over the grid, covering every square, and make sure the paths are twisty. Here's how I'll do it:

Start with a grid with no edges (every square is surrounded by walls on all sides).
Add edges (that is, knock down walls) for the entrance at upper left and exit at lower right.
Place the root of the tree in some square.
Then repeat until the tree covers the whole grid:
- Select some node already in the tree.
- Randomly select a neighbor that hasn't been added to the tree yet.
- Add an edge (knock down the wall) from the node to the neighbor.

In the example below, the root, A, has been placed in the upper-left corner, and two branches, A-B-C-D and A-b-c-d, have been randomly chosen (well, not actually random; they are starting to create the same maze as in the diagram above):

 o  o--o--o--o--o--o--o--o--o--o
 | A  b  c|  |  |  |  |  |  |  |
 o  o--o  o--o--o--o--o--o--o--o
 | B|  | d|  |  |  |  |  |  |  |
 o  o--o--o--o--o--o--o--o--o--o
 | C  D|  |  |  |  |  |  |  |  |
 o--o--o--o--o--o--o--o--o--o--o
 |  |  |  |  |  |  |  |  |  |  |
 o--o--o--o--o--o--o--o--o--o--o
 |  |  |  |  |  |  |  |  |  |  |
 o--o--o--o--o--o--o--o--o--o  o

Next I select node d and extend it to e (at which point there are no available neighbors, so e will not be selected in the future), and then I select D and extend from there all the way to N, at each step selecting the node I just added:

 o  o--o--o--o--o--o--o--o--o--o
 | A  b  c|  |  |  |  |  |  |  |
 o  o--o  o--o--o--o--o--o--o--o
 | B| e  d|  | N|  |  |  |  |  |
 o  o--o--o--o  o--o--o--o--o--o
 | C  D|  |  | M|  |  |  |  |  |
 o--o  o--o--o  o--o--o--o--o--o
 | F  E|  | K  L|  |  |  |  |  |
 o  o--o--o  o--o--o--o--o--o--o
 | G  H  I  J|  |  |  |  |  |  |
 o--o--o--o--o--o--o--o--o--o  o

Continue like this until every square in the grid has been added to the tree.

Implementing Random Trees¶

I'll make the following implementation choices:

A tree will be represented as a list of edges.
An Edge is a tuple of two nodes. I'll keep them sorted so that Edge(A, B) is the same as Edge(B, A).
A node in a tree can be anything: a number, a letter, a square, ...
The algorithm for random_tree(nodes, neighbors, pop) is as follows:
- We will keep track of three collections:
  - tree: a list of edges that constitutes the tree.
  - nodes: the set of nodes that have not yet been added to the tree, but will be.
  - frontier: a queue of nodes in the tree that are eligible to have an edge added.
- On each iteration:
  - Use pop to pick a node from the frontier, and find the neighbors that are not already in the tree.
  - If there are any neighbors, randomly pick one (nbr), add Edge(node, nbr) to tree, remove the neighbor from nodes, and keep both the node and the neighbor on the frontier. If there are no neighbors, drop the node from the frontier.
- When no nodes remain, return tree.

In [1]:

import random
from collections import deque, namedtuple

def Edge(node1, node2): return tuple(sorted([node1, node2]))

def random_tree(nodes: set, neighbors: callable, pop: callable) -> [Edge]:
    "Repeat: pop a node and add Edge(node, nbr) until all nodes have been added to tree."
    tree = []
    root = nodes.pop()
    frontier = deque([root])
    while nodes:
        node = pop(frontier)
        nbrs = neighbors(node) & nodes
        if nbrs:
            nbr = random.choice(list(nbrs))
            tree.append(Edge(node, nbr))
            nodes.remove(nbr)
            frontier.extend([node, nbr])
    return tree

Implementing Random Mazes¶

Now let's use random_tree to implement random_maze. Some more choices:

A Maze is a named tuple with three fields: the width and height of the grid, and a list of edges between squares.
A square is denoted by an (x, y) tuple of integer coordinates.
The function neighbors4 gives the four surrounding squares.

In [2]:

Maze = namedtuple('Maze', 'width, height, edges')

def neighbors4(square):
    "The 4 neighbors of an (x, y) square."
    (x, y) = square
    return {(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)}

def squares(width, height): 
    "All squares in a grid of these dimensions."
    return {(x, y) for x in range(width) for y in range(height)}

def random_maze(width, height, pop=deque.pop):
    "Use random_tree to generate a random maze."
    nodes = squares(width, height)
    tree = random_tree(nodes, neighbors4, pop)
    return Maze(width, height, tree)

In [3]:

random_maze(10,5)

Out[3]:

Maze(width=10, height=5, edges=[((6, 3), (7, 3)), ((6, 3), (6, 4)), ((6, 4), (7, 4)), ((7, 4), (8, 4)), ((8, 3), (8, 4)), ((8, 2), (8, 3)), ((7, 2), (8, 2)), ((7, 1), (7, 2)), ((7, 0), (7, 1)), ((7, 0), (8, 0)), ((8, 0), (8, 1)), ((8, 1), (9, 1)), ((9, 0), (9, 1)), ((9, 1), (9, 2)), ((9, 2), (9, 3)), ((9, 3), (9, 4)), ((6, 0), (7, 0)), ((5, 0), (6, 0)), ((5, 0), (5, 1)), ((5, 1), (6, 1)), ((6, 1), (6, 2)), ((5, 2), (6, 2)), ((4, 2), (5, 2)), ((3, 2), (4, 2)), ((3, 2), (3, 3)), ((2, 3), (3, 3)), ((2, 2), (2, 3)), ((2, 1), (2, 2)), ((2, 0), (2, 1)), ((1, 0), (2, 0)), ((0, 0), (1, 0)), ((0, 0), (0, 1)), ((0, 1), (1, 1)), ((1, 1), (1, 2)), ((0, 2), (1, 2)), ((0, 2), (0, 3)), ((0, 3), (1, 3)), ((1, 3), (1, 4)), ((0, 4), (1, 4)), ((1, 4), (2, 4)), ((2, 4), (3, 4)), ((3, 4), (4, 4)), ((4, 3), (4, 4)), ((4, 3), (5, 3)), ((5, 3), (5, 4)), ((2, 0), (3, 0)), ((3, 0), (4, 0)), ((4, 0), (4, 1)), ((3, 1), (4, 1))])

That's not very pretty to look at. I'm going to need a way to visualize a maze.

Printing a maze¶

In [4]:

def print_maze(maze, dot='o', lin='--', bar='|', sp='  '):
    "Print maze in ASCII."
    exit = Edge((maze.width-1, maze.height-1), (maze.width-1, maze.height))
    edges = set(maze.edges) | {exit}
    print(dot + sp + lin.join(dot * maze.width)) # Top line, including entrance
    def vert_wall(x, y): return (' ' if Edge((x, y), (x+1, y)) in edges else bar)
    def horz_wall(x, y): return (sp  if Edge((x, y), (x, y+1)) in edges else lin)
    for y in range(maze.height):
        print(bar + cat(sp + vert_wall(x, y) for x in range(maze.width)))
        print(dot + cat(horz_wall(x, y) + dot for x in range(maze.width)))
        
cat = ''.join
        
print_maze(random_maze(10, 5))

o  o--o--o--o--o--o--o--o--o--o
|              |     |        |
o--o--o--o  o--o  o  o  o--o  o
|           |     |        |  |
o  o  o--o--o  o--o--o--o--o  o
|  |  |     |     |     |     |
o  o--o  o  o--o  o  o--o  o--o
|  |     |        |  |  |     |
o  o  o--o--o--o--o  o  o--o  o
|                    |        |
o--o--o--o--o--o--o--o--o--o  o

Much better! But can I do better still?

Plotting a maze¶

I'll use matplotlib to plot lines where the edges aren't:

In [5]:

%matplotlib inline
import matplotlib.pyplot as plt

def plot_maze(maze):
    "Plot a maze by drawing lines between adjacent squares, except for pairs in maze.edges"
    plt.figure(figsize=(8, 4))
    plt.axis('off')
    plt.gca().invert_yaxis()
    w, h  = maze.width, maze.height
    exits = {Edge((0, 0), (0, -1)), Edge((w-1, h-1), (w-1, h))}
    edges = set(maze.edges) | exits
    for sq in squares(w, h):
        for nbr in neighbors4(sq):
            if Edge(sq, nbr) not in edges:
                plot_wall(sq, nbr)
    plt.show()

def plot_wall(s1, s2):
    "Plot a thick black line between squares s1 and s2."
    (x1, y1), (x2, y2) = s1, s2
    if x1 == x2: # horizontal wall
        y = max(y1, y2)
        X, Y = [x1, x1+1], [y, y]
    else: # vertical wall
        x = max(x1, x2)
        X, Y = [x, x], [y1, y1+1]
    plt.plot(X, Y, 'k-', linewidth=4.0)

Let's compare the two visualization functions:

In [6]:

M = random_maze(10, 5)
plot_maze(M)  
print_maze(M)

o  o--o--o--o--o--o--o--o--o--o
|              |              |
o  o--o  o--o  o  o--o--o--o  o
|  |  |     |  |  |        |  |
o  o  o--o  o  o  o--o  o--o  o
|  |  |     |  |  |     |     |
o  o  o  o--o--o  o  o--o  o--o
|     |        |  |  |     |  |
o--o  o--o--o  o  o  o--o--o  o
|           |                 |
o--o--o--o--o--o--o--o--o--o  o

`pop` strategies¶

Now I want to compare how the maze varies based on theree different choices for the pop parameter.

(1) The default is deque.pop which means that the tree is created depth-first; we always select the node at the end of the frontier, so the tree follows a single branch along a randomly-twisted path until the path doubles back on itself and there are no more neighbors; at that point we select the most recent square for which there are neighbors:

In [7]:

plot_maze(random_maze(40, 20, deque.pop))

The maze with deque.pop looks pretty good. Reminds me of those cyber brain images.

(2) An alternative is queue.popleft, which creates the maze roughly breadth-first—we start at some root square , add an edge to it, and from then on we always select first a parent edge before we select a child edge. The net result is a design that appears to radiate out in concentric layers from the root (which is chosen by random_tree and is not necessarily the top-left square; below it looks like the root is in the upper-left quadrant).

In [8]:

plot_maze(random_maze(40, 20, deque.popleft))

The deque.popleft maze is interesting as a design, but to me it doesn't work well as a maze.

(3) We can select a cell at random by shuffling the frontier before popping an element off of it:

In [9]:

def poprandom(seq):
    "Shuffle a mutable sequence (deque or list) and then pop an element."
    random.shuffle(seq)
    return seq.pop()

plot_maze(random_maze(40, 20, poprandom))

This is an interesting compromise: it has some structure, but still works nicely as a maze, in my opinion.

What other variations can you come up with to generate interesting mazes?