CSE 326 Homework 6, Autumn 2002
Due on the midnight after Monday, December 9, 2002
(by electronic turn-in)
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 a MazeRunner class, which
will run through a maze using different search techniques. The MazeRunner
class should be run from the command line in the following form:
java MazeRunner alg -input infile [-final
picfile]
where alg is either "dfs", "bfs", "ids", "best", or
"astar", infile is an input file containing maze information, and picfile
is a file to output a picture the final state of the maze to. Note that the
"-final picfile" parameter is optional. The MazeRunner class will read
the maze file contained in infile, run through it using the search
algorithm specified by alg, and, if the -final option is given, print
out a picture of the resulting maze to the file picfile.
The program should print out, in order:
- the name of the input file,
- the type of search algorithm used,
- the path found as a list of coordinates in the form (x,y),
- the length of the path length found,
- the number of nodes expanded in the search for a solution, and finally
- a blank line.
A sample output:
mazefile.txt
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
To perform the maze runs, you will need to implement
the following search algorithms to run through the maze:
- 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
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.
We have supplied the declarations for rooms, nodes, and
mazes, as well as the I/O routines for mazes. Everything else will be coded
by you.
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 search algorithms 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. (This file can be automatically
generated from the output of the program.)
- Include in the turnin a set of the final solution picture files: for each
of the input files from part B, include a file named
RUNNER-FILENAME.txt
where RUNNER is the name of the algorithm used and FILENAME the name of
the maze file. For example, java MazeRunner astar -input bigmaze1.txt -final astar-bigmaze1.txt >> results creates astar-bigmaze1.txt.
Note that it is easy to run all these experiments by writing a simple
script. For example, assuming the input files are in the current directory,
echo > results
foreach f (bigmaze*.txt maze?.txt nocycles?.txt)
foreach a (dfs bfs ids best astar)
java MazeRunner $a -input $f -final $a-$f >> results
end
end
- 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:
EasyReader.java
The EasyReader class is used by the Maze class, and is designed to provide simple access to the I/O console. (Information about it may be found
here.)
Maze.java
The Maze class itself. It contains
inner classes RoomNode (representing a room in the maze) and RoomList (representing
a list of rooms). The Maze constructor takes the name of a maze file as a
parameter, and parses it to create the maze. It also contains a blank printMaze()
routine (guess what that does?)
VisitedState.java
A short class which serves as a container
for some constants relating to the state of a particular room in the maze.
Sample input files
Above is a link to a zipfile containing sample input files (extract the inputs with the
command unzip hw6-inputs.zip in Unix.) The Maze class reads a maze file, the file format being 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|
+-+-+-+-+-+-+-+
The test mazes are called maze0-6.txt. The other mazes will
be used for answering questions.
Odds and Ends
- You may work in groups of at most three people on the project.
- Your old friends, stacks and queues, might come in handy on this project.
- 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.
V. Turning in your code
The files you should turn in (using the Unix turnin tool. This
project is called "project6" in the turnin system):
- All of your Java code. This includes all .java files you
coded and those that you were provided with.
- The files containing maze solutions output by a run of each
algorithm.
- 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.
Each group should only turnin only one copy of their project.
VI. Extra credit
- Visualization: Create a visualization routine that runs as the
maze is being solved. Pop up a window that shows the graph, with different
colors used to indicate the state of each room. Drawing routines will need
to be invoked when the maze is create and from setState. The visualization
routine should be enabled by the command line option -v.
- More Visualization: In addition to doing (1), create an applet version
on a web page that can be used to give instructional demos.
- 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 thismazegen
program.
If you did (2), then make this part of the applet, so a user can generate
and solve mazes interactively.
- Add an option to allow the mazerunner to knock down walls at a given
cost. The command line option
-knock INTEGER
specifies the cost of knocking down a wall. For example,
-knock 3
means that you can walk through walls, but the distance through
a wall is considered to be 4 (=3+1) rather than 1.
Implementing this will require changing the create maze routine
to create weighted graphs. Therefore you should also add a dijkstra
option for alg and compare it to A*. (DFS and BFS ignore
the weights.)
Try this on some examples, and discuss how changing the cost
of knocking down a while affects the search.
- Come up with entirely new feature to add to mazes and to the solver.
For example, "portals" -- if two squares on the input are labeled with the
same letter, you are allowed to move between them in a single step.
- 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.