Lab 6: Maze

When you clone your repository, you will see the following files. Files you may need to change appear in bold.

We can group these files into the major components of the maze lab, which we recommend implementing in the given order:

For this and future labs, you will occasionally be provided with implementations of the ADTs we discussed in class. These implementations make use of the C++ standard template library (STL) and are written as classes named e.g. STLList. To use these classes, simply #include the header the same way you normally would, using the directory names as necessary (e.g. #include "adts/stlList.h). You are welcome to inspect these files, but recall that a feature of implementing ADTs is that you only need to know the interface. The STLList, for example, has the exact same interface as your LinkedList implementation from last week:

The LinkedQueue and LinkedStack classes appear in the like-named files in your starter code. As we discussed in lecture, these classes are easily implemented using a linked list; you can find a linked list implementation in the form of the STLList class in the file adts/stlList.h. You should proceed by implementing each of the methods in the files linkedQueue-inl.h and linkedStack-inl.h. These methods are not meant to be complex; they require very little code to complete. You do not need to throw your own exceptions from these objects' methods since the underlying list will do so for you. For example, while pop() should raise an exception if it is called on an empty list, the STLList will throw this for you when you try to remove an element from an empty list.

This lab includes an OrderedCollection abstract class which describes the commonalities between queues and stacks (also as discussed in lecture). Note that e.g. LinkedQueue is a subclass of both Queue and OrderedCollection, so it will need not only enqueue and dequeue methods but also insert and remove methods. The insert and remove methods can be implemented simply by calling enqueue and dequeue; we will rely on this commonality later to reduce the amount of code you need to write!

Once you’ve completed your LinkedQueue and LinkedStack implementations, run the unit tests (make testStackQueue followed by ./testStackQueue) to see if they are working correctly. After these tests pass, proceed to the Maze part of the lab.

Once you have completed your LinkedQueue and LinkedStack implementations, you are prepared to implement the search algorithms we discussed in lecture. We begin by considering how we will represent the mazes we intend to solve.

Each maze is a rectangular grid. Each space in the grid is connected to the orthogonally adjacent spaces. That is, from any location in the grid, you can move one space right (east), down (south), left (west), or up (north); you cannot move diagonally. The starting point of every maze is the upper left corner; the exit is in the bottom right.

The layout of a particular maze will be stored in a text data file with the extension .map; you can find several examples in your test_data directory. We have already written the code which loads files in this format for you; this explanation is just for reference. A map file contains the following:

For instance, the following is a valid map corresponding to the grid in the figure:

This class is written for you, but you’ll need to make frequent use of this class, so it’s helpful to understand what it does.

Each Position object contains information for one place in the maze: the (X,Y) coordinates (where (0,0) is in the upper-left), and some fields which will be used during the search to construct an appropriate path through the maze. The constructor of the Position class takes the X and Y coordinate values and initializes the other fields to suitable default values.

A Maze object represents our knowledge of a particular maze; we can use this information to find a path through the maze using various search strategies. The Maze class stores the maze characters as a one-dimensional array. It also stores a one-dimensional array of Position* representing the locations within the maze. Both arrays are length width*height, which is the total size of the maze. Remember that we’ve seen that you can represent two-dimensional data in one dimensional arrays in the picfilter lab. The constructor, destructor, and many of the basic getters and setters of this class have been written for you.

The Maze class has several private methods to help you implement the search strategy: isExit, inBounds, and getNeighbors. Be sure to implement these first. Note that, when you implement getNeighbors, you should explore your neighbors in the following order: east, south, west, and then north. While the search process would work with any ordering of the neighbors, the unit tests we have written for you expect that you are using this ordering.

The Maze class has two public methods: solveBreadthFirst and solveDepthFirst. These will perform the appropriate search algorithm and return an answer. The answer is in the form of a List<Position*>*: a pointer to a new list of positions which constitute a correct path through the maze from start to finish. These two algorithms are very similar: they only differ in which data structure they use to perform the search! Regardless of whether we are using a stack (depth first) or a queue (breadth first), the search algorithm goes as follows:

† Once you have found the exit, you need to build a list containing the path from the start of the maze to the end. To do this, you can start from the end position and follow the previous position pointers backward, adding each Position* to a list until you reach the start. Then, simply return that list to end the search. If you exit the loop without finding the exit to the maze, then no path exists.

To avoid writing the same code twice, we can implement the above algorithm in the private method solve. This method takes an argument of type OrderedCollection<pair<Position*, Position*>> and uses that data structure during the search. Then, solveBreadthFirst and solveDepthFirst both call solve, each providing an appropriate data structure. Your solve method will return the list of positions that describe the correct path through the maze (or a nullptr in the event that no such path exists).

Make sure to run the provided unit tests on your code as you develop using make testMaze and ./testMaze; definitely test your code once you’ve finished the Maze class! It’ll be easier to find most bugs in your Maze implementation by direct testing than it will be by trying to find them by hand by running the maze program.

The implementation for main relies mostly on the classes you have already completed and is thus relatively short for such a large lab assignment. The loadMap and renderAnswer functions have been written for you. loadMap will read a map file; it will return a Maze* if load is successful and will throw a runtime_error otherwise. renderAnswer will produce a string containing a solution, which looks like the map from the map file but contains @ characters on the path that you found. For instance, here is a one example execution of the program:

Let’s try the same map using depth-first search:

Note that BFS should always find paths that are less than or equal in length to paths found by DFS on the same maps. Again: to ensure that you see the same results as the provided samples, examine neighbors in the following order: east, south, west, north.

Your program will take two command-line arguments:

If there is a solution to the provided map, your program should print the rendering of that solution. If there is no solution, your program should print a message to that effect.

Your program is required to run without any memory errors. Use valgrind to determine if you have any memory errors; we will do so, and any errors reported by valgrind will result in lost points. You should also use valgrind as a debugging tool as you develop your program.

You are also required not to have any memory leaks, although memory leaks will be scored far more generously. You are encouraged to worry about memory leaks only after your program is working correctly. Once your program works, commit and push it and then consider making changes to solve leaks. It’s much better to have a correct, leaky program than it is to have a leak-free program that crashes.

As usual, you will also be required to observe good coding practices: