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