Assignment 7: Spampede!
Due Tuesday, March 11 by 11:59 PM

This assignment asks you to extend the capabilities of your maze solver from HW6 (though you may use our solution code if you prefer). In addition, you will incorporate your Maze and maze-solver into a Java applet-based game that is similar to "Nibbles." Since it's spam-seeking, we'll call it Spampede. Please start this assignment early. It's fun - but also challenging!

What is the final product?

There are three parts to building your intelligent spam-seeking spampede... .

• You might want to try out the basic applet (with required functionality, but no extras), which is available at http://www.cs.hmc.edu/~dodds/Applets/SpampedeBasic/Spampede.html


• An applet with an extra feature of wrapping through tunnels in the maze (many, many more extra features are possible,of course -- see extra credit, below) is available at http://www.cs.hmc.edu/~dodds/Applets/SpampedePlus/Spampede.html


• Also, an applet that demonstrates only what is in the original set of files in the hw7files.zip folder is available at http://www.cs.hmc.edu/~dodds/Applets/SpampedeOriginal/Spampede.html

Submitting

Because there are so many files that may be involved in this assignment, you should zip the entire folder (which you might still have named hw7files) into hw7files.zip and then submit that zipped folder.

Part 1:     improving Maze.java [25 points]

This project introduces and practices a number of different techniques that are common to software engineering, that is the design and implementation of large software projects. Certainly this assignment can only provide a hint at a very rich -- and important -- field.

The first part is to improve the Maze class in which you wrote breadth-first search for assignment 6. In particular, you may start with our Maze.java file (in the hw7files.zip folder) or use your own. Either way, you should start by making sure you add at least four public accessor methods to the MazeCell class within Maze:

• public int getRow() { ... }, which returns the row of this MazeCell.
• public int getCol() { ... }, which returns the column of this MazeCell.
• public char getContents() { ... }, which returns the contents of this MazeCell.
• public void setContents(char newcontents) { ... }, which sets the contents of this MazeCell to become newcontents.

