Assignment 5

Harvey Mudd College
Computer Science 60
Assignment 5, Due Monday, February 23, by midnight

Problem 1: Spampede! (80 points)

Assignment 5 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. This will give you the chance to use Java's graphics library and event-handling code. In addition, there is a small piece of the assignment that will introduce you to the rex programming language... . As with Spamsweeper, it's important to get started early -- especially on the applet portion of this assignment!

Example Applet

You can run an example Spampede applet at www.cs.hmc.edu/~dodds/Applets/Spampede/Spampede.html . You may even notice a bug in it (it's not always readily apparent...).

Files and Classes to Create

You will need to modify a Spampede.java file that contains your Spampede class extending Applet. In addition, you will need to use the following classes, which you may spread among several files. Starting points are provided in /cs/cs60/assignments/assignment5.

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 one placed in the directory on Wednesday, in case you'd prefer not to use your own)
a DNode class (in Deque.java)
a DequeADT interface (in DequeADT.java)
a Queue class (int Queue.java, used for the Deque)
a Node class (in Queue.java)
a Spampede class that extends the built-in Applet class in Java.

In addition, the example Spampede applet has files that demonstrate the use of sound, images, and textfiles with an applet and a script for moving things to the appropriate place and setting permissions. You may use or modify these or you may ignore them:

crunch.au, an audio file
planchette.gif, an image of Java's icon
testfile.txt, a plain text file
copyFiles, a script that copies everything to your public_html directory

You should copy all of these files to your cs60 directory from /cs/cs60/assignments/assignment5.

Getting the applet running

So, the first thing to do is to make sure you can get that example applet running on your own webpage or in appletviewer. Because the appletviewer instructions were in last week's HW, we mention the browser instructions here:

Make sure you have the Java Console open for your browser for debugging.
Compile everything with javac *.java .
Copy everything to your web directory with ./copyFiles .
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

Once the above steps work for you, you're ready to write your own applet. Basically, the starting point is the Spampede.java file. You will want to change the Spampede.java file so that you

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 to 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?

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 Boardcell). Variations are welcome, but as a default you should implement

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 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 initCentipede, that resets the game's conditions. This initCentipede 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 Spampede.java -- you will not have to change them, though you may "upgrade" them if you wish.

Use double-buffering, as discussed in class and shown in the example Spampede applet, so that your applet does not flicker. Again, this is built in to the starting file provided, so there's really not a whole lot to do, I suppose... .

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 up to 20% (or far beyond...) optional bonus credit.

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.

Reading

This assignment takes advantage of Object-Oriented programming (covered in Chapter 7 of the book), but the details of Java's Applet and GUI Component classes (and much more) are available from the references page. Also, the basics of event handling and Java's built-in classes will be presented in class.

Submission and Testing

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


  > cs60submitall

which will submit most of them. If you have images or sound files, they will not be submitted. However, you should just make a note of this at the top of your Spampede.java file and copy those images and sound files (but not source code!) to your ~/public_html directory. The graders will be able to grab them from there.

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: Starting with Rex (20 points)

As a mind-clearing alternative to Spampede, there are a few, very small rex programs to write this week. As you will see, rex is a very different language than java... .

Trying out the rex interpreter

Type rex at the prompt to enter the rex interpreter. You can exit rex at any time by hitting the end-of-file character, control-d. Play around with rex and get the feel of how it works.

For example, you can use rex as an infinite-precision integer calculator:

rex >  100000000000000000 * 1000000000000000000;
100000000000000000000000000000000000

rex >  3.141592653589793 * 10;
31.4159

Rex has double-precision (about 15 places) for floating-point values, but only six places of precision are printed. Note that a semicolon terminates statements in rex. For lots of documentation on rex, see the rex lite reference card.

As practice, write a function called add42 that takes a number as input and returns a new number that is 42 greater than the input. Here it is:

rex >  add42(x) = x + 42;
1

The 1 basically indicates that rex is happy with your definition of the function add42. So happy, in fact, that you can now use that function:

rex >  add42(-7);
35

rex >  add42(190);
232

You may want to try adding 42 to the string "hello":

rex >  add42("hello");
*** warning: can't add non-numerics k
*** aborting to top-level

As you see, rex will complain if you try to add a string to an integer.

