CSE 326 Project 4, Autumn 2000

DUE THURSDAY NOVEMBER 30, 2000 at noon (preliminary README and headers)

DUE WEDNESDAY DECEMBER 6, 2000 at 8PM (complete project)

Objectives

Introduce Priority Queue ADT.
Apply Heap Data Structure.
Uptrees for a Maze Generator.
Create an Entire Program from Specification.

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 virtual world 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 A* Search. A* 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 A* 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.

Assignment

Part A: For this assignment, you are required to write a new MazeRunner, an extension of the abstract MazeRunner class we provide, which uses A* Search to find routes through mazes. The A* 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 binary 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.

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 comparator 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) = (distance_so_far + |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 to ensure that every priority value is unique.

Part B: You must also write a program called "mazegen" that generates a maze. It must use up-trees as the core datastructure with both weighted unions and path compression. The generator takes as input two parameters: the width of the maze and the height of the maze. It outputs a valid maze in the format shown below. Be sure that your generator has no intrinsic limitations on the size of the maze. We're not giving you any code for Part B: you write the functional program written in C++ that outputs correct mazes (one path from start to exit, all exterior walls intact, etc) by using uptrees. You don't need to implement this using generic templates, though you certainly can. Focus on getting solid code. Comments, of course, are still required.

If you find any of the code we've given you helpful, feel free to use it as part of your maze generator, but again, you're not required to do so.

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; third, each team member must work on both Part A and Part B; and fourth, 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. (It should then default to a sufficiently large capacity, like 100,000.) Let me repeat: we strongly encourage working in teams of two!.

What we've provided

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

PQueue.h

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 binary 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 * left_arg, 
                   const SquareMazeNode * right_arg);
};

Note that the word template does not appear here; SquareMazeNodeCompare does not need to be (and probably shouldn't be) a templated type. A sample is also in Compare.h.

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.

p4sort.cpp

This is a file that may be useful to you for understanding PriorityQueue and for testing your implementation. It takes a number as an argument, generates that many random numbers, and outputs them in sorted order using a priority queue. Note: the program is called "p4sort" because "sort" is already a unix command.

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. You should ensure that the makefile compiles a program called "mazegen" that satisfies Part B.

All provided files can be found in the project directory:

/cse/courses/cse326/00au/project4

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

Outputting a solution
The program should spit out one solution path calculated by A* 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 "A* Search". For example, the path output for the maze above might be:

      A* Search
      (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

Due on Thursday, November 30th: a preliminary version of your README and header files for your priority queue, A* Search Maze Runner, and your maze generator.

Due on Wednesday, December 6th: everything else. You are required to hand in your project4 directory. Included in this directory should be at least the files containing your MazeRunner, your heap implementation, your comparator class, and your maze generator, 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, runmaze.cpp, p4sort.cpp, and Compare.h if you choose to use it. Of course, you may create whatever files you wish. If you want to change any other files in the project, contact Alex first.

Turn your files in electronically using turnin:

% cd ~/326stuff/myproj4dir
% make clean
% cd ../
% turnin -c cse326 -p project4 myproj4dir

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 (no need to list files we provided that you didn't change).
A high level description of your MazeRunner, heap, Priority calculator, and maze generator.

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

The makeEmpty function in UnsLLPQueue.cpp is described in a comment as "ridiculously inefficient". How ridiculously inefficient is it? How would you make it better and how efficient would your version be?
What did you enjoy about this assignment? What did you hate? Could we have done anything better?

Additional utilities

We've provided a few utilities to help you develop and test your program. These are located in the directory project4/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. Note: your generator does not need to support all of those options.

Sample maze solvers

The executable bestfirstsolve is a sample solution that uses best first search.

      % ./bin/bestfirstsolve < mazefile > mazesoln

will solve mazefile and put the paths into the file mazesoln.

Also included is mazesolve, a program that outputs a solution using depth-first search, breadth-first search, and a random walk.

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)

D-Heaps: Implement d-ary heaps, skew heaps, or leftist heaps. If you implement d-ary heaps, check how long p4sort requires to sort 1 million numbers for d=2, 3, and 4. Which is the fastest and why? If you choose skew heaps or leftist heaps, think of 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 binary heaps.
Visualization: we have provided you with visualization tools to assist in debugging and understanding how algorithms work. Extend our visualization tool or create a new one to better track how your algorithm works.