Use the form below to configure your maze, then push the "generate" button to be amazed! Note that this page doesn't appear to fully work in Firefox, but it does work in Chrome. I'm still trying to figure that out.

## Discussion

So what is a maze from a technical stand-point? In the case above, a maze is a randomly generated spanning tree of a well connected graph. In a connected graph, there exists a path from every vertex to every other vertex. If for every pair of vertices, there are many pathways through the graph that connect them, then there is a higher variety of mazes we can generate from such a graph.

To generate a random spanning we tree, we do nothing more than a random breadth-first traversal of the graph. As we generate the spanning tree, each node in the tree points to its parent. This makes generating a solution to the maze trivial in the case that the root serves as the starting point of the maze, and a leaf serves as the exit point. To draw the maze's solution, we simply begin at the leaf and follow its lineage all the way back to the root. For circular mazes, the goal is to enter on the left, find the center, then exit on the right. So the solution path may retrace itself.

To me there is some question as to the whether the program is giving equal probability of generation to the set of all possible spanning trees. With some tweaks of the algorithm, I could probably make the mazes a bit more interesting. Most seem to have a fairly easy solution.