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

   1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*-
   3  * Copyright (c) 2002 by Edwin de Jong <mauddib@gmx.net>.
   4  *
   5  * Permission to use, copy, modify, and distribute this software and its
   6  * documentation for any purpose and without fee is hereby granted,
   7  * provided that the above copyright notice appear in all copies and that
   8  * both that copyright notice and this permission notice appear in
   9  * supporting documentation.
  10  *
  11  * This file is provided AS IS with no warranties of any kind.  The author
  12  * shall have no liability with respect to the infringement of copyrights,
  13  * trade secrets or any patents by this file or any part thereof.  In no
  14  * event will the author be liable for any lost revenue or profits or
  15  * other special, indirect and consequential damages.
  16  */
  17
  18 /* this file handles the AI of the ghosts and the pacman. */
  19
  20 #include <math.h>
  21 #include <assert.h>
  22 #include "pacman.h"
  23 #include "pacman_ai.h"
  24 #include "pacman_level.h"
  25
  26 #define MI_DISPLAY(MI)  ((MI)->dpy)
  27 #define MI_WINDOW(MI)   ((MI)->window)
  28 #define MI_WIDTH(MI)    ((MI)->xgwa.width)
  29 #define MI_HEIGHT(MI)   ((MI)->xgwa.height)
  30
  31 #define DIRVECS 4
  32 static const struct
  33 {
  34     int dx, dy;
  35 } dirvecs[DIRVECS] = { {
  36 -1, 0}, {
  37 0, 1}, {
  38 1, 0}, {
  39 0, -1}};
  40
  41 /* positions that match the dirvecs */
  42 typedef enum {pos_none = -1, pos_left = 0, pos_up = 1, pos_right = 2, pos_down = 3} pos;
  43
  44
  45 /* fills array of DIRVECS size with possible directions, returns number of
  46    directions. 'posdirs' points to a possibly undefined array of four
  47    integers.  The vector will contain booleans wether the direction is
  48    a possible direction or not.  Reverse directions are deleted. */
  49 static int
  50 ghost_get_posdirs (pacmangamestruct * pp, int *posdirs, ghoststruct * g)
  51 {
  52     unsigned int i, nrdirs = 0;
  53     unsigned int can_go_in = 0;
  54
  55     /* bit of black magic here */
  56     for (i = 0; i < DIRVECS; i++) {
  57         /* remove opposite */
  58         if (g->lastbox != NOWHERE && i == (g->lastbox + 2) % DIRVECS
  59             && (g->aistate != goingout )) {
  60             posdirs[i] = 0;
  61             continue;
  62         }
  63         if (g->aistate == goingout && i == 1) {
  64             posdirs[i] = 0;
  65             continue;
  66         }
  67         /* check if possible direction */
  68         can_go_in = (g->aistate == goingout || g->aistate == goingin);
  69         if ((posdirs[i] =
  70              check_pos (pp, g->row + dirvecs[i].dy,
  71                         g->col + dirvecs[i].dx,
  72                         can_go_in)) == True) {
  73             nrdirs++;
  74         }
  75     }
  76
  77     return nrdirs;
  78 }
  79
  80 /* Directs ghost to a random direction, exluding opposite (except in the
  81    impossible situation that there is only one valid direction). */
  82 static void
  83 ghost_random (pacmangamestruct * pp, ghoststruct * g)
  84 {
  85     int posdirs[DIRVECS], nrdirs = 0, i, dir = 0;
  86
  87     nrdirs = ghost_get_posdirs (pp, posdirs, g);
  88 #if 0
  89     g->ndirs = nrdirs;
  90 #endif
  91     for (i = 0; i < DIRVECS; i++)
  92         if (posdirs[i] == True)
  93             dir = i;
  94
  95     if (nrdirs == 0)
  96         dir = (g->lastbox + 2) % DIRVECS;
  97     else if (nrdirs > 1)
  98         for (i = 0; i < DIRVECS; i++) {
  99             if (posdirs[i] == True && NRAND (nrdirs) == 0) {
 100                 dir = i;
 101                 break;
 102             }
 103         }
 104
 105     g->nextrow = g->row + dirvecs[dir].dy;
 106     g->nextcol = g->col + dirvecs[dir].dx;
 107     g->lastbox = dir;
 108 }
 109
 110 /* Determines best direction to chase the pacman and goes that direction. */
 111 static void
 112 ghost_chasing (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 #if 0
 119     g->ndirs = nrdirs;
 120 #endif
 121     for (i = 0; i < DIRVECS; i++)
 122         if (posdirs[i] == True)
 123             dir = i;
 124
 125     if (nrdirs == 0)
 126         dir = (g->lastbox + 2) % DIRVECS;
 127     else if (nrdirs > 1)
 128         for (i = 0; i < DIRVECS; i++) {
 129             if (posdirs[i] == False)
 130                 continue;
 131             thisvecx = (pp->pacman.col - g->col) * dirvecs[i].dx;
 132             thisvecy = (pp->pacman.row - g->row) * dirvecs[i].dy;
 133             thisvec = thisvecx + thisvecy;
 134             if (thisvec >= highest) {
 135                 dir = i;
 136                 highest = thisvec;
 137             }
 138         }
 139
 140     g->nextrow = g->row + dirvecs[dir].dy;
 141     g->nextcol = g->col + dirvecs[dir].dx;
 142     g->lastbox = dir;
 143 }
 144
 145 /* Determines the best direction to go away from the pacman, and goes that
 146    direction. */
 147 static void
 148 ghost_hiding (pacmangamestruct * pp, ghoststruct * g)
 149 {
 150     int posdirs[DIRVECS], nrdirs = 0, i, dir = 0, highest = -100000,
 151         thisvecx, thisvecy, thisvec;
 152
 153     nrdirs = ghost_get_posdirs (pp, posdirs, g);
 154 #if 0
 155     g->ndirs = nrdirs;
 156 #endif
 157     for (i = 0; i < DIRVECS; i++)
 158         if (posdirs[i] == True)
 159             dir = i;
 160
 161     if (nrdirs == 0)
 162         dir = (g->lastbox + 2) % DIRVECS;
 163     else if (nrdirs > 1)
 164         for (i = 0; i < DIRVECS; i++) {
 165             if (posdirs[i] == False)
 166                 continue;
 167             thisvecx = (g->col - pp->pacman.col) * dirvecs[i].dx;
 168             thisvecy = (g->row - pp->pacman.row) * dirvecs[i].dy;
 169             thisvec = thisvecx + thisvecy;
 170             if (thisvec >= highest)
 171                 dir = i;
 172         }
 173
 174     g->nextrow = g->row + dirvecs[dir].dy;
 175     g->nextcol = g->col + dirvecs[dir].dx;
 176     g->lastbox = dir;
 177 }
 178
 179 #if 1
 180 static void
 181 clear_trace(ghoststruct *g)
 182 {
 183     int i = 0;
 184     g->trace_idx = 0;
 185     while (i < GHOST_TRACE){
 186         g->trace[i].vx = -1;
 187         g->trace[i++].vy = -1;
 188     }
 189 }
 190
 191
 192 static void
 193 save_position (ghoststruct *g, int x, int y)
 194 {
 195     int i = g->trace_idx;
 196     assert ( 0 <= i && i < GHOST_TRACE );
 197     g->trace[i].vx = x;
 198     g->trace[i].vy = y;
 199     g->trace_idx++;
 200 }
 201
 202 static int
 203 already_tried (ghoststruct *g, int x, int y)
 204 {
 205     int i = 0;
 206     if (! ( 0 <= g->trace_idx && g->trace_idx < GHOST_TRACE ) ){
 207         fprintf(stderr, "FOUND TRACE ERROR. DUMPING TRACE.\n");
 208         fprintf(stderr, "%d\n", g->trace_idx );
 209         for ( i = 0; i < GHOST_TRACE; i++ ){
 210             fprintf(stderr, "( %d, %d )\n", g->trace[i].vx, g->trace[i].vy );
 211         }
 212         assert ( False );
 213     }
 214     while (i < g->trace_idx){
 215         if ( x == g->trace[i].vx && y == g->trace[i].vy ){
 216             /* fprintf ( stderr, "Match FOUND (%d, %d)\n", x, y); */
 217             return 1;
 218         }
 219         i++;
 220     }
 221     return 0;
 222 }
 223 #endif
 224
 225 static void
 226 store_dir ( ghoststruct *g, pos ps ){
 227     int i = g->home_count;
 228     assert ( 0 <= i && i < GHOST_TRACE );
 229     g->way_home[i].vx = dirvecs[ps].dx;
 230     g->way_home[i].vy = dirvecs[ps].dy;
 231     g->home_count++;
 232 }
 233
 234 static void
 235 clear_dir ( ghoststruct *g ){
 236     int i = 0;
 237     g->home_count = 0;
 238     g->home_idx = 0;
 239     while (i < GHOST_TRACE){
 240         g->way_home[i].vx = -1;
 241         g->way_home[i++].vy = -1;
 242     }
 243 }
 244
 245 static int
 246 found_jail ( int col, int row ){
 247     int cx, cy;
 248     get_jail_opening ( &cx, &cy );
 249     cy += 1;
 250     if (row == cy && col == cx )
 251         return 1;
 252     else
 253         return 0;
 254 }
 255
 256 static int
 257 move_ghost ( pacmangamestruct * pp,
 258              int row, int col,
 259              pos ps,
 260              int *new_row, int *new_col){
 261     int idx = (int)ps;
 262     int tr = row + dirvecs[idx].dx;
 263     int tc = col + dirvecs[idx].dy;
 264     if ( check_pos ( pp, tr, tc, True )){
 265         *new_row = tr;
 266         *new_col = tc;
 267         return True;
 268     }
 269     else {
 270         return False;
 271     }
 272 }
 273
 274 static int
 275 recur_back_track ( pacmangamestruct * pp, ghoststruct *g, int row, int col ){
 276     int new_row, new_col;
 277
 278     if ( already_tried ( g, col, row ) )
 279         return False;
 280
 281     if ( found_jail ( col, row ) )
 282         return True;
 283
 284     save_position ( g, col, row );
 285
 286     if ( move_ghost ( pp, row, col, pos_left, &new_row, &new_col ))
 287         if ( recur_back_track ( pp, g, new_row, new_col )){
 288                  store_dir ( g, pos_left );
 289                  return True;
 290         }
 291
 292     if ( move_ghost ( pp, row, col, pos_up, &new_row, &new_col ))
 293         if ( recur_back_track ( pp, g, new_row, new_col )){
 294                  store_dir ( g, pos_up );
 295                  return True;
 296         }
 297
 298     if ( move_ghost ( pp, row, col, pos_down, &new_row, &new_col ))
 299         if ( recur_back_track ( pp, g, new_row, new_col )){
 300                  store_dir ( g, pos_down );
 301                  return True;
 302         }
 303
 304     if ( move_ghost ( pp, row, col, pos_right, &new_row, &new_col ))
 305         if ( recur_back_track ( pp, g, new_row, new_col )){
 306                  store_dir ( g, pos_right );
 307                  return True;
 308         }
 309
 310     return False;
 311 }
 312
 313 static void
 314 find_home ( pacmangamestruct *pp, ghoststruct *g ){
 315     int i;
 316     int r,c;
 317     int cx, cy;
 318     ghoststruct *tmp_ghost;
 319     tmp_ghost = (ghoststruct*)malloc(sizeof ( ghoststruct ));
 320     if ( tmp_ghost == NULL ){
 321         fprintf(stderr, "find_home : Could not allocate memory.");
 322         exit ( 1 );
 323     }
 324     tmp_ghost = memmove(tmp_ghost, g, sizeof ( ghoststruct ));
 325     if ( tmp_ghost == NULL ){
 326         fprintf(stderr, "find_home : Could not copy memory.");
 327         exit ( 1 );
 328     }
 329     clear_trace ( tmp_ghost );
 330     clear_dir ( tmp_ghost );
 331     r = tmp_ghost->row;
 332     c = tmp_ghost->col;
 333     if ( ! recur_back_track ( pp, tmp_ghost, r, c ) ){
 334         fprintf(stderr, "Could not find way home.#@$?\n");
 335         get_jail_opening ( &cx, &cy);
 336         fprintf(stderr, "Jail was at (%d%d)\n", cx,cy);
 337     }
 338     for ( i = 0; i < GHOST_TRACE; i++ ){
 339         g->way_home[i].vx = tmp_ghost->way_home[i].vx;
 340         g->way_home[i].vy = tmp_ghost->way_home[i].vy;
 341     }
 342     g->home_count = tmp_ghost->home_count;
 343     g->home_idx = tmp_ghost->home_count;
 344     free(tmp_ghost);
 345 }
 346
 347 /* Make the ghost go back to the inbox */
 348 static void
 349 ghost_goingin (pacmangamestruct * pp, ghoststruct * g)
 350 {
 351     g->home_idx--;
 352     if (g->home_idx < 0){ g->aistate = goingout; return;}
 353     /* row == vx ? wtf... Don't Ask */
 354     g->nextrow = g->row + g->way_home[g->home_idx].vx;
 355     g->nextcol = g->col + g->way_home[g->home_idx].vy;
 356 }
 357
 358
 359 /* Determines a vector from the pacman position, towards all dots.  The vector
 360    is inversely proportional to the square of the distance of each dot.
 361    (so, close dots attract more than far away dots). */
 362 static void
 363 pac_dot_vec (pacmangamestruct * pp, pacmanstruct * p, long *vx, long *vy)
 364 {
 365     int x, y, bx = 0, by = 0, ex = LEVWIDTH, ey = LEVHEIGHT;
 366     long dx, dy, dist, top = 0;
 367
 368 #if 0
 369     int rnr = NRAND (50);
 370     /* determine begin and end vectors */
 371
 372     switch (rnr) {
 373     case 0:
 374         ex = LEVHEIGHT / 2;
 375         break;
 376    case 1:
 377         bx = LEVHEIGHT / 2;
 378         break;
 379     case 2:
 380         ey = LEVHEIGHT / 2;
 381         break;
 382     case 3:
 383         by = LEVHEIGHT / 2;
 384         break;
 385     }
 386 #endif
 387     *vx = *vy = 0;
 388
 389     for (y = by; y < ey; y++)
 390         for (x = bx; x < ex; x++)
 391             if (check_dot (pp, x, y) == 1) {
 392                 dx = (long) x - (long) (p->col);
 393                 dy = (long) y - (long) (p->row);
 394                 dist = dx * dx + dy * dy;
 395                 if (dist > top)
 396                     top = dist;
 397                 *vx += (dx * ((long) LEVWIDTH * (long) LEVHEIGHT))
 398                     / dist;
 399                 *vy += (dy * ((long) LEVWIDTH * (long) LEVHEIGHT))
 400                     / dist;
 401             }
 402 }
 403
 404 /* Determine a vector towards the closest ghost (in one loop, so we spare a
 405    couple of cycles which we can spoil somewhere else just as fast). */
 406 static int
 407 pac_ghost_prox_and_vector (pacmangamestruct * pp, pacmanstruct * p,
 408                            int *vx, int *vy)
 409 {
 410     int dx, dy, dist, closest = 100000;
 411     unsigned int g;
 412
 413     if (vx != NULL)
 414         *vx = *vy = 0;
 415
 416     for (g = 0; g < pp->nghosts; g++) {
 417         if (pp->ghosts[g].dead == True ||
 418             pp->ghosts[g].aistate == inbox ||
 419             pp->ghosts[g].aistate == goingout)
 420             continue;
 421         dx = pp->ghosts[g].col + /*dirvecs[pp->ghosts[g].lastbox].dx */ -
 422             p->col;
 423         dy = pp->ghosts[g].row + /*dirvecs[pp->ghosts[g].lastbox].dy */ -
 424             p->row;
 425         dist = dx * dx + dy * dy;
 426         if (dist < closest) {
 427             closest = dist;
 428             if (vx != NULL) {
 429                 *vx = dx;
 430                 *vy = dy;
 431             }
 432         }
 433     }
 434     return closest;
 435 }
 436
 437 /* fills array of DIRVECS size with possible directions, returns number of
 438    directions.  posdirs should point to an array of 4 integers. */
 439 static int
 440 pac_get_posdirs (pacmangamestruct * pp, pacmanstruct * p, int *posdirs)
 441 {
 442     int nrdirs = 0;
 443     unsigned int i;
 444
 445     for (i = 0; i < DIRVECS; i++) {
 446         /* if we just ate, or we are in a statechange, it is allowed
 447          * to go the opposite direction */
 448         if (p->justate == 0 &&
 449             p->state_change == 0 &&
 450             p->lastbox != NOWHERE && i == (p->lastbox + 2) % DIRVECS) {
 451             posdirs[i] = 0;
 452         }
 453         else if ((posdirs[i] =
 454                   check_pos (pp, p->row + dirvecs[i].dy,
 455                              p->col + dirvecs[i].dx, 0)) == 1)
 456             nrdirs++;
 457     }
 458     p->state_change = 0;
 459
 460     return nrdirs;
 461 }
 462
 463 /* Clears the trace of vectors. */
 464 void
 465 pac_clear_trace (pacmanstruct * p)
 466 {
 467     int i;
 468
 469     for (i = 0; i < TRACEVECS; i++) {
 470         p->trace[i].vx = NOWHERE;
 471         p->trace[i].vy = NOWHERE;
 472     }
 473     p->cur_trace = 0;
 474 }
 475
 476 /* Adds a new vector to the trace. */
 477 static void
 478 pac_save_trace (pacmanstruct * p, const int vx, const int vy)
 479 {
 480     if (!(vx == NOWHERE && vy == NOWHERE)) {
 481         p->trace[p->cur_trace].vx = vx;
 482         p->trace[p->cur_trace].vy = vy;
 483         p->cur_trace = (p->cur_trace + 1) % TRACEVECS;
 484     }
 485 }
 486
 487 /* Check if a vector can be found in the trace. */
 488 static int
 489 pac_check_trace (const pacmanstruct * p, const int vx, const int vy)
 490 {
 491     int i, curel;
 492
 493     for (i = 1; i < TRACEVECS; i++) {
 494         curel = (p->cur_trace - i + TRACEVECS) % TRACEVECS;
 495         if (p->trace[curel].vx == NOWHERE && p->trace[curel].vy == NOWHERE)
 496             continue;
 497         if (p->trace[curel].vx == vx && p->trace[curel].vy == vy)
 498             return 1;
 499     }
 500
 501
 502     return 0;
 503 }
 504
 505 /* AI mode "Eating" for pacman. Tries to eat as many dots as possible, goes
 506    to "hiding" if too close to a ghost. If in state "hiding" the vectors
 507    of the ghosts are also taken into account (thus not running towards them
 508    is the general idea). */
 509 static void
 510 pac_eating (pacmangamestruct * pp, pacmanstruct * p)
 511 {
 512     int posdirs[DIRVECS], nrdirs, i, highest = -(1 << 16),
 513         score, dir = 0, dotfound = 0, prox, worst = 0;
 514     int vx, vy;
 515
 516     if ((prox = pac_ghost_prox_and_vector (pp, p, &vx, &vy)) <
 517         4 * 4 && p->aistate == ps_eating) {
 518         p->aistate = ps_hiding;
 519         p->state_change = 1;
 520         pac_clear_trace (p);
 521     }
 522
 523     if (prox > 6 * 6 && p->aistate == ps_hiding) {
 524         p->aistate = ps_eating;
 525         if (p->justate == 0)
 526             p->state_change = 1;
 527         pac_clear_trace (p);
 528     }
 529
 530     if (prox < 3 * 3)
 531         p->state_change = 1;
 532
 533     nrdirs = pac_get_posdirs (pp, p, posdirs);
 534
 535     /* remove directions which lead to ghosts */
 536     if (p->aistate == ps_hiding) {
 537         for (i = 0; i < DIRVECS; i++) {
 538             if (posdirs[i] == 0)
 539                 continue;
 540             score = vx * dirvecs[i].dx + vy * dirvecs[i].dy;
 541             if (score > highest) {
 542                 worst = i;
 543                 highest = score;
 544             }
 545             dir = i;
 546         }
 547         nrdirs--;
 548         posdirs[worst] = 0;
 549         highest = -(1 << 16);
 550     }
 551
 552     /* get last possible direction if all else fails */
 553     for (i = 0; i < DIRVECS; i++)
 554         if (posdirs[i] != 0)
 555             dir = i;
 556
 557     {
 558         long lvx = vx;
 559         long lvy = vy;
 560         pac_dot_vec (pp, p, &lvx, &lvy);
 561         vx = lvx;
 562         vy = lvy;
 563     }
 564
 565     if (vx != NOWHERE && vy != NOWHERE && pac_check_trace (p, vx, vy) > 0) {
 566         p->roundscore++;
 567         if (p->roundscore >= 12) {
 568             p->roundscore = 0;
 569             p->aistate = ps_random;
 570             pac_clear_trace (p);
 571         }
 572     }
 573     else
 574         p->roundscore = 0;
 575
 576     if (p->justate == 0)
 577         pac_save_trace (p, vx, vy);
 578
 579     for (i = 0; i < DIRVECS; i++) {
 580         if (posdirs[i] == 0)
 581             continue;
 582         score = dirvecs[i].dx * vx + dirvecs[i].dy * vy;
 583         if (check_dot (pp, p->col + dirvecs[i].dx,
 584                        p->row + dirvecs[i].dy) == 1) {
 585             if (dotfound == 0) {
 586                 highest = score;
 587                 dir = i;
 588                 dotfound = 1;
 589             }
 590             else if (score > highest) {
 591                 highest = score;
 592                 dir = i;
 593             }
 594         }
 595         else if (score > highest && dotfound == 0) {
 596             dir = i;
 597             highest = score;
 598         }
 599     }
 600
 601     p->nextrow = p->row + dirvecs[dir].dy;
 602     p->nextcol = p->col + dirvecs[dir].dx;
 603     p->lastbox = dir;
 604 }
 605
 606 #if 1
 607 /* Tries to catch the ghosts. */
 608 static void
 609 pac_chasing (pacmangamestruct * pp, pacmanstruct * p)
 610 {
 611     int posdirs[DIRVECS], nrdirs, i, highest = -(1 << 16),
 612         score, dir = 0, worst = 0;
 613     int vx = 0, vy = 0;
 614
 615     nrdirs = pac_get_posdirs (pp, p, posdirs);
 616
 617     /* keep directions which lead to ghosts */
 618     for (i = 0; i < DIRVECS; i++) {
 619         if (posdirs[i] == 0)
 620             continue;
 621         score = vx * dirvecs[i].dx + vy * dirvecs[i].dy;
 622         if (score < highest) {
 623             worst = i;
 624             highest = score;
 625         }
 626         dir = i;
 627     }
 628     nrdirs--;
 629     posdirs[worst] = 0;
 630
 631
 632     /* get last possible direction if all else fails */
 633     for (i = 0; i < DIRVECS; i++)
 634         if (posdirs[i] != 0)
 635             dir = i;
 636
 637     {
 638         long lvx = vx;
 639         long lvy = vy;
 640         pac_dot_vec (pp, p, &lvx, &lvy);
 641         vx = lvx;
 642         vy = lvy;
 643     }
 644
 645     if (vx != NOWHERE && vy != NOWHERE && pac_check_trace (p, vx, vy) > 0) {
 646         p->roundscore++;
 647         if (p->roundscore >= 12) {
 648             p->roundscore = 0;
 649             p->aistate = ps_random;
 650             pac_clear_trace (p);
 651         }
 652     }
 653     else
 654         p->roundscore = 0;
 655
 656
 657     p->nextrow = p->row + dirvecs[dir].dy;
 658     p->nextcol = p->col + dirvecs[dir].dx;
 659     p->lastbox = dir;
 660 }
 661 #endif
 662
 663 /* Goes completely random, but not in the opposite direction.  Used when a
 664    loop is detected. */
 665 static void
 666 pac_random (pacmangamestruct * pp, pacmanstruct * p)
 667 {
 668     int posdirs[DIRVECS], nrdirs, i, dir = -1, lastdir = 0;
 669
 670     if (pac_ghost_prox_and_vector (pp, p, NULL, NULL) < 5 * 5) {
 671         p->aistate = ps_hiding;
 672         p->state_change = 1;
 673     }
 674     if (NRAND (20) == 0) {
 675         p->aistate = ps_eating;
 676         p->state_change = 1;
 677         pac_clear_trace (p);
 678     }
 679
 680     nrdirs = pac_get_posdirs (pp, p, posdirs);
 681
 682     for (i = 0; i < DIRVECS; i++) {
 683         if (posdirs[i] == 0)
 684             continue;
 685         lastdir = i;
 686         if (check_dot (pp, p->col + dirvecs[i].dx,
 687                        p->row + dirvecs[i].dy) == 1) {
 688             dir = i;
 689             p->aistate = ps_eating;
 690             p->state_change = 1;
 691             pac_clear_trace (p);
 692             break;
 693         }
 694         else if (NRAND (nrdirs) == 0)
 695             dir = i;
 696     }
 697
 698     if (dir == -1)
 699         dir = lastdir;
 700
 701     p->nextrow = p->row + dirvecs[dir].dy;
 702     p->nextcol = p->col + dirvecs[dir].dx;
 703     p->lastbox = dir;
 704 }
 705
 706 static int
 707 pac_get_vector_screen (pacmangamestruct * pp, pacmanstruct * p,
 708                        const int x, const int y, int *vx, int *vy)
 709 {
 710     int lx, ly;
 711
 712     lx = (x - pp->xb) / pp->xs;
 713     ly = (y - pp->yb) / pp->ys;
 714
 715     if (lx < 0)
 716         lx = 0;
 717     else if ((unsigned int) lx > LEVWIDTH)
 718         lx = LEVWIDTH - 1;
 719
 720     if (ly < 0)
 721         ly = 0;
 722     else if ((unsigned int) ly > LEVHEIGHT)
 723         ly = LEVHEIGHT - 1;
 724
 725     *vx = lx - p->col;
 726     *vy = ly - p->row;
 727
 728     if (lx == p->oldlx && ly == p->oldly)
 729         return 0;
 730     p->oldlx = lx;
 731     p->oldly = ly;
 732     return 1;
 733 }
 734
 735 static int
 736 pac_trackmouse (ModeInfo * mi, pacmangamestruct * pp, pacmanstruct * p)
 737 {
 738     int dx, dy, cx, cy, vx, vy;
 739     unsigned int m;
 740     int posdirs[DIRVECS], i, dir = -1, highest = -(2 << 16), score;
 741     Window r, c;
 742
 743     (void) XQueryPointer (MI_DISPLAY (mi), MI_WINDOW (mi),
 744                           &r, &c, &dx, &dy, &cx, &cy, &m);
 745
 746     if (cx <= 0 || cy <= 0 ||
 747         cx >= MI_WIDTH (mi) - 1 || cy >= MI_HEIGHT (mi) - 1)
 748         return 0;
 749     /* get vector */
 750     p->state_change = pac_get_vector_screen (pp, p, cx, cy, &vx, &vy);
 751
 752     (void) pac_get_posdirs (pp, p, posdirs);
 753
 754     for (i = 0; i < DIRVECS; i++) {
 755         if (posdirs[i] == 0)
 756             continue;
 757         score = dirvecs[i].dx * vx + dirvecs[i].dy * vy;
 758         if (score > highest) {
 759             highest = score;
 760             dir = i;
 761         }
 762     }
 763
 764     p->nextrow = p->row + dirvecs[dir].dy;
 765     p->nextcol = p->col + dirvecs[dir].dx;
 766     p->lastbox = dir;
 767     return 1;
 768 }
 769
 770 /* Calls correct state function, and changes between states. */
 771 void
 772 ghost_update (pacmangamestruct * pp, ghoststruct * g)
 773 {
 774
 775     if (!(g->nextrow == NOWHERE && g->nextcol == NOWHERE)) {
 776         g->row = g->nextrow;
 777         g->col = g->nextcol;
 778     }
 779
 780     if ((g->aistate == randdir || g->aistate == chasing) && NRAND (10) == 0) {
 781         switch (NRAND (3)) {
 782         case 0:
 783             g->aistate = randdir;
 784             break;
 785         case 1:
 786             g->aistate = chasing;
 787             break;
 788         case 2:
 789             g->aistate = chasing;
 790             break;
 791         }
 792
 793     }
 794     else if (g->aistate == inbox) {
 795         if (g->timeleft < 0)
 796             g->aistate = goingout;
 797         else
 798             g->timeleft--;
 799
 800     }
 801     else if (g->aistate == goingout) {
 802         if (g->col < LEVWIDTH / 2 - JAILWIDTH / 2 ||
 803             g->col > LEVWIDTH / 2 + JAILWIDTH / 2 ||
 804             g->row < LEVHEIGHT / 2 - JAILHEIGHT / 2 ||
 805             g->row > LEVHEIGHT / 2 + JAILHEIGHT / 2)
 806             g->aistate = randdir;
 807     }
 808
 809     switch (g->aistate) {
 810     case inbox:
 811     case goingout:
 812     case randdir:
 813         ghost_random (pp, g);
 814         break;
 815     case chasing:
 816         ghost_chasing (pp, g);
 817         break;
 818     case hiding:
 819         ghost_hiding (pp, g);
 820         break;
 821     case goingin:
 822         if ( g->wait_pos ){
 823             find_home(pp, g);
 824             g->wait_pos = False;
 825         }
 826         ghost_goingin (pp, g);
 827         break;
 828     }
 829
 830     g->cfactor = GETFACTOR (g->nextcol, g->col);
 831     g->rfactor = GETFACTOR (g->nextrow, g->row);
 832 }
 833
 834 /* Calls correct pacman state function. */
 835 void
 836 pac_update (ModeInfo * mi, pacmangamestruct * pp, pacmanstruct * p)
 837 {
 838     if (!(p->nextrow == NOWHERE && p->nextcol == NOWHERE)) {
 839         p->row = p->nextrow;
 840         p->col = p->nextcol;
 841     }
 842
 843     if (pp->level[p->row * LEVWIDTH + p->col] == '.' ||
 844         pp->level[p->row * LEVWIDTH + p->col] == 'o') {
 845         pp->level[p->row * LEVWIDTH + p->col] = ' ';
 846         if (!trackmouse)
 847             p->justate = 1;
 848         pp->dotsleft--;
 849     }
 850     else if (!trackmouse) {
 851         p->justate = 0;
 852     }
 853
 854     if (!(trackmouse && pac_trackmouse (mi, pp, p))) {
 855         /* update pacman */
 856         switch (p->aistate) {
 857         case ps_eating:
 858             pac_eating (pp, p);
 859             break;
 860         case ps_hiding:
 861             pac_eating (pp, p);
 862             break;
 863         case ps_random:
 864             pac_random (pp, p);
 865             break;
 866         case ps_chasing:
 867             pac_chasing (pp, p);
 868             break;
 869         case ps_dieing:
 870             break; /* Don't move */
 871         }
 872     }
 873
 874     p->cfactor = GETFACTOR (p->nextcol, p->col);
 875     p->rfactor = GETFACTOR (p->nextrow, p->row);
 876 }