From http://www.jwz.org/xscreensaver/xscreensaver-5.30.tar.gz
[xscreensaver] / 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              pacman_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     pacman_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 ( pacman_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         pacman_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 (pacman_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                   pacman_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 pacman_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         pacman_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         pacman_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             pacman_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 (pacman_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             pacman_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         pacman_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 (pacman_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             pacman_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 pacman_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 pacman_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 (!pacman_trackmouse)
847             p->justate = 1;
848         pp->dotsleft--;
849     }
850     else if (!pacman_trackmouse) {
851         p->justate = 0;
852     }
853
854     if (!(pacman_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 }