Objectives

• Review stack and queue ADTs
• Become comfortable with the programming environment

Overview

Despite their simplicity, stacks and queues are powerful tools for storing and accessing data. In particular, these data structures are at the heart of two of the most important algorithms in computer science: depth first search (DFS) and breadth first search (BFS).

Among other things, DFS and BFS can be used to solve mazes. A DFS of a maze involves following some path through the maze as far as we can go, until a dead end or previously visited location is met. When this occurs, the search backtracks to try another path. BFS proceeds differently: it visits the locations in order of their distance from the entrance. First it visits all locations one step away, then it visits all locations that are two steps away, and so on, until the exit is found. Because of this, BFS has the nice property that it will naturally discover the shortest route through the maze.

The algorithms for DFS and BFS work very similarly. DFS starts by pushing the entrance location onto the stack. Then, until the stack is empty or the exit is found, it pops off a location from the stack, finds its children, and pushes each child location onto the stack as long as it has not already been visited (currently or previously on the stack). BFS starts by enqueueing the entrance location. Then, until the queue is empty or the exit is found, it dequeues a location from the queue, finds its children, and enqueues each child location as long as it has not already been visited.

Assignment

Teams

You may work on a team of at most two on this assignment. You may choose how to divide the work under three conditions: first, document each team member's effort in the README file; second, work together and both understand your answers to the questions below; and third, understand at least at a high level how your team member's code is structured and how it works. Remember to test your team's code as a whole to make sure that your portions work properly! Also, be aware that except in extreme cases when you notify us in advance of the deadline, all team members will receive the same grade for the project.

If you end up working alone, you may implement just one Stack and one Queue class, but otherwise, you will be responsible for the same tasks.

What we've provided

As a starting point we've provided a few files:

MazeRunner.h,MazeRunner.cpp

These define the abstract type which your MazeRunners will extend. You must implement all the undefined functionality in the abstract MazeRunner in each of your concrete MazeRunners.

RandomMazeRunner.h,RandomMazeRunner.cpp

This is a sample concrete MazeRunner which takes a random walk through the maze trying to get out.

Maze.h,Maze.cpp

These contain the abstract Maze type over which your MazeRunners should work.

SquareMaze.h,SquareMaze.cpp

These contain an implementation of a standard type of Maze (each location is square and potentially connected to four neighbors; the entire maze is rectangular). Note that your MazeRunner does not explicitly deal with this class!

runmaze.cpp

This is the main driver code for the program which we have partially implemented. Currently, it reads a maze from standard input, runs the maze with a RandomMazeRunner, and optionally views the run with the maze visualization tool. Finally, it prints the solution to the maze. You should modify the program to use your two MazeRunners in succession (DFS then BFS) rather than the RandomMazeRunner.

Makefile

make runmaze will use this to build your program. You will need to modify the makefile to add any new files you create.

/cse/courses/cse326/00wi/project1

Input files

SquareMaze reads a maze file from the standard input. The file format is a picture of the maze. There is also some header information at the front that gives the dimensions of the maze. In the maze, '-' and '|' are used for walls, ' ' for rooms and unblocked passages, '+' for the corners of the rooms, '*' for the entrance, and 'X' for the exit. For example:

      7 5
      +-+-+-+-+-+-+-+
      |*|   | | |   |
      + +-+ + + +-+ +
      |   |   |     |
      + + + +-+ +-+ +
      | |   |     | |
      + +-+-+ +-+-+ +
      |       |     |
      +-+ + +-+-+ +-+
      |   |        X|
      +-+-+-+-+-+-+-+

There are some sample input files in the directory project1/inputs that you can use to test your program.

