ICFP Programming Contest 2008

I participated as a one-person team.

The task was published 21:00 local time. First decision: Which language to use? Seeing the networking requirement and comments about latency in the task description, I decided against Haskell, as that would have meant that I would spend a big part of the contest time just to get the network stuff to work. Not even to mention multithreading. So I settled on Java.

My lightning division submission just tries to head directly home, trying to avoid obstacles by always turning right.

On sunday morning, I implemented a A* path finding. I had not done this before, but to my surprise, a more-or-less direct translation of the description on Wikipedia to Java worked quite well. To check the computed path, I also implemented a very simple GUI which displays the computed path (screenshot). This turned out to be very useful, but it also took several hours which I could have used implementing better steering. As nodes for the path finding, I use a grid of nodes distributed over the map. The time spent in path finding depends on the number of nodes used. In my final submission, I use about 300 nodes.

What is missing from my implementation is good steering. While I have a good path available, the rover has trouble following that path, because I did not bother to think much about acceleration and turning rate and so on. I had planned to implement this in the last hours of the contest, but simply ran out of steam. Thus my controller often crashes the rover into craters or takes too long to reach home because of slow maneuvering.

About martians: I completely ignore them. My earliest versions of the path finding included martians, but in testing I noted that performance was actually better when just considering boulders and craters.

My submissions: lightning, final.

Update 2008-08-07: The results from the first 7 trials of the lightning round are in. My controller made it through the first 5 trials, but failed in trial 6. This is better than I expected. Possibly due to a whim of the RNG or network latencies, I even got top rank on trial 4.

Final thoughts

I found this year's task much better suited to single person team that those of the last two years, which seemed a bit large. I also liked that the test server provided a graphical view. Without this I might have given up after the lightning round.

All in all, I'm quite pleased with my progress. While I definitely did not produce a winning entry, I did manage to implement the basic world representation and reasonably good path finding. I would probably have needed another day to improve steering and short-range obstacle avoidance to a competitive level.

Copyright © 2008 Christoph Breitkopf

Page history:

2008-08-07 Added note about lightnig round results.
2008-07-15 Fixed link to final submission. Added path GUI screenshot.
2008-07-15 First draft.