CS 160, Summer 2016
Programming Assignment P5
Maze Program

Programming due Monday, July 4th at 6:00pm; late deadline at 11:59pm.

This lab has the goal of teaching you how to:

Instantiate a Maze object and call its methods.
See your code controlling a graphical user interface.
Use control loops to manage movement in the Maze.

Description

For a visual aid, click here

This assignment features Chihiro from the Miyazaki film Spirited Away, one of the best animated films ever made. Chihiro is having trouble in the spirit world, and needs the help of Haku. While looking for Haku in the maze, Chihiro needs to stay away from the witch Yubaba. The goal of this program is to move Chihiro around the maze according to a precise set of rules. If you follow the rules, Chihiro will find Haku, and will never meet Yubaba. Note: You must follow the exact path we specify to receive full credit on this program, finding Haku is not enough!

Instructions

In Recitation 4 you should have started on P5.java. If not, follow the directions here. Leave in the code you wrote that instantiates the Maze object and retrieves the dimensions. Remove any code from the recitation that moves Chihiro around in the maze. Then add code to implement the algorithm shown below. This will require multiple control loops, which can be either while or for statements. Here is a complete specification of the Maze methods you can call:

// Constructor, parameter is name of maze file
public Maze(String fileName);

// Get width and height of maze
public int getWidth();
public int getHeight();

// Get location of Chihiro
public int getColumn();
public int getRow();

// Commands to move Chihiro
public void moveRight();
public void moveLeft();
public void moveDown();
public void moveUp();

// Check if Haku found
public boolean foundHaku();

To solve the assignment, you may want to implement the following method:

public static boolean onEdge(); // returns true if Chihiro is on any edge, false otherwise

Algorithm

The mazes can be of any size.
Chihiro can start anywhere, as specified by the maze.
Use getColumn and getRow to find the position of Chihiro.
Yubabas can be anywhere, as specified by the maze.
If you follow the rules, Chihiro will never meet Yubaba, and will find Haku.
Row and column numbers are zero based, so the first row and column is index 0.
Use the move methods to move Chihiro.
Here is the exact algorithm for finding Haku:
1. If Chihiro is not on any edge, move up to the topmost column.
2. Now Chihiro is guaranteed to be on the edge!
3. Move Chihiro counter-clockwise around the board.
4. Stop when Chihiro finds Haku.
If you go outside the maze, the maze will print an error and exit.
If you go run into Yubaba, the maze will print an error and exit.
Check whether Chihiro has found Haku after each move.
When Chihiro finds Haku, you must immediately break out of all loops, and exit the program.
There are mazes that cannot be solved using the algorithm, but we will not test your program with any of them.

The Maze is programmed to wait 0.5 seconds each time you move Chihiro, so you can issue move calls back to back, and Chihiro will move at a reasonable speed that allows you to see the moves. In addition to checking visually, the move methods will print the row and column of Chihiro, and you can use this to debug your code. For example, here is the output of Chihiro moving up the leftmost column:

Maze name: maze.txt
Maze width: 6
Maze height: 6
Moved to row 2, column 3
Moved to row 2, column 2
Moved to row 2, column 1
Moved to row 2, column 0

Testing

You should test your code with the five Mazes provided, and you can also make your own mazes. The format of a maze file is shown below. The first line is an integer specifying the maze width, followed by an integer with the maze height. These values is followed by one line for each row of the maze, with one character per column. The value 'C' is Chihiro, 'H' is Haku, and 'Y' is Yubaba.

6
6
------
-Y---H
----C-
----Y-
-Y-Y--
------

Specifications

Your program must meet the following specifications:

Chihiro must follow the exact route specified.
Chihiro can only move to a square adjacent to the current position.
Work on your own, as always.
The name of the source code file must be exactly P5.java.
Name the file exactly - upper and lower case matters!
Assignments should be implemented using Eclipse.
Assignments should be implemented using Java 1.7 or 1.8.
Make sure your code runs on machines in the COMCS 120 lab.
Submit your program to the Checkin tab as you were shown in the recitation.
Read the syllabus for the late policy.
We will be checking programs for plagiarism, so please don't copy from anyone else.

Grading Criteria

100 points for perfect submission.
0 points for no submission, will not compile, submitted class file, etc.
Preliminary Tests
- compileTest: checks that program compiles. (10 points)
- test1: Chihiro correctly solves Maze1.txt (10 points)
- test2: Chihiro correctly solves Maze2.txt (10 points)
- test3: Chihiro correctly solves Maze3.txt (10 points)
- test4: Chihiro correctly solves Maze4.txt (10 points)
- test5: Chihiro correctly solves Maze5.txt (10 points)
Preliminary tests use mazes of different sizes, so do not hard code width and height.
Final Tests
- test6: We will test with a straightforward maze, not provided to you. (10 points)
- test7: We will test with a more complex maze, not provided to you. (10 points)
- test8: We will test with a small but devious maze, not provided to you. (10 points)
- test9: We will test with a large and devious maze, not provided to you. (10 points)
Final grading includes the preliminary tests.

Submit your program to the Checkin tab on the course website, as you were shown in the recitation, and read the syllabus for the late policy (if necessary).

CS 160, Summer 2016 Programming Assignment P5 Maze Program