Outputting a solution
The program should spit out two solution paths: one computed by DFS, the other by BFS. Each path should be given on a single line and should consist of the printed locations (using the builtin print method) separated by spaces. Each path should have a line before it saying which algorithm produced that solution (e.g. BFS or DFS). For example, the path output for the maze above might be:

      DFS
      (0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (3,3) (3,2) (4,2) (4,1) (5,1) (6,1) (6,2) (6,3) (5,3) (5,4) (6,4) 
      BFS
      (0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (2,4) (3,4) (4,4) (5,4) (6,4) 

      +-+-+-+-+-+-+-+
      |*|   | | |   |
      +.+-+ + + +-+ +
      |.  |   |.....|
      +.+ + +-+.+-+.+
      |.|   |...  |.|
      +.+-+-+.+-+-+.+
      |.......|  ...|
      +-+ + +-+-+.+-+
      |   |      ..X|
      +-+-+-+-+-+-+-+

Handing in the code

You are required to hand in your project1 directory with your implementation of the MazeRunners. Included in this directory should be at least these files:

• DFSMazeRunner.[h,cpp], BFSMazeRunner.[h,cpp], runmaze.cpp, Stack.[h,cpp], Queue.[h,cpp], Makefile
• Your README file
• Any additional files you used or changed.

Turn your files in electronically using turnin:

% cd ~/326stuff/myproj1dir
% make clean
% cd ../
% turnin -c cse326=AA -p p1 myproj1dir

The README

Your README file should document your submission (though it does not by any means replace comments in the code!). It should contain the following:

• Your name(s) and team name
• Approximately how long the project took you to complete
• If you worked on a team, a breakdown of the work
• Acknowledgement of any assistance you received from anyone but your team members, the 326 staff, or the Weiss book
• A list of the files in your submission with a brief description of each file
• A high level description of your MazeRunners, Stacks, and Queues
• An example of a maze on which BFS performs much better than DFS and one on which DFS performs much better than BFS

• Why is the "as long as it [the child location] has not already been visited" clause in the description of BFS and DFS above more important for DFS than BFS?
• If you gave your MazeRunners a maze that was too large to fit in main memory, which would likely run faster? (This is a tough question; just try to think of a reasonable answer and justify it. Don't sweat getting the "right" answer.)
• Can you think of any methods for generating random mazes?
• What did you enjoy about this assignment? What did you hate? Could we have done anything better? Which is the coolest userID: zasha, bone, or wolf (note: the instructor will grade this question)?

Additional utilities

Maze generator

The executable mazegen generates random mazes to standard output. For example, invoking:

      % ./bin/mazegen -d20x10 -m > mazefile

Sample maze solver

The executable mazesolve is our sample solution for this assignment. Use it to see what we expect from you.

      % ./bin/mazesolve < mazefile > mazesoln

Viewing solutions

The sample code supplied for your programs has some extra flags that will display a solution. It will go into "Show Solution" mode if you pass it the flags -v -s, like this:

      % cat mazefile mazesoln | runmaze -v -s

The cat mazefile mazesoln part is important - the show solution mode expects to see a maze, followed by one or more solutions.

Displaying progress towards a solution

You can run the 'runmaze' program with the supplied code with the -v flag to visualize its progress. Try this with the random solver so you can see how it works (you have to call setVisitationState in MazeNode to make the colors change).

Utility scripts

We have also provided two scripts, called maze.sh and soln.sh. We do not support these, but they may make it easier for you to run your program and compare it with our sample solution. Run maze.sh using the same parameters as for mazegen. This will generate a maze and run your program on it, showing results using pathshow. Then run soln.sh to run our mazesolve on the maze, displaying the results using pathshow.

Extras (bonus)

• Iterative Deepening Search (IDS): IDS is a search that combines the advantages of DFS and BFS using the unintuitive step of re-searching portions of a maze (tree). Contact Steve (wolf@cs) to get a reference about IDS, and write an IDS MazeRunner, comparing its effectiveness and efficiency to BFS and DFS.
• Visualization: we have provided you with visualization tools to assist in debugging. Extend our visualization tool or create a new one to better track how your algorithm works.