CS202 X04 Proj1

Project 1. Maze
CS202, Summer 2004

Due: Thursday, August 5

Please email your solutions to csun@calstatela.edu, and make sure to use CS202 Summer 04 Proj1 as the subject of the email. The email should include your name, and all the source files as attachments. For all homework assignments and projects, failing to comply with the required code conventions (see Review of Language Basics, slide #7) will incur a credit penalty up to 10% of the total credit for the assignment.

[Reading] Read the following sections of SUN's Java Tutorial

Classes and Inheritance

Interfaces and Packages

[Problem Description] A maze can be simply represented by a 2-dimensional array of 0's and 1's, where 1's represent walls, and 0's represent empty cells. A maze has an entrance and an exit. A connected set of empty cells from the entrance to the exit is called a path. For simplicity, we assume a maze is always square, e.g. it has the same numbers of rows and columns. For a maze of size n x n, we also assume that the entrance is always at cell (0,0), and the exit at cell (n-1,n-1), as shown below:

entrance -->

0 1 0 0 0
0 0 0 1 0
1 0 1 1 0
1 0 0 1 0
1 0 1 1 0 <-- exit

For this project, implement a Maze class which includes at least the following methods:

Maze( int n ) -- constructs a random maze of size n x n.
Maze( String file ) -- constructs a maze from a given file. The first line of the file specify the number of rows/columns in the maze, and the rest of the file specify the values of the maze cells in proper row and column order. For example:

5
0 1 0 0 0
0 0 0 1 0
1 0 1 1 0
1 0 0 1 0
1 0 1 1 0

If the file is not in the right format, this constructor prints out an error message, and constructs a random maze of default size 11 x 11.

void read( String filename) -- reads a maze from a given file in the format described above. This method raises a MazeFormatException if the file is not in the right format.
void write(String filename) -- saves a maze to a given file in the format described above.
boolean solve() -- returns true if a path exists, or false otherwise. If there exists a path, this method also prints out the maze with the cells on the path marked by 2, for example:

2 1 2 2 2
2 2 2 1 2
1 0 1 1 2
1 0 0 1 2
1 0 1 1 2

String toString() -- returns a white space delimited string of the maze for printout.

[Random Maze Generation] Random maze generation is a well studied topic. There are many algorithms available online, which can be found by a Google search for "random maze generation". Most of these algorithms, however, are fairly complex. In this project, we will use one of two relatively simple algorithms to create an n x n maze, and both of these algorithms start with the following initial steps:

Initialize the maze to all walls (all 1's).
Knock down the walls at (i,j), where (i%2 == 0 && j%2 ==0), to create a number of isolated cells. Since we assume that the exit is always at (n-1,n-1), if n is even, we also knock down the wall at (n-1,n-1), and either the wall at (n-1,n-2) or the one at (n-2,n-1), as shown in the following examples:

n = 7	n = 6	n = 6
0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0	0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 0	0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0

Algorithm A: randomly knock down half of the remaining walls. This algorithm is extremely simple, however, note that the resulting maze may not look pretty, and worst of all, there may not exist a path from the entrance to the exit.

Algorithm B: randomly knock down walls until all cells created in the initial steps are connected. In particular, we never knock down a wall between two cells if there is already path connecting these two cells. It is fairly hard to implement this algorithm efficiently, but a maze created with this algorithm looks quite good, and is guaranteed to have a path from the entrance to the exit.

[Solving a Maze]

Solving a maze is not particularly difficult with recursion. The general idea is to use a recursive helper function boolean solve(int row, int col) which looks like the following:

// i and j are the row and column number of a cell private boolean solve( int i, int j ) { // check error conditions // if reached exit, marked the cell, return true // block the current cell so it won't be visited repeatedly // check the left, right, up and down cells. if( solve(i+1,j) || solve(i,j+1) || solve(i-1,j) || solve(i,j-1) ) { // mark current cell as path return true; } // no path found return false; }

[Grading] The total points for this project is 100, with 40 extra credit if you choose to use Algorithm B for random maze generation.

Maze read and write (40pt)
Solving maze (30pt)
Random maze generation with Algorithm A. (10pt)
Random maze generation with Algorithm B. (extra credit 40pt)
Class structure, other methods, and test code (20pt)