Homework Assignment 1

The Snake

15-211 Summer 2010

Due July 6th, 2010 at 11:59:59pm

In this assignment you will implement the game of Snake. The game has been around for ages, but recently it became popular as one of the games available on cell phones. The idea of the game is to guide a long, thin creature, resembling a snake, that eats the food. The more it eats, the longer it grows, and the more you score. If the Snake hits itself, the obstacles, or the walls, the game is terminated. Read the Wikipedia page on Snake video game.

• Implement an array based wraparound FIFO Queue data structure.
• Implement a Hash table that supports quadratic probing.
• Gain experience programming the Iterator interface.
• Gain an understanding of efficient data structures used to implement dictionaries and queues.

In the file theory.pdf there are some short theory questions. Please answer the questions in this file and turn it in class.

Download the starter code for assignment (zip file). Once you finish implementation, FTP java files to /afs/andrew.cmu.edu/course/15/211-kesden/handin/

You FTP the following java files

1. ArrayQueue.java
2. QuadraticProbingHashSet.java

This assignment involves an interactive graphical application in which you navigate the Snake by using the keyboard arrow keys. The Snake eats the food (black ovals), but stays away from obstacles (red squares) and the walls. The more it eats, the longer it gets. The food and the obstacles are randomly generated. The game has several options that allow you to change the level of the game, the background color, and to specify whether or not the caterpillar can pass through itself.

Your choice of data structure affects the operation and performance of your application. Since moving the Snake requires removing tail pixels and inserts them to the head, the Queue is the most appropriate data structure. Your task for this assignment is to provide an array based wraparound Queue implementation. The Queue's operations such as enqueue(), dequeue(), getFront() and contains() must run at constant time.

Methods dequeue() and getFront() throw exception on empty Queue.

If the Queue is full, enqueue() does not throw exception, but double the array size and copy all elements into a new array.

The contains() function is the tricky one. Its implementation involves a Queue traversal and thus runs at linear time. The longer the Queue, the more time it takes to perform the equality check. How would you implement contains() that runs at constant time?

Note: Although your final program will be required to use a hashtable to implement contains(), you may want to first implement a slow version of contains() that doesn't use a hashtable. This will allow you to test your ArrayQueue class before writing the hashtable class.

In addition you must implement an Iterator in the Queue class. The iterator is used each time when the Snake and the obstacles are drawn in the applet. It does not need to implement the remove() method.

See the provided interface QueueInterface.java for more implementation requirements.

You are required to write the ArrayQueue class that replaces the Queue class.

To provide a constant running time of contains() you must implement a second data structure, namely a hash table, which makes the insertion and find operations to run at amortized constant time. In snake, the hash table is used to represent a set of points. This naturally leads to the increase of storage space - the same data (the Snake) will be stored in two data structures. We sacrifice memory space for the sake of performance.

The hash table should not store duplicates of the same value.

One of the important issues of the hash table implementation is a dealing with collisions. You know by now that collisions should be avoided as much as possible. There are several strategies for resolving collisions. In the assignment you are to implement quadratic probing as a collision handling method.

See the provided interface HashSetInterface.java for implementation requirements.

Your assignment will be graded first by compiling and testing it. After that, we will read your code to determine whether appropriate data structures and algorithms were used, as well as judge the overall style of your code. Programs will be graded both on correctness as well as their ability to deal with so-called edge cases, like empty lists, lists with only one element, and so on. Points will be deducted for poor design decisions and un-commented, or un-readable code as determined by your TA.

To help you get started, a working implementation has been provided. This is the implementation that will be used if you initially try running GameApplet. However, the implementations of the Queue and the method contains() make use of classes that are built into the Java code. You are required to write the ArrayQueue class that replaces the Queue class.

Since the Snake game is a graphical application, it is extremely difficult to track down bugs in your Queue and hash table implementations. We therefore recommend that you write your own test cases to test out and debug each class before trying it out in the main program.

Note that it is not necessary to hand in your test cases, if you create one.