escutcheon

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.

Maze

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.

» Posted: Monday, July 2, 2007 | Comments (51) | Permanent Link
fleuron

Comments

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

very nice. i wish i were more nerd like.

» Posted by jason on July 5, 2007 07:09 PM

Great. I never seen this before.

» Posted by Jon on July 8, 2007 08:39 AM

Great job. I’ve made maze generators before but I’m usually lazy and make binary tree mazes - just flip a coin for each cell and give it either a top of a left wall but never both and never neither. Great job again!

» Posted by David Millar on July 8, 2007 05:57 PM

Neat!

You state that the maze is “rendered at the client using only standard HTML and CSS.” This is not technically correct, since it is actually JavaScript that renders the maze.

» Posted by Ray on July 11, 2007 05:30 PM

err, i just tried 10000 x 10000 and it didn’t work!

» Posted by Anonymous on July 18, 2007 06:49 AM

genial

» Posted by abe on August 6, 2007 10:24 PM

Wow! Great job!

» Posted by Anonymous on August 20, 2007 01:02 PM

Incroyable ! Une grande idée couplée à un beau travail de programmation !!!
(in french in the text ;) !)

» Posted by smwarlock on September 16, 2007 08:06 AM

Very nice. Is there a way to get an embeddable version of the generated maze?

» Posted by n8nyc on September 20, 2007 09:04 AM

Sweet! Do I have your permission to try to rewrite this in a server side language (ColdFusion) and blog it? With attribution of course.

» Posted by Raymond Camden on September 20, 2007 10:34 AM

The one additional bit of functionality I’d like to add is the creation of a permalink to a particular generated maze. This would still require the generation to be redone each time at the client, but a randomly generated seed value for the random number generator itself, could become part of the URL. This would allow a particularly “good” maze to be referenced again.

n8nyc, if by “embeddable” you mean an HTML widget, that would be pretty straight-forward to do. At some point I can put something like that together.

Raymond (or anyone), please feel free to adapt the code.

» Posted by winter on September 23, 2007 08:39 AM

How do you print it? I am using Safari for windows.

» Posted by Yukob on November 30, 2007 09:46 PM

I am VERY excited about this and will use it in my website!

» Posted by Anonymous on December 23, 2007 10:55 PM

how do you copy and paste it into a program? I don’t like to waste ink, so I usually do that, but it doesn’t say “copy” when I right click it…

» Posted by fantasyfreak on January 5, 2008 02:06 PM

how do you copy and paste it into a program? I don’t like to waste ink, so I usually do that, but it doesn’t say “copy” when I right click it…

» Posted by fantasyfreak on January 5, 2008 02:06 PM

Oh WOW! I teach children and was looking for a great maze generator. I just found this through a Yahoo search! I love it!!! (^_^) Thanks so much!

» Posted by Jeremy on March 1, 2008 01:19 PM

Am I the only one that cannot figure out how to run this file - maze.js?
And how do I add solve.js to it as well?
How does it run when both of these have been “disabled” in the website demo?
I am obviously missing something here.
A clear explanation would be helpful. Thanks.

» Posted by Confused on May 16, 2008 12:58 PM

I think perhaps you are looking at the javascript files directly. They need to be included as part of the main HTML file to actually do anything. Do a “view source” of the main file here:

http://www.xefer.com/maze-generator

and look at the <script> tags in the <head> element.

» Posted by winter on May 16, 2008 04:35 PM

ummmm… i have the scripts for this… but how do i activate thwm?… i mean like what program do i load the scripts with? is it java?

» Posted by Iain'ttelling! on June 9, 2008 07:11 PM

This is neat! May I have your permission to use as part of my website redesign?

Originally, I was going to just have a static image of a random maze, but I couldn’t find any that would generate mazes past a certain width. Yours does that….and then some.

Being able to see a different maze every time they visit and then click a small button that does the generating and solving would be an added novelty for my visitors.

Obviously, I would place a visible credit blurb for you (or URL if you wish).

