CS 51 Test Program # 2
Due: December 12th at 4:00 PM
(Design due: November 30th, in class)

A test program is a laboratory that you complete on your own, without the help of others. It is a form of take-home exam. You may consult your text, your notes, your lab work, or our on-line examples and web pages, but use of any other source for code is forbidden. You may not discuss these problems with anyone aside from the course instructor. You may only ask the TA's for help with hardware problems or difficulties in retrieving your program from a disk or network.


Centipede - with its colorful mushroom patch, tenacious centipedes, bouncing spiders, fleas and scorpions - was one of the earliest and most popular video arcade games. It was brought to life by Atari in 1981 and has remained relatively popular over the years. (One of the 55,000 game units built by Atari recently sold for several thousand dollars on EBay. Sadly, the Dean denied our request for discretionary funds to place a higher bid...) For Test Program 2, you will write a version of "Centipede." We have simplified the game somewhat to make the assignment more manageable.

If you want to experience something closer to the original arcade game, you can find a working version on-line.

Our simplified game begins with a centipede at the top of a field of mushrooms. A bug "zapper" sits at the bottom of the screen. The zapper's job is to defend itself against the attacking centipede.

The centipede is actually made up of a bunch of individual segments. Each segment moves horizon- tally across the screen, and a segment turns around and moves down a row of mushrooms toward the zapper whenever it runs into the edge of the screen or a mushroom. The segments all move at a fixed speed, but each segment keeps track of whether it is moving to the left or the right. At the start of the game, all of the segments are adjacent to each other and heading in the same direction. Thus, they appear to be a single centipede. As the game progresses, the segments may head in different directions and no longer appear as a single centipede.

The zapper moves left and right in response to the player pressing the left and right arrow keys. The zapper shoots a missile by hitting the space-bar. If a missile hits a mushroom, the mushroom disappears and the player earns one point. If a missile hits a centipede segment, the player earns 5 points. Also, the segment that was shot disappears and a mushroom appears in its place. The centipede moves its remaining segments, as before. If a segment in the middle of the "centipede" is hit, the segments between the new mushroom and the "tail" of the centipede will run into the newly created mushroom and turn around. Thus, the net effect is that there will now appear to be two "smaller centipedes" headed toward the zapper.

The game ends either when the zapper shoots all of the segments or when a segment runs into the zapper. In either case, a message is displayed to the user indicating that the game is over and showing the player's final score.

Implementation Details

You should begin the game by setting it up. This involves creating a black background, a score-keeping mechanism, a zapper, mushrooms, and all those centipede segments. We provide some suggestions on how to design and implement all of these pieces of the program below.

The starter folder includes six mushroom images and two segment images. You only need to use one of each. ("shroom2.gif" is our personal favorite.) Feel free to use the others if you want to add a little variety or animation to your program. Also, feel free to edit and include your own images, although it will be easiest if you stick to images that are 16x16 pixels.

The scorekeeper should display the score at the bottom of the screen. You must be able to increase the score when a missile hits a segment or a mushroom.

The zapper is an object that will appear at the bottom of the screen. It must provide methods for responding to the player's key strokes. Thus, a zapper should be able to move left, move right, and shoot a missile. If the zapper is hit by a centipede segment, it should stop being able to move or fire. If you want, you can make the zapper disappear in some interesting way.

The missiles shot by the zapper are active objects. They should move up the screen and stop when they reach the top, hit a mushroom, or hit a segment.

The centipede has a different representation than our Nibbles snake. In particular, a centipede is an active object that keeps a collection of segments inside it. Each segment can be thought of as a separate entity that will keep track of which direction it is moving. The segments are all initially placed next to each other and facing to the right, so that they appear to move as a single, long "centipede". The centipede animates the segments by making each segment take a step. (The segments themselves are NOT active objects.) A segment takes a step by moving a fixed distance in the direction that that segment is heading. The centipede should pause only after all of the segments are moved. Do not use smooth scrolling or pause between moving individual segments. If you do, the centipede may not appear to move properly - it will stretch out or shrink, or individual segments may move out of alignment and not look quite right.

If a segment is about to step off the screen or hit a mushroom, it should move down the screen by one row of mushrooms. The segment should also change its direction so that it will move in the opposite direction the next time it is asked to take a step. When a segment is hit by a missile, it should disappear from the screen.

You need to be careful about how you keep track of the segments in the centipede. We suggest you use an array of Segment objects. Most importantly, DO NOT TRY TO DELETE SEGMENTS THAT HAVE BEEN HIT FROM THE ARRAY AND SHIFT OTHER ELEMENTS IN THE ARRAY OVER TO FILL THE HOLE. If you do this, bad things may happen if a missile tries to rearrange your array to delete a segment that has been hit at the same time that the segment is being moved across the screen. Instead, when a segment is hit, just set a variable within the object representing the segment to indicate that it is dead and hide it from the screen.

As you can see from the demo, mushrooms never overlap and are placed inside the squares of a grid laid over the canvas. We suggest using a two dimensional array of VisibleImages to store the mushrooms. Make the array large enough to hold mushrooms laid out over the whole canvas. For reasons similar to those described above for segments, you should fill all entries in your array with mushroom visible images. Only show images for mushrooms that should be visible, and NEVER DELETE ELEMENTS FROM THE ARRAY OR SET ENTRIES TO NULL. Intuitively, if there is enough room for a grid of mushrooms with 15 rows and 10 columns in the canvas, you would create a 15x10 array and store a mushroom in each cell. The following shows how the screen would look if that grid were displayed while all but 7 mushrooms were hidden:

To "remove" a mushroom that is hit by a missile, simply use the hide method to hide the mushroom visible image. The isHidden() method may be handy for determining if a specific mushroom is visible on the screen. When a missile hits a centipede segment, you should make the mushroom in the grid location underneath the segment appear after hiding the segment.

Your program will comprise several classes, corresponding to the objects just described.

The controller will set up the game. It will also accept user input in the form of key strokes. In response to the different key presses, it should invoke methods of the zapper, making it move or shoot. We have provided the skeleton for listening to the user's key presses. You should set up the game in begin and fill in the lines where the Zapper's methods need to be invoked. Be sure to add any GUI components to the window before creating the zapper as otherwise the zapper may lie below the final location of the canvas.

The Zapper moves in response to each key press of the left and right arrow keys. The game plays more easily if each key press moves the zapper by the width of a mushroom. When the spacebar is pressed, the CentipedeController will invoke the Zapper's shoot method to launch a missile.

A Segment manages one segment of the centipede, and describes its behavior. It should keep track of the direction it is traveling and record whether or not it is still alive. A segment can take a step, and it should be able to die. The step method should determine how far and in which direction the segment should move, and know how to turn around when it runs into the edge of the screen or into a mushroom. It should also "kill" the zapper if the segment's image overlaps the zapper.

A Centipede is an ActiveObject that keeps an array of Segments. Its run method will repeatedly make each segment take a step.

The Field class holds the two-dimensional array of mushrooms. The Field constructor should create all of the mushrooms, and the class should provide methods that make it easy to implement the interactions between mushrooms and segments, and mushrooms and missiles.

A Missile is an ActiveObject that moves up the screen, stopping either when it reaches the top or when it hits something. Note that to achieve this behavior, the missile needs to know about the Field and Centipede, so that it can determine whether it hits a mushroom or segment, respectively. In order to hit a unique segment of the centipede it would be best to move the missile each time by the width of a segment. Life will also be easier if both the gun on the zapper and the missile will be something other than a line, e.g. a FilledRect or FilledOval so you can more easily detect if it overlaps something. The easiest way to provide information to the Missile is to have the Zapper's shoot method take the Field and Centipede as parameters, and then pass them to the Missile's constructor when that method creates the new missile. (Alternatively, you could store the field and centipede in instance variables in the zapper, but this is a little tricky to set up because the centipede will also need to store the zapper so that its segments will be able to kill the zapper. This circularity between the zapper and the centipede can be resolved in a number of ways, but just passing the necessary information to shoot is the easiest.)

The ScoreKeeper class displays the score on the screen. Note that the Segments and the Field should probably know about the ScoreKeeper, as they will likely need to inform it to increase when a segment dies or mushroom disappears.

You may also want to define other classes if you believe they will simplify your design.

The Design

As indicated in the heading of this document, you will need to turn in a design plan for your Centipede program well before the program itself. You should include in your design a sketch of each class including the types and names of all instance variables you plan to use, and the headers of all methods you expect to write. You should write a brief description of the purpose/function of each instance variable and method.

In addition, you should provide pseudo-code for any method whose implementation is at all complicated. In particular, if a method is complicated enough that it will invoke other methods you write (rather than just invoking methods provided by Java or our library), then include pseudo-code for the method so that we will see how you expect to use your own methods.

From your design, we should be able to find the answers to questions like the following easily:

  1. How and when is the scorekeeper updated?
  2. What information is passed to the constructor for Missiles, Segments, etc.?
  3. How do you find the mushroom appearing at a certain location on the canvas in the Field's two-dimensional array? (You will need to use this operation in several places.)
  4. How does a Segment decide when to turn around? What methods does the Field provide so that the segment can decide whether it is about to step into a mushroom?
  5. What operations should the Centipede and the Field provide to help Missiles determine when they hit and kill segments and mushrooms?

The more time you spend on the design, the easier it will be to complete the program.


The following constants appear in the starter code. Using them will ensure that your segments move at a reasonable speed and are able to turn correctly.

