You will be asked to solve and generate mazes using a queue and a stack, respectively. These processes are independent of the implementation choices for the queue and stack.

Let's consider a maze as a 2-D array of spaces, where between each space there is a wall or not. The start point of the maze will be the upper left and the finish point is the lower right. For example, we will use the following maze, while this is graphical you will represent walls with * and open spaces with a .

Notice that the maze has a width and height, and we index spaces in the maze with (w,h). The top left index is (0,0), and the bottom right index is (width-1,height-1). The maze will always start in the upper left and finish in the bottom right. We will describe two spaces as "reachable" if they are adjacent and do not have a wall between them.

Solving a Maze with a Queue

The process of solving a maze with queue is a lot like "hunting" out the end point from the start point. To do that, we must ensure that we test all possible paths. The queue will allow us to track which spaces we should visit next.

The basic routine works as follows:

Initialize a queue with the start index (0,0)

Loop Until: queue is empty

Dequeue current index and mark it as visited

If current index is the finish point

Break! We've found the end

Enqueue all indexes for reachable and unvisited neighbors of the current index

Continue the loop.

Looking over this routine, imagine the queue, full of spaces. Each time you dequeue space you are searching around for more spaces to search out next. If you find any, you add them to the queue to eventually be analyzed later.

Because of the FIFO nature of a queue, the resulting search pattern is a lot like a water rushing out from the start space, through all possible path in the maze until the end is reached. This search pattern is also referred to as Breadth First Search (or BFS).

The P should show the progress of the visited location.

For consistency, you should always enqueue the indexes into the queue in the order that they are provided via the getReachableUnvisited() neighbors method (see below). That is enqueue index 0 of the returned list first, then the next index, and so on. In this way, your algorithm match mine and should work like the animation above. The final state of your maze should look like below, once again this is a graphical representation but you will create yours with *, , and P. You should use system(clear) each time before printing the maze. For debugging purposes you should cin.ignore() after printing the maze so the output will stop until you hit enter.

Drawing a Maze with a Stack

The process of drawing a maze is very similar to solving a maze, but instead the goal is to explore all spaces, removing walls along the way, such that there exist a path between any two spaces through a series of reachable spaces. That also means that there will exist a path from the from the start to the end.

The algorithm to ensure all reachability will work as follows:

Initialize a stack with the start index (0,0)

Loop Until: stack is empty

pop current index off the stack and mark it as visited

If current index has any unvisited neighbors

Choose a random unvisited neighbor index

Remove the wall between the chosen neighbor index and the current index

push the current index on the stack

push the randomly choose neighbor index on the stack

Continue the loop.

Looking over this routine, you should be able to invision how this procedure will dive through the maze randomly, like a snake, until the snake reaches a dead end (a space without any unlisted neighbors). The exploration of the snake would then have to backtrack until there is a space with unvisited neighbors and explore from there. Eventually, the snake will have explored the entire maze, at which point, you're done. This search pattern is also referred to as Depth First Search (or DFS)

For consistency, you should make a random choice from the reachable neighbors like so:

int r = rand() %4;

Where l is the list of reachable neighbors, rnd is a Random object, and r is the index of the randomly selected neighbor. If you follow this procedure, you should be able to match the generation routine in the above animation.

Maze files

I can use an maze file, you are to create and test several files. Files are formatted as follows, the number of rows and number of columns will be on the first line. The remaining lines will represent a wall locations. The ending of the maze will be the far right column that does not have a wal.

8 6

0 0

0 1

0 2

0 3

0 4

0 5

0 6

1 6

2 0

2 2

2 4

2 6

3 0

3 2

3 4

3 6

4 0

4 2

4 3

4 4

4 6

5 0

5 4

5 6

6 0

6 2

6 3

6 4

7 0

7 1

7 2

7 3

7 4

7 5

7 6

Could not open file

Maze.cpp and .h

