src/ai.c

   1 #include "rune.h"
   2 #include "mana.h"
   3 #include "game.h"
   4 #include "ai.h"
   5
   6 #include "libs/binaryheap/binhl.h"
   7
   8 /* Define this to get lots of _printf's */
   9 //#define DEBUG_UNIT_AI
  10
  11 #ifdef DEBUG_UNIT_AI
  12 #define _printf(...) fprintf (stdout, __VA_ARGS__)
  13 #else
  14 #define _printf(...) { }
  15 #endif
  16
  17
  18 int map_cost(unit_t *u, int x, int y, int dx, int dy);
  19
  20 #define GRAPHSIZE (LEVEL_W * LEVEL_H)
  21 #define DJ_INFINITY (GRAPHSIZE * GRAPHSIZE)
  22 #define LEVEL_POS(X,Y) ((Y) * LEVEL_W + (X))
  23
  24 typedef int levelpos_t;
  25
  26 int get_closest(const long *cost, levelpos_t src, int *xx, int *xy) {
  27         int i, j;
  28
  29         long min_cost = DJ_INFINITY;
  30         int min_pos = -1;
  31
  32         long test_cost;
  33         int test_pos = -1;
  34
  35         int sy = src / level_w;
  36         int sx = src % level_w;
  37
  38         for (j = -1; j < 2; j++) {
  39                 if (sy + j < 0 || sy + j >= level_h - 1) continue;
  40                 for (i = -1; i < 2; i++) {
  41                         if (i == 0 && j == 0) continue;
  42                         if (sx + i < 0 || sx + i >= level_w - 1) continue;
  43
  44                         test_pos = LEVEL_POS(sx + i, sy + j);
  45                         test_cost = cost[test_pos] + rand() % 10;
  46                         if (test_cost < min_cost) {
  47                                 min_cost = test_cost;
  48                                 min_pos = test_pos;
  49                         }
  50
  51                 }
  52         }
  53
  54         if (min_pos != -1) {
  55                 *xy = min_pos / level_w;
  56                 *xx = min_pos % level_w;
  57         }
  58
  59         return min_pos;
  60 }
  61
  62 int build_path(const int *prev, int *next, int n, levelpos_t src, levelpos_t dest, int *nn) {
  63         int i = 0;
  64         while (1) {
  65                 i++;
  66                 if (dest == -1) return -1;
  67                 next[n - i] = dest;
  68                 if (prev[dest] == src) {
  69                         break;
  70                 }
  71                 dest = prev[dest];
  72         }
  73         *nn = i;
  74         return n - i;
  75 }
  76
  77 int get_path(const int *prev, levelpos_t src, levelpos_t dest, int *xx, int *xy) {
  78 #if 0
  79         if (dest == -1) return -1;
  80         if (prev[dest] == src)
  81         {
  82                 int y = dest / level_w;
  83                 int x = dest - (y * level_w);
  84                 *xx = x;
  85                 *xy = y;
  86                 return 0;
  87         }
  88         return get_path(prev, src, prev[dest], xx, xy);
  89 #else
  90         while (1) {
  91                 if (dest == -1) return -1;
  92                 if (prev[dest] == src) {
  93                         break;
  94                 }
  95                 dest = prev[dest];
  96         }
  97         *xy = (dest / level_w);
  98         *xx = (dest % level_w);
  99         return 0;
 100 #endif
 101 }
 102
 103 #ifdef ALLOW_DIAGONALS
 104         #define dir_turn_max 8
 105 #else
 106         #define dir_turn_max 4
 107 #endif
 108 static char dir_turn_x[9] = { -1, 0, 1, 0, -1, 1, 1,-1, 0 };
 109 static char dir_turn_y[9] = {  0,-1, 0, 1, -1, 1,-1, 1, 0 };
 110 #if 0
 111 static int offset_turn[9] = { 0 };
 112 #endif
 113 void dijkstra_fast(unit_t *u, long *d, int *prev, levelpos_t s, int pitch, int lines) {
 114
 115         binh_list open_list = { 0 };
 116
 117         int intops=0;
 118
 119         int i, n, mini;
 120         int x, y, dx, dy;
 121
 122         long dist;
 123
 124         int visited[GRAPHSIZE];
 125         int max_nodes = (pitch * lines);
 126         long infinity = max_nodes * max_nodes;
 127
 128         int max_in = 0;
 129         int revis = 0;
 130
 131         if (max_nodes > GRAPHSIZE) return;
 132 //printf("Max nodes:%d\n", max_nodes);
 133 #if 0
 134         /* Pre-calculate offsets */
 135         for (i = 0; i < dir_turn_max; i++) {
 136                 offset_turn[i] = dir_turn_y[i] * lines + dir_turn_x[i];
 137         }
 138 #endif
 139         for (i = 0; i < max_nodes; i++) {
 140                 d[i] = infinity;
 141                 prev[i] = -1; /* no path has yet been found to i */
 142                 visited[i] = 0; /* the i-th element has not yet been visited */
 143         }
 144         d[s] = 0;
 145
 146         /* Put ALL the nodes into open list */
 147         //for (i = 0; i < max_nodes; i++) {
 148                 //binhl_push(&open_list, i, d[i]);
 149         //}
 150
 151         binhl_push(&open_list, s, 0);
 152
 153         while (open_list.len) {
 154
 155                 mini = binhl_pop(&open_list);
 156
 157                 /* Revisit protection. Revisits happen very rarely
 158                  * and can be remove completeley with some care.
 159                  * This check itself is pretty costly */
 160                 if (visited[mini]) { revis ++; continue; }
 161                 visited[mini] ++;
 162
 163                 /* We shall devise a better method of node search
 164                  * to remove this bit of math: */
 165                 y = mini / pitch;               /* Get coords from id */
 166                 x = mini % pitch;               /* Yuck! */
 167
 168                 for (n = 0; n < dir_turn_max; n++) {
 169 #if 1
 170                         /* All for the sake of this out of bounds searcher */
 171                         if ((dy = y + dir_turn_y[n]) < 0 ||
 172                                 (dx = x + dir_turn_x[n]) < 0 ||
 173                                 dx > pitch-1 || dy > lines-1) continue;
 174
 175                         i = dy * pitch + dx; /* Get id from coords! :( */
 176 #else
 177                         i = mini + offset_turn[n];
 178                         if (i < 0 || i >= pitch * lines - 1) continue;
 179 #endif
 180                         intops++;
 181
 182                         /* This function get called only once per dx, dy,
 183                          * the only overhead is the call itself */
 184                         if ((dist = map_cost(u, x, y, dx, dy))) // or map_cost[mini][i]
 185                                 if (d[mini] + dist < d[i]) {
 186                                         d[i] = d[mini] + dist;
 187                                         prev[i] = mini;
 188                                         //printf("Best path from %d to %d\n", i,mini);
 189                                         if (!visited[i]) /* Again, is this check useless ? */
 190                                                 binhl_push(&open_list, i, d[i]);
 191
 192                     if (open_list.len > max_in) max_in = open_list.len ;
 193                                 }
 194                 }
 195         }
 196         //printf("IN %d cycles, MAX IN LIS: %d, REVISITS: %d\n", intops, max_in, revis);
 197 }
 198
 199
 200 int find_flag(long *cost, faction_t *faction, int type, long *min, int *id) {
 201         int i, j;
 202
 203         int test_pos;
 204         long test_cost;
 205
 206         int pos = -1;
 207         long min_cost = DJ_INFINITY;
 208         int mini = -1;
 209
 210         for (i = 0; i < faction->num_flags; i++) {
 211                 flag_t *f = &faction->flags[i];
 212
 213                 if (f->type == type) {
 214                         test_pos = LEVEL_POS(f->x, f->y);
 215                         test_cost = cost[test_pos] / 2;
 216                         if (test_cost < min_cost) {
 217                                 min_cost = test_cost;
 218                                 mini = i;
 219                         }
 220                 }
 221         }
 222         if (mini != -1) {
 223             /* Pick closest corner */
 224                 flag_t *f = &faction->flags[mini];
 225                 pos = LEVEL_POS(f->x, f->y);
 226
 227                 for (j = 0; j < f->h; j++) {
 228                         //if (j >= 0 && j < h->h) continue;
 229                         for (i = 0; i < f->w; i++) {
 230                                 //if (i >= 0 && i < h->w) continue;
 231                                 test_pos = LEVEL_POS(f->x + i, f->y + j);
 232                                 test_cost = cost[test_pos];
 233                                 if (test_cost < min_cost) {
 234                                         min_cost = test_cost;
 235                                         pos = test_pos;
 236                                 }
 237                         }
 238                 }
 239         }
 240         *min = min_cost;
 241         *id = mini;
 242         return pos;
 243 }
 244
 245 int find_entity(long *cost, int type, long *min, int s, int *id) {
 246         int pos = -1;
 247         int min_cost = DJ_INFINITY;
 248         int mini = -1;
 249         int i;
 250         for (i = 0; i < num_units; i++) {
 251                 unit_t *u = &units[i];
 252                 unit_p *p = &bunits[u->tile];
 253                 if (u->visiting) continue;
 254                 if (u->mode == ANIM_DEATH) continue;
 255                 if (u->faction == type) {
 256                         int hp = LEVEL_POS(u->x, u->y - (p->h-1));
 257                         long c = cost[hp];
 258                         if (c < min_cost) {
 259                                 min_cost = c;
 260                                 mini = i;
 261                         }
 262                 }
 263         }
 264         if (mini != -1) {
 265             /* Pick closest corner */
 266                 unit_t *u = &units[mini];
 267                 unit_p *p = &bunits[u->tile];
 268                 pos = LEVEL_POS(u->x, u->y - (p->h-1));
 269                 _printf("Hunting for unit %d\n", mini);
 270                 int j;
 271                 for (j = 0; j < p->h; j++) {
 272                         //if (j >= 0 && j < h->h) continue;
 273                         for (i = 0; i < p->w; i++) {
 274                                 //if (i >= 0 && i < h->w) continue;
 275                                 int hp = LEVEL_POS(u->x + i, u->y - (p->h-1) + j);
 276                                 long c = cost[hp];
 277                                 if (c < min_cost) {
 278                                         min_cost = c;
 279                                         pos = hp;
 280                                                 //if (pos == s) return -1;
 281                                 }
 282                         }
 283                 }
 284         }
 285         *min = min_cost;
 286         *id = mini;
 287         //printf("Found : %d, min_cost: %d\n", pos, min_cost);
 288         return pos;
 289 }
 290
 291 int find_place(long *cost, int type, long *min, int s, int *id) {
 292         int pos = -1;
 293         int min_cost = DJ_INFINITY;
 294         int mini = -1;
 295         int i;
 296         for (i = 0; i < num_houses; i++) {
 297                 house_t *h = &houses[i];
 298                 if (h->tile == type || h->built == 0) {
 299                         int hp = LEVEL_POS(h->x, h->y);
 300                         long c = cost[hp];
 301                         if (c < min_cost) {
 302                                 min_cost = c;
 303                                 mini = i;
 304                         }
 305                 }
 306         }
 307         if (mini != -1) {
 308             /* Pick closest corner */
 309                 house_t *h = &houses[mini];
 310                 pos = LEVEL_POS(h->x, h->y);
 311                 int j;
 312                 for (j = 0; j < h->h; j++) {
 313                         //if (j >= 0 && j < h->h) continue;
 314                         for (i = 0; i < h->w; i++) {
 315                                 //if (i >= 0 && i < h->w) continue;
 316                                 int hp = LEVEL_POS(h->x + i, h->y + j);
 317                                 long c = cost[hp];
 318                                 if (c < min_cost) {
 319                                         min_cost = c;
 320                                         pos = hp;
 321                                                 //if (pos == s) return -1;
 322                                 }
 323                         }
 324                 }
 325         }
 326         *min = min_cost;
 327         *id = mini;
 328         //printf("Found : %d, min_cost: %d\n", pos, min_cost);
 329         return pos;
 330 }
 331
 332 void unit_pick_destination(int i) {
 333         unit_t *u = &units[i];
 334
 335         long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */
 336         int prev[GRAPHSIZE]; /* prev[i] is the node that comes right before i in the shortest path from the source to i*/
 337         int next[GRAPHSIZE];
 338
 339         int unit_pos = LEVEL_POS(u->x, u->y);
 340         int target_pos;
 341         int target_x, target_y;
 342
 343 #ifdef DEBUG_PATHFIND
 344 #define THE_D u->d
 345 #define THE_PREV u->prev
 346 #else
 347 #define THE_D d
 348 #define THE_PREV prev
 349 #endif
 350
 351         /* Now calculate all path costs */
 352         dijkstra_fast(u, THE_D, THE_PREV, unit_pos, level_w, level_h);
 353
 354         int id = -1;
 355
 356         long target_cost = 0;
 357
 358         target_pos = -1; /* for safety */
 359
 360         if (u->strategy == STRAT_WORK) {
 361
 362                 int htype = 2;
 363                 if (u->carry_gold >= 100) htype = 7;
 364
 365                 target_pos = find_place(THE_D, htype, &target_cost, unit_pos, &id);
 366
 367                 if (target_pos != -1) {
 368
 369                         u->target_type = TARGET_HOUSE;
 370                         u->target_id = id;
 371
 372                 }
 373         }
 374
 375         if (u->strategy == STRAT_HUNT) {
 376
 377                 target_pos = find_flag(THE_D, your, 0, &target_cost, &id);
 378
 379                 if (target_pos != -1) {
 380
 381                         u->target_type = TARGET_FLAG;
 382                         u->target_id = id;
 383
 384                 }
 385
 386                 if (target_pos == -1) {
 387
 388                         target_pos = find_entity(THE_D, 1 - u->faction, &target_cost, unit_pos, &id);
 389
 390                         if (target_pos != -1) {
 391
 392                                 u->target_type = TARGET_UNIT;
 393                                 u->target_id = id;
 394
 395                         }
 396
 397                 }
 398
 399         }
 400
 401         //target_pos = get_closest(THE_D, unit_pos, &target_x, &target_y);
 402
 403         //printf("Picked: %d, %d\n", target_x, target_y);
 404
 405         if (target_pos == -1) return;
 406
 407 #ifdef DEBUG_PATHFIND
 408         u->tar_y = target_pos / level_w;
 409         u->tar_x = target_pos % level_w;
 410 #endif
 411
 412         /* Build path */
 413         int len;
 414         int start = build_path(THE_PREV, next, GRAPHSIZE, unit_pos, target_pos, &len);
 415         if (start > -1) {
 416                 int i;
 417                 int maxi = 16;
 418                 if (len < maxi) maxi = len;
 419                 for (i = 0; i < maxi; i++) {
 420                         u->path[i] = next[start + i];
 421                 }
 422                 for (; i < 16; i++) {
 423                         u->path[i] = -1;
 424                 }
 425
 426         }
 427 return;
 428
 429         /* Select a target */
 430         if (!get_path(THE_PREV, unit_pos, target_pos, &target_x, &target_y))
 431         {
 432                 u->tx = target_x;
 433                 u->ty = target_y;
 434         } else _printf("%s: No path to target\n", u->name);
 435 }
 436
 437 void unit_pick_destination2(int i) {
 438         unit_t *u = &units[i];
 439
 440         if (u->refresh.path || u->path[0] == -1) {
 441
 442                 u->refresh.path = 1;
 443                 unit_pick_destination(i);
 444                 u->refresh.path = 0;
 445
 446         }
 447
 448         if (u->path[0] != -1) {
 449                 int i;
 450                 int target_pos = u->path[0];
 451                 for (i = 0; i < 16 - 1; i++) {
 452                         u->path[i] = u->path[i + 1];
 453                 }
 454                 u->path[15] = -1;
 455
 456                 int target_y = target_pos / level_w;
 457                 int target_x = target_pos % level_w;
 458
 459                 u->tx = target_x;
 460                 u->ty = target_y;
 461         }
 462
 463 }
 464
 465 void unit_pick_strategy(int i) {
 466     unit_t *u = &units[i];
 467
 468     if (u->top_desire == DESIRE_NONE) {
 469                 _printf("%s has no desires.. Picking one at random.\n", u->name);
 470                 u->top_desire = rand() % MAX_DESIRES;
 471     }
 472     if (u->top_method == DESIRE_NONE) {
 473         _printf("%s has no method to achive his desire.. Picking one at random.\n", u->name);
 474                 u->top_method = rand() % MAX_DESIRES;
 475     }
 476         if (u->strategy == STRAT_NONE) {
 477                 _printf("%s has no strategy.\n", u->name);
 478                 /* Let's pick one... */
 479                 switch (u->top_method) {
 480                         case DESIRE_GOLD:
 481                                 /* Easiest way to get gold is to work for your kingdom */
 482                                 u->strategy = STRAT_WORK;
 483                         break;
 484                         case DESIRE_LOVE:
 485
 486                         break;
 487                         case DESIRE_POWER:
 488
 489                         break;
 490                         default:
 491                         break;
 492                 }
 493         }
 494         if (u->tactic == TACT_NONE) {
 495                 //_printf("%s has no tactic.\n", u->name);
 496         }
 497     _printf("%s wants %s, his plan is to use %s\n", u->name, desire_names[u->top_desire],desire_names[u->top_method]);
 498     _printf("  - Strategy: %s, Tactic: %s\n", start_names[u->strategy], tact_names[u->tactic]);
 499 }
 500
 501 int map_cost(unit_t *u, int x, int y, int dx, int dy) {
 502
 503         int h_ind, u_ind, f_ind;
 504         int manh = abs(u->x - dx) + abs(u->y - dy);
 505         //if (manh > 0 && manh <= 2 && find_unitT(dx, dy) != -1) return DJ_INFINITY;
 506
 507         int tile_cost = 0;
 508
 509         tile_cost = 0;
 510         if (dx - x != 0 && dy - y != 0) tile_cost = 15; //diagonal movements should be more expensive
 511
 512         if ((u_ind = find_unitT(dx, dy)) != -1) {
 513                 unit_t *u2 = &units[u_ind];
 514
 515                 /* Itself... */
 516                 if (u2 == u) {
 517                         /* probably doesn't matter */
 518                 }
 519                 /* Ally */
 520                 else if (u2->faction == u->faction) {
 521
 522                         if (u->strategy == STRAT_HEAL) {
 523
 524                                 /* Damaged unit */
 525                                 if (u2->dmg) return 10;
 526
 527                         }
 528
 529                 }
 530                 /* Foe */
 531                 else {
 532
 533                         if (u->strategy == STRAT_HUNT) {
 534
 535                                 return 10;
 536
 537                         }
 538
 539                 }
 540
 541                 /* For all other cases, treat it as solid tile (to move around) IF it's close */
 542                 if (manh > 0 && manh <= 2 && u2 != u) return DJ_INFINITY;
 543         }
 544
 545         if ((f_ind = find_flagT(dx, dy)) != -1) {
 546                 flag_t *f = &your->flags[f_ind];
 547
 548                         if (u->strategy == STRAT_WORK) {
 549                                 /* Go over flag, but don't obsess over it */
 550                                 if (f->type == 0) return 20;
 551                         }
 552                         if (u->strategy == STRAT_HUNT) {
 553                                 /* Both flags are good */
 554                                 if (f->type == 0) return 20;
 555                         }
 556         }
 557
 558         if ((h_ind = find_houseT(dx, dy)) != -1) {
 559                 house_t *h = &houses[h_ind];
 560                         if (u->strategy == STRAT_WORK) {
 561                                 /* Build/Repair building */
 562                                 if (h->hp < h->max_hp) return 10;
 563                                 /* Mine gold */
 564                                 if (h->tile == 2 && u->carry_gold < 100) return 10;
 565                                 /* Unload gold */
 566                                 if (h->tile == 7 && u->carry_gold >= 100) return 10;
 567                         }
 568                 return DJ_INFINITY/2;// && dx != u->tx && dy != u->ty) return 500;
 569         }
 570
 571         return 30 + tile_cost;
 572 }
 573
 574 void unit_think(int i) {
 575         unit_t *u = &units[i];
 576         unit_p *p = &bunits[u->tile];
 577
 578         unit_pick_strategy(i);
 579
 580         /* Tmp Hack -- override strategy */
 581         switch (p->modus) {
 582                 case MODUS_NONE: u->strategy = STRAT_NONE; break;
 583                 case MODUS_WORKER: u->strategy = STRAT_WORK; break;
 584                 case MODUS_SOLDIER: u->strategy = STRAT_HUNT; break;
 585                 case MODUS_HUNTER: u->strategy = STRAT_HUNT; break;
 586                 case MODUS_HEALER: u->strategy = STRAT_HEAL; break;
 587                 case MODUS_CARRIER: u->strategy = STRAT_NONE; break;
 588                 case MODUS_FOLLOWER: u->strategy = STRAT_NONE; break;
 589                 case MODUS_BUFFER: u->strategy = STRAT_HEAL; break;
 590                 case MODUS_DEBUFFER: u->strategy = STRAT_HEAL; break;
 591                 case MODUS_EXPLORER: u->strategy = STRAT_HUNT; break;
 592         }
 593
 594         if ((u->ox == 0 && u->oy == 0 && u->x == u->tx && u->y == u->ty) || u->refresh.path)
 595                 unit_pick_destination2(i);
 596 }