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 mystifying 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.
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", "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:
Do not print out anything else. You will lose points if you do. Any debugging output should be removed before you turn in. Your command line should work exactly as described above, even if you have extra options used with extra-credit.
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:
key(node) =
|nodex - exitx| + |nodey - exity|
The
The algorithm for Best-First Search is: insert the
entrance location into a priority queue, where its key (priority value) is its
key(node) =
distance_from_start_to_node + |nodex - exitx| + |nodey
- exity|
You will need to keep track of the true distance from the start in each node. Then, when find the neighbors of a node, their distance is the distance of the current node plus one.
There are also some other minor but important modifications you need to make to the Best-First algorithm:
We have supplied the declarations for rooms, nodes, and mazes, as well as the input routine for mazes. You may use any priority queue implementation you like, such as one of Java's built in classes or the code from Weiss (which is available on his home page.) Be sure to say what you use for the queue. Everything else will be coded by you. You may do the project in C if you wish, however you will have to implement all the code we gave you in C yourself. Your implementation needs to take the exact same command-line arguments as described above.
Part B: Using the test mazes in the Examples.zip file:
RUNNER-FILENAME
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 for f in maze*.txt; do for a in dfs bfs best astar; do java MazeRunner $a -input $f -final $a-$f >> results done done
In the file MazeJavaCode.zip are:
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.
The file Examples.zip
contains the test mazes. Each file begins with 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|
+-+-+-+-+-+-+-+
Want to see how the mazes were generated? Generator.zip contains the program used to create the mazes.
· Come up with an A* heuristic that expands fewer nodes than the one specified above, and still guarantees optimal solutions. You can demonstrate your heuristic on graphs you create yourself that are designed to show that is it better.
Recall that any heuristic which is a lower bound on the true distance will still guarantee optimal solutions. So to improve the one specified above, you need to come up with a heuristic which is always smaller than the true distance, but is "smarter" than the one above. To show that your heuristic is smarter, you need to come up with input where your heuristic does better than the fist one.
Here is one approach that might work. If the
current and goal nodes are on the same row or column, then the