Generating mazes from pictures, or “Masking Entropy”
Entropy is a measure of chaos. Higher entropy equals more unpredictability, lower entropy equals less disorder.
Mazes are collections of paths usually connecting one or more entrances to one or more exits. A regular maze looks like this:
If you look closely, you can see that some areas of the maze are slightly more orderly: straight corridors instead of ninety degrees turns and bends. But, overall, the maze looks pretty chaotic.
Below is a “bitmap mask”:
The black areas represent a ‘0’, while the white areas represent a ‘1’. This picture only uses two colors, but generally speaking bitmap masks can use every possible channel value to encode all different kinds of information.
The process of masking is what lets you overlay a picture on top of another by multiplying its transparency by the color values of a mask:
The concept can be extended to many other uses, such as encoding height maps for 3-D games as 2-D projections:
But that’s enough premise. We’re going to talk about mazes, about entropy and about masks.
Let’s get to work.
Part 0: Generating a maze
In order to achieve our goal, we must first understand how a maze is generated. For the purpose of this post, I’m going to use the recursive backtracker algorithm.
This is a depth-first search algorithm, meaning that it starts at a given node (of a graph, but you can imagine it as a grid) and ‘naively’ explores until it hits a dead end. Then it backtracks to a point where there are still unexplored neighbors left, and proceeds with its exploring until each cell has been visited at least once.
Let’s see how we can turn these words into an actual maze. From now on, all the code is going to be Python 2.x and the coding environment will be Processing (in Python mode).
Here’s my implementation, and our first example: 00 — SimpleMaze.
That’s a lot of code! But fear not, all the important bits are located inside Maze.generate(). The algorithm itself is pretty straightforward, and I hope that my comments do it justice. Feel free to yell at me if I should explain it in more depth here.
Anyway, pay special attention to this line:
# Shuffle the neighbours list by sorting it with random values and pick the first element
chosenCell = sorted(unexploredNeighbours, key=lambda c: random(1))[0]The algorithm has to pick a random unexplored neighbor. There are a few ways to achieve this, but I chose to sort the list with a custom function, the key argument. This function lets us return whatever number we deem fit for each element, and the list is then sorted against those values. By returning a random number we ensure that each element will be sorted randomly, for now.
Let’s run the code.
Great, that looks like a maze! Now we’re ready to step up our game.
Part 1: Introducing a bias
What if we wanted a mostly-horizontal maze instead of a completely random one? What we’d need is a bias. A bias is a tendency, and we want our maze to tend to have horizontal corridors.
Let’s start by sorting each neighbor by its vertical position:
chosenCell = sorted(unexploredNeighbours, key=lambda c: c.position[1])[0]This gives us a perfectly straight “maze”:
This maze has zero entropy, because each cell is part of a straight corridor. In contrast, our first maze had maximum entropy, because it was very chaotic.
Let’s throw in a random number ranging from 0 to somewhat more than 1. When that number will be higher than 1, we’ll have a random turn. Otherwise, we’ll have a straight corridor. This number is our bias, and we can tune it in various ways to achieve different results.
chosenCell = sorted(unexploredNeighbours, key=lambda c: c.position[1] + random(1.5))[0]Lo and behold, mission accomplished! And we only changed one line of code.
Full example, as unnecessary as it is: 01 — HorizontalBias
Part 2: Manipulating entropy
Now that we know how to introduce a bias, it will be trivial to manipulate the maze’s entropy as we please. For example, what about using trigonometry to generate a ‘wavy’ maze?
Wait, give me a second— I want to edit our generate() function first. I’ll add a parameter named sortfun that will default to random(1) and which will act as a custom sorting function so that we’ll be able to pass it directly by argument.
@staticmethod
def generate(w, h, sortfun=lambda c: random(1)):
...
chosenCell = sorted(unexploredNeighbours, key=sortfun)[0]
...That’s how I like it.
Back to our problem, we can now pass a sine-based formula to generate() during setup:
def setup():
global maze ... customsort = lambda c: random(2) * sin(c.position[0] / 10) + c.position[0]
maze = Maze.generate(width // scalingFactor, height // scalingFactor, sortfun=customsort)
Which yields this:
We can also make a checkered pattern:
N = 2
customsort = lambda c: (c.position[0] * c.position[1]) % N + c.position[0]
There’s really a lot of room for creativity! Here are some more examples:
Here’s the code so far: 02 — Noisy.
We have achieved control over chaos. We’re ready for the final step.
Part 3: Putting it all together
So far we’ve learned about mazes, bitmap masks and controlled randomness. Let’s try to combine these separate pieces of knowledge into something a bit more interesting.
We’re going to need a gray-scale picture, our mask.
Here we have four colors. We want a maze subdivided in four sections, each more chaotic than the last.
All the edits will happen inside setup():
def setup():
global maze
size(512, 512)
strokeWeight(1)
mazeMask = loadImage('data/maze-mask.png')
mazeMask.resize(width // scalingFactor, height // scalingFactor)
getbrightness = lambda c: brightness(mazeMask.get(c.position[0], c.position[1])) / 255
customsort = lambda c: c.position[0] + getbrightness(c) * random(4)
maze = Maze.generate(mazeMask.width, mazeMask.height, sortfun=customsort)What am I doing here?
- I load the mask from the data subdirectory.
- I scale it down to the size of our maze.
- I define a helper function, getbrightness which returns the brightness of a pixel on our mask in the 0–1 range.
- I define the customsort function in which links vertical bias to pixel brightness across 4 possible values (ergo random(4)).
- I generate the maze just like before.
Et voilà:
But we’re not done yet. Remember part 2? What if I told you that you could plug any of those functions into the finished program?
customsort = lambda c: (c.position[0] * c.position[1]) % int(1 + 4 * getbrightness(c)) * 4I don’t think it’s still fair to call it ‘bias’, not with such mathematical results:
Our sort functions have evolved into what you could call textures.
Applying a mask over a texture gives you full control over what your maze will look like.
customsort = lambda c: random(1) * getbrightness(c)
I wish I had more to talk about, but that’s it. You’re a quantum-bender now, use your powers wisely.
I hope you enjoyed reading this post as much I enjoyed writing it. I’ll leave you with the completed program and a last picture.
