Starting from:
$30
Project 2 - The search for a-MAZE-ing donuts! Solution
I. Introduction
It is an incredibly serendipitous day for you at the Paul Allen Center. A mysterious bearded benefactor has appeared during the night and has left behind donuts for the entire CSE 326 class! You've managed to get out of bed at a yawningly-early 10 AM, meaning you have first dibs on all the yummy goodness of fresh-baked donuts if you can get to them in time (and the always hungry grad students from the night before haven't beat you there). Unfortunately, the Allen Center space czars just happened to have decided to rearrange all the furniture during the night (as part of their experimentation with different settings in the new building), turning the entire building into one complex and mystifying maze. You haven't had your morning coffee yet, and you just don't feel like running around looking for donuts—but you're so hungry! Why not let your computer solve the maze and find the donuts FOR you?
II. Learning Objectives
In this assignment, you will:
Work on the PriorityQueue ADT, and implement your own data structures.
Gain experience with systematic testing.
Explore the similarities and differences between recursive and iterative algorithms.
See an application of the Stack, Queue, and PriorityQueue ADT's in maze search.
Gain experience analyzing and modifying an existing code base.
Train your computer to do your most important tasks for you—like finding donuts!
III. Assignment and Algorithm Overview
For the complete assignment, you are required to write several new maze-solving MazeRunner classes, each with one or more associated data structures. There should be one MazeRunner class for each of the following algorithms:
Depth-First Search (DFS) — please implement this search with a Stack
More information on DFS can be found here.
Breadth-First Search (BFS) — please implement this search with a Queue
More information on BFS can be found here.
Best-First Search (not abbreviated for obvious reasons) — please implement this using your priority queue implementations, with your MazeRunnerLauncher choosing among implementations as specified in Section IVb
More information on Best-First Search can be found here.
IIIa. Phase A: DFS and BFS
Your task for Phase A is to implement a stack, a queue, a depth-first search maze runner and a breadth-first search maze runner, according to the interfaces provided. Your data structure implementations should automatically grow (if interested you may also make them shrink—this is optional) as necessary. You should test these implementations to be sure they are correct before proceeding to Phase B. We'll also ask you to design and implement a collection of unit tests to verify that your code works properly.
Note: Growing an array implementation one element at a time is not likely to be the most time efficient solution; if you use arrays, try to come up with a more time-efficient solution. You may reuse any code you wrote for Project #1 for this purpose but be sure that you implement the interfaces provided for this project.
You are free to implement the stacks and queues as you wish, although arrays are as simple as anything. Our usual rule prohibiting use of the Java class libraries to do the actual work remains. You should also take this opportunity to get an understanding of how the three graph search algorithms described here work for a general graph.
You should also implement unit tests for your data structures and verify that your code passes the tests. You should turn in a TESTING.txt file with an informal description of your test plan. Summarize the tests you implemented and explain how they provide comprehensive test coverage for your classes. This should not just be a dump of the test names and comments from the code file—we can read that. What we want is to get an idea of the thinking behind what you did. We recommend use of JUnit, but this is not a requirement. The testing strategy you discuss in TESTING.txt will be evaluated as a part of the project, but the code of your actual unit tests will not.
IIIb. Phase B: Priority Queues and Best-First Search
For Phase B you will write several implementations of the Priority Queue ADT and a best-first search maze runner to use them. Specifically, you will write a binary heap, a three heap, a d-heap, and a pointer-based heap (one of: skew heap, leftist heap, or binomial queue). You will also need to modify MazeRunnerLauncher.java to accept command line arguments appropriate for each type of maze runner or priority queue. Finally, you'll need to answer the questions from the write-up and turn them in in README.txt.
All of this is more work than it sounds, so do not leave it to the last minute.
IV. Detailed Requirements
IVa. Clarifications
In your implementations of Queue and PriorityQueue, you should throw a NoSuchElementException (java.util.NoSuchElementException) if dequeue, peek, findMin, or deleteMin are called on an empty queue. Obviously, this means it's OK to import java.util.NoSuchElementException in your code.
Your d-heap class should implement the PriorityQueue interface.
When writing your additional pointer-based implementation (either a LeftistHeap or a SkewHeap or a BinomialQueue) of a PriorityQueue, do not use implementations of these that you may find on any web site - including the web site for our text book! Such use will be considered a violation of our collaboration policy. You are free to refer to skeleton code provided in our text book or in other course materials; however, the code you turn in should be your own.
Your priority queue implementations must accept Comparable objects.
Many classes such as String and Integer implement the Comparable interface. In Phase B you will need to modify/create some more classes that implement theComparable interface (in other words, writing your own compareTo method). Then you will be able to have priority queues containing those objects. Unlike your stacks implementations for Project1 that were hardcoded to use doubles, your implementations of the Stack, Queue, and PriorityQueue interface need to use generics. Your implementations need to use compareTo when comparing elements so the code will work on any Comparable object. More information about Java's Comparable interface may be found at Sun's website. In addition, you might find this description from CSE 143 of Fall 2006 to be useful. Both generics and the Comparable interface are discussed in section 1.5 of the Weiss text, and there is a good tutorial on Sun's web site. The tutorial is based on this paper by Gilad Bracha, one of the Java language designers.
IVb. Input and Output
INPUT:
You are required towrite MazeRunner classes for BFS, DFS, and BestFS. Please modify MazeRunnerLauncher to use EXACTLY the following parameters to determine which search algorithm to use:
-BFS
use BFS
-DFS
use DFS
-BestFS
use BestFS
You should assure that all of your PriorityQueue implementations work with MazeRunner. Please modify MazeRunnerLauncher to use EXACTLY the following parameters to determine which priority queue implementation to use when needed:
-bin
use Binary Heap
-three
use Three Heap
-dheap #
use a d-heap, where d = #
-ptr
use your pointer-based heap (Leftist, Skew or Binomial)
The MazeFactory class reads a maze from a text file specified on the command prompt. 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 (width, then height). In the maze, '-' and '|' are used for walls, ' ' for rooms and unblocked passages, '+' for the corners of the rooms, '*' for the start, and 'O' for the donut. (Note: start and donut can be in any cells in the maze, not just the corners.) Once you find the donut, you get to chow down and then exit out of the maze. For example, the following is a legal maze :
7 5
+-+-+-+-+-+-+-+
|*| | | | |
+ +-+ + + +-+ +
| | | |
+ + + +-+ +-+ +
| | | | |
+ +-+-+ +-+-+ +
| | |
+-+ + +-+-+ +-+
| | O|
+-+-+-+-+-+-+-+
There are some sample input files in the starter files mentioned above that you can use to test your program. You are highly encouraged to write (and share with your classmates!) other test mazes to run your MazeRunner on. Send them to us or post them on the message board (preferred).
OUTPUT:
After solving a maze, your MazeRunner should output the name of the search algorithm used followed by the solution path calculated by the search. The path should be given on a single line and should consist of the printed cells from the start to the exit, separated by single spaces. On the next line should be the length of the solution path, and on the following line should be the number of cells visited in the search, including cells that were not completely explored (i.e., marked "Visit in progress" when the search completes). For example, the output for the above maze might be:
Random search:
(0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (2,4) (3,4) (4,4) (5,4) (6,4)
Length of path: 10
Number of cells visited: 15
Please note that the start and end cells are both included, but the length of the path is the number of edges traversed ( one less than the number of cells visited). Please do not include extraneous output. For the other search algorithms, use text "Breadth-first search:", "Depth-first search:" and "Best-first search:".
The solution displayed above corresponds to the solution path shown below with dots:
+-+-+-+-+-+-+-+
|*| | | | |
+ +-+ + + +-+ +
|. | | |
+ + + +-+ +-+ +
|.| | | |
+ +-+-+ +-+-+ +
|. . . | |
+-+ + +-+-+ +-+
| |. . . . O|
+-+-+-+-+-+-+-+
Note that your MazeRunner does not need to output a text-graphical solution such as the one displayed above.
Note also that a search very likely involves visiting many nodes that are not on the final solution path. You will have to explore ways of keeping track of the solution path from the collection of nodes you visited. RandomMazeRunner gives an example of how this might be done. You will need to modify this technique to work for your algorithms.
IVc. README.txt Questions
Your README.txt should contain the following information and answer the following questions:
The names of your team members and your team's name
A breakdown of the work - a brief who-did-what description.
How much time did you spend on this project?
Acknowledgement of any assistance you received from anyone but your partner, the course staff, or the Weiss book.
Did you do any extra credit? If so, describe what you did and give instructions on how to run your code.
Why is it more important for DFS than BFS to check whether a cell has been visited yet?
If you gave your MazeRunners a maze that was too large to fit in main memory, which would likely run faster, BFS or DFS? (Any reasonable answer—as long as it is justified—will be accepted.)
In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?
Why is it important that a heuristic be easy to compute? Why is it important that a heuristic yield unique (or almost unique) values?
Why is BFS guaranteed to find the shortest path? Are the other two algorithms guaranteed to find the shortest path? If yes say why, if not, give a counter example.
What are the tradeoffs between a pointer vs. array-based heap? In particular, what are the tradeoffs between a binary heap, a threeheap, and a pointer-based heap? Some possible topics to cover include runtime, coding complexity, and memory usage. Did you observe any differences (for example in runtimes or memory use) between using these three for the larger maze inputs? (Just note if you noticed anything, it is fine if you did not. You are welcome to explore this question in more detail (timings, measurements, calculations) for extra credit.)
In general (not necessarily in the context of this project), why could it be better to use a sorted array implementation of a priority queue versus a binary heap? Why could it be worse?
What did you enjoy about this assignment? What did you hate? Could we have done anything better?
IVd. Grading Breakdown
The amount of code required for this project is actually very small. A significant part of your grade will be based on your program design and your README.txt.
Correctness - 40%
Architecture/design - 30%
README.txt - 30%
Look at the course grading policy for a more detailed explanation on grading guidelines.
V. Provided Code
The skeleton code can be downloaded as p2code.zip. Some of the important files are:
PriorityQueue.java — interface for a PriorityQueue ADT. All of your heaps should implement this..
Stack.java — interface for a Stack ADT.
Queue.java — interface for a Queue ADT.
MazeRunnerLauncher.java — the launcher that you'll need to modify to accept the specified command line arguments and construct the appropriate MazeRunner
MazeRunner.java — interface that each MazeRunner should extend. You may be able to prevent a significant amount of code duplication by handling your MazeRunner inheritance appropriately.
For Phase A we provide interfaces for a Stack and a Queue, as we as an example MazeRunner (RandomMazeRunner, which picks the direction to explore in a random fashion.). You must write the implementations of the provided Stack and Queue interfaces as described above. Your own MazeRunner classes should inherit from the abstract MazeRunner class.
For Phase B we provide code to read the input maze given as a text file, parse it, and build a Maze class object from it, which your algorithm will operate on. We also provide the interface for the Priority Queue ADT, PriorityQueue.java. You must write several implementations of the PriorityQueue interface–a BinaryHeap, a ThreeHeap, a DHeap, and a pointer-based priority queue of some kind. For the array-based heaps (BinaryHeap, ThreeHeap, etc.) you can start with a copy of your code from one and make changes as necessary, although making the original code easy to generalize making appropriate use of inheritance may save a lot of time (hint, hint).
You are not required to modify any of the provided files besides MazeRunnerLauncher.java.
Further documentation on the Maze code architecture and how to get started can be found here. If you find the large codebase a bit overwhelming, this is good place to start.
VI. Logistics and Extra Information
Teams
You are encouraged (although not required) to work with a partner of your own choosing for this project. You may choose how to divide the work between the two of you under three conditions:
You must document each team member's effort in the README file (record this now so you have the info for the Phase B readme file);
Work together so that you both understand your answers to the questions answered in the README (for Phase B);
Understand (at least) at a high level how your team member's code is structured and how it works (code for both Phases A & B).
Remember to test your team's code as a whole to make sure that your portions work together properly! Also, be aware that except in extreme cases and provided you notify us in advance of the deadline, all team members will receive the same grade for the project.
Subversion and Group Spaces
If you would like to use a shared group directory, please contact one of the TA's for instructions. This is NOT necessary, just optional if it is your preference.
We can create shared space on attu for each group if you wish to set up a subversion repository; we'll have more details once the project groups are finalized.
Each group can have a Subversion repository available if you wish to use a repository to coordinate modifications to your code base. Subversion is useful for both teams and individuals, as it allows you to store backups of your code in a central server. For teams, each team member may be working on the code concurrently, and Subversion checks for conflicts when the changes are committed. For more information about Subversion, try the Subversion book. That link describes how to use Subversion on the command-line; you can also use TortoiseSVN on Windows (documentation) or the Subclipse plugin for Eclipse (not yet installed on the lab machines, but go here for install instructions for your own machine and here for usage instructions). The repository address is:
svn+ssh://username@attu.cs.washington.edu/projects/instr/09sp/cse326/project2/groupname
where username is your username and groupname is username1-username2 for pairs and username for loners.
Testing Strategy
To facilitate understanding of this rather complex project, and to encourage good modular decomposition and "unit testing" (testing small pieces of code instead of testing the entire program all at once), we suggest improving and testing your "helper" data structures (i.e. Stack, Queue, BsinaryHeap, ThreeHeap, etc.) without worrying about the Maze-related code.
Your tests should be:
Comprehensive - you should cover all types of behavior your code might exhibit. For example, if a method's specifiication says it might throw an exception in certain cases, you should test those cases in addition to normal behavior. Also be sure to check edge cases - maybe your stack works fine when there are five elements, but what if there is just one? Or zero?
Modular - as much as possible, test each method separately, and keep the tests small and self-contained.
Concise - good test coverage is not synonymous with having lots of tests that are fundamentally the same. (Hint: You may be able to reuse a single suite of tests for both implementations of the priority queue if you think about how to take advantage of interface types and maybe inheritance in the test code. Massive cut-'n-paste is not a good an alternative.)
Using JUnit is straightforward. Your section should cover the basics of writing test cases; to run a test case from the command line, do:
java junit.textui.TestRunner MyTestCase
where MyTestCase if the name of one of your TestCase classes. Eclipse has a JUnit GUI built in; see here for a howto.
VII. Getting Started
After downloading the provided code, compile everything and try to run the provided random mazeRunner from the launcher class as follows:
% java MazeRunnerLauncher -r sample-inputs/maze2.txt
(Or try one of the other mazes in sample-inputs) The "-r" option invokes the random maze runner. Take a look at RandomMazeRunner.java to get a general idea of how things work. After understanding this file, make a copy (say BFSMazeRunner.java) and try implementing a better algorithm.
To add these files to your SVN repository, you should do an svn add <filename for each file. To import into Eclipse, you can drag-and-drop the files into your project or go to File-Import...
VIII. Going Above and Beyond
The following suggestions are meant for you to try if you finish the requirements early. Be sure to clearly describe what you did and how to run it in your README.txt. Recall that any extra-credit points you earn for these are kept separate from your assignment score and will be used to adjust your grade at the end of the quarter, as detailed in the course grading policy. Please don't put extra credit code in your main turnin—instead, put modified versions of your files in an archive extracredit.zip.
Using the Manhattan distance has several problems, including the fact that the MazeRunner is sometimes fooled into going down "dead ends" in the maze. What other heuristics might be used in your MazeRunner? When might your heuristics perform better than the Manhattan distance, and when might they perform worse (you may want to consider factors such as space usage and time to calculate the heuristic)? Implement and run your Best-First MazeRunner with its new heuristic on several mazes and report which heuristic performed better, and in what type of maze it did better in. (2 points)
There is a variation of the Best-First Search heuristic called A* (pronounced "A-Star"). A* has some theoretically and practically interesting qualities. Take a look here for a description of the algorithm. Implement A* and give a description of why the algorithm works and how it compares to your other search algorithms (e.g. When does it work better? When does it work worse? Which one would you generally choose to use? etc.) (2 points)
Add a maze generator to your program or applet. (4 points)
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. Include instructions in your README.txt file on how to run the visualization as a Java program and/or as an applet. Please have it so we can run the visualizer in your program using the "-v" oprion to MazeRunnerLauncher. Hint: have your visualizer class extend JFrame and implement MazeChangeListener.(4-6 points, depending on how nice it looks.)
Choose your own extension!: Exercise your creativity and think how you can extend this project. Can your MazeRunner handle mazes with multiple exits? What about rendering your maze in 3-D? If you do anything that alters the basic design specifications, check with the staff, and document what you did. Of course, your code should still meet the basic requirements.
IX. What to Turn In
Phases A and B will be graded together when your entire assignment is turned in with Phase B. However, 15% of your grade will be based upon the "in-progress" checkin for Phase A. Although 15% is a relatively small fraction, you are highly encouraged to successfully complete all of Phase A by this deadline, as there is much more work to do in Phase B.
Only one person from each team should submit. The same person should submit both Phases A and B. You should submit all of the Java code you wrote.
Phase A Turn-in
For Phase A please include the following files plus any others you find necessary:
MazeRunnerLauncher.java - Main launcher file, with added options to invoke your mazerunners, etc.
MazeStack.java - Your stack implementation
MazeQueue.java - Your queue implementation
DFSMazeRunner.java - Your DFS maze runner implementation
BFSMazeRUnner.java - Your BFS maze runner implementation
TESTING.txt - Your testing strategy description
Phase B Turn-in
For Phase B, turn in all your code for this assignment (from both Phase A and Phase B). So you'll turn in the following files plus any others you find necessary:
Files turned in in Phase A
BinaryHeap.java - Your binary heap implementation
ThreeHeap.java - Your three heap implementation
DHeap.java - Your d-heap implementation
Your pointer-based priority queue implementation, one ofLeftistHeap.java
SkewHeap.java
BinomialQueue.java
BestFSMazeRunner.java - Your best-first maze runner implementation
README.txt - Your answers to the assignment write-up
extracredit.zip - Any extra credit work you've done above and beyond the assignment ought to be placed in a separate zip file
Any supporting classes required to make anything else you've turned in work (wrapper classes, additional abstractions, etc.)
It is an incredibly serendipitous day for you at the Paul Allen Center. A mysterious bearded benefactor has appeared during the night and has left behind donuts for the entire CSE 326 class! You've managed to get out of bed at a yawningly-early 10 AM, meaning you have first dibs on all the yummy goodness of fresh-baked donuts if you can get to them in time (and the always hungry grad students from the night before haven't beat you there). Unfortunately, the Allen Center space czars just happened to have decided to rearrange all the furniture during the night (as part of their experimentation with different settings in the new building), turning the entire building into one complex and mystifying maze. You haven't had your morning coffee yet, and you just don't feel like running around looking for donuts—but you're so hungry! Why not let your computer solve the maze and find the donuts FOR you?
II. Learning Objectives
In this assignment, you will:
Work on the PriorityQueue ADT, and implement your own data structures.
Gain experience with systematic testing.
Explore the similarities and differences between recursive and iterative algorithms.
See an application of the Stack, Queue, and PriorityQueue ADT's in maze search.
Gain experience analyzing and modifying an existing code base.
Train your computer to do your most important tasks for you—like finding donuts!
III. Assignment and Algorithm Overview
For the complete assignment, you are required to write several new maze-solving MazeRunner classes, each with one or more associated data structures. There should be one MazeRunner class for each of the following algorithms:
Depth-First Search (DFS) — please implement this search with a Stack
More information on DFS can be found here.
Breadth-First Search (BFS) — please implement this search with a Queue
More information on BFS can be found here.
Best-First Search (not abbreviated for obvious reasons) — please implement this using your priority queue implementations, with your MazeRunnerLauncher choosing among implementations as specified in Section IVb
More information on Best-First Search can be found here.
IIIa. Phase A: DFS and BFS
Your task for Phase A is to implement a stack, a queue, a depth-first search maze runner and a breadth-first search maze runner, according to the interfaces provided. Your data structure implementations should automatically grow (if interested you may also make them shrink—this is optional) as necessary. You should test these implementations to be sure they are correct before proceeding to Phase B. We'll also ask you to design and implement a collection of unit tests to verify that your code works properly.
Note: Growing an array implementation one element at a time is not likely to be the most time efficient solution; if you use arrays, try to come up with a more time-efficient solution. You may reuse any code you wrote for Project #1 for this purpose but be sure that you implement the interfaces provided for this project.
You are free to implement the stacks and queues as you wish, although arrays are as simple as anything. Our usual rule prohibiting use of the Java class libraries to do the actual work remains. You should also take this opportunity to get an understanding of how the three graph search algorithms described here work for a general graph.
You should also implement unit tests for your data structures and verify that your code passes the tests. You should turn in a TESTING.txt file with an informal description of your test plan. Summarize the tests you implemented and explain how they provide comprehensive test coverage for your classes. This should not just be a dump of the test names and comments from the code file—we can read that. What we want is to get an idea of the thinking behind what you did. We recommend use of JUnit, but this is not a requirement. The testing strategy you discuss in TESTING.txt will be evaluated as a part of the project, but the code of your actual unit tests will not.
IIIb. Phase B: Priority Queues and Best-First Search
For Phase B you will write several implementations of the Priority Queue ADT and a best-first search maze runner to use them. Specifically, you will write a binary heap, a three heap, a d-heap, and a pointer-based heap (one of: skew heap, leftist heap, or binomial queue). You will also need to modify MazeRunnerLauncher.java to accept command line arguments appropriate for each type of maze runner or priority queue. Finally, you'll need to answer the questions from the write-up and turn them in in README.txt.
All of this is more work than it sounds, so do not leave it to the last minute.
IV. Detailed Requirements
IVa. Clarifications
In your implementations of Queue and PriorityQueue, you should throw a NoSuchElementException (java.util.NoSuchElementException) if dequeue, peek, findMin, or deleteMin are called on an empty queue. Obviously, this means it's OK to import java.util.NoSuchElementException in your code.
Your d-heap class should implement the PriorityQueue interface.
When writing your additional pointer-based implementation (either a LeftistHeap or a SkewHeap or a BinomialQueue) of a PriorityQueue, do not use implementations of these that you may find on any web site - including the web site for our text book! Such use will be considered a violation of our collaboration policy. You are free to refer to skeleton code provided in our text book or in other course materials; however, the code you turn in should be your own.
Your priority queue implementations must accept Comparable objects.
Many classes such as String and Integer implement the Comparable interface. In Phase B you will need to modify/create some more classes that implement theComparable interface (in other words, writing your own compareTo method). Then you will be able to have priority queues containing those objects. Unlike your stacks implementations for Project1 that were hardcoded to use doubles, your implementations of the Stack, Queue, and PriorityQueue interface need to use generics. Your implementations need to use compareTo when comparing elements so the code will work on any Comparable object. More information about Java's Comparable interface may be found at Sun's website. In addition, you might find this description from CSE 143 of Fall 2006 to be useful. Both generics and the Comparable interface are discussed in section 1.5 of the Weiss text, and there is a good tutorial on Sun's web site. The tutorial is based on this paper by Gilad Bracha, one of the Java language designers.
IVb. Input and Output
INPUT:
You are required towrite MazeRunner classes for BFS, DFS, and BestFS. Please modify MazeRunnerLauncher to use EXACTLY the following parameters to determine which search algorithm to use:
-BFS
use BFS
-DFS
use DFS
-BestFS
use BestFS
You should assure that all of your PriorityQueue implementations work with MazeRunner. Please modify MazeRunnerLauncher to use EXACTLY the following parameters to determine which priority queue implementation to use when needed:
-bin
use Binary Heap
-three
use Three Heap
-dheap #
use a d-heap, where d = #
-ptr
use your pointer-based heap (Leftist, Skew or Binomial)
The MazeFactory class reads a maze from a text file specified on the command prompt. 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 (width, then height). In the maze, '-' and '|' are used for walls, ' ' for rooms and unblocked passages, '+' for the corners of the rooms, '*' for the start, and 'O' for the donut. (Note: start and donut can be in any cells in the maze, not just the corners.) Once you find the donut, you get to chow down and then exit out of the maze. For example, the following is a legal maze :
7 5
+-+-+-+-+-+-+-+
|*| | | | |
+ +-+ + + +-+ +
| | | |
+ + + +-+ +-+ +
| | | | |
+ +-+-+ +-+-+ +
| | |
+-+ + +-+-+ +-+
| | O|
+-+-+-+-+-+-+-+
There are some sample input files in the starter files mentioned above that you can use to test your program. You are highly encouraged to write (and share with your classmates!) other test mazes to run your MazeRunner on. Send them to us or post them on the message board (preferred).
OUTPUT:
After solving a maze, your MazeRunner should output the name of the search algorithm used followed by the solution path calculated by the search. The path should be given on a single line and should consist of the printed cells from the start to the exit, separated by single spaces. On the next line should be the length of the solution path, and on the following line should be the number of cells visited in the search, including cells that were not completely explored (i.e., marked "Visit in progress" when the search completes). For example, the output for the above maze might be:
Random search:
(0,0) (0,1) (0,2) (0,3) (1,3) (2,3) (2,4) (3,4) (4,4) (5,4) (6,4)
Length of path: 10
Number of cells visited: 15
Please note that the start and end cells are both included, but the length of the path is the number of edges traversed ( one less than the number of cells visited). Please do not include extraneous output. For the other search algorithms, use text "Breadth-first search:", "Depth-first search:" and "Best-first search:".
The solution displayed above corresponds to the solution path shown below with dots:
+-+-+-+-+-+-+-+
|*| | | | |
+ +-+ + + +-+ +
|. | | |
+ + + +-+ +-+ +
|.| | | |
+ +-+-+ +-+-+ +
|. . . | |
+-+ + +-+-+ +-+
| |. . . . O|
+-+-+-+-+-+-+-+
Note that your MazeRunner does not need to output a text-graphical solution such as the one displayed above.
Note also that a search very likely involves visiting many nodes that are not on the final solution path. You will have to explore ways of keeping track of the solution path from the collection of nodes you visited. RandomMazeRunner gives an example of how this might be done. You will need to modify this technique to work for your algorithms.
IVc. README.txt Questions
Your README.txt should contain the following information and answer the following questions:
The names of your team members and your team's name
A breakdown of the work - a brief who-did-what description.
How much time did you spend on this project?
Acknowledgement of any assistance you received from anyone but your partner, the course staff, or the Weiss book.
Did you do any extra credit? If so, describe what you did and give instructions on how to run your code.
Why is it more important for DFS than BFS to check whether a cell has been visited yet?
If you gave your MazeRunners a maze that was too large to fit in main memory, which would likely run faster, BFS or DFS? (Any reasonable answer—as long as it is justified—will be accepted.)
In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?
Why is it important that a heuristic be easy to compute? Why is it important that a heuristic yield unique (or almost unique) values?
Why is BFS guaranteed to find the shortest path? Are the other two algorithms guaranteed to find the shortest path? If yes say why, if not, give a counter example.
What are the tradeoffs between a pointer vs. array-based heap? In particular, what are the tradeoffs between a binary heap, a threeheap, and a pointer-based heap? Some possible topics to cover include runtime, coding complexity, and memory usage. Did you observe any differences (for example in runtimes or memory use) between using these three for the larger maze inputs? (Just note if you noticed anything, it is fine if you did not. You are welcome to explore this question in more detail (timings, measurements, calculations) for extra credit.)
In general (not necessarily in the context of this project), why could it be better to use a sorted array implementation of a priority queue versus a binary heap? Why could it be worse?
What did you enjoy about this assignment? What did you hate? Could we have done anything better?
IVd. Grading Breakdown
The amount of code required for this project is actually very small. A significant part of your grade will be based on your program design and your README.txt.
Correctness - 40%
Architecture/design - 30%
README.txt - 30%
Look at the course grading policy for a more detailed explanation on grading guidelines.
V. Provided Code
The skeleton code can be downloaded as p2code.zip. Some of the important files are:
PriorityQueue.java — interface for a PriorityQueue ADT. All of your heaps should implement this..
Stack.java — interface for a Stack ADT.
Queue.java — interface for a Queue ADT.
MazeRunnerLauncher.java — the launcher that you'll need to modify to accept the specified command line arguments and construct the appropriate MazeRunner
MazeRunner.java — interface that each MazeRunner should extend. You may be able to prevent a significant amount of code duplication by handling your MazeRunner inheritance appropriately.
For Phase A we provide interfaces for a Stack and a Queue, as we as an example MazeRunner (RandomMazeRunner, which picks the direction to explore in a random fashion.). You must write the implementations of the provided Stack and Queue interfaces as described above. Your own MazeRunner classes should inherit from the abstract MazeRunner class.
For Phase B we provide code to read the input maze given as a text file, parse it, and build a Maze class object from it, which your algorithm will operate on. We also provide the interface for the Priority Queue ADT, PriorityQueue.java. You must write several implementations of the PriorityQueue interface–a BinaryHeap, a ThreeHeap, a DHeap, and a pointer-based priority queue of some kind. For the array-based heaps (BinaryHeap, ThreeHeap, etc.) you can start with a copy of your code from one and make changes as necessary, although making the original code easy to generalize making appropriate use of inheritance may save a lot of time (hint, hint).
You are not required to modify any of the provided files besides MazeRunnerLauncher.java.
Further documentation on the Maze code architecture and how to get started can be found here. If you find the large codebase a bit overwhelming, this is good place to start.
VI. Logistics and Extra Information
Teams
You are encouraged (although not required) to work with a partner of your own choosing for this project. You may choose how to divide the work between the two of you under three conditions:
You must document each team member's effort in the README file (record this now so you have the info for the Phase B readme file);
Work together so that you both understand your answers to the questions answered in the README (for Phase B);
Understand (at least) at a high level how your team member's code is structured and how it works (code for both Phases A & B).
Remember to test your team's code as a whole to make sure that your portions work together properly! Also, be aware that except in extreme cases and provided you notify us in advance of the deadline, all team members will receive the same grade for the project.
Subversion and Group Spaces
If you would like to use a shared group directory, please contact one of the TA's for instructions. This is NOT necessary, just optional if it is your preference.
We can create shared space on attu for each group if you wish to set up a subversion repository; we'll have more details once the project groups are finalized.
Each group can have a Subversion repository available if you wish to use a repository to coordinate modifications to your code base. Subversion is useful for both teams and individuals, as it allows you to store backups of your code in a central server. For teams, each team member may be working on the code concurrently, and Subversion checks for conflicts when the changes are committed. For more information about Subversion, try the Subversion book. That link describes how to use Subversion on the command-line; you can also use TortoiseSVN on Windows (documentation) or the Subclipse plugin for Eclipse (not yet installed on the lab machines, but go here for install instructions for your own machine and here for usage instructions). The repository address is:
svn+ssh://username@attu.cs.washington.edu/projects/instr/09sp/cse326/project2/groupname
where username is your username and groupname is username1-username2 for pairs and username for loners.
Testing Strategy
To facilitate understanding of this rather complex project, and to encourage good modular decomposition and "unit testing" (testing small pieces of code instead of testing the entire program all at once), we suggest improving and testing your "helper" data structures (i.e. Stack, Queue, BsinaryHeap, ThreeHeap, etc.) without worrying about the Maze-related code.
Your tests should be:
Comprehensive - you should cover all types of behavior your code might exhibit. For example, if a method's specifiication says it might throw an exception in certain cases, you should test those cases in addition to normal behavior. Also be sure to check edge cases - maybe your stack works fine when there are five elements, but what if there is just one? Or zero?
Modular - as much as possible, test each method separately, and keep the tests small and self-contained.
Concise - good test coverage is not synonymous with having lots of tests that are fundamentally the same. (Hint: You may be able to reuse a single suite of tests for both implementations of the priority queue if you think about how to take advantage of interface types and maybe inheritance in the test code. Massive cut-'n-paste is not a good an alternative.)
Using JUnit is straightforward. Your section should cover the basics of writing test cases; to run a test case from the command line, do:
java junit.textui.TestRunner MyTestCase
where MyTestCase if the name of one of your TestCase classes. Eclipse has a JUnit GUI built in; see here for a howto.
VII. Getting Started
After downloading the provided code, compile everything and try to run the provided random mazeRunner from the launcher class as follows:
% java MazeRunnerLauncher -r sample-inputs/maze2.txt
(Or try one of the other mazes in sample-inputs) The "-r" option invokes the random maze runner. Take a look at RandomMazeRunner.java to get a general idea of how things work. After understanding this file, make a copy (say BFSMazeRunner.java) and try implementing a better algorithm.
To add these files to your SVN repository, you should do an svn add <filename for each file. To import into Eclipse, you can drag-and-drop the files into your project or go to File-Import...
VIII. Going Above and Beyond
The following suggestions are meant for you to try if you finish the requirements early. Be sure to clearly describe what you did and how to run it in your README.txt. Recall that any extra-credit points you earn for these are kept separate from your assignment score and will be used to adjust your grade at the end of the quarter, as detailed in the course grading policy. Please don't put extra credit code in your main turnin—instead, put modified versions of your files in an archive extracredit.zip.
Using the Manhattan distance has several problems, including the fact that the MazeRunner is sometimes fooled into going down "dead ends" in the maze. What other heuristics might be used in your MazeRunner? When might your heuristics perform better than the Manhattan distance, and when might they perform worse (you may want to consider factors such as space usage and time to calculate the heuristic)? Implement and run your Best-First MazeRunner with its new heuristic on several mazes and report which heuristic performed better, and in what type of maze it did better in. (2 points)
There is a variation of the Best-First Search heuristic called A* (pronounced "A-Star"). A* has some theoretically and practically interesting qualities. Take a look here for a description of the algorithm. Implement A* and give a description of why the algorithm works and how it compares to your other search algorithms (e.g. When does it work better? When does it work worse? Which one would you generally choose to use? etc.) (2 points)
Add a maze generator to your program or applet. (4 points)
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. Include instructions in your README.txt file on how to run the visualization as a Java program and/or as an applet. Please have it so we can run the visualizer in your program using the "-v" oprion to MazeRunnerLauncher. Hint: have your visualizer class extend JFrame and implement MazeChangeListener.(4-6 points, depending on how nice it looks.)
Choose your own extension!: Exercise your creativity and think how you can extend this project. Can your MazeRunner handle mazes with multiple exits? What about rendering your maze in 3-D? If you do anything that alters the basic design specifications, check with the staff, and document what you did. Of course, your code should still meet the basic requirements.
IX. What to Turn In
Phases A and B will be graded together when your entire assignment is turned in with Phase B. However, 15% of your grade will be based upon the "in-progress" checkin for Phase A. Although 15% is a relatively small fraction, you are highly encouraged to successfully complete all of Phase A by this deadline, as there is much more work to do in Phase B.
Only one person from each team should submit. The same person should submit both Phases A and B. You should submit all of the Java code you wrote.
Phase A Turn-in
For Phase A please include the following files plus any others you find necessary:
MazeRunnerLauncher.java - Main launcher file, with added options to invoke your mazerunners, etc.
MazeStack.java - Your stack implementation
MazeQueue.java - Your queue implementation
DFSMazeRunner.java - Your DFS maze runner implementation
BFSMazeRUnner.java - Your BFS maze runner implementation
TESTING.txt - Your testing strategy description
Phase B Turn-in
For Phase B, turn in all your code for this assignment (from both Phase A and Phase B). So you'll turn in the following files plus any others you find necessary:
Files turned in in Phase A
BinaryHeap.java - Your binary heap implementation
ThreeHeap.java - Your three heap implementation
DHeap.java - Your d-heap implementation
Your pointer-based priority queue implementation, one ofLeftistHeap.java
SkewHeap.java
BinomialQueue.java
BestFSMazeRunner.java - Your best-first maze runner implementation
README.txt - Your answers to the assignment write-up
extracredit.zip - Any extra credit work you've done above and beyond the assignment ought to be placed in a separate zip file
Any supporting classes required to make anything else you've turned in work (wrapper classes, additional abstractions, etc.)
1 file (206.0KB)
