Assignment 12: Spampede!
Due Monday April 29 by 11:59 PM

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

1. Pair programming is permitted on all three parts of this week's assignment.  


2. You will be submitting several files for this assignment. Please zip all of your files into a single zip file named hw12files.zip and then submit that zip file for your assignment. That way, we know we'll be able to run your applet! In particular, we will look for Maze.java (Part 1), SpamMaze.java (Part 2), Spampede.java (Part 3), SpampedeBase.java (Provided), Queue.java (Provided), and QueueInterface.java (Provided).


3. 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 provided a basic README file on the main assignment page. You should edit this file and submit it. The README file will constitute part of your score on this assignment.
4. Previous students have identified some common mistakes that we think might be helpful to you!
   • Check your x/y consistency! Make sure that you're using the same conventions for storing x and y in each of your classes!
   • Remember to reset your Pede!

This assignment has three parts, which ultimately build to the Spampede game! In Part 1 (hw11), you extended the capabilities of your maze solver from HW7. 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 - if you'd like to make it accessible from your CS webspace, all the better. As noted, there is a README file in which we ask you to list the features, possible missing features, and any additions to the game that you've created.

What is the final product?

• You might want to try out the basic applet (with required functionality, but no extras, except for sound), which is available at:  http://www.cs.hmc.edu/~dodds/Applets/SpampedeBasic/Spampede.html
• Also, an applet that demonstrates only what is in the original set of hw9files.zip files 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.

• You can find an applet with some bells and whistles at http://www.cs.hmc.edu/~dodds/Applets/SpampedePlus/Spampede.html.  This applet demonstrates some additional functionality, but more is certainly possible (see the extra credit options, below).

Overview

• Maze.java: Responsible for storing the walls and spam in the maze, and for searching for spam and returning the path to the nearest spam can.  You extended the Maze class to incorporate more of the game's functionality. It will accomplish these goals with the help of Queue.java and QueueInterface.java
• SpamMaze.java: A subclass of Maze that does everything a Maze does AND keeps track of the spam that populates the board and location of the centepede.  This is the class that has all of the functionality for playing the game including moving the pede, populating the board with spam, determining whether the pede has hit a wall, etc.
• Spampede.java: A class that controls the functionality of the Applet.  This class is responsible for displaying the board to the user, handling the user's key strokes, and controlling the timesteps that move the pede forward.It accomplishes some of these tasks by extending the class SpampedeBase

Part 1:     Maze.java [possible extra credit]

You can decide if you are going to use your Maze.java code from the previous assignment or if you'd like to use the solution code. If you use your own Maze.java code, you will receive 5 points of extra credit. If you would like to use the solution from indicate in your README file that you are using the solution version of Maze.java Please email Colleen your login to get a copy of the file.

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;

How should we represent the head of the snake?    One way to do this is simply to decide that the first element of the pedeCells data member will always be the head of the snake. Equivalently, you could use the last element. Either way, it will be up to your code to make sure the head of the snake contains the 'S' character, that the other cells in the snake contain the 'P' character, and that the snake is updated appropriately.

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.

• private SpamMaze(String[] mazeString)    a private constructor called by the public static method makeSpamMaze. As shown below, makeSpamMaze calls the private SpamMaze constructor with the String array reprsenting the maze. The SpamMaze constructor calls the Maze constructor and then it should do additional initializion of the data members that are part of only the SpamMaze class (see above). We have provided the method makeSpamMaze and the first three lines of your SpamMaze constructor.
  

  	public static SpamMaze makeSpamMaze() {
  		return new SpamMaze(SpamMaze.mazeStrings);
  	}
  
  	private SpamMaze(String[] mazeStringArr) {
  		super(mazeStringArr);
  		spamCells = new LinkedList();
  		pedeCells = new LinkedList();
  		// more stuff might go here!
  	}
  

  It's most flexible to then delegate the set-up of the centipede and spam to other methods designed for that purpose: that is, you'll call resetPede and addSpam which you'll define below... .
  
  The reason that it's nice to have that functionality separate is that, when the snake crashes, you'll be able to call those reset functions -- you won't want to re-construct another SpamMaze!


• public void resetPede()    is a zero-input method that should remove all of the MazeCells from pedeCells (if any), reset their contents appropriately, and then initialize a new centipede in your game's starting position.
  
  Note that the initial state - at least in the default game - of the centipede is that its head is at maze[1][2] and that it has one body segment, which is at location maze[1][1]. Thus, the centipede is initially facing east.
  
  You might be worried -- how do I tell the applet that the snake is facing east? You won't need to do that here; rather, the Applet will start its this.dir data member assigned to east. Every time the Spampede crashes, you'll send a message to the Applet to let it know (this is the return value from advancePede).


• 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, you can use a line similar to this:
  

  	  int value = (int)(42*Math.random());
  	

  This line yields a random integer from 0 to 41 inclusive. It works because Math.random() is a random floating-point number from zero (inclusive) to one (exclusive): [0, 1). The multiplication scales that range and the cast to int rounds it down.



