Maze Generator
My son has been interested in mazes recently. This seemed like the perfect opportunity to show that I could actually do something useful on the computer (in his eyes), so I decided to put together a maze generator. Maze generation is actually relatively trivial and it is often one of the first examples of a recursive algorithm given to computer science students.
Generator: here. Main source code: here.
I’ve always found the idea of recursion magical in some way—its one of the things that really hooked me into programming.
A 30 by 70 maze on a 6 by 6 pixel grid
I wanted something that would be rendered at the client using only standard HTML and CSS. This requires no server-side resources, demands no plug-ins and allows for the mazes to be printed out easily and with good quality.
This implementation uses a standard depth-first search algorithm. It’s one of the simplest, but has the benefit of generally creating the most difficult mazes.
I was able to put together the recursive function pretty quickly, but soon realized that the standard browsers all limit the depth of recursion they allow. Since tail-recursive algorithms can be reworked using iteration, I was forced to change things around to use that technique instead. An examination of the source code shows that this basically means the stack must be managed by hand instead of automatically.
Update: I recently added code to solve the maze also.
Update: Support for for very large mazes was added. While large mazes could be made previously, the browser would be unresponsive, and in some cases warning dialogs appeared stating that the script was taking too long. The code has been reworked to give time back to the processor, so this should not happen. Mazes are now limited only by available memory and the particular browser. In practice the limit is on the order of 200,000 to 500,000 total cells, say 1000 rows by 200 columns, etc.
I love it. A friend of mine wrote a Perl maze system, and a base class that allows others to train their own maze-solving mice.
What nerds we are.
» Posted by Rich on July 5, 2007 11:08 AM