Let's have some fun with graph theory. Today, I'm showing how to generate a random maze with Quickgraph. Before going into the code, let see how we are going to make it.
The maths
Consider that you have a regular lattice like in the image below. If you consider each edge as a path, the lattice represents a highly connected network. The question is: which edge should you delete to make it a maze ?
The answer to this questions is trivial in terms of graph theory: you just need to extract a tree out of the graph and this will be a maze. In fact in a tree, there is only 1 way from the root to each of the leaf, like in mazes. This leaves us with the problem of extracting a tree from a graph.
The maze generation example was originaly brought up by David Wilson (a researcher from Microsoft). He has designed an efficient algorithm, known as Cycle-Popping Tree Generator, for extracting random tree out of graphs. This algorithm is implemented in QuickGraph so we have all the tools on our hand to start solving the problem.
The code
Let's start by building the graph and the lattice. For the cycle popping algorithm, we need a BidirectionalGraph (a graph where you can iterate the out-edges and the in-edges of the vertices). For the lattice, we create a two dimensional array of vertices and finally, we store the vertex -> lattice index relation into a Hashtable:
// We need a few namespaces for QuickGraph
using QuickGraph.Concepts;
using QuickGraph.Concepts.Traversals;
using QuickGraph.Algorithms.RandomWalks;
using QuickGraph;
using QuickGraph.Providers;
using QuickGraph.Collections;
using QuickGraph.Representations;
public class MazeGenerator
{
// the bidirecitonal graph
private BidirectionalGraph graph = null;
// 2D array of vertices
private IVertex[,] latice;
// v -> (i,j)
private Hashtable vertexIndices = null;
Next, we write the method that will populate the graph. If the lattice has m rows and n columns, the method will create m*n vertices and (m-1)*(n-1)*2 edges to link those vertices:
public void GenerateGraph(int rows, int columns)
{
this.latice=new IVertex[rows,columns];
this.vertexIndices = new Hashtable();
this.graph = new BidirectionalGraph(false); // false = does not allow parallel edges
// adding vertices
for(int i=0;icolumns;++j)
{
IVertex v =this.graph.AddVertex();
this.latice[i,j] = v;
this.vertexIndices[v]=new DictionaryEntry(i,j);
}
}
// adding edges
for(int i =0;icolumns-1;++j)
{
this.graph.AddEdge(latice[i,j], latice[i,j+1]);
this.graph.AddEdge(latice[i,j+1], latice[i,j]);
this.graph.AddEdge(latice[i,j], latice[i+1,j]);
this.graph.AddEdge(latice[i+1,j], latice[i,j]);
}
}
...
There is a bit of index gymnastics in the code above, but drawing it on a sheet of paper should make things clear. I will not focus on the drawing code on this blog: I'm using basic features of System.Drawing namespace, nothing really "extreme". So back to our maze problem, we need to apply the cycle-popping algorithm to generate a maze.
Cycle-popping algorithm
The cycle poping algorithm is implement in the QuickGraph.Algorithms.RandomWalks.CyclePoppingRandomTreeAlgorithm class. Using this algorithm is quite straightforward:
// (outi,outj) is the coordinate of the exit vertex in the lattice
// (ini,inj) is the coordinate of the entry vertex in the lattice
public void GenerateWalls(int outi, int outj, int ini, int inj)
{
// we build the algo and attach it to the graph
CyclePoppingRandomTreeAlgorithm pop = new CyclePoppingRandomTreeAlgorithm(this.graph);
// finding the root vertex
IVertex root = this.latice[outi,outj];
if (root==null)
throw new ArgumentException("outi,outj vertex not found");
// this lines lanches the tree generation
pop.RandomTreeWithRoot(root);
At this point, pop contains a dictionary which associates each vertex to it's successor edge in the tree. Remember that the tree is directed towards the root here. This dictionary has two roles: it contains the edges that are part of the maze (that's what we needed) and even better you can build the way-out using the dictionary by following the successors until you hit the root:
// we add two fields to the class:
private VertexEdgeDictionary successors = null;
private EdgeCollection outPath = null;
...
///////////////////////////////////
// GenerateMaze continued
// storing the successors
this.successors = pop.Successors;
// build the path to ini, inj
IVertex v = this.latice[ini,inj];
if (v==null)
throw new ArgumentException("ini,inj vertex not found");
// building the solution path
this.outPath = new EdgeCollection();
while (v!=root)
{
IEdge e = this.successors[v];
this.outPath.Add(e);
v = e.Target;
}
}
That's it. We can now draw the walls of the maze and draw the solution on top. Thank you Mister Propp and Mister Wilson! (The source of this example is available in the QuickGraph CVS)