When time and work priorities permit, I do plan to actually study your Javascript, HTML, and CSS so I can see how it works.

Thanks so much! :)

~Eddie

» Posted by Eddie on June 26, 2008 02:40 PM

hello

» Posted by Anonymous on July 14, 2008 06:16 AM

Great maze generator!

Are there any requirements regarding use of the produced mazes? I have needs for mazes from time to time & this is very nice.

» Posted by Michael on August 14, 2008 02:20 PM

What I really need to do is package the maze code up as a simple component that could be dropped into any web page with a few simple parameters. I just haven’t gotten around to doing so.

Feel free to use the maze and/or the code as you see fit. Right now it would take some javascript work to insert something into another web page. It’s not a lot of work, but I haven’t had the time to get to it.

» Posted by winter on August 14, 2008 10:05 PM

I would at least like to list credit to you for the creation. How would you like the credit to be listed?

Thanks

» Posted by Michael on August 15, 2008 04:49 PM

I have been trying to find out how to make my own maze generator. But the wording is thoroughly confusing to me. I don’t understand all of it. Are maze’s made in an art/photo program or a word document. I tried Word and it doesn’t make the grid when I put in a table for 16 x 12. They aren’t equal squares (cells) So, I keep searching and ran across your site. I have Bible Student’s and I also just opened a family website. On Sampasite.com
Because of the copyright’s on almost everything I was wanting to make these things myself. My time is precious to me and if I can use your generator I would be most appreciative. From reading the above comments it seems like you approve of this.
I would of course, give credit to you! (Or if I need to make a generator? HELP! lol) I want to thank your son and YOU for making this possible for all of us!
Sincerely, Carolyn

» Posted by Carolyn on September 12, 2008 01:24 PM

Thanks for sharing this. Helped me define a design concept for our green roof studio. Just FYI that Master candidates use your site too! :)

» Posted by Jeremi on September 24, 2008 07:11 PM

How do you print it? I am using Safari for windows.

» Posted by Ferienwohnung Sizilien on October 6, 2008 02:27 PM

Very nice and thanks for sharing! I’m just learning JS, and I really appreciate reading your code to see how to animate web apps, and how to use JS effectively.

» Posted by Dave on November 18, 2008 12:08 AM

Excellent little toy! I love this thing.

The only change I might suggest (regarding the web page) is to change the tab order in the table cells. From looking at the generation box, one would think they could easily tab from Rows to Columns to Cell Size, but the tab order gets caught by going to the Maze ID between Rows and Columns when a maze is not generated, and the Maze ID and an unknown element when a maze has been generated.

Tiny cosmetic thing.

Absolutely love this!

» Posted by Argle on February 13, 2009 07:17 PM

Question: I am neither a programmer or a teacher but have children also. I have created mazes by hand so they could solve them. But I took it one step further. At every avenue of choice in the maze I added a number then I gave them a key that had math problems on it. If the key was done correctly they made it through. Is there a way of doing this to this maze? and can the maze be conformed with in the boundaries of of a monochrome line art image.

» Posted by James on June 20, 2009 11:31 PM

Nice work! Does exist a simple way to print them larger? For kids they are definitely too small

» Posted by Gianmaria on June 23, 2009 03:11 AM

To users with questions:

For wider trails, increase the cell size to 16, 24, 32, or whatever looks good to you. Then change the Rows and Columns numbers so the maze fits within your screen. I got good results with 21 rows, 35 columns and 32 cell size.

Then capture the screen image (e.g. Prnt Screen on a PC) and paste the image into a graphics program like Paint. Here you can modify the image any way you want before printing it.

» Posted by GG on July 13, 2009 11:16 AM

Hey! this generator is pretty cool !

I have few suggestions. It would be awesome if the “wrong” path could be in red instead in light blue !

Also, is it possible to calculate how much time it takes to solve it in ms !

Have a nice day !

» Posted by ForceMagic on January 26, 2010 02:26 AM

i agree tough mae i dont know if i could find my way through it got anything simpler

» Posted by Anonymous on January 28, 2010 11:44 AM

