X-Git-Url: http://royale.zerezo.com/git/?p=zeRace;a=blobdiff_plain;f=bot_checkpoint.c;fp=bot_checkpoint.c;h=1d7a5a6748f3ce64e331bcd521ba7bfa1b062aea;hp=0000000000000000000000000000000000000000;hb=631d9aa41453014857220b88a07845bc661b371a;hpb=a649266e00696290ecf09f15c9dfa09f1cd35244 diff --git a/bot_checkpoint.c b/bot_checkpoint.c new file mode 100644 index 0000000..1d7a5a6 --- /dev/null +++ b/bot_checkpoint.c @@ -0,0 +1,355 @@ +/* + * zeRace "checkpoint" bot + optimizer + * http://royale.zerezo.com/zerace/ + * + * Copyright (C) 2006 Antoine Jacquet + * Licensed under GPL + * + * This robot uses a static database of checkpoint. + * It will not be able to race on an unknown track. + * + * If you want to train it for a new track, you will need to add some manual + * checkpoints to the list. + * + * You can then use the optimizer to find better checkpoints. + * An example: ./optimize formula 5 10000 4 + * Will optimize the track "formula" using 10000 races of 5 laps. + * At each loop, it will move each checkpoint of 4 pixel or less. + * The optimizer will output new values for checkpoints you should copy/paste. + */ + +#define sqr(x) ((x)*(x)) +#define MAX_STUCK 100 +#define LOOPS 1000 +#define LAPS 5 +#define INIT_PRECISION 50 +#define TIMEOUT 19999 +#define TOLERANCE_DISTANCE 30.0 + +#include +#include "bot.h" + +typedef struct { + int x; + int y; +} coord; + +char dummy[99]; + +struct { + char *trackname; + float max_speed_angle; + coord *checkpoint; +} db[] = { + /* 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, }, + /* 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, }, + /* 4700 */ "car", 0.40, (coord[]){ 781,664, 877,617, 883,479, 522,242, 291,237, 111,449, 149,580, 234,661, -1,-1, }, + /* 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, }, + /* 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, }, + /* 5792 */ "first", 0.65, (coord[]){ 500,240, 762,150, 988,418, 916,544, 712,590, 556,663, 225,646, 115,339, -1,-1, }, + /* 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, }, + /* 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, }, + /* 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, }, + /* 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, }, + /* 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, }, + /* 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, }, + /* 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, }, + /* 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, }, + /* end entry */ NULL, 0, NULL, +}; + +char *bot_name() +{ + return "Checkpoint"; +} + +int current_track = 0; +int next_checkpoint = 0; + +void bot_ia(char *trackname, struct _car *car, SDL_Surface * fun, int *ku, int *kd, int *kl, int *kr) +{ + int i; + float dx, dy, da; + float angle = 0, distance; + + /* if the track has changed */ + if (strcmp(db[current_track].trackname, trackname) != 0) + { + current_track = -1; + + /* find the good track in the db */ + for (i = 0; db[i].trackname != NULL; i++) if (strcmp(db[i].trackname, trackname) == 0) current_track = i; + + /* we did not find the track in the database */ + if (current_track == -1) + { + /* we won't be able to drive this race ... */ + fprintf(stderr, "Unknown track: %s\n", trackname); + exit(1); + } + next_checkpoint = 0; + } + + /* compute delta x/y */ + dx = db[current_track].checkpoint[next_checkpoint].x - car->x; + dy = db[current_track].checkpoint[next_checkpoint].y - car->y; + + /* compute the angle of the next checkpoint */ + if (dy > 0) + angle = 3.0 * M_PI / 2 - atan(dx/dy); + if (dy < 0) + angle = 1.0 * M_PI / 2 - atan(dx/dy); + + /* compute the distance of the next checkpoint */ + distance = sqrt( sqr(dx) + sqr(dy) ); + + /* compute the angle difference */ + da = angle - car->angle; + + /* keep it between -pi and pi */ + while (da < -M_PI) da += 2 * M_PI; + while (da > +M_PI) da -= 2 * M_PI; + + /* compute steering */ + if (da < 0) *kl = 1; else *kl = 0; + if (da > 0) *kr = 1; else *kr = 0; + + /* we try to go as fast as possible */ + *ku = 1; + *kd = 0; + + /* if the angle and speed are to big */ + if (car->speed > 0) + /* formula should be based on speed, angle diff... and distance? */ + if (sqrt(1 + car->speed) * sqr(da) > db[current_track].max_speed_angle) + { + /* we should brake! */ + *ku = 0; + *kd = 1; + } + + /* if we are close enought of the checkpoint, jump to the next one */ + if (distance < TOLERANCE_DISTANCE) + { + next_checkpoint++; + if (db[current_track].checkpoint[next_checkpoint].x == -1) next_checkpoint = 0; + } + + /* debug */ + if (0) + 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", + 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); +} + +#ifdef OPTIMIZE + +/* if the bot is called from command line, we run the track optimizer */ +int main(int argc, char *argv[]) +{ + struct _tracklist *tracklist, *loopcheck; + SDL_Surface *fun; + int loop, lap, ctime, btime = TIMEOUT, tr, nb, i, j, precision, stuck = 0, found = 0; + int ku, kd, kl, kr; + struct _car car; + coord backup[99]; + float backup_msa; + + /* check parameters */ + if (argc != 2) + { + fprintf(stderr, + "Usage : %s track\n" + " track: the name of the track you want to optimize.\n" + "Look at the source code for more details...\n" + ,argv[0]); + exit(1); + } + + /* randomize */ + srand(time(NULL)); + precision = INIT_PRECISION; + + /* load tracklist */ + if (!zeRace_get_tracks(&tracklist)) + { + fprintf(stderr, "Unable to load tracks!\n"); + exit(1); + } + + /* pick up the good track */ + loopcheck = tracklist; + do if (strcmp(tracklist->name, argv[1]) == 0) break; else tracklist = tracklist->next; while (tracklist != loopcheck); + + /* if it is not found, display an error message */ + if (strcmp(tracklist->name, argv[1]) != 0) + { + fprintf(stderr, "Unable to load track %s\n", argv[1]); + exit(1); + } + + /* load the image */ + fun = IMG_Load(tracklist->function); + + /* find the good track in the db */ + for (tr = 0; db[tr].trackname != NULL; tr++) if (strcmp(db[tr].trackname, argv[1]) == 0) break; + + /* we did not find the track in the database */ + if (db[tr].trackname == NULL) + { + printf("trying to create some checkpoints... "); fflush(stdout); + tr = 0; + strcpy(db[tr].trackname, argv[1]); + /* try to suggest some checkpoints */ + for (i = 1; i < 32; i += 1) + { + int x,y, xx = 0,yy = 0, n = 0; + + for (x = 0; x < fun->w; x += 5) + for ( y = 0; y < fun->h; y += 5) + { + Uint32 c; + Uint8 r,g,b; + /* get the pixel color under the center of car in the function map */ + c = getpixel(fun, x, y); + /* red layer (checkpoints) */ + /* green layer (road quality) */ + /* blue layer (grip) */ + SDL_GetRGB(c, fun->format, &r, &g, &b); + if (g == 255 && r/8 == i) + { + xx += x; + yy += y; + n++; + } + } + + db[tr].checkpoint[i-1].x = xx/n; + db[tr].checkpoint[i-1].y = yy/n; + } + printf("done\n"); + } + + /* while we can continue to optimize better */ + while (precision > 0 || found) + { + /* start again ? */ + if (precision == 0) + { + printf("starting again...\n"); + precision = INIT_PRECISION; + found = 0; + } + + /* check for close checkpoints */ + nb = 0; + for (i = 0; db[tr].checkpoint[i+1].x != -1; i++) + /* if the checkpoints are close */ + 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) + { + nb++; + /* we remove one from the list */ + for (j = i+1; db[tr].checkpoint[j].x != -1; j++) + { + db[tr].checkpoint[j].x = db[tr].checkpoint[j+1].x; + db[tr].checkpoint[j].y = db[tr].checkpoint[j+1].y; + } + db[tr].checkpoint[j].x = -1; + } + if (nb) printf("removing %d checkpoints...\n", nb); + + /* count the checkpoints */ + for (nb = 0; db[tr].checkpoint[nb].x != -1; nb++); + + /* copy the current checkpoints */ + memcpy(backup, db[tr].checkpoint, nb * 2 * sizeof(coord)); + backup_msa = db[tr].max_speed_angle; + + /* try with this precision */ + printf("trying with %d pixel precision...\n", precision); + + /* do X optimization races (loops) */ + for (loop = 0; loop < LOOPS; loop++) + { + /* init parameters */ + car.speed = 0; + car.angle = tracklist->a * 2 * M_PI / 360; + car.ox = car.x = tracklist->x; + car.oy = car.y = tracklist->y; + car.lastcheck = 0; + car.w = 30; + car.h = 30; + ctime = 0; + car.lapflag = 0; + lap = 0; + next_checkpoint = 0; + + /* do X laps */ + while (1) + { + bot_ia(argv[1], &car, fun, &ku, &kd, &kl, &kr); + move_car(&car, (ku<<3 | kd<<2 | kl<<1 | kr), fun); + + /* if we did a full lap, count it */ + if (car.lapflag == 1) + { + lap++; + /* we did all the lap, exit */ + if (lap == LAPS) break; + car.lapflag = 0; + } + + /* check if we are "stuck" */ + if (car.speed < 0.01) stuck++; else stuck = 0; + + /* if we missed a checkpoint or too long, exit */ + if (car.lapflag != 0 || ctime > TIMEOUT || stuck > MAX_STUCK) + { + ctime = TIMEOUT; + break; + } + + ctime++; + } + + /* check if it is the best ? */ + if (ctime < btime) + { + btime = ctime; + printf("new record: %d!!!\n", btime); + /* print the best table found */ + printf("/* %d */ \"%s\", %.2f, (coord[]){ ", btime, argv[1], db[current_track].max_speed_angle); + for (i = 0; i <= nb; i++) + printf("%d,%d, ", db[tr].checkpoint[i].x, db[tr].checkpoint[i].y); + printf("},\n"); + found = 1; + } + /* restore previous version */ + else + { + memcpy(db[tr].checkpoint, backup, nb * 2 * sizeof(coord)); + db[tr].max_speed_angle = backup_msa; + } + + /* backup the new version */ + memcpy(backup, db[tr].checkpoint, nb * 2 * sizeof(coord)); + backup_msa = db[tr].max_speed_angle; + + /* do some change to the checkpoint table */ + db[tr].max_speed_angle += ( rand() % (2 * precision + 1) - precision ) / 100.0; + for (i = 0; i < nb; i++) + { + db[tr].checkpoint[i].x += rand() % (2 * precision + 1) - precision; + db[tr].checkpoint[i].y += rand() % (2 * precision + 1) - precision; + } + } + + /* restore the best version */ + memcpy(db[tr].checkpoint, backup, nb * 2 * sizeof(coord)); + db[tr].max_speed_angle = backup_msa; + + /* try to find better... */ + precision = precision/2; + } +} + +#endif