Mazes and Maze Generation

From our discussions we know that mazes are minimum spanning trees. We would like to use

the algorithms we discussed in class $($Kruskal$\text{'}$s and Prim's$)$ to generate some mazes. We'll

focus on creating mazes that are $200$x$200$ cells. For all mazes, the entry point will be the uppe

left and the exit the lower right: We would like to generate many random mazes to find one that

vists as many cells as possible

COSC $2436$: Homework #$6$

The solution to the $30$x$30$ maze, shown here, covers $100$ of the $900$ cells in the maze, about $11\%$

of the eells. We would like to generate a maze that covers evern more cells and thus, requires

our maze generation algorithms sereatedly:

COSC $2436$: Homework #$6$

Assignment

Using C$++$ generate the code necessary to produce mazes. For this Homework, you should create

a class to hold, solve, and save a simply connected maze; one that is an MST with exactly one

$($ simple path between any two points. We will use an outside pre $)/($ shortest path solution between the upper left to lower right cells. $)$

Programming Requirements

To complete the assignment, you will need to implement a maze class. Construct mazes that are

$200\backslash$times $200$ cells, using a specified starting seed and one of the two algorithms we discussed

Accept as user input the starting seed value$($integer$)$ and use it to seed the random number

Accept as input one of two options for the algorithm $($Kruskal$\text{'}$s and Prim's$)$ to use to

make the maze. You will need to support both algorithms for making the mazes to

Generate a $200$x$200$ maze using the starting seed for the random number generator and

the algorithm selected. Solve the maze from a starting point in the upper left to an ending

point in the lower right.

Generate and solve one million $(1,000,000)$ mazes with different random seed values for

each algorithm and record the shortest path distances for each maze.

Generate a histogram including the results of the one million mazes for each algorithm

and discuss the differences in a short report.

name. Optionally, load and display the maze. the shortest$-$path solution from the start in

the upper left to the end in the lower right. Display the count of the cells visited along the

shortest path as well as the percentage.

Note: You will need to develop your own test cases for this problem. You should find the

seed that provides highest number of cells in the shortest path.

Hints: To solve this problem, recognize that the cells in the maze ar