i am also doing a mouse maze project but i couldnt build this and if i cant make it then im sure a mouse would have no idea if you can build this your a nerd but on the other hand i wish that i could i would be happy just to find my way through

» Posted by nicole on January 28, 2010 11:46 AM

I have made some large mazes with your logic right now, and then asked your logic to solve it.

I find it mildly entertaining to watch it as it tries to figure it out. (I’m such a nerd)

Have you found where it makes unsolvable mazes?

» Posted by Karl on February 21, 2010 12:16 PM

With the algorithms used, it is impossible to make a maze that doesn’t have a solution. The solving algorithm nevertheless does account for the situation just in case at some day a different algorithm is introduced.

» Posted by winter on February 21, 2010 01:17 PM

good work

» Posted by bhk on May 13, 2010 01:21 PM

Thanks for making this public and open-source! I want to tweak it to produce mazes for my kids. I will probably add a “weave” option (passages can go over/under) and some other things to interest kids, like placing little images in the maze, and varying the location of the entry/exit.

Your “anfractuosity” - is that the same as what this guy calls “river factor”?

From looking at your code, you use Eller’s algorithm for a low-anfractuosity maze, and depth-first search (= “recursive backtracker”?) for high.

» Posted by Lars on May 27, 2010 07:50 AM

Had another thought. It might be fun to be able to interactively solve these mazes in the browser.

I.e. show a cursor at the “current” point; press an arrow key to advance in a chosen direction. The program advances the cursor in that direction, probably continuing around corners as far as the next intersection. Breadcrumbs are displayed, and colored gray if a dead end is reached, as in the auto-solver. You could even let the user press ‘d’ or something to mark the current branch (since the last intersection) as dead.

Sounds like fun… :-)

» Posted by Lars on May 27, 2010 08:02 AM

OK, I implemented interactive solving, and also (what I spent most of my time on) a terrain-generating aspect.

Here:
http://www.huttar.net/lars-kathy/maze/maze-generator.htm

Note that when you select the depth-first search (high anfractuosity) maze generation algorithm, the maze will tend to flow around the hills. This is a tweakable parameter in maze.js.

The hillshading only works in Firefox, sorry. This work in progress has many other limitations too, which I’ve documented in maze.js.

» Posted by Lars on June 1, 2010 05:04 AM

Lars, this is really nice looking. Great work!

» Posted by winter on June 1, 2010 08:13 AM

Amazing,

I have a similar project but i’m a bit lost would you be so kind as to help me to solve my maze ?

regards

phil

» Posted by Phil on July 14, 2010 04:21 PM

Phil, no problem. I sent you an email at the address you provided.

» Posted by xefer on July 14, 2010 05:02 PM

Pretty good on the emac, But it doesn’t work on Windows XP using ie8 though.

» Posted by Maze.js on November 5, 2011 12:50 PM

amazing!!!

» Posted by Anonymous on February 8, 2012 02:10 PM

Hi…
I’m just wondering if you would know how to create a javascript maze OVER and existing image. I have a labyrinth image and want to create a maze over the image? Thanks:)

» Posted by Monica on February 14, 2012 10:04 PM

Thank you very much! Your generation helps me in my thesis.

» Posted by Alina on February 18, 2012 09:35 PM

Wonderful, maybe i’ll implement this to generate random navigation between divs into my single page personal site during Christmas holidays

» Posted by luigi on November 20, 2012 03:50 AM

For a general rlnaacguetr maze, of width X and height Y, I believe the solution is this:For the perimeter, you need 2*(X+Y) walls.There are P = (X-1)(Y-1) internal posts and (X+1)(Y+1) posts in total.The smallest number of walls you can have is W = int((P+1)/2).The largest number of walls you can use for an open maze is W = P.By an open maze, I mean one where all the cells are have a route to every other cell.So, for a 16 16 contest maze, you would need 289 posts, 64 walls for the perimeter and between 113 and 225 internal walls to create an open maze.Any advance on that?

» Posted by Veronika on December 26, 2012 09:33 PM