Make a maze
The challenge… #
I challenged myself to create software that can make a maze using javascript. Just for fun :)
Click here if you want to see the algorithm in action!
I defined the challenge as follows:
Generate a maze with these parameters
Size: {height, width} // h + w < 500 && h > 5 && w > 5
Start: {x, y} // (x == width || x == 0) || (y == height || y == 0)
End: {x, y} // ((x == width || x == 0) || (y == height || y == 0)) && start !== end
The maze should:
- Be solvable (so there should be a path from start to end)
- Have at least one branch (so not just one path from start to end)
- No unreachable 'blocks'
Sounds easy enough, right?
If you want to do it yourself, stop reading ;)
The Mental Model #
The challenge seemed simple enough, but after thinking about it for a while, it was not easy at all.
How do you represent a maze in code? What is a path through a maze?
When you want to create a maze using pen and paper, you probably draw a square and then draw ‘walls’ to create routes. But I couldn’t get this implemented in code in a simple way.
After multiple sketches I decided to represent my initial maze as a grid with a lot of ‘walls’ instead of an empty square. This provided me with an advantage: I could create paths through the maze simply by removing walls. Anytime I connect with an existing path I get closer to creating a complete maze.
The initial ‘maze’ is just a lot of walls:
█████████████████████
█░█░█░█░█░█░█░█░█░█░█
█████████████████████
█░█░█░█░█░█░█░█░█░█░█
█████████████████████
█░█░█░█░█░█░█░█░█░█░█
█████████████████████
█░█░█░█░█░█░█░█░█░█░█
█████████████████████
Take 1: recursion #
My first idea was to create a maze using recursion. This means running the same function a lot of times.
I start at the beginning of the maze and try to go in every direction (up, down, left, right) to see if the ’end’ is there. If it isn’t, I check if I accidentally went outside the maze or bumped into an existing path and I stop going in that direction if that’s the case. If neither of those conditions were met, I go from that second step into 4 directions and check my conditions again.
People familiar with recursion will know this leads into a lot of memory-use very quickly. Here’s an example of recursion with four branches at a depth of 2:
|
/ | | \
/||\/||\/||\/||\
Every branch is a function call, so already with a depth of 2 the same function was called 21 times!
To counter that, I created a maximum-depth dependent on the size of the maze. The maximum possible path-length is width x height, but that would be a very boring maze 🤓 (it’s the longest path possible going from A to B without branching)
So I chose:
$${maxdepth} = \frac{ {width}\times{height}}{2}$$
Note that one of the 4-directions can be closed immediately because it is the way you came from, so basically you branch only 3 times per layer in your recursion.
In mathematical terms, that’s:
$$\sum_{n = 0}^{n = {maxdepth}} 3^{n}$$
For a maze sized 10 x 10 (so max_depth = 10 x 10 / 2 = 50) the recursive function would be called a lot of times:
$$3^0 + 3^1 + 3^2 + 3^3 + … + 3^{50} = 1,076,846,981,537,778,883,155,373$$
Spoken out loud, that’s: 1 septillion 76 sextillion 846 quintillion 981 quadrillion 537 trillion 778 billion 883 million 155 thousand 373. To put that number in perspective: that’s the size of the observable universe in meters!!
Of course, our function is not called exactly that many times because potential paths get cut off if they go outside the maze or bump into an existing path. Still the amount of times my function would be called for a very tiny maze of just 10x10 is huge. And you’re not done yet after running the function this staggering amount of times because you’ve only created the initial route, the solution you plotted for the players of the maze. You then have to create a path using the same recursion from every empty spot in the maze to create the diversion paths.
Surprisingly the code ran reasonably smooth on my 6-year old laptop. It took a minute or so and resulted in very boring mazes with just straight paths.
Introducing randomness #
To try to salvage the situation, I decided to add a bit of randomness. I did this in two ways: randomly kill some potential paths and swapping around the directions (instead of always going up first, sometimes go down, right or left). The first option had the most potential because it also meant I could significantly cut into the amount of paths my algorithm had to take.
Another advantage was that I could now indicate how ‘complex’ I wanted my mazes to look.
But now I came into another problem: by killing random paths it means my algorithm sometimes would not find the correct path at all. The only solution was to add a loop that would run the ‘random recursion’-function until it found a correct path.
My algorithm took minutes to create even the simplest of mazes and sometimes just completely froze my machine.
Conclusion: I was done with recursion!
Take 2: take me to a random place! #
It hit me: I had been going about this all wrong! There was a much simpler solution!
Instead of finding a random path from start to finish in the maze, I could create an optimal path to multiple random locations in the maze.
Creating a path from one point to another point is actually very simple. You just calculate how much you have to travel vertically: $$Y_{finish} - Y_{start}$$ and horizontally: $$X_{finish} - X_{start}$$ and then go through these steps.
Concretely, suppose you want to go from [2,8] to [5,3]. Now you know you have to go three steps to the left (5-2=3) and five steps up (3-8=-5). Your route-description would be: go right, go right, go right, go up, go up, go up, go up, go up. You’ve now written an ⏌, starting at the bottom-left. If you want to make this path a bit more interesting, you can randomize the ‘instructions’.
Step 1 was to use this method to create the initial ‘solution’-path through a maze. Going from start to a random location, go from this random location to another random location and from there go to the finish.
Step 2 is to create diversion paths (branches), to confuse the solver of the maze. I let my algorithm go from each empty-spot towards the direction of the center, until it collides with an existing path.
Yes! That’s more like it! 🏆
With this method, I can easily generate mazes with near-infinite sizes. Here’s a maze with size 50x50:
Click here if you want to see the algorithm in action!
Conclusion #
- Recursion is difficult to get right
- Making (a)mazing-software is difficult and you’ll fail on your first try
- (See point 1)