In the Field class:

    // dimensions of the canvas 
    static private final int CANVAS_WIDTH = 400; 
    static private final int CANVAS_HEIGHT = 512;
    // size of mushroom pictures 
    static private final int SHROOM_SIZE = 16; 
    // dimensions of the mushroom array 
    static private final int NUM_ROWS = CANVAS_HEIGHT / SHROOM_SIZE; 
    static private final int NUM_COLS = CANVAS_WIDTH / SHROOM_SIZE; 

In the Segment class:

    // width of segment image 
    static private final int SEGMENT_WIDTH = 16; 
    // number of pixels a segment should travel in the X direction 
    static private final int SEGMENT_STEP_X = 4; 
    // number of pixels a segment should move in the Y direction 
    static private final int SEGMENT_STEP_Y = SEGMENT_WIDTH; 

In the Centipede class:

    // offset between segments when first created. 
    static private final int SEGMENT_OFFSET_X = 12; 
    // pause time between moving all of the segments 
    static private final int CENTIPEDE_PAUSE = 25; 

In the Missile class:

    // distance for missile to move each time interval. 
    static private final int DISTANCE_TO_MOVE = 12; 

Feel free to adjust these constants as you wish. However, FIELD_WIDTH, SHROOM_SIZE, SEGMENT_OFFSET_X, and DISTANCE_TO_MOVE should always be multiples of SEGMENT_STEP_X. If they are not, your centipedes may appear to separate or bunch up after running into obstacles, because some segments will turn around when they are a pixel or two further away from the obstacle than others.

Implementation Order

Begin by downloading the starter project from the handouts web page. We strongly encourage you to proceed as suggested below to ensure that you can turn in a running program. While a partial program will not receive full credit, a program that does not run at all generally receives a lower grade. Moreover it is easier to debug a program if you know that some parts do run correctly.

There is a great deal of functionality to aim for in this test program. Do not worry if you cannot implement all of the functionality. Get as much of it working as you can. As we have done throughout the semester, we will consider both issues of correctness and issues of style when grading your program. It is always best to have full functionality, but you are better off having most of the functionality and a beautifully organized program than all of the functionality with a program that is sloppy, poorly commented, etc.

Extra Credit

Since we have deliberately left out many features of the original Centipede game, there are clearly many additional features you could add to your program. We will give 1-2 points for each extension, for a maximum of 6 points extra credit. Some possible extensions are:

Turning it in

Your design should be either neatly written or typed, and it should be turned in on paper at the beginning of class on Friday, November 30. We will NOT return the design to you before the program is due. Thus you should keep a copy of your design.

Submit your code in the usual way by exporting and dragging your project into the Dropoff folder for your section. Name your folder with your last name followed by TP2. Also, be sure to double check your work for correctness, organization and style.

This program is due at 4 p.m. on December 12th, the last day of classes. While you may turn your program in late, you will be assessed a 10 point penalty for each day it is late. I.e., if you turn it in by 4 p.m. on December 6th, you will receive a 10 point penalty. If you turn it in at 4 p.m. on December 7th, you will receive a 20 point penalty, etc.

Grading Point Allocations


Design preparation (20 pts total)
2 pts Variable and constant names and types
2 pts Method signatures
2 pts English descriptions
2 pts Pseudocode
4 pts Plausibility

Grading Point Allocations



Syntax Style (14 pts total)
6 pts. Descriptive and helpful comments
2 pts. Good names
2 pts. Good use of constants
2 pts. Appropriate formatting
2 pts. Appropriate use of public/private
Semantic style (18 pts total)
4 pts. Conditionals and loops
4 pts. Efficiency issues
4 pts. Parameters, variables, and scoping
3 pts. Appropriate selection of arrays or recursive data structures
3 pts. Correct use of arrays or recursive data structure
Organization (14 pts total, 2 for each class)
Appropriate methods, parameters, instance variables and constants
Setup (12 pts total)
2 pts. zapper drawn at bottom
2 pts. one segment drawn correctly
2 pts. whole centipede drawn correctly
2 pts. one mushroom drawn correctly
2 pts. random mushrooms drawn correctly
2 pts. initial score or message correct
Zapper (8 points total)
3 pts. zapper moves left, right
3 pts. zapper shoots missile
2 pts. zapper cannot move off screen
Missiles (8 points total)
2 pts. missile moves up
2 pts. missile stops at top
2 pts. missile can hit segments
1 pts. missile can hit mushrooms
1 pts. segments turn into mushrooms
Segments and Centipede (10 points total)
2 pts. segment moves right or left
2 pts. segment turns around at edges
2 pts. segment turns around at mushrooms
2 pts. segment moves down when it turns
2 pts. array of segments move correctly
Ending the Game (4 points total)
1 pts. Game ends when all segments are hit
1 pts. Game ends when zapper is hit
2 pts. Scorekeeper keeps score correctly

Computer Science

Department of Computer Science
Pomona College