I’ve created an updated version of the maze generation script to create somewhat more difficult mazes. This version uses a depth-first search algorithm to randomly link adjacent cells. Once all the cells have been linked there is only one path from one cell to any other cell in the maze.
The algorithm first randomly chooses a cell and pushes it onto a stack. From that current cell, it chooses a random adjacent cell and links them. The chosen adjacent cell is then pushed on the stack and becomes the new current cell. This process repeats until there are no more adjacent cells that can be chosen. Once no more adjacent cells can be chosen for the current cell, it is popped from the stack and the new top cell becomes the current. It is then checked for another available adjacent cell. Again, if there are no more adjacent cells that can be chosen, it is popped. Once the stack is empty all the cells are linked with exactly one path from one cell to any other cell. A random enter and exit point is chosen and the maze can be rendered.
The depth first search algorithm generates somewhat more difficult mazes than the original minimum spanning tree algorithm I used since it generates longer continuous paths before creating a branch. When the new branch reaches an existing path it creates a dead end. Given that the branches tend to be much longer you may end up having to follow the branch and many sub-branches before discovering it is in fact a dead end. With the minimum spanning tree algorithm the branches tended to be of a similar length and don’t typically wander far from the solution path.
The maze generator requires a browser that supports HTML 5 and the ‘canvas’ element. This is basically any modern browser except Internet Explorer. (IE users can try to use excanvas.js but you’re on your own.) You can try it out here. You can also download the javascript for it here.
Useful resources:
