Team Tortue

Here is my entry for the ICFP programming contest 2003. Not a good one but at least it races all the tracks.

The tracks.

The program

You can download it.

Description

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. For example: a.out 1_Simple.

Note that it will create some intermediate outputs and a *_traj.raw that is a raw image of the trajectory.

Method

There are three parts:

• Compute how many pixels separate each pixel from the goal. It uses a simple recursive algorithm. To speed up the process, the algorithm is computed on a recursively scaled down map.
• Create a simple path made of straight lines that can have 8 directions. Each edge is a waypoint. It is garanteed that the car can follow this path by stopping at each waypoint then turning until it faces the next waypoint.
• Optimize the path.

To drive between two waypoints, the car uses two steps:

• In the first step it turns left or right until it faces the next waypoint. It tries to accelerate as much as possible or it brakes if necessary.
• In the second step it accelerates every step until it must brake. If necessary, the car rectify its trajectory by turning left or right.

The path is optimized by three ways :

• Removing a waypoint.
• Moving a waypoint.
• Raising the speed at which the car must reach a waypoint.

Result

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.

Known bugs

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.

The Marvellous History of Tortue

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.

My track

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.

About me

I'm Sidoine De Wispelaere [fr] and I'm a PhD student in physics [fr]. I do numerical simulations.