Assignment 7: Spampede!
Due Friday, March 13 by 5 PM

Please read the following carefully. There is a lot here!

1. First, note that this assignment is due at an unusual time: Friday, March 13 at 5 PM. The assignment is also worth 130 points rather than the usual 100. The following week is spring break and there is no assignment over the break. No extensions are permitted on this assignment (e.g. no "Euros").


2. Next, a friendly reminder that the midterm exam will be in class on Wednesday, March 11 (for Section 1) and Thursday, March 12 (for Section 2). The exam will cover material up to, and including, the lecture before the exam. You may bring an 8.5 by 11 sheet of paper with writing on both sides (your own writing please). Write down anything on that sheet that you like. The purpose of this sheet is to minimize memorization so that you can concentrate on concepts instead. You will submit the sheet with your exam but will get it back.


3. This week it's time to change programming partners. If you are pair programming, you should program with someone with someone with whom you have not previously sumbitted together. You and your new partner may work together for the remainder of the semester if you wish. Pair programming is permitted on all three parts of this week's assignment.


4. You will be submitting several files for this assignment. Please submit every file that you used for your assignment. We will look for Maze.java (Part 1), SpamMaze.java (Part 2), and Spampede.java (Part 3). If you define any other files as part of your project, please submit those too.


5. This week, we ask that you also submit a file that is typically submitted in any large software project: A text file called README. We have left a basic README file in the homework directory for this week: /cs/cs60/hwfiles/a7/. You should edit this file and submit it. The README file constitute part of your score on this assignment.

This assignment has three parts, which ultimately build to the Spampede game! In Part 1, you will extend the capabilities of your maze solver from HW6 (though you may use our solution code for that assignment if you prefer). In Part 2, you will use the results of Part 1 to build some of the primary functionality of the Spampede game. In Part 3, you will use Part 2 in a graphical applet that you (and your friends) can play on the web!

What is the final product?

• You might want to try out the basic applet (with required functionality, but no extras), which is available at: http://www.cs.hmc.edu/~hadas/Spampede/Spampede.html
• Also, an applet that demonstrates only what is in the original set of files in the /cs/cs60/hwfiles/a7 directory and can be tried out at http://www.cs.hmc.edu/~dodds/Applets/SpampedeOriginal/Spampede.html
Please note that some web browsers are finicky about rendering applets. If these applets don't run for you on your regular web browser, try another one (e.g. Safari, Explorer, etc.) In general, it will be much easier to develop your code using the appletviewer and only go to the web when your program is entirely complete! In any case, Parts 1 and 2 of this assignment are all text-based, so you need not even think about this for awhile.

Part 1:     Improving Maze.java [20 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 either your own Maze.java file from last week or you may use our solution to that problem in /cs/cs60/hwfiles/a7. Either way, the internal data in the MazeCell (row, col, contents, etc.) MUST be private and you should start by making sure you add at least four public accessor ("getter and setter") 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()
{
        ROWS = mazeStrings.length;
        COLUMNS = mazeStrings[0].length();
        this.maze = new MazeCell[ROWS][COLUMNS];
        for (int r=0 ; r< ROWS ; r++) 
        {
            for (int c=0 ; c< COLUMNS ; c++) 
             {
                 maze[r][c] = new MazeCell(r,c,mazeStrings[r].charAt(c));
             }
        }
}

What is protected?

When data or methods are given the access level protected, it means that derived classes may use that data or method. However, unrelated classes may not use that data or method. Thus, protected is in-between the access level of public, which any class may use, and private, where only the defining class may use the data or method. Because part 2 of this assignment asks you to write a class named SpamMaze that will be a class derived from Maze and because 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. At a minimum, you should implement the following methods. You may choose to add more methods - either private helper methods (to help these public methods) - or other public methods for your game to use.

• 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). Note that 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. It's initial direction is east as well. This may be set here in the constructor or elsewhere in the game - that's a design choice that is up to you.


• public int getRows()    is an accessor that returns the number of rows of this maze.


• public int getColumns()    is an accessor that returns the number of columns 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 addSpam()    adds one can of spam to the environment. You can choose the method used to add spam but the following properties are required:
  • An inserted can of spam may not be placed anywhere on the current location of the centipede's body nor on a wall or existing can of spam.
  • The reference to the new can of spam must be inserted in the spamCells LinkedList.
  You may wish to use random numbers to generate the locations of new spam cans. To do so, include the line import java.util.Random at the top of the file. Then, you can construct a random number generator with a line such as Random myGenerator = new Random(); which declares myGenerator to be a random number generator (an object of type Random) and instantiates a new such object. Then, the command myGenerator.nextInt(k) will generate a random integer in the range from 0 to k-1.
  
  
• public void removeSpam()    removes one can of spam from the environment when it's time for the spam to disappear. Notice that this function will simply be called periodically in order to make the game more interesting. It will not be called when the centipede consumes a can of spam. That event will be handled in the advancePede function described below. You can choose the method used to remove spam, but the following property is required: When this function is called, a can of spam is eliminated from the spamCells LinkedList. This can be done at random or (perhaps more reasonably) the oldest spam can in the list is removed.
  
  
• public int advancePede(char direction)    this is the fundamental update method for the entire game! This is where the "smarts" go. In particular, a character indicating the direction to move is passed in. The characters 'N', 'S', 'E', 'W', 'A' should represent the directions north, south, east, west, and automatic ("automatic" will be described below). Be sure to define good names for these symbols to avoid magic values in your code! For example, you might have a value such as public static final char NORTH = 'N'; So, here's what this method does:
  • Based on the direction that is passed in, the pedeCells LinkedList is updated to have the centipede move in that direction. That is, the head advances and the tail retracts in the given direction.
    
  • 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. This function need not necessarily do the resetting. Notice that this function returns an integer value (or you can change it to a char if you prefer). That value may be used to help with the resetting elsewhere in the program. This is described next...
    
  • So what exacty is the return value? It can be very handy for this function to return an integer or a character informing us (more likely the function that called this function) what happened. For example, if there was a collision with a wall, the calling function might appreciate knowing that so that. You can come back to this later - when doing part 3 - to decide what, if anything, you would like the function to return.
    
  • If the centipede's head lands on a can 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. Importantly, the can of spam that was just consumed must be removed from the spamCells LinkedList. What command will be used to do this? Check out remove command in the LinkedList class.
    
  • Finally, the automatic direction. If this function is passed in the value 'A' then we are in AI mode. That is, the spampede should navigate by itself, also heading for the nearest can of spam. To do this, it will call the multiBFS method that you wrote in Part 1. multiBFS will return a reference to the MazeCell that the spampede should move to. The spampede will then be updated to move to that cell.
  
  
• public char reversePede()    this method reverses the centipede so that it has the opposite orientation and moves in the appropriate "opposite direction". Note that if the centipede was previously moving west, it is not necessarily going to move east upon reversal. Instead, the new direction is the opposite of the direction of the tail of the centipede. That is, if the last two cells of the centipede's body indicate that the centipede is moving north, then the new direction for the reversed centipede will be south. In addition to modifying the spamCells linked list to perform the reversal, this function returns the new direction.

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 a 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:     Putting it all together: Spampede.java [60 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 the extra credit section below)!

Setting up

The "starter" applet Spampede.java and its html file Spampede.html are provided for you in /cs/cs60/hwfiles/a7 from the top-level assignments page.
There are some other files you'll need, too, such as ImagePanel.java. Be sure to grab it with

   cp /cs/cs60/hwfiles/a7/ImagePanel.java .
     

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

copyFiles

./copyFiles

chmod: cannot access `/home/apaul/public_html/*.java': No such file or directory