While this is my own take on the subject, with a
different motivational bent, I
certainly should acknowledge the excellent deck put together by Jamis Buck.
I liked it so much, I am using the same deck.js web presentation framework.
And, as long as I'm throwing out external links to any and all
related pages, I would be remiss if I didn't include the relevant
Wikipedia page on maze generation.
And, of course, the disclaimer: I make no guarantees as to the
correctness of the material or corresponding code. That being
said, I've made every attempt to test and verify the same. If
you come across a browser incompatibility, inaccuracy, or
suspected bug, I will do my best to address the issue.
Graphs
A graph is a collection of vertices
or nodes, represented by the circles, connected by
edges, shown as lines. You will find this commonly
denoted as G = (V, E).
Vertices
A vertex can represent lots of different things
Vertices as points in a plane
Vertices as components of an HTML page
Edges
Like vertices, an edge can represent a physical connection or
an abstract concept.
Edges as line segments
Edges as parent/child relations
between HTML elements
Directed Edges
In some applications, an edge may have a particular
direction
In this context, the vertex usually represents the state
of a system, and the edge represents movement between states.
This example is also acyclic, in which
no edges form a loop or cycle. In other words, you
can't re-visit a state you were previously in.
A Directed Acyclic Graph is commonly referred to as a
DAG
Weighted Edges
Some applications assign weights to edges. The interpretation of a
weight depends on the partuclar application.
Weights as line segment lengths
Weights shown as line width, meant to represent
a flow or capacity
Planar Graphs
A graph whose vertices and edges are on a 2-D surface
is planar if none of the edges cross.
A non-planar graph
The same vertices and edges, but a planar embedding
Graph Properties and Nomenclature
A graph is connected if there is a path between all
possible pairs of vertices.
A graph is complete if every vertex is directly
connected to every other vertex.
A complete graph with five or more vertices is always
non-planar.
For planar graphs, the number of edges is proportional to the
number of vertices. In computer science notation,
we have O(|V|) edges, where |V| is
the number of vertices.
If you try to create an edge that crosses another, that edge
will be removed.
If you move a vertex and its edges now cross others, those
edges are removed.
Planar Graphs and Mazes
Click the "Graph/Dual/Maze" legend to hide or show each
component.
Enough, already, what does any of this have to do with mazes?
A maze can be thought of as a graph, where the edges of the
graph correspond to walls in our maze.
Clearly, when thinking about walls and mazes, we can
intuitively see why edges/walls are not allowed to cross over
each other.
The task at hand is to transform a planar graph, which
defines a set of possible mazes, into a maze.
The graph on the right is just a regular grid of squares,
where every vertex is connected to its nearest neighbors. Each
of these edges is a wall that may be in our maze. In
math-speak, the maze is a subset of our original graph.
The Graph's Dual
Click the "Graph/Dual/Maze" legend to hide or show each
component.
The method we will use to generate a maze works by first
determining the graph's dual.
In our maze case, you can think of the dual graph as
the paths we can (potentially) walk along.
Every face in the original graph is represented as a
vertex in the dual graph. A face is a
region of the graph that is completely enclosed by a set of edges.
Edges of the dual are path segments that connect two
faces. Each edge of the dual crosses an edge of the original
graph.
Example Dual
A graph and it's dual
This graph shows the vertices as circles and marks each face
with a rectangle. Edges in the dual graph are shown in purple.
Not shown in the previous example was the dual's
vertex for the outside face of the original
graph. Click the outside face node to toggle edges
that connect to the outside face.
There is a reason it is called the dual. The original
graph is the dual of the dual. In other words, if you think of
computing the dual as an operation on a graph, D(G),
then D(D(G)) ==> G*, where G* is a graph
isomorphic to G.
Maze Properties
What sorts of mazes do we want to generate?
All areas of the maze should be reachable
The maze should not contain any loops
We should remove the minimum number of edges
Any spanning tree of the dual graph satisfies these
constraints.
Spanning Tree
Click the graph to highlight a spanning tree
Suppose we have the connected graph G = (V, E).
A spanning tree T of G is a subset
of G.
It contains all the vertices V of G.
It contains (|V|-1) edges.
All vertices must be reachable by following edges in the
spanning tree.
By definition, a graph that is a tree does not contain
any loops or cycles.
Spanning Tree to Maze
Click to overlay original graph
Edges in the dual graph correspond to (and cross over) an edge
in the original graph.
In our dual graph's spanning tree, if we have included an
edge, then we need to make a path between those two faces in
the original graph.
To make that path, we remove the edge in the original graph
that our spanning tree crosses.
Every edge included in the dual graph's spanning tree
represents an edge we remove in the original graph.
Finding a Spanning Tree
For a given graph, there can be an exponential number of
possible mazes. That just means there are lots of spanning trees
we could find.
Click the graph to animate
White: Not
visited
Blue:
Candidate node
Red: Visited
The strategy for finding a spanning tree is fairly
simple:
Start at any node in the graph.
For all the nodes we are connected to, select any unvisited
node and add it to our set of candidate nodes.
Note, we also need to remember the edge we traversed from the
current node to our candidate node.
If there are no unvisited neighbors, mark the current node
as being visited.
Select a new node from our set of candidate nodes.
When we run out of candidate nodes, we are done.
Maze Generation Strategies
Our strategy for selecting the next node will
greatly influence the "shape" of our maze.
The method implemented here is to randomly choose
our next node using two different strategies. We will either:
Extend our spanning tree from the most recently
added candidate node.
Extend our spanning tree by choosing a node at random
from the set of all candidate nodes.
Once we have selected a node, we look at all of its unvisited
neighbors and pick one at random.
When generating a maze, the animation shows the growth of the
dual graph's spanning tree. A red face shows the current face
being visited, blue represents a candidate, and
grey for a face that is no longer in the candidate pool.
When growing our tree, P(LIFO) is the probability we
will visit the most recently added node. LIFO stands for Last
In, First Out.
In this case, with probability 75%, our next node will be a neighbor
of the most recently added node. Play around with this
parameter to get a feel for how it affects the overall shape
of the maze.
Notice how a low P(LIFO) results in much shorter path
lengths in the maze.
Just like the editor, you can add, delete or move around nodes
in the graph, and add edges between them.
3D Maze
And, at long last, the 3D Maze is something we can now turn
into an explorable environment!
Click the newly enabled 'Enter 3D Maze' button to render the
maze in a new browser tab.
To explore, you can use the arrow keys to turn and walk
forwards.
Insignias on the ground will turn from gold to red as you
move onto them.
