News for hackers. Stuff that matters.
Re:How To Build A Maze by todd8 on Monday March 24, 2014 @07:02PM (#7462386)
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.

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!

Re:How To Build A Maze by Deestan on Monday March 24, 2014 @12:46PM (#7459280)
If you want to create a maze on paper as a rainy day kind of activity, the process is basically the same but manual:

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.

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.

3. Draw walls with black marker between and around the yellow paths.

4. Amaze your friends.

Re:How To Build A Maze by Vaskivo on Monday March 24, 2014 @12:30PM (#7459159)
I actually had some fun reading about maze algorithms some time ago. Here are two good links:

http://www.astrolog.org/labyrnth/algrithm.htm

http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorit...

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.

Fun stuff :)

Re:How To Build A Maze by jmduke on Monday March 24, 2014 @12:37PM (#7459212)
My favorite presentation ever, by Jamie Buck at RubyConf2011, is a great interactive survey of maze generation algorithms -- "Algorithm" is Not a Four-Letter Word:

http://www.jamisbuck.org/presentations/rubyconf2011/

Re:How To Build A Maze by fizwhiz on Monday March 24, 2014 @02:46PM (#7460388)
Found the youtube video where he's presenting this:

https://www.youtube.com/watch?v=4zjPm39kPDM

Good stuff.

Re:How To Build A Maze by bhrgunatha on Monday March 24, 2014 @10:50PM (#7463495)
That presentation was recorded by Confreaks [1] who let you download the video (and audio!) at different resolutions.

The Ruby community is really well-served by Confreaks [2] - they record and provide videos from many different Ruby conferences and have (over the years) expanded their remit to include Javascript, Scala and more.

[1] http://confreaks.com/videos/662-rubyconf2011-algorithms-is-n...

[2] http://confreaks.com/events

Re:How To Build A Maze by rabino on Monday March 24, 2014 @02:38PM (#7460305)
wow. thanks for sharing this. It's an awesome presentation.
Re:How To Build A Maze by thangalin on Monday March 24, 2014 @01:41PM (#7459782)
A one-liner maze builder for the C64:

    10 PRINT CHR$(205.5+RND(1)); : GOTO 10
http://10print.org/

http://retroplay.co/c64/ (click the play button for a C64 emulator)

Re:How To Build A Maze by ja27 on Monday March 24, 2014 @04:51PM (#7461361)
I used to type an equivalent of this into C64s in stores. I even had a few of these printed out. It does tend to have a lot of short loops but sometimes you get an amazingly complex path for such a simple method.
Re:How To Build A Maze by itp on Monday March 24, 2014 @12:29PM (#7459149)
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.

[1] http://weblog.jamisbuck.org/under-the-hood

Re:How To Build A Maze by brianpgordon on Monday March 24, 2014 @01:20PM (#7459573)
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.

There are some examples at the bottom of this page: http://www.brian-gordon.name/portfolio/maze.html

Re:How To Build A Maze by jffry on Monday March 24, 2014 @12:19PM (#7459087)
There are lots of different ways to build mazes [1]. My favorite is Prim's Algorithm, which "grows" a maze.

[1] http://en.wikipedia.org/wiki/Maze_generation_algorithm

Re:How To Build A Maze by magicarp on Monday March 24, 2014 @03:54PM (#7460948)
A few weeks ago I was fooling around implementing algorithms from that page and Prim's Algorithm looked really cool, so I implemented a version with randomized colors on my homepage: http://jeff.is/
Re:How To Build A Maze by greggman on Monday March 24, 2014 @03:30PM (#7460767)
I always recall this one from 1981 Compute Magazine

https://archive.org/stream/1981-12-compute-magazine/Compute_...

No stack, just generated the mazed directly in screen memory.

Re:How To Build A Maze by jimmaswell on Monday March 24, 2014 @06:19PM (#7462079)
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.
Re:How To Build A Maze by doppenhe on Monday March 24, 2014 @01:33PM (#7459696)
If you want to see one of these working and in action you can check out one of our demos at https://www.algorithmia.com/demo/pathplan
Re:How To Build A Maze by johnwatson11218 on Monday March 24, 2014 @02:42PM (#7460358)
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.
Re:How To Build A Maze by intruder on Monday March 24, 2014 @02:51PM (#7460436)
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.

Here's the link: https://googledrive.com/host/0Bzr7EVRN_St0UkhIdUdrQ3o4T0E/in... (might load slowly in the beginning, give it a bit of time)

Source: https://github.com/arya-s/A1/blob/master/js/A1Maze.js

Re:How To Build A Maze by waynecochran on Monday March 24, 2014 @01:32PM (#7459690)
Looks amazing similar to my sophomore data struct project: http://ezekiel.vancouver.wsu.edu/~cs223/projects/mazegen/maz...
Re:How To Build A Maze by primaryobjects on Monday March 24, 2014 @01:11PM (#7459481)
Mazes are certainly fun. Here's a javascript maze solver I wrote a while back, including a REST url for building your own maze. http://www.primaryobjects.com/maze
Re:How To Build A Maze by thearn4 on Monday March 24, 2014 @10:21PM (#7463376)
My favorite way to generate a maze (imperfect, but fun): http://www.conwaylife.com/wiki/Maze

quickstart: https://github.com/thearn/game-of-life/blob/master/rule_stri...

Re:How To Build A Maze by dmoo on Tuesday March 25, 2014 @03:24AM (#7464391)
If you want to play around with a maze then there are examples in many languages at Rosetta Code, the python one is nice http://rosettacode.org/wiki/Maze_generation#Python
Re:How To Build A Maze by tankerdude on Monday March 24, 2014 @06:28PM (#7462144)
Disjoint sets.

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.

DFS seems a bit odd for generation. For generating a solution, it would be what I would do.

Re:How To Build A Maze by kd0amg on Monday March 24, 2014 @08:03PM (#7462747)
I'm told DFS tends to produce easier mazes in the sense that after you've made a bit of progress, false paths typically end more and more quickly.
Re:How To Build A Maze by tibbon on Tuesday March 25, 2014 @12:20AM (#7463774)
Also of note, Eller's Algorithm for mazes:

http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller...