What to submit: a Makefile, executable called maze and all the code files needed to build your solution on the CSIF linux machines. Do not submit object files. Use handin to turn in your files to cs60 p3.

In this assignment, you will write code to generate a maze of arbitrary size and then solve it. Be sure to follow good coding practices throughout. Think carefully about your implementation before you begin to code. This willsave you time. The final program does not need to be very long if you code it intelligently.

Part 1: Generate a Maze (30 points)

For part 1, you must generate a maze using the method based on disjoint sets that is discussed in Chapter 8 of Weiss. Read this chapter carefully and make sure you understand the method. You will need to use Find() and Union() to generate your maze. You should implement the approach that has O(1) performance for Union and you should use the smart union algorithm. You do not need to add path compression, but try it if you have time. Your maze should only have one solution (this will occur by default if you implement the algorithm properly).

Your code should take a height, width and seed as input. The height and width determine the size of the maze. The seed is used as input to a random number generator so that you can generate different mazes by providing different seeds (use srand(seed) to initialize the random number generator and then (int)maxVal * (float)(rand()/((double)RAND_MAX + 1)) ( int )(maxVal * rand() /(float)(RAND_MAX + 1))). The starting point of the maze is the upper left corner and the ending point is the lower right corner. See the main function and sample runs below.

(NEW: The original command above works fine with Visual Studio, but seems to be causing issues on CSIF. Breaking out the new command, RAND_MAX is defined by the library implementation. Im casting it to double to avoid triggering a possible integer overflow when I add 1 to it. The float cast is to ensure that the compiler treats the quantity weve just calculated with the division as a float and not an int as it will be between 0 and 1. The leading int cast is to convert everything to the desired int value.)

The code should calculate the maze, then print it to stdout and finally solve the maze and print the output (part 2). This is what the main function below does.

For the print routine, use a + at the intersection of all lines, use a | for vertical lines and a – for horizontal lines. See the sample output below. If a border between cells is removed in constructing the maze, remove the corresponding or | from what you print out.

Think carefully about the data structures and algorithms you need for both Part 1 and Part 2 before starting to code. A clean design will lead to a compact solution.

Part 2: Solve the Maze (20 points)

In the second part of the assignment, you should solve the maze and print out the solution path. The solution path should be the shortest path from the start to the finish and should not contain unnecessary nodes. No nodes should be repeated. Simply print each node you must travel through, starting with node 0. See the sample output below.

You should also print out a solved version of the maze. Use an O to mark each location you need to pass through on the shortest path that solves the maze. This should be printed out below the list of nodes, as shown below. I suggest coding the print routine to just display the maze (part 1) first, and then extending that routine to allow you to print out the solution as well.

You should solve the maze using a tree. Start the tree at one end and grow it until you reach the other. Hint: I used a queue in my implementation.

Sample code

Main

Please use the following main file.

#include <iostream>

#includeMaze.h

using namespace std;

int main(int argc, char* argv[])

{

if(argc < 4)

{

cout << Usage: Maze <height> <width> <seed> << endl;

return 1;

}

int width, height, seed;

height = atoi(argv[1]);

width = atoi(argv[2]);

seed = atoi(argv[3]);

CMaze theMaze(height,width);

//build the maze

theMaze.MakeMaze(seed);

//print it to cout

theMaze.PrintMaze();

//find the solution and print out the successful (shortest) path and maze with solution

theMaze.SolveMaze();

return 0;

}

Maze Class

Your maze class should contain at least the following methods. You can (should) include additional private helper methods and data. You may also define other classes if you need them. I defined a node class and also use a queue in my SolveMaze code.

class CMaze

{

public:

CMaze(int numRows, int numColumns);

~CMaze(void);

void MakeMaze(int seed);

void PrintMaze();

void SolveMaze();

private:

//disjoint set methods

void Union(int item1, int item2);

int Find(int itemIndex);

};

Sample output:

imapssl% maze 5 5 10

+ +-+-+-+-+

| |

+ +-+-+-+ +

| | | |

+ + +-+ +-+

| | |

+ +-+-+ + +

| | | | |

+-+ + + +-+

| | |

+-+-+-+-+ +

0 5 10 11 12 13 18 23 24

+ +-+-+-+-+

O | |

+ +-+-+-+ +

|O| | |

+ + +-+ +-+

|O O O O| |

+ +-+-+ + +

| | |O| |

+-+ + + +-+

| | | O O

+-+-+-+-+ +

imapssl% maze 7 7 0

+ +-+-+-+-+-+-+

| | | |

+-+ +-+ + + +-+

| | | |

+-+ +-+ +-+ + +

| | | | |

+ +-+-+ + +-+ +

| | | |

+-+-+ + + +-+ +

| | | | |

+ +-+ +-+-+ +-+

| | | | |

+-+-+ +-+ + + +

| | |

+-+-+-+-+-+-+ +

0 1 8 9 10 3 4 11 12 19 20 27 34 33 40 47 48

+ +-+-+-+-+-+-+

O O |O O| | |

+-+ +-+ + + +-+

| O O O|O O| |

+-+ +-+ +-+ + +

| | | |O O|

+ +-+-+ + +-+ +

| | | O|

+-+-+ + + +-+ +

| | | |O O|

+ +-+ +-+-+ +-+

| | |O| |

+-+-+ +-+ + + +

| | |O O

+-+-+-+-+-+-+ +

imapssl% maze 9 25 33

+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| | | | | | | | |

+ + +-+-+-+ + + +-+ +-+-+ + +-+-+ +-+ + + +-+ +-+-+

| | | | | | | | | | | | | | |

+ + +-+-+-+ +-+ +-+-+-+ +-+ + + + + +-+ +-+ + +-+ +

| | | | | | | | | | |

+-+-+-+ + + +-+ +-+-+ +-+ +-+ + +-+-+-+ +-+-+ +-+ +

| | | | | | | | | | | | | | |

+-+-+ + +-+-+ + +-+-+ +-+-+ + + + + + +-+-+-+ +-+-+

| | | | | | | | | | | | |

+-+ +-+-+-+ + + +-+ +-+-+ +-+ + +-+-+-+-+ +-+-+ + +

| | | | | | | | | | | | | |

+-+-+-+ + +-+ +-+ +-+-+ + + + +-+ +-+ + +-+-+-+-+-+

| | | | | | | | | | | |

+ + + +-+-+ + + +-+ +-+ +-+-+-+ + +-+ + +-+ +-+-+ +

| | | | | | | | | | | | | | |

+-+ +-+-+-+-+ + +-+ + +-+ + + +-+ + +-+ +-+-+ +-+ +

| | | | | | | | |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +

0 25 50 51 52 53 78 103 104 105 106 131 156 181 206 207 182 183 184 159 160 161 162 137 138 139 114 89 64 65 66 41 42 67 68 69 70 71 46 47 72 97 122 121 120 145 144 169 194 219 220 221 222 197 196 171 172 173 174 199 224

+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

O| | | | | | | | |

+ + +-+-+-+ + + +-+ +-+-+ + +-+-+ +-+ + + +-+ +-+-+

|O| | | | | | | |O O| | |O O| | |

+ + +-+-+-+ +-+ +-+-+-+ +-+ + + + + +-+ +-+ + +-+ +

|O O O O| | | | | |O O O|O O O O O|O | |

+-+-+-+ + + +-+ +-+-+ +-+ +-+ + +-+-+-+ +-+-+ +-+ +

| |O| | | | | | |O| | | | O | |

+-+-+ + +-+-+ + +-+-+ +-+-+ + + + + + +-+-+-+ +-+-+

| | O O O O| | | | | O| | | | O O O | |

+-+ +-+-+-+ + + +-+ +-+-+ +-+ + +-+-+-+-+ +-+-+ + +

| | | | |O| | |O O O| | |O O | | |

+-+-+-+ + +-+ +-+ +-+-+ + + + +-+ +-+ + +-+-+-+-+-+

| O| | |O O O O| | | | | |O| O O O O|

+ + + +-+-+ + + +-+ +-+ +-+-+-+ + +-+ + +-+ +-+-+ +

| | | | |O|O O O | | | | | |O |O O| O|

+-+ +-+-+-+-+ + +-+ + +-+ + + +-+ + +-+ +-+-+ +-+ +

| | O O| | | | |O O O O| |O

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +