royale.zerezo.com Git - zeRace/blob - bot_checkpoint.c

   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  */
  20
  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
  28
  29 #include <complex.h>
  30 #include "bot.h"
  31
  32 typedef struct {
  33         int x;
  34         int y;
  35 } coord;
  36
  37 char dummy[99];
  38
  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 };
  60
  61 char *bot_name()
  62 {
  63         return "Checkpoint";
  64 }
  65
  66 int current_track = 0;
  67 int next_checkpoint = 0;
  68
  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;
  74
  75         /* if the track has changed */
  76         if (strcmp(db[current_track].trackname, trackname) != 0)
  77         {
  78                 current_track = -1;
  79
  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         }
  92
  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;
  96
  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);
 102
 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;
 112
 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;
 120
 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         }
 130
 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);
 142 }
 143
 144 #ifdef OPTIMIZE
 145
 146 /* if the bot is called from command line, we run the track optimizer */
 147 int main(int argc, char *argv[])
 148 {
 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;
 156
 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         }
 167
 168         /* randomize */
 169         srand(time(NULL));
 170         precision = INIT_PRECISION;
 171
 172         /* load tracklist */
 173         if (!zeRace_get_tracks(&tracklist))
 174         {
 175                 fprintf(stderr, "Unable to load tracks!\n");
 176                 exit(1);
 177         }
 178
 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);
 182
 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         }
 189
 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;
 195
 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         }
 231
 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;
 285
 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                         }
 313
 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                         }
 332
 333                         /* backup the new version */
 334                         memcpy(backup, db[tr].checkpoint, nb * 2 * sizeof(coord));
 335                         backup_msa = db[tr].max_speed_angle;
 336
 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         }
 353 }
 354
 355 #endif