You should have a new zero-input contstructor for Maze (this is already in the solution file, or you can copy it from here:

protected Maze()
{
  int HEIGHT = mazeStrings.length;
  int WIDTH = mazeStrings[0].length();
  this.maze = new MazeCell[HEIGHT][WIDTH];
  for (int r=0 ; r<HEIGHT ; ++r) {
    for (int c=0 ; c<WIDTH ; ++c) {
      maze[r][c] = new MazeCell(r,c,mazeStrings[r].charAt(c));
    }
  }
}

What is protected?

The access level protected indicates that derived classes may use a method (or data member), but not simply any class at all. It is between the access of public (any class may use it) and private (only the defining class may use it). Since part 2 asks you to write a class named SpamMaze that derives from Maze and SpamMaze will use this zero-argument constructor, protected is an appropriate access level.

A more flexible breadth-first-search

The final method to write in Maze.java is

protected MazeCell multiBFS(MazeCell start, char destination) ...

What should multiBFS do?

This method should have the following behavior:

• printing, but not changing, the Maze    That is, when multiBFS finds a path from start to destination, it should mark it with the 'o' characters, as before, and then print out this Maze. Afterwards -- before returning -- it should remove the 'o' characters and then return the next MazeCell on the path to the destination. If the Maze was not solvable, it should print that message and still return a valid MazeCell neighboring start. (See next point...)
• returning the next MazeCell on the path    This method should return the MazeCell that is adjacent to the start along the path that it found to the destination. If there was no path from start to any cell containing destination, then the multiBFS method should return any empty MazeCell that neighbors start to the N, E, W, or S. If there are no empty neighbors, then multiBFS should return an arbitrary MazeCell that neighbors start (and the centipede will crash!)
• really not changing the Maze!    Regardless of whether a path is found or not, this method should reset all visited flags and parent data members of every MazeCell in the Maze. Unlike the previous assignment, where a Maze was solved only once, here your code will be solving a Maze repeatedly, so multiBFS must be really sure to leave the maze as it was before running breadth-first search. There is an empty method private void clearFlags() to write for just this purpose.

Testing your code

Be sure to test your code thoroughly before heading to part 2 of this assignment... there is a test in main for this purpose, and you should try editing the mazeStrings in order to make sure it works in a variety of conditions!

Part 2:     writing SpamMaze.java [50 points]

The overview

In this part of the assignment you will create a derived class named SpamMaze that handles the model for the applet, which is part 3. A derived class is simply an extension of the data and capabilities (methods) available in the base class. Thus, by starting the code as in the provided SpamMaze.java file:

import java.lang.Math;
import java.util.LinkedList;

class SpamMaze extends Maze
{
  // your code goes here...
}

The data

Because a SpamMaze object represents the model for the Spampede applet, it needs to keep track of (1) the maze, (2), the centipede, and (3) the spam in the environment. Remember that (1) is already taken care of because your SpamMaze is a derived class of Maze. To keep track of (2) and (3), you should use lists of MazeCells. In particular, you will declare two data members:

  // The data members representing the spam and the centipede
  private LinkedList<MazeCell> spamCells;
  private LinkedList<MazeCell> pedeCells;

The methods

You should, in essence, implement all of the functionality, but not the graphics front end, for the Spampede game inside SpamMaze. Here is one possible suggestion for a decomposition into methods:

• public SpamMaze()    a zero-argument constructor. This should call the base class's zero-argument constructor (to create the Maze) and then it should do additional initializion of the data members that are part of only the SpamMaze class (see above).
• public int getHeight()    is an accessor that returns the height of this maze.
• public int getWidth()    is an accessor that returns the width of this maze.
• public char getContents(int r, int c)    is an accessor that returns the contents of the MazeCell at row r and column c in this maze.
• public void setContents(int r, int c, char newcontents)    is an accessor that sets the contents of the MazeCell at row r and column c to become the char newcontents in this maze.
• public void reset()    I found this useful for cleaning everything up after a crash and restarting the game.
• public void addSpam()    to add one can of spam to the environment
• public void removeSpam()    to remove one can of spam to the environment
• public char advancePede(char direction)    this method could be used to update the centipede, that is, the pedeCells, so that the start of the centipede has moved one step in the direction designated by direction. This method is the fundamental update for the game -- see below for details on the capabilities that should be built-in. Because you should define public static final constants for the different possible directions, the input parameter is probably going to be whatever type represents those constants.
  
  Why the return value? It's not required, but you may want to pass back the "result" of the centipede's motion, e.g., a crash, a change in direction, eating a spam, etc.

Notes on the behavior of the centipede

• The advancePede(char direction) method should update the centipede's position within the maze. That is, the centipede's head advances one MazeCell in whatever direction is specified, and the centipede's tail retracts by one MazeCell.
• The initial state of the centipede is that its head is at maze[1][2] and that it has only one body segment, at location maze[1][1]. Thus, the centipede is initially facing east.
• If the centipede's head moves to a MazeCell that contains a wall or another part of the centipede, the centipede dies, and the centipede should be reset to its initial state.
• If the centipede's head advances into a MazeCell that contains a morsel of spam, the centipede grows by one MazeCell. That is, when the centipede next moves, its head advances one square, but its tail does not retract.
• The following directions should be supported as input to advancePede:
  • 'N' - move north 1 MazeCell (upwards on the screen)
  • 'E' - move east 1 MazeCell (rightwards on the screen)
  • 'W' - move west 1 MazeCell (leftwards on the screen)
  • 'S' - move south 1 MazeCell (downwards on the screen)
  • 'A' - move 1 MazeCell toward the nearest spam (using the resuults from multiBFS)
  However, be sure NOT to use any of these values in your code except in order to define constants that provide them more representative names. Such constants are most often public, static, and final, which means they can be used from any class, they are members of the class (and not a specific SpamMaze instance), and they can not be changed - hence final.

  
  		public static final char NORTH = 'N';
  	

  and so on... .

Testing!!

As with Maze, be sure to test your SpamMaze thoroughly in main before worrying about the graphical front-end of the applet in part 3. Below is my main method, which you should feel free to adapt to your implementation. Remember that you do not need to write toString -- the version that's already in Maze will work perfectly well!

  public static void main(String[] args)
  {
    SpamMaze SM = new SpamMaze();

    System.out.println("SM is\n" + SM);
    MazeCell nextSpot = SM.multiBFS(SM.pedeCells.getFirst(), SPAM);
    System.out.println("nextSpot is\n" + nextSpot);
    System.out.println("SM is\n" + SM);

    SM.advancePede(EAST);
    System.out.println("SM is\n" + SM);
    System.out.println("pedeCells is " + SM.pedeCells);

    SM.advancePede(EAST);
    System.out.println("SM is\n" + SM);
    System.out.println("pedeCells is " + SM.pedeCells);

    SM.advancePede(EAST);
    System.out.println("SM is\n" + SM);
    System.out.println("pedeCells is " + SM.pedeCells);

    SM.advancePede(SOUTH);
    System.out.println("SM is\n" + SM);
    System.out.println("pedeCells is " + SM.pedeCells);

    SM.advancePede(SOUTH);
    System.out.println("SM is\n" + SM);
    System.out.println("pedeCells is " + SM.pedeCells);
  }

Part 3:     writing Spampede.java [50 points]

The overview

The Spampede applet gives a user control over a spam-seeking centipede. Key presses from the keyboard change the direction of the centipede's movement in order to intersect snacks (spam) that appear at random places on the screen. For each snack consumed, the centipede grows by one segment (a segment is simply one MazeCell). Variations are welcome (see Ex. Cr.)!

Setting up

The "starter" applet Spampede.java and its html file Spampede.html are provided for you in hw7files from the top-level assignments page.

Finally, we have also provided the following files which you may wish to use (but they are totally optional):

• Spam.au, an audio file
• spam.gif, an image of a can of Spam