Purpose: Learning how to program a maze generation algorithm.
The goal of this exercise is to be able to create an algorithm to generate mazes using the "Recursive Division" method.
This exercise requires you to use the Computer Art program from the RoboCatz website. You will write a program according to the instructions below. Try not to just jump to the end of the lesson and copy the whole program. You won't learn much by doing that. Follow the individual steps shown below. Follow them in order--so that you'll know what to do when you have to write your own programs some day.
Initialize 2 variables to help generate the dimensions of the maze:
numRows = 6 numCols = 6
First, we will start off with a small 6 by 6 cell maze. After developing code with this smaller maze, we will then increase the number of rows and columns to create bigger mazes. In the Computer Art program, click on "Lesson 1", delete all of the code from that lesson and insert the two variable assignment statements above.
Add to your new program, two statements to calculate the width and height of each cell in the maze:
In generating the maze, we will use colors to help observe the program in action. The maze will also require an Array to store information about the location of the walls in the maze. Add the following assignments to your new program:
Next we will create the array that will store all of the data about each wall in the maze. This array will be a 2-dimensional array (rows and columns). Add the following for() loops to your program:
As you can see from the above for() loops, each cell in the 2-dimensional array will contain the following object:
This literal object contains two properties: .vertical and .horizontal. Both properties will be assigned the value of 1. In our maze program, a "level" will be used to help show the program in action. The level can also help control the amount (or level of) recursion. Recursion occurs when a function calls itself. This can lead to a "race condition" in which the program enters an infinite loop from which it cannot escape.
The next part of the program is to "render" the maze. Render means to draw the maze based on the algorithm created so far. The maze will be rendered using the following for() loops. Add these to your program:
At this point, your program should appear as follows:
If you run this program, you will see the array of walls.
Dividing on a Random Row or Column
Update the two initial for loops to clear the maze of any walls:
Assigning the vertical and horizontal walls to zero (0) will create an open space without a wall. A function will be added to create walls between the divided areas. The random function will return an integer value between a minimum and maximum value. For example, add the following function after the initial for() loops:
Then add a function to perform the process of dividing the area. This function will use the random integer function you just added. Add the following function after the random integer function:
The divide() function requires 5 parameters minimum and maximum column, minimum and maximum row, and the level. The level will be used to colorize the walls to make it more clear when and where the computer has divided the area. If .vertical or .horizontal properties are assigned a zero, there is no wall. If they are assigned any non zero integer, the wall will be drawn with a specific color. After you have defined the divide() function, you should call it with the following statement:
divide(0, numCols, 0, numRows, 1)
Your program should now appear as:
Now run your program.
Any error messages? I hope not. Run the program multiple times to see various possibilities for dividing the area. The area is not yet completely divided. However, you should be able to see where the division will occur.
The next step is to modify the program so that the division occurs across all rows and columns. For this, we will need to add for() loops to the divide() function. Update your divide() to use the following statements instead:
Let's remove the -5 from the rendering for() loops. By deleting that subtraction you should be able to connect the line segments.
Your program should now appear as follows:
Run the program several times to see where the divisions may occur. You might notice that the divisions sometimes occur at the edge of the maze boundary. This will leave little to no space to navigate around the wall. Therefore, we will need to restrict the range of the random numbers generated. To restrict the ranges, we will add 1 to the minimum values being sent into the random number generator. See updated divide() function below. Make these updates to your program as well.
Now run your program several times.
Recursion - "A function calling itself"
Now we will attempt to further divide each of the quadrants from the initial division. This will occur by calling the divide function with the coordinates and size of each quadrant. You will also need to update your colors array to include additional colors for the walls. Make the following change to your program:
Now update the divide() function to include the additional calls to the divide() function (i.e., calls to itself; a.k.a. recursion). Make this change:
Run your program once. It may appear that it is no longer working. However, it may actually be working too much (a.k.a. stuck in a loop). View the console to see if there are any error messages and any indication of how many times through the divide() function the computer has performed.
Press F12 to access the Developer tools and the console panel.
How many times did it execute the divide function?
Try using the whole program below which includes a counter for the divide function.
Run the program. It probably appears that it is not working. Look at the console panel to see how many times the divide() function has been called. Your computer probably executed the function thousands of times before it crashed.
Notice that it is infinitely dividing Row 1 column 1. The program never stops trying to divide that cell.
Recursion - Knowing when to return from the function.
We need to help the divide() function know when there isn't enough space to divide any more. Plus we can also specify a maximum level that will be permitted for the division. The value for level is incremented each time the divide() function calls itself. Update your divide() function to use the following:
Note that we have added another "argument" to the list of arguments passed into the divide() function. This last argument is called: quadrant and will be a string passed into the divide function to help update the log output to include the quadrant currently being worked on. This means that you also need to update the initial call to the divide function to appear as:
divide(0, numCols, 0, numRows, 1, 'All')
Try running your program. Does it work? If not, feel free to use the code below as the complete program to this point in the lesson.
As you may have figured out, each division of the area occurs on one of the array coordinates (row and column).
As an exercise, let's also draw the level number at that intersection point. This level information will give you a better understanding of where the computer is creating the various divisions.
Update the divide() function to use the following:
Run the program. Does it show the level indicators at each intersection of lines?
Add the following near the beginning of your program:
openDoor = 0
This value (zero) is the value that represents an open door in a segment of the wall.
Each time an area is divided, we need to add a few doors in the walls to enable a path through the maze. Without these doors, the maze area will be divided without a way of getting from one end of the maze to the other. The doors will be added in the divide() function following the determination of where the division should occur. The position of the doors will be randomly selected using the current random integer function. Update your divide() function to use the following:
Note that two horizontal and two vertical doors are created to enable the user to pass through to each quadrant. No quadrant is omitted from a possible path.
The Whole program should now appear as:
Now we will turn off the colors and just show black lines by changing the following line at the beginning of the program:
withColors = false
Let's also create a Boolean variable to turn the numbering on/off. Add the following (before or after) the withColors assignment statement at the beginning of the program:
withNumbers = false
To implement this change, update your divide() function to use the following for generating the numbers at the intersections:
As you can see, the above if() statement will determine if the numbers should be shown (or not) based on the value of the Boolean variable.
Some of the areas created may appear small. We can try to get the computer to create more "squarish" areas and less "very thin" or "very tall" areas by adding an "offset" to further restrict the range of spaces where a division can occur. Add the following near the beginning of the program:
levelDivisionOffset = [4,3,2,1,0]
Update the divide() function to use the following changed lines:
The final version of the program (using lines) should now appear as:
The final version of the program (using tubes) should now appear as: