Git

1 /*
2  * zeRace "checkpoint" bot + optimizer
3  * http://royale.zerezo.com/zerace/
4  * 
5  * Copyright (C) 2006  Antoine Jacquet <royale@zerezo.com>
6  * Licensed under GPL
7  *
8  * This robot uses a static database of checkpoint.
9  * It will not be able to race on an unknown track.
10  *
11  * If you want to train it for a new track, you will need to add some manual
12  * checkpoints to the list.
13  *
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.
19  */
21 #define sqr(x) ((x)*(x))
22 #define MAX_STUCK 100
23 #define LOOPS 1000
24 #define LAPS 5
25 #define INIT_PRECISION 50
26 #define TIMEOUT 19999
27 #define TOLERANCE_DISTANCE 30.0
29 #include <complex.h>
30 #include "bot.h"
32 typedef struct {
33         int x;
34         int y;
35 } coord;
37 char dummy[99];
39 struct {
40         char *trackname;
41         float max_speed_angle;
42         coord *checkpoint;
43 } db[] = {
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,
59 };
61 char *bot_name()
62 {
63         return "Checkpoint";
64 }
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)
70 {
71         int i;
72         float dx, dy, da;
73         float angle = 0, distance;
75         /* if the track has changed */
76         if (strcmp(db[current_track].trackname, trackname) != 0)
77         {
78                 current_track = -1;
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;
82                 
83                 /* we did not find the track in the database */
84                 if (current_track == -1)
85                 {
86                         /* we won't be able to drive this race ... */
87                         fprintf(stderr, "Unknown track: %s\n", trackname);
88                         exit(1);
89                 }
90                 next_checkpoint = 0;
91         }
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 */
98         if (dy > 0)
99                 angle = 3.0 * M_PI / 2 - atan(dx/dy);
100         if (dy < 0)
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) );
105         
106         /* compute the angle difference */
107         da = angle - car->angle;
108         
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;
116         
117         /* we try to go as fast as possible */
118         *ku = 1;
119         *kd = 0;
121         /* if the angle and speed are to big */
122         if (car->speed > 0)
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)
125         {
126                 /* we should brake! */
127                 *ku = 0;
128                 *kd = 1;
129         }
131         /* if we are close enought of the checkpoint, jump to the next one */
132         if (distance < TOLERANCE_DISTANCE)
133         {
134                 next_checkpoint++;
135                 if (db[current_track].checkpoint[next_checkpoint].x == -1) next_checkpoint = 0;
136         }
137         
138         /* debug */
139         if (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);
144 #ifdef OPTIMIZE
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;
150         SDL_Surface *fun;
151         int loop, lap, ctime, btime = TIMEOUT, tr, nb, i, j, precision, stuck = 0, found = 0;
152         int ku, kd, kl, kr;
153         struct _car car;
154         coord backup[99];
155         float backup_msa;
157         /* check parameters */
158         if (argc != 2)
159         {
160                 fprintf(stderr,
161                         "Usage : %s track\n"
162                         "  track:  the name of the track you want to optimize.\n"
163                         "Look at the source code for more details...\n"         
164                         ,argv[0]);
165                 exit(1);
166         }
168         /* randomize */
169         srand(time(NULL));
170         precision = INIT_PRECISION;
172         /* load tracklist */
173         if (!zeRace_get_tracks(&tracklist))
174         {
175                 fprintf(stderr, "Unable to load tracks!\n");
176                 exit(1);
177         }
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)
185         {
186                 fprintf(stderr, "Unable to load track %s\n", argv[1]);
187                 exit(1);
188         }
190         /* load the image */
191         fun = IMG_Load(tracklist->function);
192         
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)
198         {
199                 printf("trying to create some checkpoints... "); fflush(stdout);
200                 tr = 0;
201                 strcpy(db[tr].trackname, argv[1]);
202                 /* try to suggest some checkpoints */
203                 for (i = 1; i < 32; i += 1)
204                 {
205                         int x,y, xx = 0,yy = 0, n = 0;
206                         
207                         for (x = 0; x < fun->w; x += 5)
208                                 for ( y = 0; y < fun->h; y += 5)
209                                 {
210                                         Uint32 c;
211                                         Uint8 r,g,b;
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)
219                                         {
220                                                 xx += x;
221                                                 yy += y;
222                                                 n++;
223                                         }
224                                 }
225                         
226                         db[tr].checkpoint[i-1].x = xx/n;
227                         db[tr].checkpoint[i-1].y = yy/n;
228                 }
229                 printf("done\n");
230         }
232         /* while we can continue to optimize better */
233         while (precision > 0 || found)
234         {
235                 /* start again ? */
236                 if (precision == 0)
237                 {
238                         printf("starting again...\n");
239                         precision = INIT_PRECISION;
240                         found = 0;
241                 }
242                 
243                 /* check for close checkpoints */
244                 nb = 0;
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)
248                         {
249                                 nb++;
250                                 /* we remove one from the list */
251                                 for (j = i+1; db[tr].checkpoint[j].x != -1; j++)
252                                 {
253                                         db[tr].checkpoint[j].x = db[tr].checkpoint[j+1].x;
254                                         db[tr].checkpoint[j].y = db[tr].checkpoint[j+1].y;
255                                 }
256                                 db[tr].checkpoint[j].x = -1;
257                         }
258                 if (nb) printf("removing %d checkpoints...\n", nb);
259                 
260                 /* count the checkpoints */
261                 for (nb = 0; db[tr].checkpoint[nb].x != -1; nb++);
262                 
263                 /* copy the current checkpoints */
264                 memcpy(backup, db[tr].checkpoint, nb * 2 * sizeof(coord));
265                 backup_msa = db[tr].max_speed_angle;
266                 
267                 /* try with this precision */
268                 printf("trying with %d pixel precision...\n", precision);
269                 
270                 /* do X optimization races (loops) */
271                 for (loop = 0; loop < LOOPS; loop++)
272                 {
273                         /* init parameters */
274                         car.speed = 0;
275                         car.angle = tracklist->a * 2 * M_PI / 360;
276                         car.ox = car.x = tracklist->x;
277                         car.oy = car.y = tracklist->y;
278                         car.lastcheck = 0;
279                         car.w = 30;
280                         car.h = 30;
281                         ctime = 0;
282                         car.lapflag = 0;
283                         lap = 0;
284                         next_checkpoint = 0;
286                         /* do X laps */
287                         while (1)
288                         {
289                                 bot_ia(argv[1], &car, fun, &ku, &kd, &kl, &kr);
290                                 move_car(&car, (ku<<3 | kd<<2 | kl<<1 | kr), fun);
291                                 
292                                 /* if we did a full lap, count it */
293                                 if (car.lapflag == 1)
294                                 {
295                                         lap++;
296                                         /* we did all the lap, exit */
297                                         if (lap == LAPS) break;
298                                         car.lapflag = 0;
299                                 }
300                                 
301                                 /* check if we are "stuck" */
302                                 if (car.speed < 0.01) stuck++; else stuck = 0;
303                                 
304                                 /* if we missed a checkpoint or too long, exit */
305                                 if (car.lapflag != 0 || ctime > TIMEOUT || stuck > MAX_STUCK)
306                                 {
307                                         ctime = TIMEOUT;
308                                         break;
309                                 }
310                                 
311                                 ctime++;
312                         }
314                         /* check if it is the best ? */
315                         if (ctime < btime)
316                         {
317                                 btime = ctime;
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);
323                                 printf("},\n");
324                                 found = 1;
325                         }
326                         /* restore previous version */
327                         else
328                         {
329                                 memcpy(db[tr].checkpoint, backup, nb * 2 * sizeof(coord));
330                                 db[tr].max_speed_angle = backup_msa;
331                         }
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++)
340                         {
341                                 db[tr].checkpoint[i].x += rand() % (2 * precision + 1) - precision;
342                                 db[tr].checkpoint[i].y += rand() % (2 * precision + 1) - precision;
343                         }
344                 }
345                 
346                 /* restore the best version */
347                 memcpy(db[tr].checkpoint, backup, nb * 2 * sizeof(coord));
348                 db[tr].max_speed_angle = backup_msa;
349                 
350                 /* try to find better... */
351                 precision = precision/2;
352         }
355 #endif