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) = |node_x - exit_x| + |node_y - exit_y|

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

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