Exercise #5: A Random Maze Generator

◀ Solving Word Ladder Game - Step 4▶ Creating A Random Maze - Step 1 Amazon You probably have played mazes before, especially in your childhood. You enter at one point and exit at another. Most of the mazes you have played before were probably manually drawn. Nowadays with the advent of computers, we are able to instruct a computer to do this task for us.

In this programming exercise, you are to write a random maze generator that generates a rectangular maze of size specified by the user. At the most basic level, you should have the program output relevant information about the generated maze, including each of its cells’ location and which walls are knocked down.

You can actually generate code for programming languages with graphics capabilities such as Java applet, OpenGL, Visual Basic, and Matlab so that they can display the maze.

There are a ton of tutorials in these languages on the Internet, and all you need is a passion for learning!
Generating a maze is no small task for a new programmer. You can go sit on a couch right now and think about it and see if you can figure it out. Chances are that you come back utterly confused.


Now you find a wall at random, check to see if the cells sharing that wall belong to the same set; if so, ignore them because they are already connected with each other; if not, knock down the wall and merge them so that they are in the same set.

The point is that there should be exactly one path to go from one cell to another.
If you keep knocking down walls this way, at some point all cells will belong to the same set while only several walls are knocked down. Then a maze is generated and you are done.

Simple, huh? You can start writing this program and show me what you are made of. If you succeed without reading any further, send me an email. I will congratulate you myself.

Basically you need a class that defines two functions: one finds you the root of a cell and the other makes two cells belong to the same set. In addition, you should define the attributes of each cell, including its parent’s id, its location, and which surrounding walls are knocked down.

One thing to keep in mind is that the initial parent’s id of all cells should be –1, indicating that they are all roots. The two functions, to your surprise, take only one line each in my program. Here they are:

/*
precondition: n must be >= 0 and < s.size()
postcondition: return the root of n
*/
int find_root(int n){
	return s[n]<0 ? n : find_root(s[n]);
}

/*
precondition: root1 and root2 both must be >= 0 and < s.size()
postcondition: root1 and root2 belong to the same set
*/
void union_cell(int root1, int root2){
	s[find_root(root2)] = root1;
}

As you can see in the preconditions of both functions, the arguments must be greater than or equal to 0 and less than s.size(). If this is not true, you will most likely get a segmentation fault.

In both functions, s[n] is the parent’s id of n. find_root() simply searches recursively until s[n] is less than 0; union_cell() makes the root of root2 a child of root1. Given these two functions, you should have no problem knocking down walls and generating a maze.

After you successfully generate a maze, you should find the solution path to that maze.
In a maze generated by my program, one opening is in the upper left corner and the other one lower right corner, one indicating the entrance and the other the exit. To find a solution, start at the entrance cell and choose an obstacle-free cell to go to, and go to another obstacle-free cell.

This process continues until you cannot go on anymore. Then you try another valid path recursively. Yup, recursion again. You got to learn to love recursion because it’s extremely powerful. Finding the solution to a maze gives you another taste in working with recursion.

Here are the proposed steps of the program:

• exit if something is missing in the command line
• generate a random rectangular maze of the specified size
• find the solution to the maze
• output relevant information about the maze
• if you know any language with graphics capabilities, generate code and have it display the maze and its solution

The following is a list of what my program does:

• accept two files from the command line, one is where the maze without solution outputs and the other the maze with solution outputs
• generate a random rectangular maze as well as find its solution
• output appropriate Matlab code to the appropriate files

Here is a sample maze displayed using Matlab:



Let's apply the Four Step Programming Model described in Chapter 11.8!◀ Solving Word Ladder Game - Step 4▶ Creating A Random Maze - Step 1