2 * Copyright (c) 2002 by Edwin de Jong <mauddib@gmx.net>.
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.
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.
17 /* this file handles the AI of the ghosts and the pacman. */
20 #include "pacman_ai.h"
21 #include "pacman_level.h"
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)
29 static const struct { int dx, dy; } dirvecs[DIRVECS] =
30 { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
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. */
38 ghost_get_posdirs(pacmangamestruct *pp, int *posdirs, ghoststruct *g)
40 unsigned int i, nrdirs = 0;
42 /* bit of black magic here */
43 for (i = 0; i < DIRVECS; i++) {
45 if (g->lastbox != NOWHERE && i == (g->lastbox + 2) % DIRVECS
46 && g->aistate != goingout) {
50 if (g->aistate == goingout && i == 1) {
54 /* check if possible direction */
56 check_pos(pp, g->row + dirvecs[i].dy,
57 g->col + dirvecs[i].dx,
58 g->aistate == goingout ? True : False)) ==
67 /* Directs ghost to a random direction, exluding opposite (except in the
68 impossible situation that there is only one valid direction). */
70 ghost_random(pacmangamestruct *pp, ghoststruct *g)
72 int posdirs[DIRVECS], nrdirs = 0, i, dir = 0;
74 nrdirs = ghost_get_posdirs(pp, posdirs, g);
75 for (i = 0; i < DIRVECS; i++)
76 if (posdirs[i] == True) dir = i;
78 if (nrdirs == 0) dir = (g->lastbox + 2) % DIRVECS;
80 for (i = 0; i < DIRVECS; i++) {
81 if (posdirs[i] == True && NRAND(nrdirs) == 0) {
87 g->nextrow = g->row + dirvecs[dir].dy;
88 g->nextcol = g->col + dirvecs[dir].dx;
92 /* Determines best direction to chase the pacman and goes that direction. */
94 ghost_chasing(pacmangamestruct *pp, ghoststruct *g)
96 int posdirs[DIRVECS], nrdirs = 0, i, dir = 0, highest = -100000,
97 thisvecx, thisvecy, thisvec;
99 nrdirs = ghost_get_posdirs(pp, posdirs, g);
100 for (i = 0; i < DIRVECS; i++)
101 if (posdirs[i] == True) dir = i;
103 if (nrdirs == 0) dir = (g->lastbox + 2) % DIRVECS;
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) {
116 g->nextrow = g->row + dirvecs[dir].dy;
117 g->nextcol = g->col + dirvecs[dir].dx;
121 /* Determines the best direction to go away from the pacman, and goes that
124 ghost_hiding(pacmangamestruct *pp, ghoststruct *g)
126 int posdirs[DIRVECS], nrdirs = 0, i, dir = 0, highest = -100000,
127 thisvecx, thisvecy, thisvec;
129 nrdirs = ghost_get_posdirs(pp, posdirs, g);
130 for (i = 0; i < DIRVECS; i++)
131 if (posdirs[i] == True) dir = i;
133 if (nrdirs == 0) dir = (g->lastbox + 2) % DIRVECS;
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)
144 g->nextrow = g->row + dirvecs[dir].dy;
145 g->nextcol = g->col + dirvecs[dir].dx;
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). */
153 pac_dot_vec(pacmangamestruct *pp, pacmanstruct *p, long *vx, long *vy)
155 int x, y, bx = 0, by = 0, ex = LEVWIDTH, ey = LEVHEIGHT;
156 long dx, dy, dist, top = 0;
160 /* determine begin and end vectors */
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;
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;
179 *vx += (dx * ((long)LEVWIDTH * (long)LEVHEIGHT))
181 *vy += (dy * ((long)LEVWIDTH * (long)LEVHEIGHT))
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). */
189 pac_ghost_prox_and_vector(pacmangamestruct *pp, pacmanstruct *p,
192 int dx, dy, dist, closest = 100000;
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)
203 dx = pp->ghosts[g].col + /*dirvecs[pp->ghosts[g].lastbox].dx*/ -
205 dy = pp->ghosts[g].row + /*dirvecs[pp->ghosts[g].lastbox].dy*/ -
207 dist = dx * dx + dy * dy;
208 if (dist < closest) {
218 /* fills array of DIRVECS size with possible directions, returns number of
219 directions. posdirs should point to an array of 4 integers. */
221 pac_get_posdirs(pacmangamestruct *pp, pacmanstruct *p, int *posdirs)
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) {
234 } else if ((posdirs[i] =
235 check_pos(pp, p->row + dirvecs[i].dy,
236 p->col + dirvecs[i].dx, 0)) == 1)
244 /* Clears the trace of vectors. */
246 pac_clear_trace(pacmanstruct *p)
250 for(i = 0; i < TRACEVECS; i++) {
251 p->trace[i].vx = NOWHERE; p->trace[i].vy = NOWHERE;
256 /* Adds a new vector to the trace. */
258 pac_save_trace(pacmanstruct *p, const int vx, const int vy)
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;
267 /* Check if a vector can be found in the trace. */
269 pac_check_trace(const pacmanstruct *p, const int vx, const int vy)
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)
278 if (p->trace[curel].vx == vx &&
279 p->trace[curel].vy == vy)
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). */
292 pac_eating(pacmangamestruct *pp, pacmanstruct *p)
294 int posdirs[DIRVECS], nrdirs, i, highest = -(1 << 16),
295 score, dir = 0, dotfound = 0, prox, worst = 0;
298 if ((prox = pac_ghost_prox_and_vector(pp, p, &vx, &vy)) <
299 4 * 4 && p->aistate == ps_eating) {
300 p->aistate = ps_hiding;
305 if (prox > 6 * 6 && p->aistate == ps_hiding) {
306 p->aistate = ps_eating;
307 if (p->justate == 0) p->state_change = 1;
311 if (prox < 3 * 3) p->state_change = 1;
313 nrdirs = pac_get_posdirs(pp, p, posdirs);
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) {
328 highest = -(1 << 16);
331 /* get last possible direction if all else fails */
332 for (i = 0; i < DIRVECS; i++)
333 if (posdirs[i] != 0) dir = i;
338 pac_dot_vec(pp, p, &lvx, &lvy);
343 if (vx != NOWHERE && vy != NOWHERE && pac_check_trace(p, vx, vy) > 0) {
345 if (p->roundscore >= 12) {
347 p->aistate = ps_random;
353 if (p->justate == 0) pac_save_trace(p, vx, vy);
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) {
364 } else if (score > highest) {
368 } else if (score > highest && dotfound == 0) {
374 p->nextrow = p->row + dirvecs[dir].dy;
375 p->nextcol = p->col + dirvecs[dir].dx;
380 /* Tries to catch the ghosts. */
382 pac_chasing(pacmangamestruct *pp, pacmanstruct *p)
387 /* Goes completely random, but not in the opposite direction. Used when a
390 pac_random(pacmangamestruct *pp, pacmanstruct *p)
392 int posdirs[DIRVECS], nrdirs, i, dir = -1, lastdir = 0;
394 if (pac_ghost_prox_and_vector(pp, p, NULL, NULL) < 5 * 5) {
395 p->aistate = ps_hiding;
398 if (NRAND(20) == 0) {
399 p->aistate = ps_eating;
404 nrdirs = pac_get_posdirs(pp, p, posdirs);
406 for (i = 0; i < DIRVECS; i++) {
407 if (posdirs[i] == 0) continue;
409 if (check_dot(pp, p->col + dirvecs[i].dx,
410 p->row + dirvecs[i].dy) == 1) {
412 p->aistate = ps_eating;
416 } else if (NRAND(nrdirs) == 0)
420 if (dir == -1) dir = lastdir;
422 p->nextrow = p->row + dirvecs[dir].dy;
423 p->nextcol = p->col + dirvecs[dir].dx;
428 pac_get_vector_screen(pacmangamestruct *pp, pacmanstruct *p,
429 const int x, const int y, int *vx, int *vy)
433 lx = (x - pp->xb) / pp->xs;
434 ly = (y - pp->yb) / pp->ys;
437 else if ((unsigned int) lx > LEVWIDTH) lx = LEVWIDTH - 1;
440 else if ((unsigned int) ly > LEVHEIGHT) ly = LEVHEIGHT - 1;
445 if (lx == p->oldlx && ly == p->oldly) return 0;
446 p->oldlx = lx; p->oldly = ly;
451 pac_trackmouse(ModeInfo * mi, pacmangamestruct *pp, pacmanstruct *p)
453 int dx, dy, cx, cy, vx, vy;
455 int posdirs[DIRVECS], i, dir = -1, highest = -(2 << 16), score;
458 (void) XQueryPointer(MI_DISPLAY(mi), MI_WINDOW(mi),
459 &r, &c, &dx, &dy, &cx, &cy, &m);
461 if (cx <= 0 || cy <= 0 ||
462 cx >= MI_WIDTH(mi) - 1 ||
463 cy >= MI_HEIGHT(mi) - 1)
466 p->state_change = pac_get_vector_screen(pp, p, cx, cy, &vx, &vy);
468 (void) pac_get_posdirs(pp, p, posdirs);
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) {
479 p->nextrow = p->row + dirvecs[dir].dy;
480 p->nextcol = p->col + dirvecs[dir].dx;
485 /* Calls correct state function, and changes between states. */
487 ghost_update(pacmangamestruct *pp, ghoststruct *g)
490 if (!(g->nextrow == NOWHERE && g->nextcol == NOWHERE)) {
496 if (g->dead == True) /* dead ghosts are dead,
497 so they don't run around */
500 if ((g->aistate == randdir || g->aistate == chasing) &&
504 g->aistate = randdir; break;
506 g->aistate = chasing; break;
508 g->aistate = chasing; break;
511 } else if (g->aistate == inbox) {
513 g->aistate = goingout;
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;
525 switch (g->aistate) {
532 ghost_chasing(pp, g);
539 g->cfactor = GETFACTOR(g->nextcol, g->col);
540 g->rfactor = GETFACTOR(g->nextrow, g->row);
543 /* Calls correct pacman state function. */
545 pac_update(ModeInfo *mi, pacmangamestruct *pp, pacmanstruct *p)
547 if (!(p->nextrow == NOWHERE && p->nextcol == NOWHERE)) {
552 if (pp->level[p->row * LEVWIDTH + p->col] == '.') {
553 pp->level[p->row * LEVWIDTH + p->col] = ' ';
557 } else if (!trackmouse) {
561 if (!(trackmouse && pac_trackmouse(mi, pp, p))) {
563 switch (p->aistate) {
581 p->cfactor = GETFACTOR(p->nextcol, p->col);
582 p->rfactor = GETFACTOR(p->nextrow, p->row);