HW2: Mazes, Part I

25 points; due Fri 4/1, 15 minutes before class Sat 4/2 at noon .

Goals

To learn about programming with inner classes, get experience working with “2-D lists”, and lay the groundwork for the maze-navigating program you'll write in the next assignment.

Setup and Requirements

The code that you write for this assignment will build on top of the same List ADT and implementation as the People Sorter assignment. The three files you will need are:

Every source-code file you turn in must have your name in a comment at the top.

You are encouraged to work with a partner for this assignment. Please respond to the partner thread on Piazza once you choose a partner. Keep in mind that there's a second half to this assignment, so if you work alone or in a pair on this assignment, you should do the same for the next one. Make sure to put both people's names at the top of each file. Write your code by pair programming: code together, at the same computer, and switch off who's at the keyboard. Only one of you should ultimately submit your team's code via Canvas.

Specification

What your program should do

You'll write a class called Maze. Each instance of Maze will represent a single maze. Maze.java will also include a main() method that acts as a test of the loading and printing of mazes. When you run java Maze maze.txt, your program should load the maze from maze.txt and print a human-readable representation of the maze to System.out.

For example, if maze.txt is:

6 5
0 0
5 4
L-_|_-
|L--|_
|-_-|_
|L|L||
L__L__

then the printed output should be:

+-----+-----+-----+-----+-----+-----+
|                 |                 |
|  S              |                 |
|                 |                 |
+-----+     +-----+     +-----+     +
|     |                 |           |
|     |                 |           |
|     |                 |           |
+     +-----+     +     +     +-----+
|                       |           |
|                       |           |
|                       |           |
+     +     +-----+     +     +-----+
|     |     |     |     |     |     |
|     |     |     |     |     |     |
|     |     |     |     |     |     |
+     +-----+     +-----+     +     +
|                 |                 |
|                 |              F  |
|                 |                 |
+-----+-----+-----+-----+-----+-----+

The maze file format

For this assignment, we'll assume that our mazes are rectangular, and that they have walls along the entire outside of the maze, with no gaps in these outer walls. We will also specify a “start square” and an “finish square” to indicate the goal of the maze-solver — to get from S to F.

Maze files will have the following structure:

<Number of columns> <Number of rows>
<0-based column number of the start square> <0-based row number of the start square> 
<0-based column number of the finish square> <0-based row number of the finish square> 
<Row 0 description>
<Row 1 description>
...

Each row description includes a single character for each square in that row, and each character describes the left and bottom walls for its square. Specifically:

Your program should throw an IllegalArgumentException with a descriptive message if:

(For any of the above, or any other errors in the input, it's also okay to let exceptions generated by built-in tools, like Scanner, bubble up and crash your program, even if they're a different kind of exception.)

Putting this together in a small example, if the input file contains the following:

FileInterpretation
3 2
0 0
2 0
L-|
L__
The maze has 3 columns and 2 rows
The start square is at the upper left
The finish square is at the upper right
(0,0) has left and bottom walls; (0,1) has neither; (0,2) has left
(1,0) has left and bottom walls; (1,1) has bottom; (1,2) has bottom

then the resulting maze would be printed as follows:

+-----+-----+-----+
|           |     |
|  S        |  F  |
|           |     |
+-----+     +     +
|                 |
|                 |
|                 |
+-----+-----+-----+

Note that we specify only the left and bottom walls for each square, and not the top and right walls. This is sufficient to describe the whole maze (but why?).

Output format

The two examples above show the appropriate format of the printed output. The corner point of every maze square is a + sign. Each pair of adjacent corners is separated by either 3 characters (vertically) or 5 characters (horizontally). If there's no wall between these corners, these characters are spaces; if there is a wall between them, these characters are either pipes (|) or hyphens (-), for vertical or horizontal walls, respectively. Therefore the interior of each maze square is 3x5 characters: either they're all spaces, or the center is an S or F and the rest are spaces.

Code Structure

Structure your code as shown below, stored in a file Maze.java. (Note that this is a requirement, not a suggestion.) By storing the Maze as a 2-dimensional collection of Square objects, you'll be well prepared to execute the maze-solving algorithm in the next assignment.

/**
 * HW2: Maze, Part I
 * [Date, partner, period, class, etc.]
 * 
 * @author [Your name here], adapted from skeleton code by Jadrian Miles.
 * 
 * A program to read an input file representing a maze, and then print out a
 * depiction of that maze on standard out.
 */

/**
 * A rectangular maze on a square grid.
 */
public class Maze {
    // The "2-D list" of maze squares.
    private List<List<Square>> rowList;
    //[Other instance variables if you need them]
    
    /** A single square of the Maze. */
    private static class Square {
        //[Instance variables of your choosing]

        //[Whatever methods you need, like:]
        //public boolean hasTopWall() {
        //   [...]
        //}
    }

    /** Default Maze constructor. */
    public Maze() {
        //[...]
    }
    
    /** Loads a maze file, given its filename. */
    public void load(String fileName) {
        //[...]
    }
    
    /** Prints out a graphical depiction of the maze. */
    public void print() {
        //[... print the Maze to System.out ...]
    }

    //[...
    // More methods if you need them.
    // Remember that your methods should always be private unless
    // you have a very good reason to expose them publicly.]

    /**
     * This main program acts as a simple unit test for the
     * load-from-file and print-to-System.out Maze capabilities.
     */
    public static void main(String[] args) {
        if(args.length != 1) {
            System.err.println("Usage: java Maze <mazeFile>");
            System.exit(1);
        }

        Maze maze = new Maze();
        maze.load(args[0]);
        maze.print();
    }
}

Hints

One tricky thing about this assignment is that you can't “draw” a whole square before you “draw” another one in the same row, because our “drawing” is really just a string, with some newlines in it, displayed on the command line. Here's a simplified representation of a 2×3 maze:

+--+--+--+
|  |     |
+  +--+  +
|        |
+--+--+--+

(Note that this is just a simplified example; an actual 2×3 maze would be printed on 9 lines [4 lines per row, plus one extra] with 19 characters in each [6 characters per column, plus one extra].)

Think about the string that gives you this picture:

"+--+--+--+\n|  |     |\n+  +--+  +\n|        |\n+--+--+--+\n"

It's clear that you can't draw the side walls of the upper-left maze square until you've drawn the top walls of all three maze squares across the top.

So this should give you some ideas for a successful design for the rendering portion of your program. The square should not try to draw itself all in one go. Instead, your maze should be able to ask each square for its contribution to a particular portion of that string. You can either construct the whole string and then print it, or print the string as you go.

There are other approaches that would work too, where you conceive of the picture as a different structure than just a string, but ultimately they're equivalent.

Submission and Grading

Submit your Maze.java file on Canvas.

Start early, ask lots of questions, and have fun!

Assignment requirements

This is a partial list of the things that I'll be looking for when evaluating your work:

Grading

This assignment originally designed by Jeff Ondich. Thanks for sharing, Jeff!