Homework 5: Snake Game

Due November 4 @ 8:00pm on Autolab

1. Introduction

In this assignment, you’ll be writing the underlying data structures for a 2-player snake game and then adding a few new features to the game. You won’t need to worry about writing a GUI for the game, as one is provided.

Download a pre-prepared Eclipse Project hw5.zip and import it into Eclipse using these instructions. You will make all of your changes inside of the Java files in this project.

2. Game Overview

This assignment involves a computer game called Snakes. In Snakes, two players each control a snake to move around in a grid in which there are small green pellets of food. The two players race to eat as many pellets as possible. When all of the pellets are gone, the player who has managed to eat the most pellets is the winner.

The game makes use of two data structures: SimpleList and SimpleQueue. The SimpleList is used to store the locations of all of the pellets on the board. The SimpleQueue is used to store the locations of the snakes.

3. Your Tasks

You have two main tasks.

  1. Finish the MyList data structure that implements both the SimpleList and SimpleQueue interfaces. Once you have a fully functional MyList implementation, you can run the SnakesGame and play it. Do not compile and run the SnakesGame class until you have all the methods and the iterator written and tested in isolation in MyList. Since all the SimpleList and SimpleQueue methods are used by SnakesGame, they all need to be working before SnakesGame will work. Also, you should make sure all the non-Iterator methods work correctly before implementing the Iterator. You should also test the Iterator by creating a for-each loop inside the main method before going on to run SnakesGame.

  2. Modify the snake game to add some new features.

3.1. Finishing MyList

3.1.1. The Interfaces

There are two interfaces provided for you: SimpleList and SimpleQueue. SimpleList is a basic list with add, remove, and isEmpty operations. SimpleQueue is a basic queue with enqueue, dequeue, peek, and isEmpty. See the source files (or the javadoc below) for more information.

Note that both interfaces also require you to implement Iterator.

3.1.2. Implementing MyList

The MyList data structure that you build should implement both SimpleList and SimpleQueue. That means it needs to contain implementations for every method from both interfaces. Recall that a class can implement more than one Interface. The first thing to do will be to create “stub” public methods (since interface methods are default public access) with the appropriate headers copy-pasted from the interfaces into the MyList.java file.

Since I want you to get additional practice with linked lists, you will use a linked list as the underlying data structure and implementation. As a result, you will likely refer to (and use) code that we developed in class as well as the code you wrote in the last assignment. This is perfectly fine, but some of that code will need to be adapted for the methods that must be implemented in the SimpleList and SimpleQueue interfaces, given the specifications provided.

3.1.3. Note on Efficiency

Some of the methods have efficiency requirements. Both add (from SimpleList) and enqueue (from SimpleQueue) must be \(O(1)\). In order to make them \(O(1)\) you will need to keep (and update) a last reference, in addition to the head reference we maintained for the singly linked list that we wrote previously. Note that last must be updated appropriately and consistently in any methods that could possibly alter it. Doing this allows the last ListNode to be accessible in constant time.

Both of your Iterator methods (hasNext() and next()) must also be \(O(1)\).

3.2. Modifications to Snakes

After you have the game working properly, you need to add three new features to it:

  1. Grow the snake by one cell each time it eats a pellet.
  2. Wrap the snake around to the other side of the grid once it reaches an edge (top/bottom/left/right).
  3. Determine if a snake can no longer move and force a win for the other player.

We will manually run your game to test it for this functionality.

4. javadoc

I have generated the javadoc documentation for the provided code. You can find it here.

5. Grading and Submission

There are multiple parts of the grading of this assignment:

  1. For the first 70 points, your submission will be auto-graded on Autolab based on your implementation of MyList.
  2. For the next 20 points, your submission will be manually graded as a result of running your final game and ensuring it has the new features.
  3. For the next 5 points, your submission will be manually graded to check for good implementation methodologies. (Did you use a good approach to solving the problems?)
  4. For the next 5 points, your submission will be manually graded to check for good testcases that you include in the main method. (Do you have 2-3 basic testcases for each method, and do they all execute automatically?)
  5. Your code will also be checked for style. The parts of style that can be checked automatically (things like spacing, indentation, the use of CamelCase, etc.) are automatically checked by the autograder. Other parts of style, such as choosing good variable names, will be checked manually. Autograded style guide violations can result in, at most, -10 points. Manually checked style guide violations can result in, at most, -5 points.

You will submit your program to Autolab. Login to the system and you will see the homework.

For this homework you’ll need to submit a zip file containing your code. Lucky for you, however, Eclipse can create this zip file for you. Check out these instructions. On Autolab, you’ll submit that exported zip file. On the page that follows your submission you will see your live score (out of 90). It may take up to a few minutes for your score to appear, during that time just hit refresh in your browser. If you receive a lower score than you expect, you can click on the score to see the feedback from the autograder.

For this assignment you have 15 submissions. Use them wisely.

6. Additional Information

6.1. Testcases

In this homework we are not providing any testcases.

You need to write at least three testcases for each of the new methods. At least one of those three must be non-basic. All of your testcases should be in the MyList class included with the skeleton code. You must follow the model of our testcases (meaning you print when you start, print when you finish, etc.) Additionally, you must comment each testcase with a note describing what it tests.

6.2. Restrictions

You may only use the following Java libraries in this assignment:

java.util.Iterator
java.util.Random
java.util.NoSuchElementException
java.awt.Color
java.awt.Graphics
java.awt.Point
java.awt.Font
java.awt.Frame
java.awt.Graphics
java.awt.event.KeyAdapter
java.awt.event.KeyEvent
java.awt.event.WindowAdapter
java.awt.event.WindowEvent
javax.swing.JOptionPane

6.3. Important Notes