In 1980, while working at Texas Instruments, I wrote a program to draw mazes one night. My first version started out quite simple and elegant, but the mazes it printed (on our departments line printer) weren't very difficult to solve. The next night I improved the mazes produced by the program, adding tweaks here and there in the code to make the mazes harder to solve. I added long winding dead ends, corridors with loops and so forth. The mazes caught on and soon many cubicles had the three page mazes with hand drawn solutions as decoration. Marketing folks headed to a trade show saw these mazes and wanted the program to run on a system on the trade show floor so that personalized mazes could be handed out as trade show swag.<p>Unfortunately, version two of program wasn't very pretty with all the little hacks and tweaks, but it did make fun mazes. Six or nine months later I got a call from someone wanting help with a Pascal program (I was one of the Pascal experts in the company at the time so I would get calls like this). As they described the program on the phone, I recognized it as my maze program. They said they got it off of the distribution tape for the TI Pascal compiler (I had programmed the program in Pascal). I was mortified that someone had made the ugly program a sample program for a TI product but at least it didn't have my name on it!
If you want to create a maze on paper as a rainy day kind of activity, the process is basically the same but manual:<p>1. Mark a start point and an end point, and draw the solution using yellow marker. A moderately windy path will do fine. Don't overdo it, or you'll actually make it too easy.<p>2. Using the same yellow marker, draw branching paths off from the solution path, and make branches off the branches until the maze area is too cramped to draw more.<p>3. Draw walls with black marker between and around the yellow paths.<p>4. Amaze your friends.
I actually had some fun reading about maze algorithms some time ago.
Here are two good links:<p><a href="http://www.astrolog.org/labyrnth/algrithm.htm" rel="nofollow">http://www.astrolog.org/labyrnth/algrithm.htm</a><p><a href="http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap" rel="nofollow">http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...</a><p>The first link is interesting because it describes some maze toponomy (types and characteristics of mazes)
The second has a lot of algorithm implementations with nice demos.<p>Fun stuff :)
My favorite presentation ever, by Jamie Buck at RubyConf2011, is a great interactive survey of maze generation algorithms -- <i>"Algorithm" is Not a Four-Letter Word</i>:<p><a href="http://www.jamisbuck.org/presentations/rubyconf2011/" rel="nofollow">http://www.jamisbuck.org/presentations/rubyconf2011/</a>
A one-liner maze builder for the C64:<p><pre><code> 10 PRINT CHR$(205.5+RND(1)); : GOTO 10
</code></pre>
<a href="http://10print.org/" rel="nofollow">http://10print.org/</a><p><a href="http://retroplay.co/c64/" rel="nofollow">http://retroplay.co/c64/</a> (click the play button for a C64 emulator)
Jamis Buck has a fantastic series of blog posts about maze generation[1]. It looks like he's no longer updating the blog, but all of the entries are still up. Start at the bottom and work up.<p>[1] <a href="http://weblog.jamisbuck.org/under-the-hood" rel="nofollow">http://weblog.jamisbuck.org/under-the-hood</a>
Something interesting about this type of maze is that you can use a flood-fill algorithm on the walls to find a solution. This is because there's exactly one path between the start and finish, and that path divides the the maze into two parts.<p>There are some examples at the bottom of this page: <a href="http://www.brian-gordon.name/portfolio/maze.html" rel="nofollow">http://www.brian-gordon.name/portfolio/maze.html</a>
There are lots of different ways to build mazes [1]. My favorite is Prim's Algorithm, which "grows" a maze.<p>[1] <a href="http://en.wikipedia.org/wiki/Maze_generation_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Maze_generation_algorithm</a>
I always recall this one from 1981 Compute Magazine<p><a href="https://archive.org/stream/1981-12-compute-magazine/Compute_Issue_019_1981_Dec#page/n55/mode/2up" rel="nofollow">https://archive.org/stream/1981-12-compute-magazine/Compute_...</a><p>No stack, just generated the mazed directly in screen memory.
One cool way to make a maze is how the old Windows OpenGL maze screensaver did it, starting with every square having full walls, starting somewhere, and making sure every room has at least one broken wall and they're all connected, traversing it. I forget how exactly it picked the end point. I used that when I wrote a Javascript game about that maze but it was hosted on nyhacker and it's gone now. Might still have it around somewhere on a hard drive though.
If you want to see one of these working and in action you can check out one of our demos at
<a href="https://www.algorithmia.com/demo/pathplan" rel="nofollow">https://www.algorithmia.com/demo/pathplan</a>
I don't have time to read all the links in this thread but I used to draw mazes all the time in school. My approach was to start with an "in" tube and start branching it, so long as I kept one branch open I could split and recombine all the others and know that I still had a valid maze. After I had filled up most of the page I would stop and declare the end position.
It might not be clear from my description but I kept adding paths to the maze by doubling back on what was already there and building it out so it looked like a brain.
The main point is that I kept one path open, never closing all my paths in a dead end. That way I knew there was a solution but since I did them so fast I wouldn't know the solution myself.
I implemented this in JS some time ago to get into JS. I visualized the carving of the maze and still think it's pretty cool to look at it.<p>Here's the link: <a href="https://googledrive.com/host/0Bzr7EVRN_St0UkhIdUdrQ3o4T0E/index.html" rel="nofollow">https://googledrive.com/host/0Bzr7EVRN_St0UkhIdUdrQ3o4T0E/in...</a> (might load slowly in the beginning, give it a bit of time)<p>Source: <a href="https://github.com/arya-s/A1/blob/master/js/A1Maze.js" rel="nofollow">https://github.com/arya-s/A1/blob/master/js/A1Maze.js</a>
Looks amazing similar to my sophomore data struct project:
<a href="http://ezekiel.vancouver.wsu.edu/~cs223/projects/mazegen/mazegen.pdf" rel="nofollow">http://ezekiel.vancouver.wsu.edu/~cs223/projects/mazegen/maz...</a>
Mazes are certainly fun. Here's a javascript maze solver I wrote a while back, including a REST url for building your own maze. <a href="http://www.primaryobjects.com/maze" rel="nofollow">http://www.primaryobjects.com/maze</a>
My favorite way to generate a maze (imperfect, but fun):
<a href="http://www.conwaylife.com/wiki/Maze" rel="nofollow">http://www.conwaylife.com/wiki/Maze</a><p>quickstart:
<a href="https://github.com/thearn/game-of-life/blob/master/rule_string.py" rel="nofollow">https://github.com/thearn/game-of-life/blob/master/rule_stri...</a>
If you want to play around with a maze then there are examples in many languages at Rosetta Code, the python one is nice
<a href="http://rosettacode.org/wiki/Maze_generation#Python" rel="nofollow">http://rosettacode.org/wiki/Maze_generation#Python</a>
Disjoint sets.<p>1) Each cell in the maze is a set.
2) Randomize walls. Check if wall to be removed are already in the same set. Merge the set if wall is removed.
3) Repeat until entire maze is in one set.<p>DFS seems a bit odd for generation. For generating a solution, it would be what I would do.
Also of note, Eller's Algorithm for mazes:<p><a href="http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm" rel="nofollow">http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller...</a>