1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
3 * Copyright (c) 2002 by Edwin de Jong <mauddib@gmx.net>.
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.
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.
18 /* this file handles the AI of the ghosts and the pacman. */
23 #include "pacman_ai.h"
24 #include "pacman_level.h"
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)
35 } dirvecs[DIRVECS] = { {
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;
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. */
50 ghost_get_posdirs (pacmangamestruct * pp, int *posdirs, ghoststruct * g)
52 unsigned int i, nrdirs = 0;
53 unsigned int can_go_in = 0;
55 /* bit of black magic here */
56 for (i = 0; i < DIRVECS; i++) {
58 if (g->lastbox != NOWHERE && i == (g->lastbox + 2) % DIRVECS
59 && (g->aistate != goingout )) {
63 if (g->aistate == goingout && i == 1) {
67 /* check if possible direction */
68 can_go_in = (g->aistate == goingout || g->aistate == goingin);
70 check_pos (pp, g->row + dirvecs[i].dy,
71 g->col + dirvecs[i].dx,
72 can_go_in)) == True) {
80 /* Directs ghost to a random direction, exluding opposite (except in the
81 impossible situation that there is only one valid direction). */
83 ghost_random (pacmangamestruct * pp, ghoststruct * g)
85 int posdirs[DIRVECS], nrdirs = 0, i, dir = 0;
87 nrdirs = ghost_get_posdirs (pp, posdirs, g);
91 for (i = 0; i < DIRVECS; i++)
92 if (posdirs[i] == True)
96 dir = (g->lastbox + 2) % DIRVECS;
98 for (i = 0; i < DIRVECS; i++) {
99 if (posdirs[i] == True && NRAND (nrdirs) == 0) {
105 g->nextrow = g->row + dirvecs[dir].dy;
106 g->nextcol = g->col + dirvecs[dir].dx;
110 /* Determines best direction to chase the pacman and goes that direction. */
112 ghost_chasing (pacmangamestruct * pp, ghoststruct * g)
114 int posdirs[DIRVECS], nrdirs = 0, i, dir = 0, highest = -100000,
115 thisvecx, thisvecy, thisvec;
117 nrdirs = ghost_get_posdirs (pp, posdirs, g);
121 for (i = 0; i < DIRVECS; i++)
122 if (posdirs[i] == True)
126 dir = (g->lastbox + 2) % DIRVECS;
128 for (i = 0; i < DIRVECS; i++) {
129 if (posdirs[i] == False)
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) {
140 g->nextrow = g->row + dirvecs[dir].dy;
141 g->nextcol = g->col + dirvecs[dir].dx;
145 /* Determines the best direction to go away from the pacman, and goes that
148 ghost_hiding (pacmangamestruct * pp, ghoststruct * g)
150 int posdirs[DIRVECS], nrdirs = 0, i, dir = 0, highest = -100000,
151 thisvecx, thisvecy, thisvec;
153 nrdirs = ghost_get_posdirs (pp, posdirs, g);
157 for (i = 0; i < DIRVECS; i++)
158 if (posdirs[i] == True)
162 dir = (g->lastbox + 2) % DIRVECS;
164 for (i = 0; i < DIRVECS; i++) {
165 if (posdirs[i] == False)
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)
174 g->nextrow = g->row + dirvecs[dir].dy;
175 g->nextcol = g->col + dirvecs[dir].dx;
181 clear_trace(ghoststruct *g)
185 while (i < GHOST_TRACE){
187 g->trace[i++].vy = -1;
193 save_position (ghoststruct *g, int x, int y)
195 int i = g->trace_idx;
196 assert ( 0 <= i && i < GHOST_TRACE );
203 already_tried (ghoststruct *g, int x, int y)
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 );
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); */
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;
235 clear_dir ( ghoststruct *g ){
239 while (i < GHOST_TRACE){
240 g->way_home[i].vx = -1;
241 g->way_home[i++].vy = -1;
246 found_jail ( int col, int row ){
248 get_jail_opening ( &cx, &cy );
250 if (row == cy && col == cx )
257 move_ghost ( pacmangamestruct * pp,
260 int *new_row, int *new_col){
262 int tr = row + dirvecs[idx].dx;
263 int tc = col + dirvecs[idx].dy;
264 if ( check_pos ( pp, tr, tc, True )){
275 recur_back_track ( pacmangamestruct * pp, ghoststruct *g, int row, int col ){
276 int new_row, new_col;
278 if ( already_tried ( g, col, row ) )
281 if ( found_jail ( col, row ) )
284 save_position ( g, col, row );
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 );
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 );
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 );
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 );
314 find_home ( pacmangamestruct *pp, ghoststruct *g ){
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.");
324 tmp_ghost = memmove(tmp_ghost, g, sizeof ( ghoststruct ));
325 if ( tmp_ghost == NULL ){
326 fprintf(stderr, "find_home : Could not copy memory.");
329 clear_trace ( tmp_ghost );
330 clear_dir ( tmp_ghost );
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);
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;
342 g->home_count = tmp_ghost->home_count;
343 g->home_idx = tmp_ghost->home_count;
347 /* Make the ghost go back to the inbox */
349 ghost_goingin (pacmangamestruct * pp, ghoststruct * g)
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;
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). */
363 pac_dot_vec (pacmangamestruct * pp, pacmanstruct * p, long *vx, long *vy)
365 int x, y, bx = 0, by = 0, ex = LEVWIDTH, ey = LEVHEIGHT;
366 long dx, dy, dist, top = 0;
369 int rnr = NRAND (50);
370 /* determine begin and end vectors */
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;
397 *vx += (dx * ((long) LEVWIDTH * (long) LEVHEIGHT))
399 *vy += (dy * ((long) LEVWIDTH * (long) LEVHEIGHT))
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). */
407 pac_ghost_prox_and_vector (pacmangamestruct * pp, pacmanstruct * p,
410 int dx, dy, dist, closest = 100000;
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)
421 dx = pp->ghosts[g].col + /*dirvecs[pp->ghosts[g].lastbox].dx */ -
423 dy = pp->ghosts[g].row + /*dirvecs[pp->ghosts[g].lastbox].dy */ -
425 dist = dx * dx + dy * dy;
426 if (dist < closest) {
437 /* fills array of DIRVECS size with possible directions, returns number of
438 directions. posdirs should point to an array of 4 integers. */
440 pac_get_posdirs (pacmangamestruct * pp, pacmanstruct * p, int *posdirs)
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) {
453 else if ((posdirs[i] =
454 check_pos (pp, p->row + dirvecs[i].dy,
455 p->col + dirvecs[i].dx, 0)) == 1)
463 /* Clears the trace of vectors. */
465 pac_clear_trace (pacmanstruct * p)
469 for (i = 0; i < TRACEVECS; i++) {
470 p->trace[i].vx = NOWHERE;
471 p->trace[i].vy = NOWHERE;
476 /* Adds a new vector to the trace. */
478 pac_save_trace (pacmanstruct * p, const int vx, const int vy)
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;
487 /* Check if a vector can be found in the trace. */
489 pac_check_trace (const pacmanstruct * p, const int vx, const int vy)
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)
497 if (p->trace[curel].vx == vx && p->trace[curel].vy == vy)
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). */
510 pac_eating (pacmangamestruct * pp, pacmanstruct * p)
512 int posdirs[DIRVECS], nrdirs, i, highest = -(1 << 16),
513 score, dir = 0, dotfound = 0, prox, worst = 0;
516 if ((prox = pac_ghost_prox_and_vector (pp, p, &vx, &vy)) <
517 4 * 4 && p->aistate == ps_eating) {
518 p->aistate = ps_hiding;
523 if (prox > 6 * 6 && p->aistate == ps_hiding) {
524 p->aistate = ps_eating;
533 nrdirs = pac_get_posdirs (pp, p, posdirs);
535 /* remove directions which lead to ghosts */
536 if (p->aistate == ps_hiding) {
537 for (i = 0; i < DIRVECS; i++) {
540 score = vx * dirvecs[i].dx + vy * dirvecs[i].dy;
541 if (score > highest) {
549 highest = -(1 << 16);
552 /* get last possible direction if all else fails */
553 for (i = 0; i < DIRVECS; i++)
560 pac_dot_vec (pp, p, &lvx, &lvy);
565 if (vx != NOWHERE && vy != NOWHERE && pac_check_trace (p, vx, vy) > 0) {
567 if (p->roundscore >= 12) {
569 p->aistate = ps_random;
577 pac_save_trace (p, vx, vy);
579 for (i = 0; i < DIRVECS; i++) {
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) {
590 else if (score > highest) {
595 else if (score > highest && dotfound == 0) {
601 p->nextrow = p->row + dirvecs[dir].dy;
602 p->nextcol = p->col + dirvecs[dir].dx;
607 /* Tries to catch the ghosts. */
609 pac_chasing (pacmangamestruct * pp, pacmanstruct * p)
611 int posdirs[DIRVECS], nrdirs, i, highest = -(1 << 16),
612 score, dir = 0, prox, worst = 0;
615 prox = pac_ghost_prox_and_vector (pp, p, &vx, &vy);
617 nrdirs = pac_get_posdirs (pp, p, posdirs);
619 /* keep directions which lead to ghosts */
620 for (i = 0; i < DIRVECS; i++) {
623 score = vx * dirvecs[i].dx + vy * dirvecs[i].dy;
624 if (score < highest) {
632 highest = -(1 << 16);
635 /* get last possible direction if all else fails */
636 for (i = 0; i < DIRVECS; i++)
643 pac_dot_vec (pp, p, &lvx, &lvy);
648 if (vx != NOWHERE && vy != NOWHERE && pac_check_trace (p, vx, vy) > 0) {
650 if (p->roundscore >= 12) {
652 p->aistate = ps_random;
660 p->nextrow = p->row + dirvecs[dir].dy;
661 p->nextcol = p->col + dirvecs[dir].dx;
666 /* Goes completely random, but not in the opposite direction. Used when a
669 pac_random (pacmangamestruct * pp, pacmanstruct * p)
671 int posdirs[DIRVECS], nrdirs, i, dir = -1, lastdir = 0;
673 if (pac_ghost_prox_and_vector (pp, p, NULL, NULL) < 5 * 5) {
674 p->aistate = ps_hiding;
677 if (NRAND (20) == 0) {
678 p->aistate = ps_eating;
683 nrdirs = pac_get_posdirs (pp, p, posdirs);
685 for (i = 0; i < DIRVECS; i++) {
689 if (check_dot (pp, p->col + dirvecs[i].dx,
690 p->row + dirvecs[i].dy) == 1) {
692 p->aistate = ps_eating;
697 else if (NRAND (nrdirs) == 0)
704 p->nextrow = p->row + dirvecs[dir].dy;
705 p->nextcol = p->col + dirvecs[dir].dx;
710 pac_get_vector_screen (pacmangamestruct * pp, pacmanstruct * p,
711 const int x, const int y, int *vx, int *vy)
715 lx = (x - pp->xb) / pp->xs;
716 ly = (y - pp->yb) / pp->ys;
720 else if ((unsigned int) lx > LEVWIDTH)
725 else if ((unsigned int) ly > LEVHEIGHT)
731 if (lx == p->oldlx && ly == p->oldly)
739 pac_trackmouse (ModeInfo * mi, pacmangamestruct * pp, pacmanstruct * p)
741 int dx, dy, cx, cy, vx, vy;
743 int posdirs[DIRVECS], i, dir = -1, highest = -(2 << 16), score;
746 (void) XQueryPointer (MI_DISPLAY (mi), MI_WINDOW (mi),
747 &r, &c, &dx, &dy, &cx, &cy, &m);
749 if (cx <= 0 || cy <= 0 ||
750 cx >= MI_WIDTH (mi) - 1 || cy >= MI_HEIGHT (mi) - 1)
753 p->state_change = pac_get_vector_screen (pp, p, cx, cy, &vx, &vy);
755 (void) pac_get_posdirs (pp, p, posdirs);
757 for (i = 0; i < DIRVECS; i++) {
760 score = dirvecs[i].dx * vx + dirvecs[i].dy * vy;
761 if (score > highest) {
767 p->nextrow = p->row + dirvecs[dir].dy;
768 p->nextcol = p->col + dirvecs[dir].dx;
773 /* Calls correct state function, and changes between states. */
775 ghost_update (pacmangamestruct * pp, ghoststruct * g)
778 if (!(g->nextrow == NOWHERE && g->nextcol == NOWHERE)) {
783 if ((g->aistate == randdir || g->aistate == chasing) && NRAND (10) == 0) {
786 g->aistate = randdir;
789 g->aistate = chasing;
792 g->aistate = chasing;
797 else if (g->aistate == inbox) {
799 g->aistate = goingout;
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;
812 switch (g->aistate) {
816 ghost_random (pp, g);
819 ghost_chasing (pp, g);
822 ghost_hiding (pp, g);
829 ghost_goingin (pp, g);
833 g->cfactor = GETFACTOR (g->nextcol, g->col);
834 g->rfactor = GETFACTOR (g->nextrow, g->row);
837 /* Calls correct pacman state function. */
839 pac_update (ModeInfo * mi, pacmangamestruct * pp, pacmanstruct * p)
841 if (!(p->nextrow == NOWHERE && p->nextcol == NOWHERE)) {
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] = ' ';
853 else if (!trackmouse) {
857 if (!(trackmouse && pac_trackmouse (mi, pp, p))) {
859 switch (p->aistate) {
873 break; /* Don't move */
877 p->cfactor = GETFACTOR (p->nextcol, p->col);
878 p->rfactor = GETFACTOR (p->nextrow, p->row);