Once you've got a little bit of experience with rex, close rex and change to your assignment5 directory or some subdirectory, if you prefer. There, create a file named hw5.rex that will hold your answers for the rex part of this assignment, e.g., using emacs or some other text editor.

Place your add42 function at the top of the file. You should add a comment with your name, date, and HW number, as well as a comment for your function. (Commenting in rex is identical to Java or C++.) All in all, your file will look something like this

  // CS 60 Homework 0
  // Zach Dodds 
  // 2/19/2004
  
  // Problem 1: add42 is a function that adds 42 to its input argument

  add42(x) = x + 42;

Save the file as hw5.rex (you don't need to close emacs, however).

At your unix prompt from the directory containing hw5.rex, you can run rex on your file by typing

  >  rex hw5.rex

This will start rex and load in the file. If there are no errors, you will see the rex prompt after a message:

hw5.rex loaded
rex >

Now, you can test your add42 function by hand, as before.

Alternatively, start rex with just rex and then, at the rex prompt, type *i hw5.rex. This will load in the file (the "*i" stands for "include") and you can now use the functions that were defined in that file.

You don't have to test things by hand, though for this assignment it wouldn't be too bad to do so. There is a rex function named test which allows for easy testing of your functions from within a file. Add the lines (even better, copy-and-paste then from this webpage...):

  test( add42(-7), 35 );
  test( add42(0), 41 );

to your hw0.rex file (emacs is still open, right?) Save the file, and in your rex window, kill rex and restart it the same way. You will see the messages

ok: add42(-7) ==> 35
bad: add42(0) returned 42, should be 41

This way, for complicated functions, you won't have to retype or recopy tests again and again... . Of course, in this case add42 isn't wrong; instead, the problem is with the second test.

The Problems

You may be worried that you don't know enough about rex to work on HW problems, but read on and (we hope) you'll find these not too bad... . Use the add42 example as a guide!

Lots more information on using rex is available at the rex summary page. Remember -- this is only a brief introduction to rex -- next week's assignment will start to really explore the language.

When the problem states that a function's input has a given form, you may assume that the test cases will not take any other forms; that is, you do not need to put in error-checking for erroneous input types.

Write each of the following functions in your hw5.rex file. Place at least a line of blank space between each problem and use at least one comment line (see the above example of add42 for an example of appropriate commenting).

You will want to use these operators (perhaps they're familiar?):

   + addition
   - subtraction
   * multiplication
   / division
   % the "mod" or remainder operator

as well as other things you might want to use ... be creative :)

Problem 1: Be sure to include the add42 function.

Problem 2: Create a function called octuple that takes a number as input and returns eight times that number as output. Example input and output are
```
      rex >  octuple(5.25);
      42

      rex >  octuple(300.1);
      2400.8
      
```

Problem 3: Create a function called halve that takes a number (integer or floating-point) as input and returns one-half that number as output. Example input and output are
```
      rex >  halve(42);
      21

      rex >  halve(41);
      20.5
      
```

Problem 4: Create a function called lastdigit that takes an integer as input and returns the last digit of that integer as output. (A negative sign should be preserved.) The function does not have to work on floating-point numbers at all. Example input and output are
```
      rex >  lastdigit(42);
      2

      rex >  lastdigit(-9678);
      -8
      
```
Hint: this function is just like the previous three, except that it uses the "mod" operator: %.

Problem 5: Create a function named f that takes any number (integer or floating point) as input and returns another number as output. The only requirements on f are that
```
         f(1) must return 7
         f(2) must return 10
           and
         f(6) must return 42
      
```
Example input and output are
```
      rex >  f(1);
      7

      rex >  f(2);
      10

      rex >  f(6);
      42
      
```
Keep in mind that f must not produce an error on other numeric inputs, but it can otherwise do anything you want!

For optional extra credit of 3 points, write two functions named g and h such that for as many integers as possible
```
      g(h(x)) is equal to 1 + h(g(x))
     
```
Full credit will go to a solution in which the above relationship holds for all integers. Some credit will go for solutions that handle some integers, but not all. It does not matter what your functions do for nonintegers.

Submission

Running cs60submitall will submit your hw5.rex file.

Harvey Mudd College Computer Science 60 Assignment 5, Due Monday, February 23, by midnight