HTML5 Maze Generator Demo
Posted by jimblackler on Jan 4, 2012
This next project is a bit of fun for the new year. It’s a maze generator written with JavaScript/HTML5 Canvas. I was thinking about possible algorithms to generate classic maze puzzles and thought it might be interesting to write one.
The algorithm is simple at heart. It’s from a class of puzzle generators that work in conjunction with a solver algorithm; changing the puzzle step by step while continuously trying to solve it to see if it’s still viable.
Method
The maze generator starts with a blank grid. One in four squares are blocked with base ‘columns’. It keeps a list in memory of all the squares on the grid that could be filled in, the ‘blockable’ squares. It then solves the grid in its current state by a classic flood-fill algorithm.
In the solve operation every square that forms part of the shortest path (or joint shortest paths) from top left to bottom right is detected (this are the squares painted as red in the demo visualizer). Because in the early phases there are many equally good routes, it is typical that much of the maze can be painted red.
These squares are then searched in random order to find one that is still in the ‘blockable’ list. It’s removed from the list, the grid square is blocked, and the solver re-run. If the solver reports that every blank square on the grid is no longer accessible from every other square, that piece cannot be blocked without breaking the puzzle. We ‘unblock’ it, but we don’t put it back in the list because it can *never* be blocked without breaking the puzzle. If the solver reports the puzzle is still universally accessible, the current grid is rendered to the screen and the solver repeats.
When there are no squares remaining from the path that are in the blockable list, the algorithm just attempts to block any random squares in the list (with the same accessibility checks) until nothing remains in that list. Then the puzzle is complete.
The reason that squares along the current best route are considered first is that in doing so the length of the solution path can only be increased. Without this constraint virtually every maze ends up with a solution that is too short and almost always forms a diagonal path roughly direct from top left to bottom right.
Please take a look at the demo. Different sized puzzles can be selected (you can customize the values if you’d like to edit the URL parameters). When the puzzle is complete the red solution indicator can be turned on and off. If you’d like to look at the source you can do so in Chrome Web Developer tools or similar tools in other browsers.