class Maze {

Maze();

/**

* Constructor that creates a maze and assigns the initial position

*

* @param maze String containing the information of the maze

* @param initialR Row number of the initial position

* @param initialC Column number of the initial position

* */

Maze(String maze, int initialR, int initialC);

/**

* Sets the initial position to the given row and column in the maze grid

*

* @param r The row number of the initial position

* @param c The column number of the initial position

* @return False if the initial position is not valid, true otherwise

* */

boolean setInitial(int r, int c)

/**

* Return the space at the position given

*

* @param r Row number of the space that needs to be returned

* @param c Column number of the space that needs to be returned

* @return Space element at row r, column c

* */

Space getSpace(int r, int c);

/**

* Given a specific space element, it returns a set of spaces around it that are free.

*

* @param currentSpace The space of which the neighbors need to be checked

* @return Returns the set of free spaces neighboring in a stack structure

* */

stack getFreeNeighborsStack(Space currentSpace);

/**

* Finds the exit from a given Space, if found, returns true otherwise it returns false

*

* @param currentSpace The space that is being focused on, the one from which it finds the exit

* @return True if an exit is found, false if not (the stack is empty)

* */

boolean findExitStack(Space currentSpace);

/**

* Returns the solution stack with all the spaces that have been visited

*

* @return The stack containing the solution

* */

stack getSolutionStack();

/**

* Given a specific space element, it returns a set of spaces around it that are free.

*

* @param currentSpace The space of which the neighbors need to be checked

* @return Returns the set of free spaces neighboring in a queue structure

* */

queue getFreeNeighborsQueue(Space currentSpace);

/**

* Finds the exit from a given Space, if found, returns true otherwise it returns false

*

* @param currentSpace The space that is being focused on, the one from which it finds the exit

* @return True if an exit is found, false if not (the queue is empty)

* */

bool findExitQueue(Space currentSpace);

/**

* Gets the solution in the queue format

*

* @return A set of spaces in the format of the queue

* */

queue getSolutionQueue();

//Method that manages errors, depending on a certain index

void errorFound(int n);

private:

//All the spaces in a two dimensional array

Space[][]grid;

//The total number of rows and colums

int rows, cols;

//The current row and column of the Space

int currentR, currentC;

//Stack of the found free neighbors in the stack

stack freeNeighborsStack;

//Stack of the solution spaces, to be printed to the file

stack solutionStack;

//Stack of the found free neighbors in the queue

queue freeNeighborsQueue;

//Queue of the solution spaces, to be printed to the file

queue solutionQueue;

};

Space.cpp and .h

class space {

public:

space();

space(char type, int row, int col);

int getRow();

char getType();

void setType(char type);

int getCol();

private:

vector type;

int row;

int col;

};

Required Command Line Declaration for File read

The full declaration of main looks like this:

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

The integer, argc is the ARGument Count (hence argc). It is the number of arguments passed into the program from the command line, including the name of the program. The array of character pointers is the listing of all the arguments. argv[0] is the name of the program, or an empty string if the name is not available. After that, every element number less than argc is a command line argument. You can use each argv element just like a string, or use argv as a two dimensional array. argv[argc] is a null pointer. How could this be used? Almost any program that wants its parameters to be set when it is executed would use this. One common use is to write a function that takes the name of a file and outputs the entire text of it onto the screen.

#include

#include

using namespace std;

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

{

if ( argc != 2 ) // argc should be 2 for correct execution

// We print argv[0] assuming it is the program name

cout<<"usage: "<< argv[0] <<" ";

else {

// We assume argv[1] is a filename to open

ifstream the_file ( argv[1] );

// Always check to see if file opening succeeded

if ( !the_file.is_open() )

cout<<"Could not open file ";

else {

char x;

// the_file.get ( x ) returns false if the end of the file

// is reached or an error occurs

while ( the_file.get ( x ) )

cout<< x;

}

// the_file is closed implicitly here

}

}

This program is fairly simple. It incorporates the full version of main. Then it first checks to ensure the user added the second argument, theoretically a file name. The program then checks to see if the file is valid by trying to open it. This is a standard operation that is effective and easy. If the file is valid, it gets opened in the process.

Your Program output will either be

Could not open file

Or

Stack Solution

With the individual steps appearing one at a time

Queue Solution

With the individual steps appear one at a time