Here is my entry for the ICFP programming contest 2003. Not a good one but at least it races all the tracks.
You can download it.
This is a C++ source code. It is standard C++ except for the 64 bits integers (there is no "at least 64 bits integer" in the standard).
Note that this is written in a mix of english en french.
I compiled it with Linux and Windows.
No special libraries needed. On Linux with Intel C Compiler, use :
icc -O3 ci.cpp. Easy, isn't it?
Run it by giving in parameter the name of the track without the extension.
Note that it will create some intermediate outputs and a
that is a raw image of the trajectory.
There are three parts:
To drive between two waypoints, the car uses two steps:
The path is optimized by three ways :
The result is not really good. It can always drive a valid track because there is no assumption made and the user has not to input anything, but the model is too simple.
The main flaw is the way that the car goes from a waypoint to an other. In order to allow a fast optimization of the path, it may be too simple.
Optimization is done in a too simplistic way.
Moving the waypoints is not well tuned.
The car crashes at the end of Een. In fact, the end of the trajectory is not done correctly, but it works with the other tracks.
The model does not support skiding in the rally mode.
My first goal was to solve the problem without any human input (the same program is used on any track, the ones provided or any other) and quickly. In fact I wanted my program to be translated into GOTO++ before the end, the C++ being used only for prototyping.
But I faced two problems: 1) any solver asks too many memory and processor time 2) I need 64 bits integers. And GOTO++ is not fast (two time slower than Perl in fact) and its 64 bits support is only partial. Plus I used a recursive algorithm and the GOTO++ stack is not very big. Plus, GOTO++ or not, I don't know anything in pathfinding or so.
So, finally, I sticked with a bad C++ program. At least it is somewhat fast (less than two minutes to solve any track on a P4 2,4 GHz) and it doesn't need any input. Just type a.out nameofthetrack and wait for the result. Or don't wait and drive the race at hand, it will be better.
Oh yeah, in case you didn't know: tortue means turtle in french.
After submitting my entry I decided to make something more useful, so is born the beautiful track NIACity. It is on the track page. My program completes it in 18242 steps.
I'm Sidoine De Wispelaere [fr] and I'm a PhD student in physics [fr]. I do numerical simulations.