This post is a how-to generate random labyrinths. Keep in mind there are a lot of algorithms and this is not the best neither the most optimized. In my opinion it is the simplest though.

## Introduction

###

What you will need:

###
- lab: an array to store the labyrinth (I'll be using a 2D array);
- visitedCells: a secondary array to keep record of the visited cells;
- guideCell: the coordinates of the head of the path;
- pathHistory: a stack to keep a record of the path taken.

How the algorithm works:

- The guide cell starts
__next to the exit__; - The guide cell advances to a
__random unvisited cell__; - The guide cell keeps advancing until there are
__no unvisited cells around__it; - When there are no unvisited cells around, the
__stack__gets useful: __back trace__to a point of the path where there is__at least one unvisited cell__and develop the algorithm from there;- The maze is completely
__finished__when__all cells have been visited__. - An even easier way to know it is finished is when the
__stack gets empty__.

###

Restrictions:

- The dimension of the maze needs to be an odd number.

##

Detailed Algorithm Analysis

Let's say we need to generate a 7x7 maze.

The first step is to fill the 2D array with walls (I'll be using 'X' to display walls). After this we need to free the cells which have odd x and y coordinates, just like the picture below:

And this is the base matrix where the algorithm will work. That's why the the maze needs to have an odd dimension.

The next step would be

__randomly__picking one

__free cell__(as long as it is right next to the maze borders) and marking it as the

__guideCell__. After that, place an 'S' on the maze border to mark the

__exit__:

S: exit

+: guideCell

The next step is to create the visitedCells array to keep track of the cells which have been visited or not. This array will not be 7x7 but 3x3. The dimension of the visitedCells array is given by

visitedCellsDimension = (labDimension - 1) / 2

.: unvisited cell

+: visited cell

Ok, by this time we have our lab array and our visitedCell ready. We just need to push the guideCell coords to the stack:

Now that we have everything ready, let the algorithm start working! Yay! :D

First we need to generate a

__random direction__and check if that cell has already been visited. If not, the guide cell will advance to that direction.

Assume that the computer randomly says: "guideCell, go down!". The cell below the guideCell current location has not yet been visited according to the visitedCells array, so this is what will happen:

- the
__guideCell__coords will be updated and pushed to the stack; - the
__visitedCells__matrix will be updated: - a '+' will be marked at {2, 1};
- the
__lab__array will also be updated: - the 'X' on {5, 2} will be removed.

Ok let's speed up things a little bit. I hope you are catching up with me.

Let's say the computer generated this directions randomly:

- right;
- up;
- left;
- down;
- right.

The 1st direction (right) will be ignored because the guide cell can not go right! That's the border of the maze!

The 2nd direction generated (up) will also be ignored because according to the visitedCells, the cell above the guideCell has already been visited. Do you get it? :)

The 3rd direction is a valid one though! The guideCell can indeed go left. So this is what will happen:

The 4th direction generated was 'down':

And finally, the 5th direction generated was 'right':

Ok, by now you should have realized how the algorithm works.

Notice what happens now:

- If the computer generates
__right__or__down__, the guideCell can not go there because that is the__maze borders__! - If the computer generates
__left__or__up__, the guideCell can not go there as well because according to the visitedCells array, both cells in that direction have__already been visited__!

__dead end__! So, how do we finish generating the maze? It's not finished yet...

Well, it's not that hard! This is why we have the

__stack__with the history of the path we took!

When we run into this problem we just need to

__back trace__the stack and

__look for a cell__that has

__at least one neighbor__that has

__not yet been visited__. When we do find this cell, it becomes our new guideCell.

Let me use the example we have been working on to illustrate what I mean:

The current guideCell has no unvisited cells as neighbors, so we need to

__remove__it from the stack. And since we removed it, the

__top__of the stack is {1, 2}, and this cell has at least one neighbor unvisited:

**This is our new guideCell.**

And since there is only one valid direction (left), the following algorithm iterations will be:

And at this point, once again, we got to a

__dead end__. What did we do when this happened before? That is right! We popped the stack until we found a cell that had at least one unvisited neighbor.

This time though, we will pop the stack and won't find a cell that matches this condition. Why? Because all cells have been visited! You can check that by looking to the visitedCells array.

The program will therefore be

__popping__the stack and eventually

__empty__it.

And that concludes the algorithm: when the stack gets empty, all the cells have been visited and the maze generation was successfully completed! :)

Here is an example of a 31x31 maze generated with this algorithm:

I hope this helped you and was not too confusing... Cheers!

Do you still check this blog at all? I have a question about this algorithm. Why is the visited cells array only 3x3? As far as I can tell it doesn't move with the guide cell, so how do you use the visited cells array once the guide cell moves out of the visited cells bounds?

ReplyDelete