Files and Required Functions / Classes

In order to create some modularity, your program will be written in several files and should utilize several functions. We will give you skeletons for them.

• maze.cpp: the main maze-solving program.
• mazeio.cpp and mazeio.h: routines for input and output.
• queue.cpp and queue.h: the definition of the Location structure and Queue class.

mazeio.cpp

our mazeio.cpp must define the following functions:

char** read_maze(char* filename, int *rows, int *cols); 

Use file streams to read the maze from the given filename. Return NULL if the file does not exist, or you are unable to read two numbers from the start of the file. Dynamically allocates a 2D array for the maze and returns it. The rows and cols arguments should point to variables (check maze.cpp line 16) that can be filled in with the dimensions of the maze read in.

void print_maze(char **maze, int rows, int cols); 

Prints the maze dimensions and maze contents to cout in a two dimensional format. (Your completed program will call this after filling the shortest path with asterisks.)

queue.cpp

our queue.cpp/queue.h files will define the Location structure as well as the following API for the Queue class:

Queue( int max_size); // constructor ~Queue(); // destructor void Queue::add_to_back(Location loc); // add new location Location Queue::remove_from_front(); // get oldest location bool Queue::is_empty(); // am I empty? 

Most of the class definition will be provided for you. You will have to fill in the body of the add_to_back and remove_from_front functions.

maze.cpp

Your maze.cpp should be broken modularly into two functions:First,

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

Starts the program, calls the input function, solves the maze, prints the output. Note: the main function is not yet complete.Second,

int maze_search(char**maze, introws, intcols) 

Given a maze, performs the BFS search for a valid path, filling in the path with * if found. Returns 1 if a valid path was found, 0 if no path was found, and -1 if the input is of the wrong format. Specifically, it should check that the input contains exactly one start (S) cell and exactly one finish (F) cell.Keep in mind the following restrictions:

• You must exclusively use dynamically-allocated arrays of exactly the right size for this assignment. If you do not use dynamic memory, it is unlikely you will pass all of the test cases.
• A valid path consists of steps north, west, south, and east but no diagonals. Thus we only need to explore neighbors of a cell in those 4 directions, not along diagonals.

BFS Pseudocode

Here is the review of BFS description given earlier:

mark the start location as explored add start location to q while q is not empty do: set loc = extract the item from the front of q for each neighbor (i.e., N,W,S, and E) of loc do: if the neighbor is valid, open, and not yet explored do: mark the neighbor as explored add the neighbor to the back of q set predecessor of the neighbor = loc 

Simplification

While the order of exploration doesn't matter, to help the course staff debug your code (in case you need help) and to ensure we all get the SAME shortest path if many exist, you should explore a cell's neighbors in the following order: North, West, South, East.

The 'Explored' Array

You need to avoid adding any location to the queue more than once. Otherwise, your search can cycle infinitely or exceed the maximum queue size. We do this by creating a data structure that remembers, for each cell, if it's already been added to the queue or not. This data structure should let you look up, for a given location (row/col indices), whether that cell has already been explored, or not yet explored.What type of structure could you use for this?In your code, you will need to dynamically allocate and initialize this structure before you start the BFS algorithm.The 'Predecessor' Array

The final step is actually locating the optimal path and marking it with *. This requires a little more bookkeeping, like a "trail of breadcrumbs" that you can follow from the finish back to the start.This is the predecessor array referred to earlier. It should be a 2D array of Locations, so that for a given [row][col], you can lookup the Location (row/column) of which neighbor caused it to be added to the queue (i.e. was its predecessor.)The predecessor is utilized to find the actual path when your algorithm is complete: we trace it from the finish back to the start. In other words, the predecessor of the finish cell will tell us how to go back one step, then that cell's predecessor will tell us how to go back another step, and so on until we reach the start cell.Essentially, as we walk back the next step backward can be found from our curr (current) location by accessing pred[curr.row][curr.col]Here are some more questions to consider:

• Where should the backtracking start and finish?
• What kind of loop should you use for backtracking?

Writing your code

The following is just a set of suggestions as to how you can develop the code while keeping the debugging work as simple as possible.

Checkpoint 1: Input/Output

Complete the mazeio.cpp code so that you can read/write mazes. In main() of maze.cpp, write a program that simply reads the input and prints it to the screen without trying to solve it. Again, don't forget that your maze has to be dynamically allocated.Compile and run your program:

make maze ./maze maze1.in 

should produce

.S.#. ##.#. ..... .#### ....F 

Check that the printed output looks correct.

Checkpoint 2: Deallocate the mymaze array in main.cppAfter we are done with our mymaze array, don't forget to deallocate it at the end of main(), so that we don't get memory leak errors.At this point you can also decide where you want to implement basic format checking of the input maze. Don't forget to deallocate what has been allocated when you encounter an error. Thinking about where and how to do that can lead to varying amounts of code that need be written.We have defined several messages that you can print out to ensure your formatting is correct:

 const char* invalid_char_msg = "Error, invalid character."; const char* invalid_maze_msg = "Invalid maze."; const char* no_path_msg = "No path could be found!"; 

Note: The last message is when the maze has no solution.You should also test your program with valgrind and ensure there are no errors.

valgrind --tool=memcheck --leak-check=yes ./maze maze1.in 

Checkpoint 3: Queue

