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, prox, worst = 0;
 613     int vx, vy;
 614
 615     prox = pac_ghost_prox_and_vector (pp, p, &vx, &vy);
 616
 617     nrdirs = pac_get_posdirs (pp, p, posdirs);
 618
 619     /* keep directions which lead to ghosts */
 620     for (i = 0; i < DIRVECS; i++) {
 621         if (posdirs[i] == 0)
 622             continue;
 623         score = vx * dirvecs[i].dx + vy * dirvecs[i].dy;
 624         if (score < highest) {
 625             worst = i;
 626             highest = score;
 627         }
 628         dir = i;
 629     }
 630     nrdirs--;
 631     posdirs[worst] = 0;
 632     highest = -(1 << 16);
 633
 634
 635     /* get last possible direction if all else fails */
 636     for (i = 0; i < DIRVECS; i++)
 637         if (posdirs[i] != 0)
 638             dir = i;
 639
 640     {
 641         long lvx = vx;
 642         long lvy = vy;
 643         pac_dot_vec (pp, p, &lvx, &lvy);
 644         vx = lvx;
 645         vy = lvy;
 646     }
 647
 648     if (vx != NOWHERE && vy != NOWHERE && pac_check_trace (p, vx, vy) > 0) {
 649         p->roundscore++;
 650         if (p->roundscore >= 12) {
 651             p->roundscore = 0;
 652             p->aistate = ps_random;
 653             pac_clear_trace (p);
 654         }
 655     }
 656     else
 657         p->roundscore = 0;
 658
 659
 660     p->nextrow = p->row + dirvecs[dir].dy;
 661     p->nextcol = p->col + dirvecs[dir].dx;
 662     p->lastbox = dir;
 663 }
 664 #endif
 665
 666 /* Goes completely random, but not in the opposite direction.  Used when a
 667    loop is detected. */
 668 static void
 669 pac_random (pacmangamestruct * pp, pacmanstruct * p)
 670 {
 671     int posdirs[DIRVECS], nrdirs, i, dir = -1, lastdir = 0;
 672
 673     if (pac_ghost_prox_and_vector (pp, p, NULL, NULL) < 5 * 5) {
 674         p->aistate = ps_hiding;
 675         p->state_change = 1;
 676     }
 677     if (NRAND (20) == 0) {
 678         p->aistate = ps_eating;
 679         p->state_change = 1;
 680         pac_clear_trace (p);
 681     }
 682
 683     nrdirs = pac_get_posdirs (pp, p, posdirs);
 684
 685     for (i = 0; i < DIRVECS; i++) {
 686         if (posdirs[i] == 0)
 687             continue;
 688         lastdir = i;
 689         if (check_dot (pp, p->col + dirvecs[i].dx,
 690                        p->row + dirvecs[i].dy) == 1) {
 691             dir = i;
 692             p->aistate = ps_eating;
 693             p->state_change = 1;
 694             pac_clear_trace (p);
 695             break;
 696         }
 697         else if (NRAND (nrdirs) == 0)
 698             dir = i;
 699     }
 700
 701     if (dir == -1)
 702         dir = lastdir;
 703
 704     p->nextrow = p->row + dirvecs[dir].dy;
 705     p->nextcol = p->col + dirvecs[dir].dx;
 706     p->lastbox = dir;
 707 }
 708
 709 static int
 710 pac_get_vector_screen (pacmangamestruct * pp, pacmanstruct * p,
 711                        const int x, const int y, int *vx, int *vy)
 712 {
 713     int lx, ly;
 714
 715     lx = (x - pp->xb) / pp->xs;
 716     ly = (y - pp->yb) / pp->ys;
 717
 718     if (lx < 0)
 719         lx = 0;
 720     else if ((unsigned int) lx > LEVWIDTH)
 721         lx = LEVWIDTH - 1;
 722
 723     if (ly < 0)
 724         ly = 0;
 725     else if ((unsigned int) ly > LEVHEIGHT)
 726         ly = LEVHEIGHT - 1;
 727
 728     *vx = lx - p->col;
 729     *vy = ly - p->row;
 730
 731     if (lx == p->oldlx && ly == p->oldly)
 732         return 0;
 733     p->oldlx = lx;
 734     p->oldly = ly;
 735     return 1;
 736 }
 737
 738 static int
 739 pac_trackmouse (ModeInfo * mi, pacmangamestruct * pp, pacmanstruct * p)
 740 {
 741     int dx, dy, cx, cy, vx, vy;
 742     unsigned int m;
 743     int posdirs[DIRVECS], i, dir = -1, highest = -(2 << 16), score;
 744     Window r, c;
 745
 746     (void) XQueryPointer (MI_DISPLAY (mi), MI_WINDOW (mi),
 747                           &r, &c, &dx, &dy, &cx, &cy, &m);
 748
 749     if (cx <= 0 || cy <= 0 ||
 750         cx >= MI_WIDTH (mi) - 1 || cy >= MI_HEIGHT (mi) - 1)
 751         return 0;
 752     /* get vector */
 753     p->state_change = pac_get_vector_screen (pp, p, cx, cy, &vx, &vy);
 754
 755     (void) pac_get_posdirs (pp, p, posdirs);
 756
 757     for (i = 0; i < DIRVECS; i++) {
 758         if (posdirs[i] == 0)
 759             continue;
 760         score = dirvecs[i].dx * vx + dirvecs[i].dy * vy;
 761         if (score > highest) {
 762             highest = score;
 763             dir = i;
 764         }
 765     }
 766
 767     p->nextrow = p->row + dirvecs[dir].dy;
 768     p->nextcol = p->col + dirvecs[dir].dx;
 769     p->lastbox = dir;
 770     return 1;
 771 }
 772
 773 /* Calls correct state function, and changes between states. */
 774 void
 775 ghost_update (pacmangamestruct * pp, ghoststruct * g)
 776 {
 777
 778     if (!(g->nextrow == NOWHERE && g->nextcol == NOWHERE)) {
 779         g->row = g->nextrow;
 780         g->col = g->nextcol;
 781     }
 782
 783     if ((g->aistate == randdir || g->aistate == chasing) && NRAND (10) == 0) {
 784         switch (NRAND (3)) {
 785         case 0:
 786             g->aistate = randdir;
 787             break;
 788         case 1:
 789             g->aistate = chasing;
 790             break;
 791         case 2:
 792             g->aistate = chasing;
 793             break;
 794         }
 795
 796     }
 797     else if (g->aistate == inbox) {
 798         if (g->timeleft < 0)
 799             g->aistate = goingout;
 800         else
 801             g->timeleft--;
 802
 803     }
 804     else if (g->aistate == goingout) {
 805         if (g->col < LEVWIDTH / 2 - JAILWIDTH / 2 ||
 806             g->col > LEVWIDTH / 2 + JAILWIDTH / 2 ||
 807             g->row < LEVHEIGHT / 2 - JAILHEIGHT / 2 ||
 808             g->row > LEVHEIGHT / 2 + JAILHEIGHT / 2)
 809             g->aistate = randdir;
 810     }
 811
 812     switch (g->aistate) {
 813     case inbox:
 814     case goingout:
 815     case randdir:
 816         ghost_random (pp, g);
 817         break;
 818     case chasing:
 819         ghost_chasing (pp, g);
 820         break;
 821     case hiding:
 822         ghost_hiding (pp, g);
 823         break;
 824     case goingin:
 825         if ( g->wait_pos ){
 826             find_home(pp, g);
 827             g->wait_pos = False;
 828         }
 829         ghost_goingin (pp, g);
 830         break;
 831     }
 832
 833     g->cfactor = GETFACTOR (g->nextcol, g->col);
 834     g->rfactor = GETFACTOR (g->nextrow, g->row);
 835 }
 836
 837 /* Calls correct pacman state function. */
 838 void
 839 pac_update (ModeInfo * mi, pacmangamestruct * pp, pacmanstruct * p)
 840 {
 841     if (!(p->nextrow == NOWHERE && p->nextcol == NOWHERE)) {
 842         p->row = p->nextrow;
 843         p->col = p->nextcol;
 844     }
 845
 846     if (pp->level[p->row * LEVWIDTH + p->col] == '.' ||
 847         pp->level[p->row * LEVWIDTH + p->col] == 'o') {
 848         pp->level[p->row * LEVWIDTH + p->col] = ' ';
 849         if (!trackmouse)
 850             p->justate = 1;
 851         pp->dotsleft--;
 852     }
 853     else if (!trackmouse) {
 854         p->justate = 0;
 855     }
 856
 857     if (!(trackmouse && pac_trackmouse (mi, pp, p))) {
 858         /* update pacman */
 859         switch (p->aistate) {
 860         case ps_eating:
 861             pac_eating (pp, p);
 862             break;
 863         case ps_hiding:
 864             pac_eating (pp, p);
 865             break;
 866         case ps_random:
 867             pac_random (pp, p);
 868             break;
 869         case ps_chasing:
 870             pac_chasing (pp, p);
 871             break;
 872         case ps_dieing:
 873             break; /* Don't move */
 874         }
 875     }
 876
 877     p->cfactor = GETFACTOR (p->nextcol, p->col);
 878     p->rfactor = GETFACTOR (p->nextrow, p->row);
 879 }