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:
- Depth-First Search (DFS).
Look here for more information.
- Breadth-First Search.
Look here
for more information.
- 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 (*).
- 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.
- 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:
- 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.
- 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
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:
- MinHeap.h, MinHeap.cpp
- Compare.h
- runmaze.cpp
- 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
- 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
The files you should turn in (using the Unix
turnin tool. This project is called "project7" in
the turnin system):
-
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.
Each group should only turnin only one copy of their project.
VI. Extra credit
- 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.
- 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.
- 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.