Harvey Mudd
College
Computer Science 60
Fall
Semester, 2010
Assignment 8: DESC Applet
Due Date: Wed. Nov. 10, 11:59 p.m.
Working in pairs is possible on this assignment, and is highly
recommended. Do not work in groups
larger than two, please. If you need a partner, please contact me as soon as
possible, so I can help you find one. Also, if you have been working mostly
with one partner, it is time to switch.
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. I will explain how to do this in class. Email the URL where your DESC
will be hosted once you’ve decided.
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/2010/fall/cs60/desc/
Zipped code for a starter kit
may be found at:
http://www.cs.hmc.edu/courses/2010/fall/cs60/DESCstarterKit.zip
Similar starter code running as
an applet may be found at:
http://www.cs.hmc.edu/courses/2010/fall/cs60/DESCstarterKit
The starter code crunches spam,
but does not search for it. Instead, a detached head with no body moves around
randomly on the grid. If it happens to hit spam, it crunches it. It does not go
through walls.
Hints:
·
Please use the
“boilerplate” code provided for graphics buffering, so that your applet does
not flicker.
- 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 an IDE such as Netbeans,
or 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 (Double-Ended
Queue) 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.
- Possible heuristics (for
extra credit):
- For searching in a
dense region, some kind of raster scan strategy by the DESC might be more
cost-effective than search.
- 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.