git.hungrycats.org Git - xscreensaver/blob - hacks/pacman_ai.h

   1 /*-
   2  * Copyright (c) 2002 by Edwin de Jong <mauddib@gmx.net>.
   3  *
   4  * Permission to use, copy, modify, and distribute this software and its
   5  * documentation for any purpose and without fee is hereby granted,
   6  * provided that the above copyright notice appear in all copies and that
   7  * both that copyright notice and this permission notice appear in
   8  * supporting documentation.
   9  *
  10  * This file is provided AS IS with no warranties of any kind.  The author
  11  * shall have no liability with respect to the infringement of copyrights,
  12  * trade secrets or any patents by this file or any part thereof.  In no
  13  * event will the author be liable for any lost revenue or profits or
  14  * other special, indirect and consequential damages.
  15  */
  16
  17 /* this file is a part of pacman.c, and included via pacman.h.  It handles the
  18    AI of the ghosts and the pacman. */
  19
  20
  21 /* fills array of DIRVECS size with possible directions, returns number of
  22    directions. 'posdirs' points to a possibly undefined array of four
  23    integers.  The vector will contain booleans wether the direction is
  24    a possible direction or not.  Reverse directions are deleted. */
  25 static int
  26 ghost_get_posdirs(pacmangamestruct *pp, int *posdirs, ghoststruct *g)
  27 {
  28         unsigned int i, nrdirs = 0;
  29
  30         /* bit of black magic here */
  31         for (i = 0; i < DIRVECS; i++) {
  32                 /* remove opposite */
  33                 if (g->lastbox != NOWHERE && i == (g->lastbox + 2) % DIRVECS
  34                                 && g->aistate != goingout) {
  35                         posdirs[i] = 0;
  36                         continue;
  37                 }
  38                 if (g->aistate == goingout && i == 1) {
  39                         posdirs[i] = 0;
  40                         continue;
  41                 }
  42                 /* check if possible direction */
  43                 if ((posdirs[i] =
  44                         check_pos(pp, g->row + dirvecs[i].dy,
  45                                 g->col + dirvecs[i].dx,
  46                                 g->aistate == goingout ? True : False)) ==
  47                                 True) {
  48                         nrdirs++;
  49                 }
  50         }
  51
  52         return nrdirs;
  53 }
  54
  55 /* Directs ghost to a random direction, exluding opposite (except in the
  56    impossible situation that there is only one valid direction). */
  57 static void
  58 ghost_random(pacmangamestruct *pp, ghoststruct *g)
  59 {
  60         int posdirs[DIRVECS], nrdirs = 0, i, dir = 0;
  61
  62         nrdirs = ghost_get_posdirs(pp, posdirs, g);
  63         for (i = 0; i < DIRVECS; i++)
  64                 if (posdirs[i] == True) dir = i;
  65
  66         if (nrdirs == 0) dir = (g->lastbox + 2) % DIRVECS;
  67         else if (nrdirs > 1)
  68                 for (i = 0; i < DIRVECS; i++) {
  69                         if (posdirs[i] == True && NRAND(nrdirs) == 0) {
  70                                 dir = i;
  71                                 break;
  72                         }
  73                 }
  74
  75         g->nextrow = g->row + dirvecs[dir].dy;
  76         g->nextcol = g->col + dirvecs[dir].dx;
  77         g->lastbox = dir;
  78 }
  79
  80 /* Determines best direction to chase the pacman and goes that direction. */
  81 static void
  82 ghost_chasing(pacmangamestruct *pp, ghoststruct *g)
  83 {
  84         int posdirs[DIRVECS], nrdirs = 0, i, dir = 0, highest = -100000,
  85                 thisvecx, thisvecy, thisvec;
  86
  87         nrdirs = ghost_get_posdirs(pp, posdirs, g);
  88         for (i = 0; i < DIRVECS; i++)
  89                 if (posdirs[i] == True) dir = i;
  90
  91         if (nrdirs == 0) dir = (g->lastbox + 2) % DIRVECS;
  92         else if (nrdirs > 1)
  93                 for (i = 0; i < DIRVECS; i++) {
  94                         if (posdirs[i] == False) continue;
  95                         thisvecx = (pp->pacman.col - g->col) * dirvecs[i].dx;
  96                         thisvecy = (pp->pacman.row - g->row) * dirvecs[i].dy;
  97                         thisvec = thisvecx + thisvecy;
  98                         if (thisvec >= highest) {
  99                                 dir = i;
 100                                 highest = thisvec;
 101                         }
 102                 }
 103
 104         g->nextrow = g->row + dirvecs[dir].dy;
 105         g->nextcol = g->col + dirvecs[dir].dx;
 106         g->lastbox = dir;
 107 }
 108
 109 /* Determines the best direction to go away from the pacman, and goes that
 110    direction. */
 111 static void
 112 ghost_hiding(pacmangamestruct *pp, ghoststruct *g)
 113 {
 114         int posdirs[DIRVECS], nrdirs = 0, i, dir = 0, highest = -100000,
 115                 thisvecx, thisvecy, thisvec;
 116
 117         nrdirs = ghost_get_posdirs(pp, posdirs, g);
 118         for (i = 0; i < DIRVECS; i++)
 119                 if (posdirs[i] == True) dir = i;
 120
 121         if (nrdirs == 0) dir = (g->lastbox + 2) % DIRVECS;
 122         else if (nrdirs > 1)
 123                 for (i = 0; i < DIRVECS; i++) {
 124                         if (posdirs[i] == False) continue;
 125                         thisvecx = (g->col - pp->pacman.col) * dirvecs[i].dx;
 126                         thisvecy = (g->row - pp->pacman.row) * dirvecs[i].dy;
 127                         thisvec = thisvecx + thisvecy;
 128                         if (thisvec >= highest)
 129                                 dir = i;
 130                 }
 131
 132         g->nextrow = g->row + dirvecs[dir].dy;
 133         g->nextcol = g->col + dirvecs[dir].dx;
 134         g->lastbox = dir;
 135 }
 136
 137 /* Determines a vector from the pacman position, towards all dots.  The vector
 138    is inversely proportional to the square of the distance of each dot.
 139    (so, close dots attract more than far away dots). */
 140 static void
 141 pac_dot_vec(pacmangamestruct *pp, pacmanstruct *p, long *vx, long *vy)
 142 {
 143         int x, y, bx = 0, by = 0, ex = LEVWIDTH, ey = LEVHEIGHT;
 144         long dx, dy, dist, top = 0;
 145
 146 #if 0
 147         int rnr = NRAND(50);
 148         /* determine begin and end vectors */
 149
 150         switch (rnr) {
 151                 case 0: ex = LEVHEIGHT/2; break;
 152                 case 1: bx = LEVHEIGHT/2; break;
 153                 case 2: ey = LEVHEIGHT/2; break;
 154                 case 3: by = LEVHEIGHT/2; break;
 155         }
 156 #endif
 157         *vx = *vy = 0;
 158
 159         for (y = by; y < ey; y++)
 160                 for (x = bx; x < ex; x++)
 161                         if (check_dot(pp, x, y) == 1) {
 162                                 dx = (long)x - (long)(p->col);
 163                                 dy = (long)y - (long)(p->row);
 164                                 dist = dx * dx + dy * dy;
 165                                 if (dist > top)
 166                                         top = dist;
 167                                 *vx += (dx * ((long)LEVWIDTH * (long)LEVHEIGHT))
 168                                        / dist;
 169                                 *vy += (dy * ((long)LEVWIDTH * (long)LEVHEIGHT))
 170                                        / dist;
 171                         }
 172 }
 173
 174 /* Determine a vector towards the closest ghost (in one loop, so we spare a
 175    couple of cycles which we can spoil somewhere else just as fast). */
 176 static int
 177 pac_ghost_prox_and_vector(pacmangamestruct *pp, pacmanstruct *p,
 178                 int *vx, int *vy)
 179 {
 180         int dx, dy, dist, closest = 100000;
 181         unsigned int g;
 182
 183         if (vx != NULL)
 184                 *vx = *vy = 0;
 185
 186         for (g = 0; g < pp->nghosts; g++) {
 187                 if (pp->ghosts[g].dead    == True  ||
 188                     pp->ghosts[g].aistate == inbox ||
 189                     pp->ghosts[g].aistate == goingout)
 190                         continue;
 191                 dx = pp->ghosts[g].col + /*dirvecs[pp->ghosts[g].lastbox].dx*/ -
 192                         p->col;
 193                 dy = pp->ghosts[g].row + /*dirvecs[pp->ghosts[g].lastbox].dy*/ -
 194                         p->row;
 195                 dist = dx * dx + dy * dy;
 196                 if (dist < closest) {
 197                         closest = dist;
 198                         if (vx != NULL) {
 199                                 *vx = dx; *vy = dy;
 200                         }
 201                 }
 202         }
 203         return closest;
 204 }
 205
 206 /* fills array of DIRVECS size with possible directions, returns number of
 207    directions.  posdirs should point to an array of 4 integers. */
 208 static int
 209 pac_get_posdirs(pacmangamestruct *pp, pacmanstruct *p, int *posdirs)
 210 {
 211         int nrdirs = 0;
 212         unsigned int i;
 213
 214         for (i = 0; i < DIRVECS; i++) {
 215                 /* if we just ate, or we are in a statechange, it is allowed
 216                    to go the opposite direction */
 217                 if (p->justate == 0 &&
 218                     p->state_change == 0 &&
 219                     p->lastbox != NOWHERE &&
 220                     i == (p->lastbox + 2) % DIRVECS) {
 221                         posdirs[i] = 0;
 222                 } else if ((posdirs[i] =
 223                         check_pos(pp, p->row + dirvecs[i].dy,
 224                                 p->col + dirvecs[i].dx, 0)) == 1)
 225                         nrdirs++;
 226         }
 227         p->state_change = 0;
 228
 229         return nrdirs;
 230 }
 231
 232 /* Clears the trace of vectors. */
 233 static void
 234 pac_clear_trace(pacmanstruct *p)
 235 {
 236         int i;
 237
 238         for(i = 0; i < TRACEVECS; i++) {
 239                 p->trace[i].vx = NOWHERE; p->trace[i].vy = NOWHERE;
 240         }
 241         p->cur_trace = 0;
 242 }
 243
 244 /* Adds a new vector to the trace. */
 245 static void
 246 pac_save_trace(pacmanstruct *p, const int vx, const int vy)
 247 {
 248         if (!(vx == NOWHERE && vy == NOWHERE)) {
 249                 p->trace[p->cur_trace].vx = vx;
 250                 p->trace[p->cur_trace].vy = vy;
 251                 p->cur_trace = (p->cur_trace + 1) % TRACEVECS;
 252         }
 253 }
 254
 255 /* Check if a vector can be found in the trace. */
 256 static int
 257 pac_check_trace(const pacmanstruct *p, const int vx, const int vy)
 258 {
 259         int i, curel;
 260
 261         for (i = 1; i < TRACEVECS; i++) {
 262                 curel = (p->cur_trace - i + TRACEVECS) % TRACEVECS;
 263                 if (p->trace[curel].vx == NOWHERE &&
 264                     p->trace[curel].vy == NOWHERE)
 265                         continue;
 266                 if (p->trace[curel].vx == vx &&
 267                     p->trace[curel].vy == vy)
 268                         return 1;
 269         }
 270
 271
 272         return 0;
 273 }
 274
 275 /* AI mode "Eating" for pacman. Tries to eat as many dots as possible, goes
 276    to "hiding" if too close to a ghost. If in state "hiding" the vectors
 277    of the ghosts are also taken into account (thus not running towards them
 278    is the general idea). */
 279 static void
 280 pac_eating(pacmangamestruct *pp, pacmanstruct *p)
 281 {
 282         int posdirs[DIRVECS], nrdirs, i, highest = -(1 << 16),
 283                 score, dir = 0, dotfound = 0, prox, worst = 0;
 284         long vx, vy;
 285
 286         if ((prox = pac_ghost_prox_and_vector(pp, p, (int *)&vx, (int *)&vy)) <
 287                                 4 * 4 && p->aistate == ps_eating) {
 288                 p->aistate = ps_hiding;
 289                 p->state_change = 1;
 290                 pac_clear_trace(p);
 291         }
 292
 293         if (prox > 6 * 6 && p->aistate == ps_hiding) {
 294                 p->aistate = ps_eating;
 295                 if (p->justate == 0) p->state_change = 1;
 296                 pac_clear_trace(p);
 297         }
 298
 299         if (prox < 3 * 3) p->state_change = 1;
 300
 301         nrdirs = pac_get_posdirs(pp, p, posdirs);
 302
 303         /* remove directions which lead to ghosts */
 304         if (p->aistate == ps_hiding) {
 305                 for (i = 0; i < DIRVECS; i++) {
 306                         if (posdirs[i] == 0) continue;
 307                         score = vx * dirvecs[i].dx + vy * dirvecs[i].dy;
 308                         if (score > highest) {
 309                                 worst = i;
 310                                 highest = score;
 311                         }
 312                         dir = i;
 313                 }
 314                 nrdirs--;
 315                 posdirs[worst] = 0;
 316                 highest = -(1 << 16);
 317         }
 318
 319         /* get last possible direction if all else fails */
 320         for (i = 0; i < DIRVECS; i++)
 321                 if (posdirs[i] != 0) dir = i;
 322
 323         pac_dot_vec(pp, p, &vx, &vy);
 324
 325         if (vx != NOWHERE && vy != NOWHERE && pac_check_trace(p, vx, vy) > 0) {
 326                 p->roundscore++;
 327                 if (p->roundscore >= 12) {
 328                         p->roundscore = 0;
 329                         p->aistate = ps_random;
 330                         pac_clear_trace(p);
 331                 }
 332         } else
 333                 p->roundscore = 0;
 334
 335         if (p->justate == 0) pac_save_trace(p, vx, vy);
 336
 337         for (i = 0; i < DIRVECS; i++) {
 338                 if (posdirs[i] == 0) continue;
 339                 score = dirvecs[i].dx * vx + dirvecs[i].dy * vy;
 340                 if (check_dot(pp, p->col + dirvecs[i].dx,
 341                                   p->row + dirvecs[i].dy) == 1) {
 342                         if (dotfound == 0) {
 343                                 highest = score;
 344                                 dir = i;
 345                                 dotfound = 1;
 346                         } else if (score > highest) {
 347                                 highest = score;
 348                                 dir = i;
 349                         }
 350                 } else if (score > highest && dotfound == 0) {
 351                         dir = i;
 352                         highest = score;
 353                 }
 354         }
 355
 356         p->nextrow = p->row + dirvecs[dir].dy;
 357         p->nextcol = p->col + dirvecs[dir].dx;
 358         p->lastbox = dir;
 359 }
 360
 361 #if 0
 362 /* Tries to catch the ghosts. */
 363 static void
 364 pac_chasing(pacmangamestruct *pp, pacmanstruct *p)
 365 {
 366 }
 367 #endif
 368
 369 /* Goes completely random, but not in the opposite direction.  Used when a
 370    loop is detected. */
 371 static void
 372 pac_random(pacmangamestruct *pp, pacmanstruct *p)
 373 {
 374         int posdirs[DIRVECS], nrdirs, i, dir = -1, lastdir = 0;
 375
 376         if (pac_ghost_prox_and_vector(pp, p, NULL, NULL) < 5 * 5) {
 377                 p->aistate = ps_hiding;
 378                 p->state_change = 1;
 379         }
 380         if (NRAND(20) == 0) {
 381                 p->aistate = ps_eating;
 382                 p->state_change = 1;
 383                 pac_clear_trace(p);
 384         }
 385
 386         nrdirs = pac_get_posdirs(pp, p, posdirs);
 387
 388         for (i = 0; i < DIRVECS; i++) {
 389                 if (posdirs[i] == 0) continue;
 390                 lastdir = i;
 391                 if (check_dot(pp, p->col + dirvecs[i].dx,
 392                         p->row + dirvecs[i].dy) == 1) {
 393                         dir = i;
 394                         p->aistate = ps_eating;
 395                         p->state_change = 1;
 396                         pac_clear_trace(p);
 397                         break;
 398                 } else if (NRAND(nrdirs) == 0)
 399                         dir = i;
 400         }
 401
 402         if (dir == -1) dir = lastdir;
 403
 404         p->nextrow = p->row + dirvecs[dir].dy;
 405         p->nextcol = p->col + dirvecs[dir].dx;
 406         p->lastbox = dir;
 407 }
 408
 409 static int
 410 pac_get_vector_screen(pacmangamestruct *pp, pacmanstruct *p,
 411                 const int x, const int y, int *vx, int *vy)
 412 {
 413         int lx, ly;
 414
 415         lx = (x - pp->xb) / pp->xs;
 416         ly = (y - pp->yb) / pp->ys;
 417
 418         if (lx < 0) lx = 0;
 419         else if ((unsigned int) lx > LEVWIDTH) lx = LEVWIDTH - 1;
 420
 421         if (ly < 0) ly = 0;
 422         else if ((unsigned int) ly > LEVHEIGHT) ly = LEVHEIGHT - 1;
 423
 424         *vx = lx - p->col;
 425         *vy = ly - p->row;
 426
 427         if (lx == p->oldlx && ly == p->oldly) return 0;
 428         p->oldlx = lx; p->oldly = ly;
 429         return 1;
 430 }
 431
 432 static int
 433 pac_trackmouse(ModeInfo * mi, pacmangamestruct *pp, pacmanstruct *p)
 434 {
 435         int dx, dy, cx, cy, vx, vy;
 436         unsigned int m;
 437         int posdirs[DIRVECS], i, dir = -1, highest = -(2 << 16), score;
 438         Window r, c;
 439
 440         (void) XQueryPointer(MI_DISPLAY(mi), MI_WINDOW(mi),
 441                          &r, &c, &dx, &dy, &cx, &cy, &m);
 442
 443         if (cx <= 0 || cy <= 0 ||
 444                     cx >= MI_WIDTH(mi) - 1 ||
 445                     cy >= MI_HEIGHT(mi) - 1)
 446                 return 0;
 447         /* get vector */
 448         p->state_change = pac_get_vector_screen(pp, p, cx, cy, &vx, &vy);
 449
 450         (void) pac_get_posdirs(pp, p, posdirs);
 451
 452         for (i = 0; i < DIRVECS; i++) {
 453                 if (posdirs[i] == 0) continue;
 454                 score = dirvecs[i].dx * vx + dirvecs[i].dy * vy;
 455                 if (score > highest) {
 456                         highest = score;
 457                         dir = i;
 458                 }
 459         }
 460
 461         p->nextrow = p->row + dirvecs[dir].dy;
 462         p->nextcol = p->col + dirvecs[dir].dx;
 463         p->lastbox = dir;
 464         return 1;
 465 }
 466
 467 /* Calls correct state function, and changes between states. */
 468 static void
 469 ghost_update(pacmangamestruct *pp, ghoststruct *g)
 470 {
 471
 472         if (!(g->nextrow == NOWHERE && g->nextcol == NOWHERE)) {
 473                 g->row = g->nextrow;
 474                 g->col = g->nextcol;
 475         }
 476
 477         /* update ghost */
 478         if (g->dead == True) /* dead ghosts are dead,
 479                                 so they don't run around */
 480                 return;
 481
 482         if ((g->aistate == randdir || g->aistate == chasing) &&
 483                         NRAND(10) == 0) {
 484                 switch (NRAND(3)) {
 485                         case 0:
 486                                 g->aistate = randdir; break;
 487                         case 1:
 488                                 g->aistate = chasing; break;
 489                         case 2:
 490                                 g->aistate = chasing; break;
 491                 }
 492
 493         } else if (g->aistate == inbox) {
 494                 if (g->timeleft < 0)
 495                         g->aistate = goingout;
 496                 else
 497                         g->timeleft--;
 498
 499         } else if (g->aistate == goingout) {
 500                 if (g->col < LEVWIDTH/2 - JAILWIDTH/2 ||
 501                     g->col > LEVWIDTH/2 + JAILWIDTH/2 ||
 502                     g->row < LEVHEIGHT/2 - JAILHEIGHT/2 ||
 503                     g->row > LEVHEIGHT/2 + JAILHEIGHT/2 )
 504                         g->aistate = randdir;
 505         }
 506
 507         switch (g->aistate) {
 508                 case inbox:
 509                 case goingout:
 510                 case randdir:
 511                         ghost_random(pp, g);
 512                         break;
 513                 case chasing:
 514                         ghost_chasing(pp, g);
 515                         break;
 516                 case hiding:
 517                         ghost_hiding(pp, g);
 518                         break;
 519         }
 520
 521         g->cfactor = GETFACTOR(g->nextcol, g->col);
 522         g->rfactor = GETFACTOR(g->nextrow, g->row);
 523 }
 524
 525 /* Calls correct pacman state function. */
 526 static void
 527 pac_update(ModeInfo *mi, pacmangamestruct *pp, pacmanstruct *p)
 528 {
 529         if (!(p->nextrow == NOWHERE && p->nextcol == NOWHERE)) {
 530                 p->row = p->nextrow;
 531                 p->col = p->nextcol;
 532         }
 533
 534         if (pp->level[p->row * LEVWIDTH + p->col] == '.') {
 535                 pp->level[p->row * LEVWIDTH + p->col] = ' ';
 536                 if (!trackmouse)
 537                         p->justate = 1;
 538                 pp->dotsleft--;
 539         } else if (!trackmouse) {
 540                 p->justate = 0;
 541         }
 542
 543         if (!(trackmouse && pac_trackmouse(mi, pp, p))) {
 544                 /* update pacman */
 545                 switch (p->aistate) {
 546                         case ps_eating:
 547                                 pac_eating(pp, p);
 548                                 break;
 549                         case ps_hiding:
 550                                 pac_eating(pp, p);
 551                                 break;
 552                         case ps_random:
 553                                 pac_random(pp, p);
 554                                 break;
 555                         case ps_chasing:
 556 #if 0
 557                                 pac_chasing(pp, p);
 558 #endif
 559                                 break;
 560                 }
 561         }
 562
 563         p->cfactor = GETFACTOR(p->nextcol, p->col);
 564         p->rfactor = GETFACTOR(p->nextrow, p->row);
 565 }