CSE 326 Homework 7, Winter 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:
   • Did A* search always find equal or shorter in length solutions as compared to the other search algorithms? If so, can you argue that A* still performed better? Justify your answer.
     
     
   • Did any search method perform just as well as A* Search? If so, describe why you think that occurred.
     
     
   • Design a non-trivial, small maze that both DFS and A* search perform better than BFS and Iterative Deepening.
     
     
   • On what mazes did Best-First search perform poorly on? Describe briefly the qualities of a bad maze for this search method.
     
     
   • The maze generator discussed in Weiss only generates mazes without cycles. For such mazes, is depth-first search guaranteed to find optimal solutions? Explain why or why not. How could you easily modify the mazegen algorithm to allow some cycles in the maze?

III. Provided Code

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

Odds and Ends

• You may work in groups of at most three people on the project.
• Be certain to read over the code in the RandomMazeRunner files. This will be a good foundation to base your work on.
• Your old friends, stacks and queues, might come in handy on this project.
• Make judicious use of the ExtraNodeInfo structs in the MazeRunners.
• Outputting a solution
  After solving a maze, a MazeRunner should spit out one solution path calculated by the 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. On the next line should be the length of the solution path, and on the following line should be the number of nodes expanded in the search. 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) (2,4) (3,4) (4,4) (4,5) (4,6) 
       10
       15
  

  The solution path looks like:

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

  Note that a search might involve visiting many nodes not on the solution path. You will have to find a means of extracting the path from the collection of nodes you visited.
• 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).

V. Turning in your code

• All of your C++ code. This includes all .h and .c files you coded and those that you were provided with.
• README - the members of your group, the distribution of work among the members of the group, an explanation of your design decisions, the issues that came up while writing this project, as well as
a one to two paragraph explanation of the differences between the different maze solvers that you implemented. Were you surprised by how well or poorly any performed? Intuitively, what makes the good solvers better than the poor ones? We're not looking for formal proofs, just your honest opinions and intutitions.
• answers Contains your answers for the questions in part B.
• results Contains your resultss for running the search methods over the 13 test mazes.
• Makefile - A Makefile which compiles your mazegen and runmaze programs. You will lose points for not including a Makefile this time.

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.