http://www.jwz.org/xscreensaver/xscreensaver-5.10.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              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 }