CSE 326 Homework 7, Winter 2002

Due on the midnight after Wednesday, March 13, 2002
(by electronic turn-in)

No late turn-ins will be accepted
after 2:30 PM Friday, March 15, 2002

I. Introduction

It is an incredibly important day for you at work at Minotaur, Inc. You've managed to arrive before any of your fellow co-workers, meaning you have first dibs on some freshly-baked donuts IF you can get there in time. Unfortunately, your pointy-haired boss had the cubicles rearranged during the night, turning the whole office space into a complex and mistifying maze. Since you doubt you can find the true path in time, you decide to let your computer solve the maze for you.

Graph search algorithms easily lend themselves to solving mazes. Each square of a maze can be viewed as a node in a graph. Two nodes are connected by an edge if the squares they represent are adjacent in the maze and a wall is not between them. You will implement several maze solvers that use different graph search techniques.

II. The Assignment

Part A: You will be required to implement several new MazeRunner classes that are all extensions of the abstract MazeRunner class provided. Using the code provided, you will implement the following graph search algorithms as these new MazeRunner classes:

  1. Depth-First Search (DFS).
    Look here for more information.

  2. Breadth-First Search.
    Look here for more information.

  3. Iterative Deepening Search.
    Iterative deepening is depth-first search to a fixed depth. In the case of a maze, you first try all paths of length 1 from the start. If you do not reach the exit, you try paths of length 2, then of length 3, etc. Eventually, you should reach the exit assuming it was a well-formed maze. You may assume the mazes are well-formed. For more information on iterative deepening, look Look here .

    The algorithm for Iterative Deepening is: Set i=1. (*) Consider each path of length i from the start. If a path ends in the exit of the maze, stop the algorithm. Otherwise, increment i and return to (*).

  4. Best-First Search.
    Best-first search means you always choose the path that makes you the closest to the goal (the exit of the maze). To determine the distance from the goal, we want you to use what is known as the manhattan distance . The manhattan distance is the distance you would have to walk if you were forced to only move on the lines of a grid (or on the streets that make up a city block). Mathematically, it is calculated as:
    value(node) = |nodex - exitx| + |nodey - exity|

    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 neighbors, mark each neighbor with its manhattan distance to the exit, and insert each neighbor location onto the priority queue as long as it has not already been visited.

  5. A* Search.
    A* Search is an incredibly powerful search technique used in AI. A* Search uses a heuristic function, a function which provides an approximate judgment on the quality of a node (i.e., how far it is from the exit). Given this function, it explores the most promising leads in the maze first, leaving poor prospects for later search. As it turns out, this approximation will often give better performance than even Best-First search. Try to design a maze where the Best-First algorithm will perform poorly.

    Importantly, A* Search is provably optimal! It will always return the most efficient solution to any maze you give it.

    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 neighbors, mark each neighbor with a value according to some heuristic function, and insert each child location onto the priority queue as long as it has not already been visited.

    Here is the heuristic function for A* search:

    value(node) = (distance_so_far + |nodex - exitx| + |nodey - exity|) * maze_height * maze_width + nodex * maze_height + nodey

    Note that this is manhattan distance plus some extra stuff to ensure that every priority value is unique.

Part B: For each of the ten bigmazes and for the three nocycles mazes (found in the inputs directory-- see below), you should do the following:

  1. Run each of the five mazerunners on each maze. Record the path length found and the number of nodes each search algorithm had to expand in a separate file named results.

    NOTE: Do not run RandomMazeRunner on the larger mazes. You will be there for days.

  2. Answer the following questions and record them in a file named answers:

III. Provided Code

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 this file. 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.

For more information on using comparators, please look here at information from a previous quarter.

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 a specific MazeRunner based on the following command-line input:

     runmaze -runner random < maze.txt    // for random search
     runmaze -runner dfs < maze.txt       // for depth-first search
     runmaze -runner bfs < maze.txt       // for breadth-first search
     runmaze -runner ids < maze.txt       // for iterative-deepening
     runmaze -runner best < maze.txt      // for best-first search
     runmaze -runner astar < maze.txt     // for A* search
MinHeap.h, MinHeap.cpp, HeapInst.cpp
These provide a sample concrete PriorityQueue (an array-based minimum binary heap) that also uses a comparator. You will need to complete any of the unfinished code in this class. HeapInst.cpp is used for properly instantiating the MinHeap class.
p4sort.cpp, p4sortCompare.h
This is a file that may be useful to you for understanding MinHeap, using comparators, 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. The comparator class used by this algorithm is found in p4sortCompare.h. 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 for any new files you create.
GPKernel.h, GPKernel.cpp, VisualizeSquareMazeRunner.h ,VisualizeSquareMazeRunner.cpp
These files are used for maze visualization. You do NOT have to edit these. In fact, if you do edit them, the course staff is not responsible for any loss of hair, teeth, or sanity that may result.
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 /inputs that you can use to test your program. The test mazes are called maze0-6.txt. The other mazes will be used for answering questions.

To retiterate, you should ONLY have to change the following files:

  1. MinHeap.h, MinHeap.cpp
  2. Compare.h
  3. runmaze.cpp
  4. Makefile
If you so choose, you can modify the other files. If you decide to use your own Heap class, it MUST use a comparator class. All provided files can be found here .

Odds and Ends

V. Turning in your code

The files you should turn in (using the Unix turnin tool. This project is called "project7" in the turnin system): Each group should only turnin only one copy of their project.

VI. Extra credit

  1. A Maze Generator: After successfully claiming your donuts (we recommend the ones with sprinkles) by solving the maze, you can choose todesign a maze generator to further test the robustness of your maze solvers. After all, you never know when your boss will rearrange the office.

    Write a program called "mazegen" that generates a well-formed 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 above. Be sure that your generator has no intrinsic limitations on the size of the maze. Edit your makefile to compile this mazegen program.

    Extra bonus: Incorporate cycles into your mazes efficiently.

  2. 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.

  3. Go all out: We're letting you express your creative side here. Currently, the mazes you construct likely don't have cycles. How can you efficiently add cycles to the maze? How about mazes with multiple exits? Or with trapdoors that randomly move you around the maze? How about mazes with multiple floors? Or rendering the maze in 3-D? If you do anything above the basic design specifications, document what you did and we will be curious to see your artistry. Of course, your code should still meet the basic requirements.