Maze Design

Introduction

In a rectangular maze we should be able to have a unique path from the origin to the destination. Additionally, all cells in the grid should be reachable by a path. If we think of the squares in the grid as nodes, and an open wall between thm as a path we see that a perfect maze is the same thing as the minimum spanning tree of a graph where the squares are the nodes and each node (in the original graph) has an edge leading to each of its direct neighbors.

So our Maze building algorithm starts with a collection of all nodes, and a collection of all edges possible in the maze. Using Kruskal algorithm, we select random edges, one at a time from the collection of edges and add it to the maze (i.e. linking the two adjacent nodes in both directions, which amounts to tearing down the wall between them) - as long as adding of ths edge does not create a cycle. We stop once we have added n - 1 edges to connect n nodes.

We illustrate this process on a simple example. Here is a four by five maze at the start:

We add a few edges (a b), (b f), (i, j) (f, j), (g, h) (e, i) and get:

If we try to add the edge (e, f) we see that we would make a cycle, and so we discard this edge. But adding the edge (f, g) is OK:

When we finish, the maze may look like this:

So the path from a to t is

a-b-f-g-h-l-p-o-n-r-s-t

and the following paths lead to dead ends:

a-b-f-j-i-e

a-b-f-g-h-d-c

a-b-f-g-k-l-p-o-n-r-q-m

It is clear that adding any additional edge would result in a cycle.