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

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