Carving "perfect" mazes with Perl

As a lunch-time programming exercise I've been writing a maze-building Perl script. After some minor hair pulling I finally got it working. The snippet to the right is a section of a 100x100 cell "perfect" maze generated by the script. Click on the picture to see the whole thing. Warning: can induce seizures! (okay...not really, but it's still difficult to look at for long).

Why is it called a "perfect" maze? Simple: every cell in the maze is reachable from any other cell and there is only one solution. Also, there are no loops or unreachable cells. Perfect mazes are the ones you see printed most often in newspapers and such.

According to Think Labyrinth there are several different ways to generate perfect mazes. The most obvious way is to use an algorithm called a recursive backtracker. This algorithm starts with a completely filled maze and carves passages into it until the maze is complete. The pseudo-code looks like this:

1. Start with a random "room" in the maze.
2. Get a list of neighboring rooms that have not been visited yet.
3. Knock down the wall between the current room and a randomly selected neighbor. Push the rest of the rooms onto a stack.
4. Move into the selected neighbor.
5. Keep repeating steps #2 - #4 until you hit a room with no unvisited neighbors. You then pop one of the unvisited rooms from the stack (#3) and repeat #2 - #4 until the stack is empty.

You can implement this algorithm without using recursion but the recursive solution is simpler, and in my opinion, more elegant. Then again, anything solved using recursion is going to be elegant. I guess my fondness for Lisp is showing through again!

Anyway, click here to download the script and some nasty little .gif files I made so the maze can be viewed in a browser. To run the script simply extract the ZIP archive and do something like this:

perl maze.pl [x] [y] > maze.html

where x and y are the desired dimensions of the maze. To generate the 100x100 sample maze above I did this:

perl maze.pl 100 100 > maze.html

This generates a gigantic HTML file that upon opening with your browser will display a maze similar to what you see above. If your computer is slow or has little memory I'd suggest starting with something a little smaller like 20x20.

Comments

[Dejunai]

This is such solid code, I am amazed that there are no comments. I found this code a few months ago, tho I could make no use of it for my particular application. I want to MOD a PC game by the name of Oblivion ( by Bethesda Softworks ). I swear I am not 14 ( 40-ish actually ). The game has the ability to randomize, and be modded; However the developers made very little use of the randomization possibilities. As such I have wanted to develop a MOD that can add some random-ness to the game. A maze is the perfect starting point. The engine however is limited by a script-system, that does not allow advanced programing such as stacks. Which makes maze-making a bit more difficult, :)... This post pointed me at ThinkLabyrinth and I cannot be more grateful. Using what I found there I have been able to make randomly generated maze-like environments. However, I have recently discovered I can indeed use an outside utility to alter the MOD files. Making Perl very useful to the end application. Tho "perfect" mazes aren't the goal, I have effectively merged some of your code into a maze Perl script I wrote a few years ago.

I just wanted to say "Thank You"; and if you ever want to dabble in a MOD for a game, feel free to contact me. :D

This is an image link to a maze I have built using your code and mine: http://img483.imageshack.us/my.php?image=20070311072807il8.jpg

[del]

Hey, thanks for the kind words, Dejunai. Judging by the Google keywords that people are using to find my maze-building posts I assumed that they were mostly college students looking for solutions to programming exercises. It's good to know that folks besides students trying to cheat on assignments are finding my code useful! Good luck with your game MOD!

[Yula Loginova]

Great maze!!!! It's just like where's the way in and out? I'm not a student looking for programming solutions, rather a graphic designer looking of ideas to feed my inspiration. And this maze was really useful for a calendar based on different kinds of puzzles, something kinda like "Finding Solutions" theme. So I really need to know where to start and finish, not only to hypnotize people by its visual form, but also to make them intrested in finding a way out. Thans in any case.

[Vince Pelss]

I modified the code to be used at:
http://www.emogic.com/cgi/3dmaze/3dmaze.cgi
In my retro rat 3d dungeon style maze.

I use css vs images for your maze code.

[del]

Vince - That's awesome! I love what you did with the maze code. I didn't think of using CSS instead of images, mostly because I didn't know much about CSS at the time!