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