Problem 1:     Spampede! (70 points)

The Spampede game takes advantage of the double-ended Queue (Deque) class you wrote in Assignment 4 in order to implement a centipede in search of spam within a simple Maze-like world.

Example Applet

You can run an example Spampede applet at www.cs.hmc.edu/~hadas/applets/Spampede.html.

You can also run the "starter" Spampede applet which we saw in class by clicking here. We have provided the code for this starter applet and you will be modifying it until you have the working game!

Files and Classes

You will need to write the Spampede.java file that contains your Spampede class extending Applet. The "starter" applet Spampede.java and its html file Spampede.html are provided for you in /cs/cs60/assignments/assignment5/Spampede/.

In addition, you will need to use the following classes. These files are also provided:

• a Boardcell class (a default class modified from HW4 is provided)
• a Deque class (such as the one you wrote last week -- there will be a fully functional one placed in the directory on Wednesday, in case you'd prefer not to use your own.)
• a DNode class (provided in Deque.java)
• a DequeADT interface (provided in DequeADT.java)
• a Queue class (providedin Queue.java, used for the Deque)
• a Node class (provided in Queue.java)

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

• Spam.au, an audio file
• spam.gif, an image of a can of Spam
• copyFiles, a script that copies everything to your public_html directory

Getting the applet running

Make sure that you can run the provided "starter" applet from the appletviewer or from your webpage. If you're using your webpage, here are things to remember:

1. Make sure you have the Java Console open for your browser for debugging.
2. Compile everything with javac *.java .
3. Copy everything to your web directory with ./copyFiles. (If you are copying the files manually, please make sure not to copy the .java files.)
4. Now your Spampede applet (in it's current state) should appear from any web browser at the address

          http://www.cs.hmc.edu/~<your turing login name>/Spampede.html
          

Writing the applet

• create, in init, a 2d array of Boardcells. The reference to this 2d array is called grid and is already defined. Be sure you don't have a 2d array of nulls!


• initialize the contents of each of these Boardcells. This is similar to adding mines in Spamsweeper, except that you should be sure that the edges of your grid are all designated as walls. This will prevent many out-of-bounds errors! (Internal walls are OK, but not required.) The Boardcell.java file has setContents and getContents members. By default, it uses chars to represent its contents. Also, each Boardcell should hold its coordinates (while not strictly necessary, this is often helpful).


• draw the 2d array of Boardcells with the off-screen Graphics object named g. This should happen every time cycle gets called, and perhaps more often, e.g., when a key is pressed, as well. You should draw the 2d array of Boardcells as a 2d array of colored rectangles, with 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.


• keep track of a Deque of spam. You can add (and/or remove) spam by calling a method from cycle every so often (probably not every time). You can also add spam as needed (e.g., when one is eaten). But, you should have spam on the board at all times!


• keep track of the centipede (i.e., the "spampede") with a Deque. Your centipede will be a Deque of Boardcells, where the head of the centipede is at the front (not surprisingly), and the body of the centipede, which should be a different color, is the remainder of the Deque. The centipede should advance one square each time the cycle method is called. Keep in mind that no Boardcells are moving! Rather, it's the Deque that's wending its way through the 2d array of Boardcells.

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

What does the code have to do?

• Drawing the grid and the centipede within it. Each Boardcell should be 10 pixels by 10 pixels. The default environment should be a simple room 30 Boardcells (in the y direction) by 50 Boardcells (in the x direction), the outer boundary of which consists of walls. Additional obstacles/walls are totally optional.


• Every so often, the centipede's position should be updated within the maze. That is, the centipede's head advances one Boardcell in whatever direction it is facing, and the centipede's tail retracts by one Boardcell. (You need not stick to any particular speed, but remember that the graders will be using your applet -- try to keep them happy!) This is done in the cycle method, which is called every so often independent of the other things going on in the applet.


• If the centipede's head moves to a Boardcell that contains a wall or another part of the centipede, the centipede dies, and the game can either stop with an approprite message or it may start again. Note: it's tempting to try to call init, but applets should not do this. Rather, you might write another method, perhaps called reset, that resets the game's conditions. This reset method could be called from init, as well as in the case that the centipede dies.


• If the centipede's head occupies a Boardcell that contains a morsel of spam, the centipede grows by one Boardcell. That is, when the centipede next moves, its head advances one square, but its tail does not retract.


• 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
  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.


• Note on "reverse" The reverse key (r) does not necessarily send the centipede in the compass direction opposite to which it was just heading. Instead, it switches the current tail to become the head and the current head to become the tail. It then should determine which direction the centipede's head segment and second segment are heading and set the current heading appropriately. (It's a good thing you wrote reverse, peekFront, and peek2Front methods in your Deque class!


• Maintain Start and Pause buttons. Working versions are provided in Babypede.java -- you will not have to change them, though you may "upgrade" them if you wish.

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 4 points for each additional feature for up to 12 bonus points in total.) However, please do the rex part of this assignment first. (The rex part is important and will help you prepare for the exam.)

If you add optional features, please document them in ALL UPPERCASE in a comment at the top of your Spampede.java file so that the grutors will see this.

• 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.
  

Submission and Testing

There are a lot of files that make up this assignment, so the easiest thing to do is to run

  > cs60submitall

No tests will be run on your code; instead the graders will play your Spampede applet to see if it does all of the things it should!

Problem 2:     Playing with Rex! (30 points)

In this part of the assignment, you will have a chance to write some rex functions.

Type rex at the prompt to enter the rex interpreter. You can exit rex at any time by pressing CTRL-D (control key and D). (By doing this, you will lose all of the functions that you defined while you were in the interpreter.) Play around with rex and get the feel of how it works. For practice, try typing in some of the functions that we wrote in class and try them out. For more documentation, see the rex reference guides available from the "Reference Guides" link on the course homepage.

Exit rex and use your favorite editor (emacs, vim, etc.) to create a file called hw5.rex. You'll write your functions for this assignment in this file. After you write each function, we recommend that you save and close the file. Then, test those functions in rex. Remember, you can start rex with a file by typing rex hw5.rex or you can just type rex and once you are there you can include a file by typing *i hw5.rex at the rex prompt.

In this part of the assignment, you may use any built-in functions which we have seen in class. You may also define your own additional helper functions if you wish. For full credit, try to keep your code simple - all of these functions can be implemented very succinctly.

Your hw5.rex file should contain programs ("functions") for the following:

1. A function called twiddle(L) which takes as input a list L and returns a list that is just like L except that the first two elements have been swapped (or "twiddled"). If the list contains fewer than 2 elements, then your program can behave any way you wish. For example, here is some sample input and output:

     rex > twiddle(["i", "like", "the", "number", 42]);
     [like, i, the, number, 42]
     

2. supertwiddle(L) returns a list identical to L except that every pair of successive elements has been swapped. If the list has an odd number of elements then the last element is untouched. For example here is some sample input and output:

     rex > supertwiddle([1, 2, 3, 4, 5, 6]);
     [2, 1, 4, 3, 6, 5]
   
     rex > supertwiddle([1, 2, 3, 4, 5]);
     [2, 1, 4, 3, 5]
     

3. A function called find_index(X, L) which returns the index of the first occurrence of element X in list L. The first item in the list is assumed to have index 0. If X is not an element of L then this function should return a number larger than the index of any element in the list. For example here is some sample input and output:

     rex > find_index(1, [1, 2, 3]);    
     0
   
     rex > find_index(3, [1, 2, 3]);
     2
   
     rex > find_index(42, [1, 2, 3]);
     4
     

   Note that since 4 is not in the list [1, 2, 3], the function returned a number larger than the length of the list, which is 3. My solution printed 4, but any number larger than 3 would be OK in this case.
   
   
4. A function remove(X, L) which constructs a list identical to L except that every occurrence of X in L has been removed. The order of the unremoved elements should not be changed. If X does not occur in L then, naturally, this function simply constructs a list identical to L. For example here is some sample input and output:

     rex > remove(3, [5, 4, 3, 2, 3, 1, 2]);
     [5, 4, 2, 1, 2]
     

5. pair(X, L) returns a list of all pairs (a pair is a list with exactly two elements) in which the first element is X and the second element is taken from L. For example here is some sample input and output:

     rex > pair(1, [2, 3, 4]);
     [[1, 2], [1, 3], [1, 4]]
     

6. all_pairs(L1, L2) takes two lists as arguments and returns a list whose elements are all the pairs with the first element from L1 and the second element from L2. For example here is some sample input and output:

     rex > all_pairs([1, 2, 3], [4, 5]);
     [[1, 4], [1, 5], [2, 4], [2, 5], [3, 4], [3, 5]]
     

7. height(T) takes a list representing a tree as input (remember from lecture that a tree is just cleverly represented as a list!) and returns the height of the tree. The height of the empty tree is defined to be 0. The height of a tree with just one node is 1. The height of a tree, in general, is the maximum number of nodes among all paths from the root of the tree to a leaf of the tree. For example here is some sample input and output:

     rex > mytree = [5, [3, [], []], []];
     1
   
     rex > height(mytree);
     2
     

8. dupereverse(L) takes a list L whose elements could be numbers or lists (the elements of those lists could be numbers and/or lists). This function returns a list which is the reversal of L. If L contains a list, then that list gets recursively reversed. For example here is some sample input and output.

     rex > dupereverse([1, [2, 3], [4, [5, 6, [7, 8], 9] ] ]);
     [[[9, [8, 7], 6, 5], 4], [3, 2], 1]
     

   You may use any built-in rex functions. In particular, the reverse function and atomic predicate (take a look at how we implemented flatten) will be especially useful here.
   
   
9. uniquify(L) returns a list identical to L except that only the first occurence of each item of the list is saved. That is, all duplicates of an item are removed except for the first occurence. For example here is some sample input and output:

     rex > uniquify([1, 2, 1, 3, 2, 4, 2]);
     [1, 2, 3, 4]