Steam-powered Turing Machine University of Washington Computer Science & Engineering
 CSE326 Summer 2006
  CSE Home     326 Home  About Us    Search    Contact Info 

Administrative
 Home
 Message Board
 Annoucement ArchiveCSE only
 Class List ArchiveCSE only
 Anonymous Feedback
 Mail Instructor & TAs
Lectures
 Calendar & Slides
 Midterm Study Guide
Projects
 Project 1
 Project 2 Phase A
 Project 2 Phase B
 Project 2 Phase C
 Project 3
Homework
 Homework 1
 Homework 2
 Homework 3
 Homework 4
 Homework 5
 Homework 6
 Homework 7
 Homework 8
Policies
 General Guidelines
 Grading Policies
 Programming Guidelines
 Writeup Guidelines
Computing
 Unix Basics
   

Project 2 - The search for a-MAZE-ing donuts!

Phase B

Important Deadlines

Phase B Due

Thurs, July 13

Electronic turnin (code + README.txt) by 11:00pm

 

Outline

VII. More Provided Code

For the second phase of this project, we are providing 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 are also providing the code for a simple maze solver method that picks the direction to explore in a random fashion. You will add the following methods to the Maze class:

You will also need to modify the MazeCell class to return the appropriate neighboring cells for the algorithms. For instance, you might want to return all the neighboring cells that have not been visited; or you might want to be able to set the priority of the MazeCell. You should not modify MazeCell to hold the i, j location of the cell. This is bad object-oriented programming style. If you insist on modifying MazeCell in this way you will lose points.

The provided code is here. It is in a tar-gzip format, which WinZip will open. You can also run the commands gunzip Maze.tar.gz followed by tar -xvf Maze.tar to unzip the file. There are sample mazes here.

You will want to add to it all of the code from Phase A, including your changes. Further documentation on the Maze code architecture can be found here.

VIII. Maze Input and Output

INPUT: 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 entrance, and 'O' for the donut. 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 : (Note: entrance and donut can be in any cells in the maze, not just the corners)

       7 5
      +-+-+-+-+-+-+-+
      |*|   | | |   |
      + +-+ + + +-+ +
      |   |   |     |
      + + + +-+ +-+ +
      | |   |     | |
      + +-+-+ +-+-+ +
      |       |     |
      +-+ + +-+-+ +-+
      |   |        O|
      +-+-+-+-+-+-+-+

There are some sample input files here 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 Maze on. Send them to us or to the 326 discussion list or post them on the message board.

IX. Getting Started

To see the program work, you will have to have an X-term window open. After combining your code from Phase A and the new provided code for Phase B, compile everything and try to run the program as follows:

  • To compile, run javac MazeViewer.java
  • To start the program, run java MazeViewer mazes/maze2.txt random, assuming you've decompressed the sample mazes in the same directory as the provided code
Take a look at solveRandomMaze to get a general idea of how things work. After understanding this method, try to fill in solveDFSMaze or solveBFSMaze using the algorithms described here.

X. Detailed Requirements

In Phase B you are required to:

  • Write methods for BFS, DFS, and BestFS. For more information on the three search algorithms, go here. You will also have to write a helper method (or two) in MazeCell to obtain the correct neighboring cells. For example, you might want to create a method that returns all the neighoring cells that have not been visited.

Electronic Turnin

Include the following files plus any others you find necessary:               

  • README (see the next sub-section for details)
  • (code from Phase A) Queue, Stack, BinaryHeap, ThreeHeap: all improved to grow as necessary
  • Maze.java -- Main algorithm file
  • MazeCell.java -- Will contain helper methods
You should NOT have to modify MazeViewer.java or MazeFactory.java.

README Questions

Your README should contain the following information:

  1. The names of your team members and your team's name
  2. A breakdown of the work - a brief who-did-what description.
  3. (Answer this question before you begin) How long do you think this project will take you to finish?
  4. How much time did you actually spend on this project?
  5. Acknowledgement of any assistance you received from anyone but your partner, the course staff, or the Weiss book.
  6. A brief description of how your project goes "above and beyond" the basic requirements, if it does.

Answer the following questions:

  1. Why is it more important for DFS than BFS to check whether a cell has been visited yet?
  2. If you gave your Maze 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.)
  3. In what ways are DFS and Best-first search similar? How are BFS and Best-first similar?
  4. Why is it important that a heuristic be easy to compute? Why is it important that a heuristic yield unique (or almost unique) values?
  5. 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.
  6. 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 binomial queue? 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 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.)
  7. 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?
  8. What did you enjoy about this assignment? What did you hate? Could we have done anything better?

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

  • Correctness - 40%
  • Architecture/design- 30%
  • README- 30%

Look at the course grading policy for a more detailed explanation on grading guidelines.

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

  • Using the Manhattan distance has several problems, including the fact that the Maze is sometimes fooled into going down "dead ends" in the maze. What other heuristics might be used in your Maze? 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 Maze with its new heuristic on several mazes and report which heuristic performed better, and in what type of maze it did better in.
  • 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.)
  • Choose your own extension!: Exercise your creativity and think how you can extend this project. Can your Maze 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.

XIII. Phase B Turnin

For Phase B, turn in all your code for this assignment (from both Phase A and Phase B).

Only one person from each team should submit. The same person who submitted Phase A should submit Phase B. The turn-in link is here. You should submit electronically:

  1. All of the Java code (use *.java) that you need to compile your program
  2. The README.txt file


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to gyngve]