• 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 exactly is the return value? It is handy for this function to return an integer or some other data informing the Applet what happened... . For example, if there was a collision with a wall, the return value can let the Applet know this, so that the Applet can reset this.dir to EAST and make other changes it might need. For the moment, you might just return 0 here -- you can always 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 pedeCells linked list to perform the reversal, this function returns the new direction.
  
  There are a number of ways to handle this. For one, you could you could take all of the cells off pedeCells and create a brand new LinkedList (in the newly-correct order) and use that as pedeCells going forward. A more difficult method is to not change pedeCells at all, but simply remember which side you're treating as the head and which side as the tail. Although it is computationally less intensive running the game if you add logic to treat either side of pedeCells as the head, we strongly encourage you to start with the strategy of creating a new LinkedList with the correct order. An important rule in software engineering is to optimize as late in the process as possible! First - just get something working! It may turn out that there is something else that is much more important to spend your optimizing time on.

Testing!!

As with Maze, be sure to test your SpamMaze thoroughly before worrying about the graphical front-end of the applet in part 3.

Part 3:     Putting it all together: Spampede.java [50 points]

Overview of Spampede.java

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 on the top-level assignments page.  There are some other files you'll need, like ImagePanel.java, so make sure all the files are in the same directory with the files you developed for parts 1 and 2.

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

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

Getting the applet compiling, running, recompiling, and rerunning

When you run Spampede.java in Eclipse, you will first get a very small window!

To get the regular size window, you must go to the Run Configurations dialog box. You can do this by opening up the Spampede.java file and clicking Run->Run Configurations. In the Run Configuration menu (shown below), click on the "Parameter" tab and modify "Width" and "Height" to both be 600.

Now if you run Spampede.java you should see this:

Writing the applet

• Be sure to create, in init and/or in reset, a SpamMaze and make sure it is in a suitable starting configuration. There is already a data member named this.themaze to hold the created object.


• Draw the contents of the SpamMaze within the drawEnvironment method already provided. This will require writing a nested loop to create the 2d array of 10x10 pixel squares that represent the maze. This drawEnvironment method will be called every so often by the cycle method to show the latest state of the maze. You should use different colors of your choice representing walls, empty space, the head of the centipede and the body of the centipede. You will want to use the fillRect command to accomplish this.


• Update the spam within the SpamMaze named themaze. Within updateSpam you can add (and/or remove) spam every so often -- though doing so every cycle will probably be too fast!. You can also add spam as needed (e.g., when one is eaten). But, you should make sure to have at least one spam on the board at all times.


• Keep track of the centipede (i.e., the "spampede"). The updatePede method is provided as a placeholder for where you would do this. You might want a data member that keeps track of the centipede's current direction so that advancePede can be called appropriately -- the provided code has a data member private char dir that you might use for this. In this case, key presses would simply change this internally-stored dir.
  
  Keep in mind that no MazeCells are moving as the centipede crawls through the maze! Rather, it's the data member named pedeCells of type LinkedList that's snaking its way through the 2d array of MazeCellss by changing the cells to which it refers.


• Handle key presses. You will see a method that prints out certain characters when track of the centipede (i.e., the "spampede"). When the user presses the following keys, the centipede should change direction as indicated:
  • r : reverse, switching its head's position to its tail
  • i : turn north
  • j : turn west
  • l : turn east
  • k : turn south
  • a : go into autonomous, spam-seeking mode ("AI")
  If the centipede is already heading in the direction that the user chooses, nothing changes. If the user changes the centipede's direction so that it is moving back on itself (from South to North, say, or West to East), you may reverse direction, ignore the command, or "terminate" the centipede.

As you write your code, please compile and rerun the applet often to make sure you're on the right path. Use the appletviewer (or a web browser with a Java Console) to help with debugging and error-detection. Basically, this means many iterations of the compilation, copying, and testing steps above.

A Reminder On What to Submit

Extra Credit (10 points)

In addition to the extra credit described below, we'll have a unique type of extra credit this week. While I know that many many CS60ers help their classmates to debug the homework assignments, this week there will be an extra insentive to do so! To earn these 10 extra credit points...

• Complete (and submit) hw12 by Sunday at 3pm
• Sign-up for a two-hour grutoring slot here
• Go to your grutoring slot and check-in with the grutors - answer questions and help people debug. Here are some important grutoring guidelines
  • Be friendly!
  • Don't touch the person's keyboard or mouse
  • Don't stand next to the person while you help them. Sit or crouch down next to them.
  • Don't be afraid to ask for additional help!
• Add a note to your README that you're doing this extra credit

I want more!

If you haven't had enough of the Spampede.java file at the end of this assignment, there are a couple of specific items and an open-ended invitation to improve on the applet for optional bonus credit. (Up to 20 points in total.)

If you add optional features, please explain them carefully in the README file.

• Enemy Pedes!: Allow there to be one or more "enemy" pedes that use the multiBFS and/or other heuristics to play against your pede. (This is worth extra bonus points since it is a bit more challenging.)


• Speed up: You might want to have the rate at which the centipede is moving to increase as the game progresses.


• Scoring: You might want to have a system of scoring with a running total displayed as a label or text field or simply drawn to the applet panel.


• Lives: Rather than resetting or stopping the game after a single Spampede crash, keep a text field (or label) with the number of lives remaining and decrement it after each crash. When there are no lives left, stop the game (though you might want to consider a "reset" button.)
  


• Levels: Rather than maintaining a single, static maze, you may want to have the centipede advance to different mazes after consuming enough spam.
  


• Wrapping: Allow the centipede to wrap around the game board -- either in an unlimited fashion or through small tunnels in the walls. Or you might consider a "hyperspace" square, that "sends" cells to another spot on the board.


• General improvements: Feel free to add additional features you think would enhance the Spampede applet: different kinds of spam, sounds, images, other graphical widgets like pull-down menus or text boxes, etc.