Brian Hoffman
bhoffman@alum.mit.edu
ICFP Programming Contest 2002
Monday 2nd September
v1.0 4:00 AM PDT

Details Regarding Submission:

    This entry is entirely written in C, and was coded from scratch
starting this Labor Day weekend on Saturday afternoon. I got the
communications with the server running by Saturday night, which left
most of Sunday to implement and debug the path planning algorithm. The
path planning algorithm went fairly smoothly, leaving a little time to
work on strategy Sunday night / Monday morning.

    The pathfinding algorithm used is straight A*, coded from scratch,
but based on the pseudocode presented at:

    http://www.gamasutra.com/features/19970801/pathfinding.htm

    which originally appeared in Game Developer magazine, Oct 1996.

    Regarding the buildme script, it's a file which contains one
commented build line. If the binary doesn't work for some reason,
running that one commented line at pretty much any shell prompt
should rebuild the binary.

    Thanks for putting this contest on. It's been a lot of fun!

Sincerely,
Brian Hoffman

-----
v1.0 4:00 AM PDT

  Implementation:
  ==============

  The program follows rather strict orders regarding what to do next.

  1) If the robot sees any packages, attempt to pick them up
	- Pick up the first package it sees
	- Make sure that the package isn't too heavy

  2) If no packages are visable, see if we're currently transporting
     a package. If so, follow the path to that destination.

  3) If we're not following a path at the moment, we might have
     arrived at our destination. Check to see if we have any packages
     to drop off here.

  4) If we don't have anything to drop off here, but are still
     carrying packages, plan a path to drop off the next package.

  5) If we have no packages left, head for the most desirable home base.

	Desirability for a home base is a weighted sum of:
         - Distance away
         - If the home base has been visited before
         - If it has been visited, if we saw any packages.

  6) If no home base can be found, do a random little dance.

  Improvements:
  ============

  1) No attempt to push other robots is made.

       - A more agressive strategy whereby packages can be
         obtained by pushing other robots might be pursued.

  2) Avoiding other robots is only incidental -

       - The robot recognizes if it was pushed or is no longer
         on its desired path, and replans its path.

       - If a package was dropped when it was pushed, it discards
         that package, and plans a path for the next one.

  3) The client could really use a GUI that shows the map & robots

  4) Selection of which package to pick could be improved.

       - This should really be based on some heuristic of the
         package weight, the distance required to travel, 
         if other packages can be delivered nearby, etc.
         I decided a client which functioned was better than a
         half coded client which didn't.

  5) Code cleanup very needed ... it got uglier and uglier as the
     evening progressed.

-----
*EOF*
