Quite a while ago, I stumbled across some documentation that described a simple maze generation algorithm. A few days ago I decided to play around with it and this is where I ended up.

If you’re familiar with what makes me tick, you’ll know that I really enjoy watching how complex and interesting patterns can evolve from a few simple rules. What you’ll see when you click through, I hope, is precisely that.

The Algorithm

So a little info on the maze drawing algorithm before I discuss what you see unfolding below. For the full explanation make sure you check out this page - it’s what I used. What’s happening in the first demo below is:

• After starting at position 2,2 on the grid, the algorithm randomly chooses an adjacent target location (up, down, left or right) that is exactly two cells away.
• After making its choice, it connects its current position with that location.
• When it successfully makes a choice, it remembers the new location and chooses again.
• When no locations are available - it has hit a dead end - it grabs the last successful position and tries again.
• When there are no available positions left to try, the maze is complete.

The result is a maze with exactly one path between any two possible points.

The Twist

I was initially thinking that it would be interesting to bias the maze by using the mouse to influence the likelihood of it growing in a particular direction - effectively enabling the user to paint the maze. This would have been interesting, but nothing special. After chatting about the project with James (the designer at work) I got thinking about how using a greyscale bitmap to influence the maze would be a novel way to make resulting pattern actually resemble something… as you’ll see… it almost does.

So I adjusted the algorithm to refer to a base bitmap and to choose direction based on the lightest (most white) of its current options. More than the end result, I think watching it render is the most interesting part of the experiment - almost hypnotic.

Instructions

Pretty straight forward…

• There are six images in the following demo - the first being a plain grey canvas and the original random algorithm
• Click at any time to snap-render the current image (it may take a second or two)
• Click again to jump to the next image

I’ve included mainly greyscale, high-contrast images as these seem to produce the best results. There is a demo in there with some colour, you’ll see that it still renders in colour bands, though the paths are much shorter.

Check it out (click to progress through the six images)

The next step is to decrease the resolution and play with it using the webcam as input. I think motion may make the visual boundaries more obvious. You’ll probably see it here in a few days.

I hope the demo performs well enough on your machine - it runs much faster locally than through the browser.

Link: The original maze algorithm explained
Link: Lots of info on many more maze algorithms