Creating A Random Maze - Step 1

◀ Exercise #5: A Random Maze Generator▶ Creating A Random Maze - Step 2 Amazon Let’s apply the 1st step of the Four-Step Programming Model to generate a random maze!

Four Step Programming Model: Step 1
After carefully analyzing what I need, I know I need many array data members in the class to store information regarding each cell. I use vector to do that because of its easy, user-friendly operations. Each cell keeps track of its right and lower walls only.

For cells that do not have both walls, do something to distinct them from the rest of the cells. For example, you can set a variable so that it indicates that the cell’s lower wall must be up.

This program is a lot larger than the previous ones, so while working on the skeletons, you may be confused as to what functions or class you need. You can start with main() and develop from there like I did.

void remove(int);
void findSol(int, int);
void displaySol();

class Maze{
public:
Maze(int);
int find_root(int);	
	void union_cell(int, int);
};
/*
precondition: n must be a positive integer
postcondition: attributes of each cell are assigned values
*/
Maze::Maze(int n){
- determine each cell’s location and initialize the data members
}
/*
precondition: n must be >= 0 and < the number of all cells
postcondition: return the root of n
*/
int Maze::find_root(int n){
- return the root of n
}
/*
precondition: root1 and root2 both must be >= 0 and < the number of all cells
postcondition: root1 and root2 belong to the same set
*/
void Maze::union_cell(int root1, int root2){
- make root1 and root2 belong to the same set
}

int main(int argc, char** argv){
- exit if something is missing in the command line
- exit if the user provides unacceptable information
- initialize the random number generator
- store critical data in variables
- push all elements into a vector except the last one because it has no walls to knock down
- use a while loop to construct the maze
- inside the while loop
	randomly choose a cell
	deal with the case when the cell has 2 neighbors
	deal with the case when the cell has only 1 neighbor 
- generate code for Matlab to display the maze
- find and put solution code in the solution file
}
/*
precondition: victim should, but not must, be an element in the vector that holds all cells
postcondition: victim is erased from the vector
*/
void remove(int victim){
- remove victim the vector because victim is already processed
}
/*
precondition: from and to must be >= 0 and < numOfCells
postcondition: find the solution
*/
void findSol(int from, int to){
- push from to the solution vector
- mark from visited
- if from equals to, that means we’ve found the solution, so we call displaySol() to write code to output files
- now go through each surrounding wall 
- inside an if block
if the right wall is down and the cell on the other side is not visited yet, use that cell to call findSol recursively
if control returns here, that means this cell has led to a deadlock, so pop the element in the back of the solution vector
- inside an if block
if the lower wall is down and the cell on the other side is not visited yet, use that cell to call findSol recursively
if control returns here, that means this cell has led to a deadlock, so pop the element in the back of the solution vector
- inside an if block
if the upper wall is down and the cell on the other side is not visited yet, use that cell to call findSol recursively
if control returns here, that means this cell has led to a deadlock, so pop the element in the back of the solution vector
- inside an if block
if the left wall is down and the cell on the other side is not visited yet, use that cell to call findSol recursively
if control returns here, that means this cell has led to a deadlock, so pop the element in the back of the solution vector
}
/*
precondition: none
postcondition: put code for displaying the maze in file2
*/
void displaySol(){
- generate code for Matlab to display the solution to the second output file
}

Wow, it looks like a pretty big program. Well, it is big compared to the programming exercises you have done earlier, but it is not that big.

As long as you know what to do, you will finish this program finitely, the sole aim of reading this book.

Let's look at the next step!◀ Exercise #5: A Random Maze Generator▶ Creating A Random Maze - Step 2