This post is all about creating mazes, and then solving them.

It all started with me looking for a new screensaver, xscreensaver giving me the option maze. I thought a little about creating something similar, found the difficulty not too high. The plan was to make it in CPP first, a language I’m reasonably comfortable with, then use HTML and JS to draw the proper maze and show the animations of Depth First Search solving the maze.

Generation of the Maze

We start with a rectangular grid. Each cell is not connected to any other. This can be modeled as a graph, G(V, E). In this model, we consider the cells to be the vertices, and the walls separating them to be the edges. Choose random vertices in the edges of the grid to be the start and end vertices. Now the problem reduces to finding a tree connecting the start vertex to the end vertex.

There are many algorithms to find a tree, given a connected graph. Prim’s algorithm and Kruskal’s algorithm have been classically used to find minimum spanning trees. Here, instead of the minimum weight edge, we choose any random edge. Once we generate the tree as H(V’, E’), we can break the walls represented by the edges in E’ in the rectangular grid to get a maze. More tweaks give better mazes. The tree also guarantees that there exists only one path between all the vertices in the tree, this applies for the start and end vertex, giving us a unique solution.

Solving the Maze:

During generation, we make sure there’s only one unique solution. So we can apply Depth First Search to find the solution. Start a DFS from start vertex. Each time DFS visits a cell, mark it green Failed DFS will change the color to red. DFS stops and traces back when the target vertex has been reached.

The CPP solution came fast, first the output was made in ASCII, using +,-,|. After a bit of googling, I found out that gnuplot can be used to generate an image. Then I coded up a solution the js, testing it on an html page. Canvas was extensively used. Animations were added. I came across real trouble adding the animations, so I went to ask in IRC. They say I’m terrible when it comes to coding in JS, so changing this has been added to the to-do list. Still, the code works now, thanks to their help.

The js demo can be found here.