2 * zeRace "checkpoint" bot + optimizer
3 * http://royale.zerezo.com/zerace/
5 * Copyright (C) 2006 Antoine Jacquet <royale@zerezo.com>
8 * This robot uses a static database of checkpoint.
9 * It will not be able to race on an unknown track.
11 * If you want to train it for a new track, you will need to add some manual
12 * checkpoints to the list.
14 * You can then use the optimizer to find better checkpoints.
15 * An example: ./optimize formula 5 10000 4
16 * Will optimize the track "formula" using 10000 races of 5 laps.
17 * At each loop, it will move each checkpoint of 4 pixel or less.
18 * The optimizer will output new values for checkpoints you should copy/paste.
21 #define sqr(x) ((x)*(x))
25 #define INIT_PRECISION 50
27 #define TOLERANCE_DISTANCE 30.0
41 float max_speed_angle;
44 /* dummy entry used for new tracks */ dummy, 0.5, (coord[]){ -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, -1,-1, },
45 /* 7373 */ "bio", 0.59, (coord[]){ 890,683, 502,526, 277,599, 72,530, 45,302, 298,232, 781,192, 826,185, 916,324, 970,548, -1,-1, },
46 /* 4700 */ "car", 0.40, (coord[]){ 781,664, 877,617, 883,479, 522,242, 291,237, 111,449, 149,580, 234,661, -1,-1, },
47 /* 5572 */ "city", 0.65, (coord[]){ 49,266, 122,198, 259,174, 349,183, 377,211, 453,229, 749,308, 917,487, 681,595, 546,574, 417,596, 233,571, 128,486, 45,414, -1,-1, },
48 /* 13338 */ "desert", 0.40, (coord[]){ 561,378, 382,338, 285,415, 367,522, 440,594, 377,697, 103,289, 136,154, 258,66, 366,57, 588,50, 729,126, 821,308, 897,525, 777,649, 720,495, -1,-1, },
49 /* 5792 */ "first", 0.65, (coord[]){ 500,240, 762,150, 988,418, 916,544, 712,590, 556,663, 225,646, 115,339, -1,-1, },
50 /* 6602 */ "formula", 0.60, (coord[]){ 682,577, 968,495, 964,255, 762,232, 722,421, 554,610, 215,520, 160,448, 266,252, -1,-1, },
51 /* 21470 */ "hairpins", 0.50, (coord[]){ 353,604, 182,617, 68,516, 195,501, 217,381, 159,342, 119,346, 103,207, 250,97, 334,123, 346,259, 446,309, 492,104, 588,37, 632,93, 791,140, 862,136, 971,271, 806,200, 722,262, 802,446, 838,460, 865,593, 838,697, 698,595, 637,491, 487,504, 481,470, 570,550, 549,665, -1,-1, },
52 /* 8581 */ "http", 0.58, (coord[]){ 635,88, 689,98, 796,232, 776,292, 773,364, 792,408, 809,521, 665,693, 622,710, 518,696, 476,663, 408,689, 344,461, 431,366, 338,224, 245,303, 110,216, 297,118, 404,83, 473,97, 528,47, -1,-1, },
53 /* 5854 */ "icy", 0.67, (coord[]){ 792,164, 951,255, 873,535, 710,593, 616,635, 547,667, 235,657, 116,353, 329,202, -1,-1, },
54 /* 13889 */ "kart", 1.16, (coord[]){ 132,657, 38,387, 109,171, 332,215, 472,276, 512,201, 834,108, 957,343, 274,336, 275,512, 900,560, 918,694, -1,-1, },
55 /* 9063 */ "loop", 0.61, (coord[]){ 412,720, 207,659, 68,442, 115,183, 397,132, 523,281, 855,331, 892,276, 839,106, 712,182, 651,208, 658,473, 855,542, 915,630, 719,702, 638,700, -1,-1, },
56 /* 13333 */ "simple", 0.61, (coord[]){ 362,629, 169,663, 78,608, 143,151, 396,375, 420,288, 416,206, 601,131, 652,273, 922,440, 962,541, -1,-1, },
57 /* 12926 */ "wave", 0.57, (coord[]){ 733,381, 916,512, 884,633, 732,540, 872,281, 822,132, 722,137, 647,163, 586,177, 616,173, 573,202, 475,173, 443,206, 405,189, 301,140, 287,169, 155,291, 560,593, 446,681, 334,636, 203,572, 151,525, 676,413, -1,-1, },
58 /* end entry */ NULL, 0, NULL,
66 int current_track = 0;
67 int next_checkpoint = 0;
69 void bot_ia(char *trackname, struct _car *car, SDL_Surface * fun, int *ku, int *kd, int *kl, int *kr)
73 float angle = 0, distance;
75 /* if the track has changed */
76 if (strcmp(db[current_track].trackname, trackname) != 0)
80 /* find the good track in the db */
81 for (i = 0; db[i].trackname != NULL; i++) if (strcmp(db[i].trackname, trackname) == 0) current_track = i;
83 /* we did not find the track in the database */
84 if (current_track == -1)
86 /* we won't be able to drive this race ... */
87 fprintf(stderr, "Unknown track: %s\n", trackname);
93 /* compute delta x/y */
94 dx = db[current_track].checkpoint[next_checkpoint].x - car->x;
95 dy = db[current_track].checkpoint[next_checkpoint].y - car->y;
97 /* compute the angle of the next checkpoint */
99 angle = 3.0 * M_PI / 2 - atan(dx/dy);
101 angle = 1.0 * M_PI / 2 - atan(dx/dy);
103 /* compute the distance of the next checkpoint */
104 distance = sqrt( sqr(dx) + sqr(dy) );
106 /* compute the angle difference */
107 da = angle - car->angle;
109 /* keep it between -pi and pi */
110 while (da < -M_PI) da += 2 * M_PI;
111 while (da > +M_PI) da -= 2 * M_PI;
113 /* compute steering */
114 if (da < 0) *kl = 1; else *kl = 0;
115 if (da > 0) *kr = 1; else *kr = 0;
117 /* we try to go as fast as possible */
121 /* if the angle and speed are to big */
123 /* formula should be based on speed, angle diff... and distance? */
124 if (sqrt(1 + car->speed) * sqr(da) > db[current_track].max_speed_angle)
126 /* we should brake! */
131 /* if we are close enought of the checkpoint, jump to the next one */
132 if (distance < TOLERANCE_DISTANCE)
135 if (db[current_track].checkpoint[next_checkpoint].x == -1) next_checkpoint = 0;
140 printf("debug: x=%.2f y=%.2f a=%.0f s=%.2f | kl=%d kr=%d ku=%d kd=%d | c=%d a=%.0f d=%.2f dx/dy=%.0f/%.0f da=%.2f\n",
141 car->x, car->y, 180/M_PI*car->angle, car->speed, *kl, *kr, *ku, *kd, next_checkpoint, 180/M_PI*angle, distance, dx, dy, da);
146 /* if the bot is called from command line, we run the track optimizer */
147 int main(int argc, char *argv[])
149 struct _tracklist *tracklist, *loopcheck;
151 int loop, lap, ctime, btime = TIMEOUT, tr, nb, i, j, precision, stuck = 0, found = 0;
157 /* check parameters */
162 " track: the name of the track you want to optimize.\n"
163 "Look at the source code for more details...\n"
170 precision = INIT_PRECISION;
173 if (!zeRace_get_tracks(&tracklist))
175 fprintf(stderr, "Unable to load tracks!\n");
179 /* pick up the good track */
180 loopcheck = tracklist;
181 do if (strcmp(tracklist->name, argv[1]) == 0) break; else tracklist = tracklist->next; while (tracklist != loopcheck);
183 /* if it is not found, display an error message */
184 if (strcmp(tracklist->name, argv[1]) != 0)
186 fprintf(stderr, "Unable to load track %s\n", argv[1]);
191 fun = IMG_Load(tracklist->function);
193 /* find the good track in the db */
194 for (tr = 0; db[tr].trackname != NULL; tr++) if (strcmp(db[tr].trackname, argv[1]) == 0) break;
196 /* we did not find the track in the database */
197 if (db[tr].trackname == NULL)
199 printf("trying to create some checkpoints... "); fflush(stdout);
201 strcpy(db[tr].trackname, argv[1]);
202 /* try to suggest some checkpoints */
203 for (i = 1; i < 32; i += 1)
205 int x,y, xx = 0,yy = 0, n = 0;
207 for (x = 0; x < fun->w; x += 5)
208 for ( y = 0; y < fun->h; y += 5)
212 /* get the pixel color under the center of car in the function map */
213 c = getpixel(fun, x, y);
214 /* red layer (checkpoints) */
215 /* green layer (road quality) */
216 /* blue layer (grip) */
217 SDL_GetRGB(c, fun->format, &r, &g, &b);
218 if (g == 255 && r/8 == i)
226 db[tr].checkpoint[i-1].x = xx/n;
227 db[tr].checkpoint[i-1].y = yy/n;
232 /* while we can continue to optimize better */
233 while (precision > 0 || found)
238 printf("starting again...\n");
239 precision = INIT_PRECISION;
243 /* check for close checkpoints */
245 for (i = 0; db[tr].checkpoint[i+1].x != -1; i++)
246 /* if the checkpoints are close */
247 if (sqrt( sqr(db[tr].checkpoint[i].x - db[tr].checkpoint[i+1].x) + sqr(db[tr].checkpoint[i].y - db[tr].checkpoint[i+1].y)) < TOLERANCE_DISTANCE)
250 /* we remove one from the list */
251 for (j = i+1; db[tr].checkpoint[j].x != -1; j++)
253 db[tr].checkpoint[j].x = db[tr].checkpoint[j+1].x;
254 db[tr].checkpoint[j].y = db[tr].checkpoint[j+1].y;
256 db[tr].checkpoint[j].x = -1;
258 if (nb) printf("removing %d checkpoints...\n", nb);
260 /* count the checkpoints */
261 for (nb = 0; db[tr].checkpoint[nb].x != -1; nb++);
263 /* copy the current checkpoints */
264 memcpy(backup, db[tr].checkpoint, nb * 2 * sizeof(coord));
265 backup_msa = db[tr].max_speed_angle;
267 /* try with this precision */
268 printf("trying with %d pixel precision...\n", precision);
270 /* do X optimization races (loops) */
271 for (loop = 0; loop < LOOPS; loop++)
273 /* init parameters */
275 car.angle = tracklist->a * 2 * M_PI / 360;
276 car.ox = car.x = tracklist->x;
277 car.oy = car.y = tracklist->y;
289 bot_ia(argv[1], &car, fun, &ku, &kd, &kl, &kr);
290 move_car(&car, (ku<<3 | kd<<2 | kl<<1 | kr), fun);
292 /* if we did a full lap, count it */
293 if (car.lapflag == 1)
296 /* we did all the lap, exit */
297 if (lap == LAPS) break;
301 /* check if we are "stuck" */
302 if (car.speed < 0.01) stuck++; else stuck = 0;
304 /* if we missed a checkpoint or too long, exit */
305 if (car.lapflag != 0 || ctime > TIMEOUT || stuck > MAX_STUCK)
314 /* check if it is the best ? */
318 printf("new record: %d!!!\n", btime);
319 /* print the best table found */
320 printf("/* %d */ \"%s\", %.2f, (coord[]){ ", btime, argv[1], db[current_track].max_speed_angle);
321 for (i = 0; i <= nb; i++)
322 printf("%d,%d, ", db[tr].checkpoint[i].x, db[tr].checkpoint[i].y);
326 /* restore previous version */
329 memcpy(db[tr].checkpoint, backup, nb * 2 * sizeof(coord));
330 db[tr].max_speed_angle = backup_msa;
333 /* backup the new version */
334 memcpy(backup, db[tr].checkpoint, nb * 2 * sizeof(coord));
335 backup_msa = db[tr].max_speed_angle;
337 /* do some change to the checkpoint table */
338 db[tr].max_speed_angle += ( rand() % (2 * precision + 1) - precision ) / 100.0;
339 for (i = 0; i < nb; i++)
341 db[tr].checkpoint[i].x += rand() % (2 * precision + 1) - precision;
342 db[tr].checkpoint[i].y += rand() % (2 * precision + 1) - precision;
346 /* restore the best version */
347 memcpy(db[tr].checkpoint, backup, nb * 2 * sizeof(coord));
348 db[tr].max_speed_angle = backup_msa;
350 /* try to find better... */
351 precision = precision/2;