Homework 5: Snake Game

Due November 12 @ 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

The assignment will be graded as follows:

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

5.2. Style

In this homework you will be strictly graded according to the style guide. A style checker has been incorporated with Autolab and will assign these style points automatically. You can see your style score and feedback as part of the Autolab output.

5.3. How to Submit

For this assignment you are limited to 15 submissions on Autolab. Use them wisely. If you run out of submissions, you will automatically receive a 0.

You will submit your program to Autolab. Login to the system and you will see the 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. 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.

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

7. Important Notes