The goal of this assignment is to review the use of classes and dynamic arrays in C$++,$ both in the context of a maze generation application. The assignment is worth a total of $75$ points. If you have any questions or need any help, please visit us during office hours and$/$or post questions on edstem.

If you need to post any of your actual source code on edstem for any reason, please be sure to tag the post as being private $/$ visible to instructors only, so that you don't inadvertently share code with others and violate class rules on plagiarism.

What is a Maze?

A maze is a puzzle, with starting and ending points, in which a player is tasked to find a path connecting an starting point to an ending point. Many algorithms for automatically generating random mazes have been proposed. In this assignment we will implement a randomized depth$-$first search approach that uses dynamic arrays. For the context of this assignment, every maze is two$-$dimensional and it only contains $1$ starting and $1$ ending cell. There should be exactly one path connecting both cells. The example below illustrates a random maze of dimensions n$=6,$ m$=12,$ n rows and m columns. Note that the starting point always happens at cell $0,0$ and the ending point at n$-1,$ m$-1.$

Maze Generation

A data structure for representing a maze in memory may be a two dimensional array in which every cell encodes whether each of the $4$ walls is closed or open. We can assume each cell has $4$ walls: north, south, east, and west.

The algorithm for generating a maze starts with a grid where only $2$ walls are removed, north for the starting position, and south for the ending position, as illustrated in the $6$x$6$ grid below.

A common approach for maze generation involves removing interior walls iteratively. At each iteration a wall is removed to connect two adjacent cells. This iterative process must follow these rules:

walls to be removed should be selected randomly. Use std::rand$()$ to generate random numbers and std::srand$()$ to provide a seed to the random number generator

there should be exactly one path connecting the starting and ending cells

every cell must be reachable from the starting cell

The algorithm below should be followed in your implementation. This is not the most efficient way to solve the problem of maze generation, however it is easy to understand and can be implemented with the support of simple data structures such as dynamic arrays $($std::vector in C$++).$

We strongly suggest you to trace this algorithm on paper using a small example $($e$.$g$.$ a $4$ x $4$ grid$)$ until you fully understand how it works, before starting to code.

create empty dynamic array $`$A$`$

mark cell $[0,0]$ as visited

insert cell $[0,0]$ at the end of $`$A$`$

while $`$A$`$ is not empty

$`$current$`<-$ remove last element from $`$A$`$

$`$neighbors$`<-`$current$`\text{'}$s neighbors not visited yet

if $`$neighbors$`$ is not empty

insert $`$current$`$ at the end of $`$A$`$

$`$neigh$`<-$ pick a random neighbor from $`$neighbors$`$

remove the wall between $`$current$`$ and $`$neigh$`$

mark $`$neigh$`$ as visited

insert $`$neigh$`$ at the end of $`$A$`$

endif

endwhile

In order to match the autograder tests, picking a random neighbor must follow this procedure: "check the neighbors of a cell in N$-$S$-$E$-$W order and append the ones that were not visited yet into an empty vector neighbors, then use the index idx below to pick a random neighbor with neighbors$[$idx$]"$

idx $=$ std::rand$()/(($RAND$\_$MAX $+1$u$)/$ neighbors.size$())$;

Your Task

Your goal in this assignment is to develop a command line tool that will generate a random maze, given some options provided by the user.

Command Line Arguments

Your program must accept the following command line arguments:

the seed value for the random number generator

number of rows in the grid N $>0$

number of cols in the grid M $>0$

file name for the output

The seed argument is very important as it initializes the random number generator. If you change the seed, you will generate a different maze. In your code make sure you call this function exactly once before generating the maze:

std::srand$($seed$)$;

The last argument will be used to save the generated maze into a text file. Note that you can provide any value as fname. See the example below:

$ $./$generator $01010$ example.txt

Maze file format

The file format for saving the maze is just a two dimensional array of integers, where each integer is used to represent a cell and its walls. Each integer in the matrix ranges from $0$ to $15.$ The idea behind this representation is that the walls are encoded using $4$ bits, and the ingeters are just their corresponding values in decimal notation. The figure below illustrates the encoding:

When saving the grid, the output file must be a text file in which cell values are separated by a single whitespace, and organized in n rows and m columns $($the grid dimensions$).$ For example, the image below shows one grid with $5$ rows and $5$ columns. The text file representation of