So far, I’ve only talked about how to solve problems. Today I will tell you how to create one for a change. You can create mazes as hard as you want and have fun watching your friends try to solve them!
There are many algorithms for creating a maze, of course (♫ You’ll take the high road and I’ll take the low road, and I’ll be in Scotland before you ♫). The algorithm I will show you is called recursive backtracking. It will be easy as a Dr. Oetker pudding recipe once you know what depth-first search (DFS) and a stack means. I will try to explain them as I go on.
We start with a table like this (here, I chose a 4×8 table. You can start your maze with anything you like, it’s not important – unless you start with a 1×1 one).
We randomly choose a box to start. Then, we again randomly choose an unvisited “neighbor” to step on – either the left, right, up or down one (down-left box is not a neighbor, for example). When we travel from one box to another, we remove the wall between them. We keep repeating this algorithm until all squares are visited.
We have to be careful though – if we step to a box and that box happens to have no unvisited neighbors, we will have to take a step/steps back until everything turns back to normal. We will still mark that box as visited. This is called as DFS since we do not backtrack until we reach the very end.
As we visit boxes for the first time, we will put them in a stack. Stack is a data structure which follows the last in first out (LIFO) principle. A box of Pringles is an example of a
stack – the last chip you will eat is actually the one which is packed first (we also use “stack” as a term in Ultimate Frisbee – usually the last one in the stack makes the first cut). We dynamically grow or shrink the stack as we continue on. The program terminates when stack is finally empty.
‘Nuff said. Let’s start with the box 32. I will color the visited boxes with blue and add them to a stack as I proceed (click on the images pls):
Then, I randomly chose 31. I delete the walls between 30 and 31, and mark 31 as visited as usual.
We’ve reached a dead end. We cannot proceed from 31 to anywhere since all of its neighbors are already visited. We “pop” 31 from the stack and see if 30 has other neighbors. Fortunately, 30 has 29 as a neighbor so we do not need to backtrack anymore.
So far so good…
Obviously this maze will start at 32 and end at 1, but this doesn’t change the fact that we need to visit every box in this table, meaning that the big square should be completely blue and the stack should be empty when we finish.
It’s actually very difficult to show these step by step, so I will skip a few steps. I believe you already understood how to proceed anyway:
Again, we’ve reached a dead end. This time, one step back is not enough, so we continue backtracking and popping off the stack until we can proceed with another box.
We still have 13 to visit:
Although we see it clearly from this image, we still need to backtrack from 13 in order to see if any box is unvisited:
You may now think this algorithm is not worth it since our final maze is very easy. However, I used a table of only 4×8 as an example. Also, I explained it step by step which made the creation seem so long. That’s what computers are for: once you implement this algorithm, you will see it’s a very fast algorithm. I will not give a full implementation though (if I feel like it later, I will edit here). I just wanted to show you how mazes are created with computers.
Some day, inshallah mashallah (lol), I will be able to create my own demos. Until that day comes, here is an a-mazing (lolol) animation (warning, may cause addiction):
~~IMPORTANT EDIT~~ My classmate Mahmut made an awesome demo! Please also check that out. You can play with the animation rate and grid size.
So long, folks!
- Check out this awesome demo!
- Wikipedia, of course
- I love this blog
- Easy learn tutorial – implementation