You will need to implement the constructor, destructor, add_to_back(), and remove_from_front() member functions of the Queue class in queue.cpp. Each function requires only 1-2 lines. add_to_back() should add the incoming Location to the end of the list. remove_from_front() should return the Location that has been waiting the longest to be removed. Each of these functions should update the appropriate counter. For help with the syntax, see the description of the member variables in queue.h and also look at how is_empty is defined in queue.cpp.For some hints, go back to Queue section on the previous page in the guide!!Execute the following two commands in terminal.

make queue_test ./queue_test 

It should print out:

true false 3 1 2 2 true 

Checkpoint 4: Core BFS algorithm

Prerequisites:

1. Add the #include "queue.h" header to maze.cpp.
2. complete the main function to call this the maze_search() function correctly.

In maze_search():

1. Find the start and finish cells and check that the maze is valid. Return -1 for a badly-formatted maze.
2. Create your queue with an appropriate size i.e., rows*cols
3. Dynamically allocate the predecessor and explored arrays. If applicable, you may also need to initialize them.
4. Perform the breadth-first search algorithm described earlier.
5. When the algorithm is done and the finish cell is found, add the code to walk the predecessor array backwards from the finish location to the start location, filling in the intermediate locations of the maze with *.
6. Make sure all dynamically allocated memory is deallocated (for the predecessor and explored arrays).
7. Return the correct status code: 1 for success, 0 for no path exists.
8. Compile and run your program on all available sample cases, as well as the one you created yourself. The more testing, the better.

Does your program successfully distinguish mazes where a path exists, from ones where a path does not? You should be able to run it on all of the test cases.

Debugging Tip

If need be, print out the location (its row and column) of each item you add or remove to the queue so that you know that the order of exploration is correct and that it makes sense to you. Trace through the input manually and see if your code works the same way.Here is one sample run:

make maze ./maze maze1.in 

should produce

5 5 .S*#. ##*#. ***.. *#### ****F

Complete mazeio.cpp and maze.cpp

mazeiocpp:

/*

mazeio.cpp

*/

#include

#include

#include "mazeio.h"

using namespace std;

/*************************************************

* read_maze:

* Read the maze from the given filename into a

* 2D dynamically allocated array.

*

* Return the pointer to that array.

* Return NULL (a special address) if there is a problem,

* opening the file or reading in the integer sizes.

*

* The first argument is the filename of the maze input.

* You should use an ifstream to open and read from this

* file.

*

* We also pass in two pointers to integers. These are

* output parameters (i.e. declared by the caller and

* passed-by-reference for this function to fill in).

* Fill the integers pointed to by these arguments

* with the number of rows and columns

* read (the first two input values).

*

*************************************************/

char** read_maze(char* filename, int* rows, int* cols)

{

// *** You complete **** CHECKPOINT 1

}

/*************************************************

* Print the maze contents to the screen in the

* same format as the input (rows and columns, then

* the maze character grid).

*************************************************/

void print_maze(char** maze, int rows, int cols)

{

// *** You complete **** CHECKPOINT 1

}

queue.cpp

/*

queue.cpp

*/

#include "queue.h"

//Constructor. maxlen must be as large as the total number

// of Locations that will ever be entered into this Queue.

Queue::Queue(int maxlen) {

contents = new Location[maxlen];

head = 0;

tail = 0;

// *** You complete **** CHECKPOINT 3

// need storage!!

}

//Destructor. releases resources. C++ will call it automatically.

Queue::~Queue() {

// *** You complete **** CHECKPOINT 3

delete[]contents;

}

//Insert a new Location at the end/back of our list

void Queue::add_to_back(Location loc) {

// *** You complete **** CHECKPOINT 3

contents[tail].row = loc.row;

contents[tail].col = loc.col;

tail++;

}

//Return and "remove" the oldest Location not already extracted

Location Queue::remove_from_front() {

// *** You complete **** CHECKPOINT 3

head++;

return contents[head - 1];

}

//Is this Queue empty? (did we extract everything added?)

//This is complete, you don't need to change it.

bool Queue::is_empty() {

return head == tail;

}

maze.cpp

/*

maze.cpp

*/

#include

#include "mazeio.h"

// #include "queue.h"

using namespace std;

// Prototype for maze_search, which you will fill in below.

int maze_search(char**, int, int);

// Add other prototypes here for any functions you wish to use

// main function to read, solve maze, and print result

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

int rows, cols, result;

char** mymaze=NULL;

const char* invalid_char_message = "Error, invalid character.";

const char* invalid_maze_message = "Invalid maze.";

const char* no_path_message = "No path could be found!";

if(argc < 2)

{

cout << "Please provide a maze input file" << endl;

return 1;

}

mymaze = read_maze... // <---TASK: COMPLETE THIS FOR CHECKPOINT 1

// For checkpoint 2 you should check the validity of the maze

// You may do so anywhere you please and can abstract that

// operation with a function or however you like.

//================================

// When working on Checkpoint 4, you will need to call maze_search

// and output the appropriate message or, if successful, print

// the maze. But for Checkpoint 1, we print the maze, regardless.

print_maze(mymaze, rows, cols);

//================================

// ADD CODE BELOW

// to delete all memory that read_maze allocated: CHECKPOINT 2

return 0;

}

/**************************************************

* Attempt to find shortest path and return:

* 1 if successful

* 0 if no path exists

*

* If path is found fill it in with '*' characters

* but don't overwrite the 'S' and 'F' cells

* NOTE: don't forget to deallocate memory in here too!

*************************************************/

int maze_search(char** maze, int rows, int cols)

{

// *** You complete **** CHECKPOINT 4

return 0; // DELETE this stub, it's just for Checkpoint 1 to compile.