CSE 326 Data Structures Project 2

CSE 326 Data Structures
Project 2
A Smarter Maze Solver

Due: Friday, January 28, 2000

Objectives

Introduce Priority Queue ADT
Apply Heap and d-Heap Data Structures

Overview

The Priority Queue ADT provides very similar functionality to stacks and queues. However, stacks and queues use a "blind" policy to choose the next object to remove from storage. That is, they do not know (nor do they need to know) anything about the objects, and the order the objects are removed is independent of the objects' properties. Sometimes these blind policies are insufficient for the needs of an algorithm. Priority queues use an evaluation function provided by the object to always remove the lowest scoring object in the queue.

If we use the same algorithm as used in the last project for depth first search and breadth first search but use a priority queue as the storage structure, we get a new kind of search which can take into account the promise of unsearched nodes for reaching a solution. This new algorithm is called "Best First Search" (which is not generally abbreviated for obvious reasons). Best First Search requires a heuristic function, a function which provides an approximate judgment on the quality of a node. Given this function, it explores the most promising leads in the maze first, leaving poor prospects for later search.

The algorithm for Best First Search is: insert the entrance location into the priority queue. Then, until the priority queue is empty or the exit is found, delete the minimum location from the priority queue, find its children, and insert each child location onto the priority queue as long as it has not already been visited. That should sound very familiar.

N.B.: I promise that the next programming assignment will not involve MazeRunners!

Assignment

For this assignment, you are required to write a new MazeRunner, an extension of the abstract MazeRunner class we provide, which uses Best First Search to find routes through mazes. The Best First Search MazeRunner will use a priority queue. We will provide an abstract base class for a priority queue; you should extend that class to implement a concrete priority queue using a heap with a parameter which controls its "arity" (2-heap vs. 3-heap vs. d-heap; the heap should default to a 2-heap). Your MazeRunner should refer to only the abstract base class PriorityQueue except for the one line at which you initialize the priority queue. You should also write a program which will take a maze as input (in a file format described below) and output a solution path for the maze from your MazeRunner.

Your heap implementation should also automatically resize its array if more items are insterted than can fit into the array. Because of this, the 20x20 limit on maze size from the previous assignment is removed!

Note that on this assignment it may be necessary for your MazeRunner to refer to SquareMazeNode and SquareMaze explicitly in order to calculate values for the heuristic. Try to restrict this to as small a portion of your code as possible (in particular, your compator class). Elsewhere, refer to MazeNode and Maze.

Here is the heuristic function for rating the value of a SquareMazeNode which you should implement and use as the innards of your comparator class:

value(node) = (|node_x - exit_x| + |node_y - exit_y|) * maze_height * maze_width + node_x * maze_height + node_y

Note that this is Manhattan distance plus some extra stuff. The extra stuff ensures that every priority value is unique.

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.

We strongly encourage working in teams of two!. However, if you end up working alone, you do not have to implement dynamic resizing of the heap.

What we've provided

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

PQueue.h,PQueue.cpp

These declare the abstract base class "PriorityQueue". PriorityQueues are templated according to the type of Object stored in the queue as well as the comparator used to determine the minimum queue element. You may not change these files. You should extend PriorityQueue to implement a parameterizable d-Heap which is also templated according to both objects type in the queue and comparator. In a separate file, construct a comparator for SquareMazeNode pointers or whatever data type you place on the heap. For SquareMazeNode pointers, the class declaration would look something like:

class SquareMazeNodeCompare {
  bool operator() (const SquareMazeNode * larg, 
                   const SquareMazeNode * rarg);
};

Note that the word template does not appear here; SquareMazeNodeCompare does not need to be (and probably shouldn't be) a templated type.

MazeRunner.h,MazeRunner.cpp

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

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 MazeRunner should (mostly) 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).

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 MazeRunner rather than the RandomMazeRunner.

UnsLLPQueue.h,UnsLLPQueue.cpp

These provide a sample concrete PriorityQueue (an Unsorted Linked List Priority Queue) which stores the nodes in an unordered, doubly-linked, circular list. Inserts are fast (just put the node in) but deletes require checking the whole list.

sort.cpp

This is a file that may be useful to you for understanding PriorityQueue and for testing your implementation. It takes a list of numbers as input and sorts the numbers using a priority queue. This will also be useful in answering the questions for the assignment. Make sure you type ./sort to run sort (as another utility called sort exists).

Makefile

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

All provided files can be found in the project directory:

/cse/courses/cse326/00wi/project2

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 project2/inputs that you can use to test your program.

Outputting a solution
The program should spit out one solution path calculated by Best First Search. The path should be given on a single line and should consist of the printed locations (using the builtin print method) separated by spaces. The path should have a line before it saying "Best First". For example, the path output for the maze above might be:

      Best First
      (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)

The solution path looks like:

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

Handing in the code

You are required to hand in your project2 directory with your implementation of the MazeRunner. Included in this directory should be at least the files containing your MazeRunner, your heap implementation, your solution to the sort question below, and your comparator class, along with your README and any additional files you used or changed.

Note: of the files we provide to you, you should need to change only Makefile and runmaze.cpp (of course, you may create whatever files you wish). If you want to change any other files in the project, contact one of us first!

Turn your files in electronically using turnin:

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

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 MazeRunner, heap, and Priority calculator

Also answer the following questions (justify your answers, of course, 3-4 sentences apiece should be fine):

Is Best First Search gauranteed to find the shortest solution to the maze?
The makeEmpty function in UnsLLPQueue.cpp is described in a comment as "ridiculously inefficient". How ridiculously inefficient is it? Write pseudocode that would implement a more efficient version of makeEmpty. How efficient is your version?
Modify sort.cpp to produce one million random numbers and output the first ten thousand in sorted order. Which arity of heap runs this algorithm the fastest: 2-heaps, 3-heaps, or 4-heaps? Why do you think this is so? (Justify your answer with test results!)
What did you enjoy about this assignment? What did you hate? Could we have done anything better? What are Nic's, Zasha's, and Steve's middle names?

Additional utilities

We've provided a few utilities to help you develop and test your program. These are located in the directory project2/bin.

Maze generator

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

      % ./mazegen -d20x12 > myMaze.txt

will put a rectangular maze with 20 columns and 12 rows into myMaze.txt. The -m option asks for a maze with multiple paths from start to finish, rather than a maze with a single solution. Type mazegen -h to see all its options.

Sample maze solver

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

      % ./bin/bestfirstsolve < mazefile > mazesoln

will solve mazefile and put the paths into the file 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

This will display the maze and solution paths from above in a window.

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 bestfirstsolve on the maze, displaying the results using pathshow.

Extras (bonus)

Fast merging: implement one of the advanced heap data structures discussed in class (skew heaps and leftist heaps). Think of and implement a small but reasonable application that requires fast merging of priority queues and give experimental results showing whether your heap implementation is faster than normal d-heaps.
A* search: there is a version of Best First Search called A* with some theoretically and practically interesting qualities. Contact Steve to get a reference to A*, and write an A* MazeRunner. Comment on its advantages and disadvantages.
Only if you didn't do it last time 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.