CS 60

                                Assignment a06

		     Due Midnight, morning of 9 March 2003

                              Breadth-First Search

This assignment is the first part of the implementation of the Double-Ended
SpamCruncher (DESC) game.  It entails creating the code to perform a
breadth-first search to find the shortest path from a designated square
on a grid to spam.  Shortest is defined be the shortest path via the
city-block distance (up, down, left, and right count as 1), without passing
through designated blockages on the grid.

In this assignment you will also be dealing with the issues of defining
"Applets" so that your programs can be run from a web page.

A number of setup classes will be provided:

    BaseApplet: 

    This is a base class that provides many of the common things needed
    when doing applet graphics, such as ensuring flicker-free real-time
    animation.  This class extends Applet, and your particular applet
    will extend it.


    BreadthFirstApplet:

    This is the applet to be completed for this assignment.  It contains
    a certain amount of setup code for selecting grid samples and
    delay times.  It will draw the basic grid for you, but you will have
    to do some augmentation.


    Grid:

    This class provides a 2-dimensional array of Squares.  It is
    the class in which your breadth-first search will be done.


    Applet Grid:

    This class extends Grid and provides information regarding how
    the Grid is displayed on the screen.


    Square:

    This class provides one square in a Grid.  It contains an integer
    that designates its contents, and any additional information
    used in the search.


    Pair:

    This class represents a pair of coordinates used to index the Grid.


    bf.html

    This is the .html file needed to trigger execution of your applet.
    This file may be called in either of two ways:

    1)  appletviewer bf.html 	# on turing, while using an xterm

    The above command only works while using an xterm under an X server
    on one of the NCD workstations, or on your personal machine if you
    have an X server.  Examples of the latter would include X/Darwin
    on MacOSX, or Exceed on Windows.  It will not work from an ordinary
    tty window not connected with an X server.

    2)  Through a web-server.  

    To use this method, copy bf.html to your directory on turing:

        ~/public_html

    Copy all class files from your a06 sub-directory to the above
    directory as well.  
   
    Set the permissions of your ~/public_html so that they are world-readable.
    Simply run this command:

        /cs/cs60/bin/readonweb

    To execute the applet from a browser, use the URL:

        www.cs.hmc.edu/~yourlogin/bf.html

    where yourlogin is replaced with your personal login id.


How to start:

Start by copying the setup files /cs/cs60/a/06/*.java and bf.html
to your a06 sub-directory.  Make sure they compile.

At this point it would be a good time to being using RCS (Revision Control
System) so follow the instructions provided in class regarding it.

Then copy your .class files and the .html file to ~/public_html and try
them both with the appletviewer and with Netscape.


What to program:

The setup provides a way to initialize the grid with various configurations
of spam and blockage.  spam is marked with an X and blockage is a blue fill.

One the grid has been initialized, we want to conduct a breadth-first
search from an arbitrary square (designated by its row and column indices)
to the closest spam, avoiding blockages.

Use square at (row, column) = (0, 1) as a specific starting point, but
don't wire this in because we will want to keep it flexible.

Each step in the search should be one step of the while loop in the run()
method of your BreadthFirstApplet.  As you search, color the squares
encountered with a distinctive color.  (If you want to get fancy,
figure out how to make a gradient.)

Once you reached the spam, revise the display to show only the shortest
path from the starting point to it.  

A good way to hold the path would be in a Deque, since in the next
assignment we will want to be able to get to both ends of the path.