// You know, the normal imports...
// "awt.*" for all the buttons, textareas, etc.
// "event.*" for all the event handling stuff
// "PixelGrabber" is used to find the color of each pixel on the map image
import java.awt.*;
import java.awt.event.*;
import java.awt.image.PixelGrabber;

// All the "listener"s take care of events
// "Runnable" helps make the analysis an independent thread
// (so the applet doesn't freeze when it's analyzing)
public class mapthingy extends java.applet.Applet implements
	ActionListener, MouseListener, MouseMotionListener, AdjustmentListener, Runnable {

  int progress;
  int pixelmap[];
  int mapimage[][];
  int mapwidth=0, mapheight=0;
  int pixelcount;
  int nplaces;
  int places[];
  int active=-1;
  int nroads;
  int roads[];
  boolean trackMouse;
  int startplace=-1, endplace=-1;
  int shortest[];

// These constants will be used as indicators during the analysis of the map
  final int WHITE=1;
  final int BLACK=2;
  final int FOUND=3;
  final int POSSIBLE=4;
  final int LINE=5;
  final int TEXT=6;
  final int PLACE=7;
  final int ROAD=8;
  final String direction[]={"s, ", "e, ", "d, ", "u, ", "w, ", "n, "};
  final int VERTICAL=0;
  final int HORIZONTAL=1;
  final int DIAGONAL=2;

// Definition of all the components that you see on the screen
  Label L1=new Label("1. Enter the name of the image file (must be in the same directory as this applet):");
  Label L2=new Label("2. Choose starting and ending points by clicking on the map:");
  Label L3=new Label("Starting from");
  Label L4=new Label("Arriving at");
  Label L5=new Label("3. Here's the best route found:");
  Label action=new Label("Image processor is ready");
  Button loadimage=new Button("Load image");
  TextField link=new TextField();
  TextArea route=new TextArea("", 1, 500, TextArea.SCROLLBARS_NONE);
  Canvas bar=new Canvas();
  Canvas maparea=new Canvas();
  Canvas start=new Canvas();
  Canvas end=new Canvas();
  Scrollbar updown=new Scrollbar(Scrollbar.VERTICAL, 0, 400, 0, 400);
  Scrollbar leftright=new Scrollbar(Scrollbar.HORIZONTAL, 0, 600, 0, 600);

// "Graphics" are objects that you can draw on
// You need a Graphics object for each Canvas in order to draw on them
// "map" is the image loaded from file
  Image map;
  Graphics gmap;
  Graphics gbar;
  Graphics gstart;
  Graphics gend;

// These two are used for "double buffering", which updates the screen without flickering
  Image osi;
  Graphics osg;

// The Thread makes the analysis stoppable
  Thread analyze;

  public void init() {
    setBackground(Color.white);
    setLayout(null);

// Put everything on the screen
    add(L1);
    add(L2);
    add(L3);
    add(L4);
    add(L5);
    add(action);
    add(loadimage);
    add(link);
    add(route);
    add(bar);
    add(maparea);
    add(start);
    add(end);
    add(updown);
    add(leftright);

// Putting them at the right place
// (this takes a little more effort, but I prefer this over any other Layout stuff)
    L1.setBounds(10, 10, 500, 20);
    link.setBounds(20, 30, 400, 20);
    loadimage.setBounds(440, 30, 100, 20);
    action.setBounds(20, 60, 500, 20);
    bar.setBounds(20, 80, 500, 5);
    L2.setBounds(10, 100, 400, 20);
    maparea.setBounds(20, 120, 600, 400);
    updown.setBounds(620, 120, 18, 400);
    leftright.setBounds(20, 520, 600, 18);
    L3.setBounds(20, 550, 80, 20);
    L4.setBounds(270, 550, 80, 20);
    start.setBounds(100, 550, 150, 90);
    end.setBounds(350, 550, 150, 90);
    L5.setBounds(10, 650, 200, 20);
    route.setBounds(20, 670, 500, 20);

// Add the event listeners as appropriate
    loadimage.addActionListener(this);
    link.addActionListener(this);
    updown.addAdjustmentListener(this);
    leftright.addAdjustmentListener(this);
    maparea.addMouseListener(this);
    maparea.addMouseMotionListener(this);

// Getting the Graphics object for each Canvas
    gmap=maparea.getGraphics();
    gbar=bar.getGraphics();
    gstart=start.getGraphics();
    gend=end.getGraphics();

// setting up the graphics and image used for double buffering
    osi=createImage(600, 400);
    osg=osi.getGraphics();

// a few final steps, not too important
    route.setEditable(false);
    bar.setBackground(Color.white);
    maparea.setBackground(Color.white);
    start.setBackground(Color.white);
    end.setBackground(Color.white);
    updown.setBlockIncrement(400);
    leftright.setBlockIncrement(600);
    updown.setUnitIncrement(10);
    leftright.setUnitIncrement(10);
  }

// This is the ultimate function that takes care of
// analyzing the image, finding places and roads, ...
  public void run() {

// Setting a few things so the user doesn't mess up the analysis
    loadimage.setLabel("Stop analysis");
    link.setEnabled(false);

    int i, j;
    mapwidth=0;
    mapheight=0;
    mapimage=null;
    map=null;
    nplaces=0;
    active=-1;
    nroads=0;
    trackMouse=false;
    startplace=-1;
    endplace=-1;
    shortest=null;
    route.setText("");

// For the showProgress function, see below
    showProgress("Loading image", 0);
    repaint();

// This part takes care of loading the image from file into an Image object
// The MediaTracker makes sure the image is fully loaded before continuing
    try {
      map=getImage(getDocumentBase(), link.getText());
    } catch (Exception e) {
      showProgress("The file cannot be accessed from this applet.", -1);
    }
    MediaTracker mt=new MediaTracker(this);
    mt.addImage(map, 0);
    try {
      mt.waitForAll();
    } catch (Exception a) {
      showProgress("Image loading process was interrupted.  Try again.", -1);
    }

// Once the image is loaded, get its width and height, the program will need them.
// Also, if width and height are found to be -1, it means something is wrong.
    mapwidth=map.getWidth(this);
    mapheight=map.getHeight(this);
    if (mapwidth==-1 || mapheight==-1)
      showProgress("An error occurred while loading the image.  The file may not exist.", -1);

// Putting the new settings to accomodate the new image
// (adjust scroll bars, draw the map on the screen, ...)
    leftright.setValue(0);
    updown.setValue(0);
    updown.setMaximum(mapheight<400 ? 400 : mapheight);
    leftright.setMaximum(mapwidth<600 ? 600 : mapwidth);
    drawMap();
    showProgress("Image is successfully loaded.", 20);

// Here's where PixelGrabber comes in.  It reads the RGB color of each pixel
// and stores it in a big array of int.
    pixelmap=new int[mapwidth*mapheight];
    PixelGrabber pg=new PixelGrabber(map, 0, 0, mapwidth, mapheight, pixelmap, 0, mapwidth);
    showProgress("Reading image: "+Integer.toString(mapwidth)+"x"+Integer.toString(mapheight)+" pixels", 20);
    try {
      pg.grabPixels();
    } catch (Exception a) {
      showProgress("An error occurred while reading the image.  Try again.", -1);
    }

// Now we analyze the pixelmap.  In this step, each pixel is observed, transferred
// to the mapimage array and classified as either "black" or "white".
// We count the number of black pixels, which will be used later.
// firstblack indicates the position of the first black pixel, also used later.
    mapimage=new int[mapheight][mapwidth];
    int blackspots=0;
    int firstblackr=-1;
    int firstblackc=-1;
    for (i=0; i<mapheight; i++) {
      for (j=0; j<mapwidth; j++) {

// Don't stare at this "if" line for too long.  It just adds up the
// value for each color.  If the total is more than 550
// (e.g. FFFFFF=255+255+255), then it's considered WHITE.
// otherwise it is BLACK.
        if ((((pixelmap[i*mapwidth+j]>>16) & 0xff) +
             ((pixelmap[i*mapwidth+j]>>8 ) & 0xff) +
              (pixelmap[i*mapwidth+j]      & 0xff)) > 550) {
          mapimage[i][j]=WHITE;
        } else {
          mapimage[i][j]=BLACK;
          blackspots++;
          if (firstblackr == -1 || firstblackc == -1) {
            firstblackr = i;
            firstblackc = j;
          }
        }
      }

      if (40+60*i/mapheight > progress)
        showProgress("Looking for black pixels", 40+i*60/mapheight);
    }
    if (blackspots<2)
      showProgress("Map image does not have any recognizable black pixels.", -1);

    pixelmap=null;

// The "threshold" will be used to differentiate between line and text.
// Here the threshold will be set so that at least 98% of black pixels
// can be interconnected with lines shorter than the threshold.
// This is not always foolproof, but it's the only way I can think of, for now.
    int threshold;
    for (threshold=0; pixelcount<(blackspots*98)/100; threshold++) {
      showProgress("Examining threshold="+threshold, 100+65*i/blackspots);

// for the nextPixel function, see below
// If the map has too many black pixels, this recursive function will cause a
// "stack overflow" error.
      pixelcount=0;
      try {
        nextPixel(threshold, firstblackr, firstblackc, BLACK);
      } catch (StackOverflowError e) {
        showProgress("The image has too many black pixels.  Try reducing its size.", -1);
      }
      for (i=0; i<mapheight; i++) {
        for (j=0; j<mapwidth; j++) {
          if (mapimage[i][j]==FOUND)
            mapimage[i][j]=BLACK;
        }
      }
    }
    threshold = (threshold*6)/5;

// Go through every row of pixels and identify segments of black pixels
// Each segment is delimited by white gaps longer than the threshold.
// If the segment contains at least one small gap, it is possibly text
// otherwise it is considered a line.
    int gap;
    int segment;
    boolean isPossible=false;

    for (i=0; i<mapheight; i++) {
      gap=threshold+1;
      segment=0;
      for (j=0; j<mapwidth; j++) {
        if (mapimage[i][j]==BLACK) {

// if it's the beginning of a segment (first black pixel after long gap)
          if (gap>threshold) {
            segment=0;
            gap=0;
            isPossible=false;
          }

// if it's the first black pixel after a short gap
          if (gap!=0) {
            segment += gap;
            gap=0;
            isPossible=true;
          }

          segment++;
        }
        if (mapimage[i][j]==WHITE) {
          gap++;

// if the gap is longer than the threshold, then it's time
// to take care of the segment
          if (gap==threshold) {
            for (int k=gap; k<segment+gap; k++) {
              mapimage[i][j-k] = isPossible ? POSSIBLE : LINE;

// create an artificial gap for a step in the near future...
              if (i>0) {
                if (mapimage[i][j-k]==POSSIBLE && mapimage[i-1][j-k]==POSSIBLE)
                  mapimage[i][j-k]=WHITE;
              }
            }
            segment=0;
          }
        }
      }

// take care of any segments that are on the right edge of the map
// normally they are not recognized because the "gap" after the text
// (the right border of the map) is shorter than the threshold
      if (segment!=0) {
        for (int k=(gap>threshold?0:gap)+1; k<segment+(gap>threshold?0:gap)+1; k++) {
          mapimage[i][j-k] = isPossible ? POSSIBLE : LINE;

// more artificial gaps
          if (i>0) {
            if (mapimage[i][j-k]==POSSIBLE && mapimage[i-1][j-k]==POSSIBLE)
              mapimage[i][j-k]=WHITE;
          }
        }
      }
      if (165+40*i/mapheight>progress)
        showProgress("Recording horizontal segments", 165+40*i/mapheight);
    }

// Now go through every column of pixels and classify "possible"s as either
// text or line.  This is necessary because some horizontal lines are
// recognized as text in the previous part.
// This is also where the "artificial gaps" come in.  Without them,
// blocks of "probable"s will be recognized as lines instead of text.
    for (j=0; j<mapwidth; j++) {
      gap=threshold+1;
      segment=0;
      for (i=0; i<mapheight; i++) {
        if (mapimage[i][j]==POSSIBLE) {

// if it's the beginning of a segment (first black pixel after long gap)
          if (gap>threshold) {
            segment=0;
            gap=0;
            isPossible=false;
          }

// if it's the first black pixel after a short gap
          if (gap!=0) {
            segment += gap;
            gap=0;
            isPossible=true;
          }

          segment++;
        }
        if (mapimage[i][j]!=POSSIBLE) {
          gap++;

// if the gap is longer than the threshold, then it's time
// to take care of the segment
          if (gap==threshold) {
            for (int k=gap; k<segment+gap; k++)
              mapimage[i-k][j] = isPossible ? TEXT : LINE;
            segment=0;
          }
        }
      }

// take care of any segments that are on the bottom edge of the map
// normally they are not recognized because the "gap" after the text
// (the bottom border of the map) is shorter than the threshold
      if (segment!=0) {
        for (int k=(gap>threshold?0:gap)+1; k<segment+(gap>threshold?0:gap)+1; k++)
          mapimage[i-k][j] = isPossible ? TEXT : LINE;
      }

      if (205+40*j/mapwidth>progress)
        showProgress("Recording vertical segments", 205+40*j/mapwidth);
    }

// Expand the borders a little bit so that users won't feel squished
    for (i=0; i<mapheight; i++) {
      for (j=0; j<mapwidth; j++) {
        if (mapimage[i][j]==TEXT) {
          mapimage[i][j]=PLACE;
          for (int a=-5; a<=5; a++) {
            for (int b=-5; b<=5; b++) {
              if ((i+a)>=0 && (i+a)<mapheight && (j+b)>=0 && (j+b)<mapwidth) {
                if (mapimage[i+a][j+b] != TEXT)
                  mapimage[i+a][j+b]=PLACE;
              }
            }
          }
        }
      }
      if (i%25==0)
        showProgress("Expanding place borders", 245+30*i/mapheight);
    }

// Scan the map and count the number of regions of "text" pixels
// These regions are the "places" on the map.
    for (i=0; i<mapheight; i++) {
      for (j=0; j<mapwidth; j++) {
        if (mapimage[i][j]==PLACE) {
          nextPixel(2, i, j, PLACE);
          nplaces++;
          int temp[]=new int[nplaces*5];
          for (int a=0; a<temp.length-5; a++)
            temp[a]=places[a];
          places=temp;

// Each set of 5 elements in places[] represents the top, left,
// bottom and right borders for the place, plus an extra element
// used later to store information about the best route
          places[nplaces*5-5]=i;
          places[nplaces*5-4]=j;
          places[nplaces*5-3]=i;
          places[nplaces*5-2]=j;

// Find actual borders for the new place
          for (int a=0; a<mapheight; a++) {
            for (int b=0; b<mapwidth; b++) {
              if (mapimage[a][b]==FOUND) {
                mapimage[a][b]=WHITE;
                if (a<places[nplaces*5-5])
                  places[nplaces*5-5]=a;
                if (b<places[nplaces*5-4])
                  places[nplaces*5-4]=b;
                if (a>places[nplaces*5-3])
                  places[nplaces*5-3]=a;
                if (b>places[nplaces*5-2])
                  places[nplaces*5-2]=b;
              }
            }
          }
        }
      }
      if (i%25==0)
        showProgress(nplaces+" places found", 275+100*i/mapheight);
    }

// Recognize roads between places.  The method is similar to the one above
    for (i=0; i<mapheight; i++) {
      for (j=0; j<mapwidth; j++) {
        if (mapimage[i][j]==LINE) {
          pixelcount=0;
          nextPixel(2, i, j, LINE);

// Detects dirty spots that might interfere with analysis
          if (pixelcount<threshold/2) {
            for (int a=0; a<mapheight; a++) {
              for (int b=0; b<mapwidth; b++) {
                if (mapimage[a][b]==FOUND)
                  mapimage[a][b]=WHITE;
              }
            }
            continue;
          }

          nroads++;
          int temp[]=new int[nroads*3];
          for (int a=0; a<temp.length-3; a++)
            temp[a]=roads[a];
          roads=temp;

// Find the top, bottom, left and right edges of the line blob
          int topX=j, topY=i, bottomX=j, bottomY=i, leftX=j, leftY=i, rightX=j, rightY=i;
          for (int a=0; a<mapheight; a++) {
            for (int b=0; b<mapwidth; b++) {
              if (mapimage[a][b]==FOUND) {
                mapimage[a][b]=ROAD;
                if (a<topY) {
                  topX=b;
                  topY=a;
                }
                if (a>bottomY) {
                  bottomX=b;
                  bottomY=a;
                }
                if (b<leftX) {
                  leftX=b;
                  leftY=a;
                }
                if (b>rightX) {
                  rightX=b;
                  rightY=a;
                }
              }
            }
          }

// Each group of 3 elements in roads[] represents the source, destination and direction

// These variables will be used later to find source and destination of each line
          double deltaX, deltaY;

// For the direction, test which dimension is significantly larger than the other
          if ((rightX-leftX) > (bottomY-topY)*15) {
            roads[3*nroads-1]=HORIZONTAL;
            deltaX=1.5;
            deltaY=0.0;
          } else if ((bottomY-topY) > (rightX-leftX)*15) {
            roads[3*nroads-1]=VERTICAL;
            deltaX=0.0;
            deltaY=1.5;

// This supposedly detects "+" type roads (with doors/traps)
          } else if (Math.abs(rightX+leftX-2*topX)<threshold/2 ||
                     Math.abs(topY+bottomY-2*leftY)<threshold/2) {
            if ((rightX-leftX)>(bottomY-topY)) {
              roads[3*nroads-1]=HORIZONTAL;
              deltaX=1.5;
              deltaY=0.0;
            } else {
              roads[3*nroads-1]=VERTICAL;
              deltaX=0.0;
              deltaY=1.5;
            }

// if it's a / type diagonal
          } else if (Math.abs(topX-leftX) > Math.abs(topX-rightX)) {
            roads[3*nroads-1]=DIAGONAL;
            int u=(leftX-rightX)*(leftX-rightX)+(topY-bottomY)*(topY-bottomY);
            deltaX=1.5*(leftX-rightX)/Math.sqrt((double)u);
            deltaY=1.5*(bottomY-topY)/Math.sqrt((double)u);

// if it's a \ type diagonal
          } else {
            roads[3*nroads-1]=DIAGONAL;
            int u=(rightX-leftX)*(rightX-leftX)+(topY-bottomY)*(topY-bottomY);
            deltaX=1.5*(rightX-leftX)/Math.sqrt((double)u);
            deltaY=1.5*(bottomY-topY)/Math.sqrt((double)u);
          }

// Extend line in both directions to find starting and ending places
          int a=0;
          roads[3*nroads-3]=-1;
          while (roads[3*nroads-3]==-1) {
            a++;
            mouseTrack((leftX+rightX)/2-(int)(deltaX*a), (topY+bottomY)/2-(int)(deltaY*a));
            roads[3*nroads-3]=active;
          }

          int b=0;
          roads[3*nroads-2]=-1;
          while (roads[3*nroads-2]==-1) {
            b++;
            mouseTrack((leftX+rightX)/2+(int)(deltaX*b), (topY+bottomY)/2+(int)(deltaY*b));
            roads[3*nroads-2]=active;
          }

// Remove lines that don't point to anything
          if (roads[3*nroads-3]==-2 || roads[3*nroads-2]==-2)
            nroads--;
        }
      }
      if ((i%25)==0)
        showProgress(nroads+" roads found", 375+120*i/mapheight);
    }

// Finally, finished !!!!
    trackMouse=true;
    active=-1;
    showProgress("(100%) Analysis completed successfully.", 500);
  }

// This function stops the analysis and resets a few things
  public void stop() {
    loadimage.setLabel("Load image");
    link.setEnabled(true);
    repaint();

    if (analyze!=null) {
      analyze.stop();
      analyze=null;
    }
  }

// the showProgress function.  It updates the current status out of 500.
// If p=-1, it means an error occurred.  If p=500, then the analysis is finished.
  public void showProgress(String e, int k) {
    progress=k;
    if (k<0 || k==500) {
      action.setText(e);
      stop();
    } else {
      action.setText("("+Integer.toString(k/5)+"%) "+e+"...");
    }
    drawProgress();
  }

// drawProgress draws the progress bar
  public void drawProgress() {
    if (progress<0) {
      osg.setColor(Color.red);
      osg.fill3DRect(0, 0, 500, 5, true);
    } else {
      osg.setColor(Color.blue);
      osg.fill3DRect(0, 0, 500, 5, true);
      osg.setColor(Color.green);
      osg.fill3DRect(0, 0, progress, 5, true);
    }
    gbar.drawImage(osi, 0, 0, this);
  }

// drawMap draws the map and the tracking rectangle
  public void drawMap() {
    osg.clearRect(0, 0, 600, 400);
    osg.drawImage(map, -leftright.getValue(), -updown.getValue(), this);

/*
// debug: enable this if you want to see all the detected places
    osg.setColor(Color.blue);
    for (int a=0; a<nplaces*5; a+=5)
      osg.drawRect(places[a+1]-leftright.getValue(), places[a]-updown.getValue(),
                   places[a+3]-places[a+1], places[a+2]-places[a]);
*/
/*
// debug: enable this if you want to see all the detected roads
    osg.setColor(Color.blue);
    for (int a=0; a<nroads*3; a+=3) {
      int startX=(places[roads[a]+3]+places[roads[a]+1])/2;
      int startY=(places[roads[a]+2]+places[roads[a]])/2;
      int endX=(places[roads[a+1]+3]+places[roads[a+1]+1])/2;
      int endY=(places[roads[a+1]+2]+places[roads[a+1]])/2;
      osg.drawLine(startX-leftright.getValue(), startY-updown.getValue(),
                   endX-leftright.getValue(), endY-updown.getValue());
    }
*/

    if (active>=0) {
      osg.setColor(new Color(100, 35, 100));
      osg.drawRect(places[active+1]-leftright.getValue(), places[active]-updown.getValue(),
                   places[active+3]-places[active+1], places[active+2]-places[active]);
      osg.drawRect(places[active+1]-leftright.getValue()-1, places[active]-updown.getValue()-1,
                   places[active+3]-places[active+1]+2, places[active+2]-places[active]+2);
    }
    osg.setColor(Color.red);
    if (startplace>=0)
      osg.drawRect(places[startplace+1]-leftright.getValue(), places[startplace]-updown.getValue(),
                   places[startplace+3]-places[startplace+1], places[startplace+2]-places[startplace]);
    if (endplace>=0)
      osg.drawRect(places[endplace+1]-leftright.getValue(), places[endplace]-updown.getValue(),
                   places[endplace+3]-places[endplace+1], places[endplace+2]-places[endplace]);

    osg.setColor(Color.green);
    for (int a=0; shortest!=null && a<shortest.length-1; a++) {
      int startX=(places[shortest[a]+3]+places[shortest[a]+1])/2;
      int startY=(places[shortest[a]+2]+places[shortest[a]])/2;
      int endX=(places[shortest[a+1]+3]+places[shortest[a+1]+1])/2;
      int endY=(places[shortest[a+1]+2]+places[shortest[a+1]])/2;
      osg.drawLine(startX-leftright.getValue(), startY-updown.getValue(),
                   endX-leftright.getValue(), endY-updown.getValue());
    }

    gmap.drawImage(osi, 0, 0, this);
  }

// This draws the start and end locations that the user selected
  public void drawLocations() {
    gstart.clearRect(0, 0, 150, 90);
    if (startplace>=0) {
      int x=(places[startplace+3]+places[startplace+1])/2;
      int y=(places[startplace+2]+places[startplace])/2;
      gstart.drawImage(map, 75-x, 45-y, this);
      gstart.setColor(Color.red);
      gstart.drawRect(75-x+places[startplace+1], 45-y+places[startplace],
                      places[startplace+3]-places[startplace+1],
                      places[startplace+2]-places[startplace]);
    }
    gend.clearRect(0, 0, 150, 90);
    if (endplace>=0) {
      int x=(places[endplace+3]+places[endplace+1])/2;
      int y=(places[endplace+2]+places[endplace])/2;
      gend.drawImage(map, 75-x, 45-y, this);
      gend.setColor(Color.red);
      gend.drawRect(75-x+places[endplace+1], 45-y+places[endplace],
                    places[endplace+3]-places[endplace+1],
                    places[endplace+2]-places[endplace]);
    }
  }

// Warning: recursive function - takes a LOT of memory for big maps
// Basically takes every wanted pixel and looks for any other wanted pixel within
// the specified range, replacing each one with the replacement, and repeat
  public void nextPixel(int range, int row, int column, int wanted) {
    mapimage[row][column]=FOUND;
    pixelcount++;

// check all valid neighboring pixels
    for (int a=row-range; a<=row+range; a++) {
      for (int b=column-range; b<=column+range; b++) {
        if (a>=0 && a<mapheight && b>=0 && b<mapwidth && mapimage[a][b]==wanted)
          nextPixel(range, a, b, wanted);
      }
    }
  }

// actionPerformed happens when you click a button
// or press "enter" when typing the image file's name
// Each request is dealt with appropriately
  public void actionPerformed(ActionEvent e) {

// in this case, the user is asking to start the analysis
    if (e.getSource()==link || e.getActionCommand()=="Load image") {
      analyze=new Thread(this);
      analyze.start();
    }

// stop the analysis
    if (e.getActionCommand()=="Stop analysis")
      showProgress("Analysis was interrupted by the user.", -1);

  }

// mouseReleased happens when you click on the map
// If you happen to click on a valid location, it will set
// the starting or ending spot to be that location.
  public void mouseReleased(MouseEvent e) {
    if (active>=0) {

// here the user is only choosing a starting location - easy
      if (startplace<0) {
        startplace=active;

// here the user is choosing the same ending location as the starting location
// we do not allow that to happen
      } else if (endplace<0 && active==startplace) {
        // (nothing happens here)

// The user chooses a valid ending location - time to find the shortest route
// for this I chose the one-way waterflow method for simplicity
// it's actually pretty quick even with 1.gif (~150 places + ~150 roads)
      } else if (endplace<0) {
        endplace=active;

// first clear any previous records
        for (int a=4; a<nplaces*5; a+=5)
          places[a]=-1;
        route.setText("");

// mark the number of steps it takes to get from the endplace to a place
// stop when the startplace is reached
        places[endplace+4]=1;
        while (places[startplace+4]==-1) {
          for (int a=0; a<nroads*3; a+=3) {
            if (places[roads[a]+4]!=-1 && (places[roads[a+1]+4]==-1 || places[roads[a+1]+4]>places[roads[a]+4]))
              places[roads[a+1]+4]=places[roads[a]+4]+1;
            if (places[roads[a+1]+4]!=-1 && (places[roads[a]+4]==-1 || places[roads[a]+4]>places[roads[a+1]+4]))
              places[roads[a]+4]=places[roads[a+1]+4]+1;
          }
        }

// now trace back the numbers for the quickest route
        int currentlocation=startplace;
        shortest=new int[places[startplace+4]];
        shortest[0]=startplace;
        int b=1;
        while (currentlocation!=endplace) {
          for (int a=0; a<nroads*3; a+=3) {
            if (roads[a]==currentlocation && places[roads[a]+4]==places[roads[a+1]+4]+1) {
              currentlocation=roads[a+1];
              shortest[b]=currentlocation;
              b++;
              route.append(direction[roads[a+2]]);
            }
            if (roads[a+1]==currentlocation && places[roads[a+1]+4]==places[roads[a]+4]+1) {
              currentlocation=roads[a];
              shortest[b]=currentlocation;
              b++;
              route.append(direction[5-roads[a+2]]);
            }
          }
        }

// here the user has alrady completed one analysis, and is choosing
// a brand new starting location - reset everything, and get starting location
      } else {
        startplace=active;
        endplace=-1;
        shortest=null;
        route.setText("");
      }
      repaint();
    }
  }

// mousePressed and mouseClicked are not used to do anything
// but I still have to include them, or else the compiler complains
  public void mousePressed(MouseEvent e) {}
  public void mouseClicked(MouseEvent e) {}

// mouseEntered, mouseExited, mouseDragged and mouseMoved
// help keep track of the mouse's movement so I can draw the
// tracking rectangle around the correct location
  public void mouseExited(MouseEvent e) {
    if (trackMouse) {
      active=-1;
      drawMap();
    }
  }

  public void mouseEntered(MouseEvent e) {
    if (trackMouse)
      mouseTrack(e.getX()+leftright.getValue(), e.getY()+updown.getValue());
  }

  public void mouseDragged(MouseEvent e) {
    if (trackMouse)
      mouseTrack(e.getX()+leftright.getValue(), e.getY()+updown.getValue());
  }

  public void mouseMoved(MouseEvent e) {
    if (trackMouse)
      mouseTrack(e.getX()+leftright.getValue(), e.getY()+updown.getValue());
  }

// As its name suggests, it tracks where the mouse is.
// It tests if the mouse is pointing at some different place.
// active is set to -1 if no place is found
// -2 if the coordinates are invalid
  public void mouseTrack(int x, int y) {
    int temp;
    if (active<0 || y<places[active] || x<places[active+1] || y>places[active+2] || x>places[active+3]) {
      if (x<0 || x>mapwidth || y<0 || y>mapheight) {
        temp=-2;
      } else {
        temp=-1;
        for (int a=0; a<nplaces*5; a+=5) {
          if (places[a]<=y && places[a+1]<=x && places[a+2]>=y && places[a+3]>=x) {
            temp=a;
            break;
          }
        }
      }

// temp!=active if either no place is found, or a new place is found
      if (temp!=active) {
        active=temp;
        if (trackMouse)
          drawMap();
      }
    }
  }

// this takes care of drawing the map when you use the scroll bars
  public void adjustmentValueChanged(AdjustmentEvent e) {
    drawMap();
  }

  public void paint(Graphics e) {
    drawProgress();
    drawMap();
    drawLocations();
  }

}