Check out my Home Page
In the animated gifs, the car is the yellow square and the line indicates the velocity. The direction of the line tells you the direction of the car. The length of the line is proportional to its speed.
The memory of ICFP 2002 still haunts us. We had a good enough working program but goofed it all up just a few minutes before submitting it. It still hurts.
This time we hoped we'd do better.
I and Atul woke up at 5:30 in the morning, Saturday when the task was to be put up. Mugdha (my fiancee!), Atul and I are from Pune, India, and work at VERITAS Software. Shirish stays in the U.S. We read the task description and could make no sense out of opening the track files in notepad. So I wrote a quick toppm.exe to convert all the track files to ppm format so that we could view it using Irfan View . I mailed it out to Atul and Shirish, and we all got thinking of what next to do. I and Atul got ready to get to office and work on this.
We wanted to write a simulator. But none of has had done any GUI/graphics programming. So while we were thinking about how to write a program that will automatically output the trace commands, we were also frantically hunting for something that could tell us how to bring up a window and put some graphics in it. After about a hour and a half we found sample code from Microsoft's MSDN (called gdidemo.exe, the name stuck.) that displayed boxes and bouncing balls.
I modified that to display our tracks and also enable us to play the game interactively. As keys were pressed to drive the car around a trace file was generated in the background. The current car state was being displayed in the right margin. The car was a circle and a line. The direction of the line told us the direction of the car, and the length of the line was proportional to the speed.
Atul provided me the code for the car model that gave me the next state of the car when I feed it the current state.
We also got thinking about how to build an automated driver. The approach we came up with was that the driver would be given a set of "control points" along the track. The driver should then try to stay close to the path that connects these points and also try and be as fast as possible at each step. To decide what command to output, we created a simple table which tells us what command to output depending on two parameters.
Yes, the model is too simplistic, but well we wanted to get started with something!
Here's our table that decides what command to emit.
velocity !low !medium ! high -------. ! ! ! angle . ! ! ! deviation.! ! ! ------------------------------------ low ! a. ! a. ! . ----------------------------------- medium ! at. ! at. ! t. ----------------------------------- high ! at. ! t. ! b.
The cardrive.exe mentioned above needs "control points" to guide the automatic driver. So I was roped in to add a Click Mode to gdidemo.exe. With this, you could click anywhere on the track and a file of those co-ordinates would be created. This file served as an input for cardrive.exe. The automated driver would try and stick to the path determined by these control points.
Mugdha came along in the evening and added her charm to the tired atmosphere. She patiently clicked on the tracks using my gdidemo.exe and created the control points.
cardrive.exe wouldn't work well. We changed it so that instead of trying to be at the "tangent along the smooth curve" joining the control points, the car would just head towards the next control point (yeah it gets simpler and boring). Also we tried running it on the tracks tweaking the following values:
Now that we had an automated driver we wanted to see him drive. So we added a third mode - the Replay Mode to gdidemo.exe. With this you could replay the trace and watch cardrive.exe drive his car around (not a very pretty sight, at least in the beginning before we fixed it).
It was really boring and slow trying to manually driving the car using gdidemo.exe. Also the replay took about ten minutes for even moderately long tracks. So we added the feature of being dynamically change the time interval between renderings. This feature was a big relief.
We didn't even know how to put up text boxes or take string inputs, so had to work on inputs on the Character Event to give all these features. High time I learn some cool and quick scripting language!
Spent some time getting right solutions for some tracks by playing around with our automated driver, cardrive.exe. It didn't do too bad.
Shirish was trying to drive along track#9 and was crashing often. He asked for two features in gdidemo.exe and I got working on those.
He wanted some way to go back to any time in the past and continue driving from there. This way you are not afraid of crashing any more. Not only that, you can go back and try again and again until you get what you think is the best drive along some patch in the track. Our first dirty windows program was turning out to be real useful!
The other feature was to be able to dump a trace file at any intermediate stage while driving. This way we could run a partial trace file on the ICFP simulator to confirm that it works. Also we could load any trace file, jump to any time, and continue driving.
The problem with cardrive was that you could not give too high a velocity threshold because it would crash on sharp turns. But if you gave a small threshold, it would go slow even on those straight patches. Atul modified it so that given some command line parameters, he'd bump up the high velocity threshold when the distance between the successive control points was high (usually true in the straighter patches). So now the velocity threshold changed dynamically along the track.
The remaining hours were spent in manually driving the car around and trying to get better values with cardrive.exe.
Then we had solutions that we could submit.
PHEW!
Atul was annoyed that instead of trying to drive more and get better times, I spent some time writing code that given a trace file and a timestep, created multiple ppms. I used this to convert the ppms to gifs and supplying that to a program that created an animated gif out of these multiple gif frames. I was quite successful at warding off Atul's attacks and completing this.
These hours were fun! Shirish said "the game is quite addictive!". (The guy spent an hour and half in the train playing this game. I can imagine the co-passengers wondering what is this strange guy upto, and why is he concentrating so hard trying to move a line aloing a track sitting in a train!).
We wish we could have somebody in the team who'd just sit and play and try get better times. Also we thought we should have integrated cardrive.exe and gdidemo.exe so we could have some portions of the track taken care of by the automated driver, and some portions by the human.
Can't wait to see the algorithms and approaches other folks used.
