Harvey Mudd College
Computer Science 65
Fall Semester, 2008
Assignment 9: DESC Applet
Due
Date: Wed. night. Nov. 19
Requirement: Implement
a Java Applet demonstrating the Double-Ended Spam Cruncher (DESC) behavior on a
variety of grid samples, selected from a menu. The DESC could model an AI
player in certain types of games.Your applet should be runnable using a web
browser. It can be hosted either on your CS Department account, or some other
place of your choosing. Email the URL where your DESC will be hosted once
you’ve decided.
Working
in pairs is highly recommended. Do not work
in groups larger than two, please. If you need a partner, please contact me as
soon as possible. Once the assignment is complete, we may hold some kind of
competition to see which team gets the highest number of points on a few test
cases not seen before.
A screen shot of one version of the
applet is given below. The objective of the DESC is to crunch as much spam as
possible, in the fewest number of moves possible, while staying in its
two-dimensional environment. In addition, there is a penalty for spam left
uncrunched. The point values are 20 for each crunched spam, -10 for each leftover
spam, and -2 for each step taken. The DESC is shown below with its two red
heads and a body of magenta circles. The spam is shown as green rounded rectangles.
The blue squares are walls through
which the DESC cannot pass. Neither can it pass through its own body, and it
must stay on the given grid. The
body always follows one of the two heads. Only heads, not body cells, can “crunch”.
(The DESC is not a constrictor.)
When spam on a cell is “crunched” by
either head, the DESC’s body lengthens by one cell. In the picture above, the
DESC has already crunched 36 spam. Thus it has extended its original size of
only two cells (both heads) to 38 cells total. The crunch effect is to be
achieved as follows: If the DESC can move its head onto a spam cell, then the
head takes the place of that cell and a body cell is added where the head
formerly was. The DESC should not break apart nor cross over itself.
The DESC can only move in one of four
directions (N, S, E, W). The DESC always starts on the leftmost two squares in
the top row. Those squares are considered sacred, and no spam or wall can be
placed on them.
The left choice menu lists the available
samples. The right choice menu chooses the delay between steps of the DESC. The
DESC begins moving as soon as an example is chosen, and the delay can be set at
any time, without restarting the current example.
The square size we are using is 15x15
pixels, and we suggest that the grid be limited to 40x40 cells.
Resources:
One of my versions of the DESC will be
found at:
http://www.cs.hmc.edu/courses/current/cs65/desc/
Zipped code for a starter kit may be
found at:
http://www.cs.hmc.edu/courses/current/cs65/descStarter.zip
The starter code running as an applet may
be found at:
http://www.cs.hmc.edu/courses/current/cs65/descStarter
The starter code does not search for
spam. Instead, a detached head moves around randomly on the grid. If it happens
to hit spam, it crunches it. It does not go through walls.
Hints:
·
Please compile your code under
Java 1.5, not 1.6, as not all browser (such as Firefox) run 1.6 yet. Use the “boilerplate”
code provided for flicker-freedom.
- Debugging through a browser can be annoying, partly because
browsers tend to cache the code, so you are never quite sure whether the
browser has the most recently compiled code. Thus it is better to debug
using the appletviewer on the
desktop. The appletviewer runs the Java class named in the desc.html file that is provided as
an argument, as does the browser.
- A Deque is the recommended structure for the DESC. Keep track of
the cells covered as (row, column) pairs.
- Treat one head as dominant for controlling motion at any one time,
but enable switching between the two heads easily. A form of backup can be
achieved by switching head dominance, then switching back.
- For searching for the closest spam, at least in the case of sparse
regions, perform a breadth-first search starting with both heads
simultaneously on the queue.
·
Other possible heuristics (only if you can afford the time):
·
For searching in a dense region, some kind of raster scan might be more
cost-effective.
·
When out of obvious possibilities, maybe “regroup” by having the DESC “coil
up” in an unoccupied region.
·
Search along the body of the DESC to find a cell from which spam can be
“seen”, then try to back up the head to that cell.