Maze Generation A Programmer's Tale by Simon Rovder

Winter 2015. I'm sitting at home, the winds and rains are pushing against the poor window in my room. The sun is but a faded memory of a different life and I'm praying to whatever higher power would hear me, that the nail I used to hammer my window back into place earlier that day will hold. In other words, a typical Scottish Wednesday.

Anyway, I'm browsing random videos on Youtube, when I stumble upon a rather curious video that mentioned the "Largest Maze on the Internet". It was this little snippet right here:

And that was Goodbye to boredom, Hello competitiveness. 10 000 by 10 000 pixel maze? Surely I could do better than that... right..?

So I quickly whipped out my Python IDE and started coding. Snatching a bitmap writing library from the internet was the easiest thing and within a couple of minutes I had a DFS recursive maze carving algorithm. Not much, not very effective, but I wanted to see some result to bounce off of and here it was:

Yaaaaay! I have a maze!

I know what you're thinking... You're thinking "That's the tiniest maze I have ever seen." Well, I'm still thinking "Yaaaaaay!"

OK, now to make it larger. The stack is generally very unhappy with this kind of approach, so I decided to implement my own "stack". Basically storing the values a function should be called with recursively, and calling it only once the initial function exits. Not too shabby, the stack is happy and here's what I got:

Here's the thing with area... It scales quadratically with the length of the sides. It took my inefficient algorithm about 5 seconds to generate this 500 by 500 maze and unless my math is wrong, making a maze of 10 000 by 10 000 pixels would take about a half hour. And that is the current record holder, which I'd have to beat. In other words, a new, better algorithm was needed.

Picking a new algorithm was a very straight-forward task because of one key aspect. Parallelism. There are a variety of maze generation algorithms, but only one really stands out with respect to parallelism and it is the Recursive Division Method. The general idea is, you start off with an empty "room", split it in half with a wall, make a hole in the wall and repeat this on the two newly created rooms.

I think Wikipedia has a very nice GIF explaining it:

OK, looks pretty straight forward, let's give it a shot!

* Coding *

* Coding *

* Lunch *

* Coding *

At this point, I ran the code and a very crappy looking maze came out of it (I forgot to save this one). I got misled by how simple Wikipedia made it look and realised I had to add some order to the randomness. Due to the nature of the algorithm, one needs to be careful to make sure the walls never block out a hole in the wall. Turns out following two simple rules solves this:

  • Only build walls along an even coordinate
  • Only put the holes on odd coordinates

I trusted you, Wikipedia... OK, never mind, the fix has been added, code has been run and voila:

Looks pretty good! And seems to be very fast, I'm happy. OK, it's time to do the thing where I beat the record holder! Let's see, what was the record again? I look up the website mentioned in the video and... the video was wrong. The record is no longer 10 000 by 10 000, it is now 32767 by 32767.

OK, never fear, I have faith in my algorithm! Let's make a 40 000 by 40 000 one! Run all the generation!

Several minutes later, the algorithm is done, I open the file and snap. "File is Invalid". All the programs I used seemed to uniformly agree that the file is invalid. But why? Well... It turns out there is a reason the record holder is only as large as it is. The size limit on a Bitmap file is 32767 by 32767 pixels.

Ehm... Well this is awkward...

Now what?

It's not like I was going to give up here. I was very determined on beating the world record. So I devised a plan. It was time for some good old fashioned Divide-And-Conquer.

The plan was simple: Preprocess the required dimensions of the maze and split it into several smaller "tiles". Store the describing parameters of these tiles in a data structure and then generate all these tiles separately in parallel. Once all the tiles have been generated, create a .html file which includes all the tiles in a recursive table structure generated to "stitch" the tiles back together.

Or simply put: Generate the maze by parts.

Sounds simple enough, right? Well, it turns out, it really is simple. Due to the recursive nature of the algorithm and the two rules about placing walls and holes, it is quite easy to split the maze into smaller tiles and have them be independent of one another. This is the kind of result I got:

This was Victory. The limits of the Bitmap file were handled, the stitching worked, I wrote my own Bitmap file generating code (because nowhere on the internet could I find one that saved monochromatic bitmaps) and am ready to do this.

I ran the code and it was a success. A 40 000 by 40 000 maze has been generated. You can find it below, even though your browser might not be very happy with the amount of memory those images require and might leave some of them out (rest assured though, they are all there).

The record breaking 40 000 by 40 000 pixel maze

See, this is where most people would call it a day and decide they have something better to do. Not me though. I wanted to see how far I could go, I wanted to take it to it's naturally ridiculous conclusion, so I rented out a 16 core Compute Engine instance on the Google Cloud, mounted 150 Gigabytes of memory to it, put the code there and ran it to generate a 1 000 000 by 1 000 000 pixel maze.

32 hours later, there it was. 125 Gigabytes of monochromatic Bitmap files. I downloaded this monstrosity of a maze and have it taking up a significant chunk of one of my disks.

It was an interesting project, I had fun and potentially broke some world records.

...

Yaaaaay! : )