1 /* This program was written by Alexander Siegel in September of 1989   */
2 /* at Cornell University.  It may may copied freely for private use or */
3 /* public dispersion provided that this comment is not removed.  This  */
4 /* program, any portion of this program, or any derivative of this     */
5 /* program may not be sold or traded for financial gain.               */
6 
7 #include <stdio.h>
8 #include <X11/Xlib.h>
9 #include <X11/keysym.h>
10 #include <golddig.h>
11 
12 #define MAXBADGUY 30     /* Maximum number of bad guys */
13 #define MAXBADSCORE 20   /* Maximum amount of score given for */
14                          /* killing bad guys */
15 int numbadguy = 0;       /* Total number of bad guys. */
16 struct thing_s badguys[MAXBADGUY];  /* Array describing state of all */
17                                     /* bad guys */
18 char movetree[MAXLEVEL]; /* Direction that badguy should go at each location */
19 int badscore;            /* Score given during current level due to */
20                          /* killing bad guys */
21 
22 /* Graphics cursors for drawing the possible states of the badguys */
23 extern GC badguy1gc,badguy2gc,badguy3gc;
24 
25 /* Initialize data structure for bad guys from level data */
start_badguy()26 void start_badguy()
27 {
28   register int x,y,pos;
29 
30   /* Reset the limit on bad guy score given */
31   badscore = 0;
32   /* Initialize number of bad guys to 0 */
33   numbadguy = 0;
34   pos = 0;
35   /* Iterate through each position in level array */
36   for(x=0;x<xsize;++x)
37     for(y=0;y<ysize;++y) {
38       /* Check if level holds a bad guys block at that position */
39       if(level[pos] == BADGUY) {
40         /* Replace bad guys block with space */
41         level[pos] = SPACE;
42         if(numbadguy < MAXBADGUY) {
43           /* Add bad guy to global array.  Note the multiplication by */
44           /* 2 when producing position. */
45           badguys[numbadguy].xstart = badguys[numbadguy].xpos = x << 1;
46           badguys[numbadguy].ystart = badguys[numbadguy].ypos = y << 1;
47           badguys[numbadguy].dir = STAND;
48           /* Bad guys start holding nothing */
49           badguys[numbadguy].hold = SPACE;
50           numbadguy ++;
51         }
52       }
53       pos ++;
54     }
55 }
56 
57 /* Draw all the bad guys out to the game window */
draw_badguys()58 void draw_badguys()
59 {
60   register int i;
61   GC drawgc;
62 
63   /* Iterate through each bad guy */
64   for(i=0;i<numbadguy;++i) {
65     /* If bad guy is horizontally offset, use the second graphics */
66     /* cursor */
67     if(badguys[i].xpos & 1)
68       drawgc = badguy2gc;
69     /* If bad guy is vertically offset, use the third graphics cursor */
70     else if(badguys[i].ypos & 1)
71       drawgc = badguy3gc;
72     /* Otherwise use the normal graphics cursor */
73     else
74       drawgc = badguy1gc;
75     /* Fill rectangle surrounding bad guy */
76     XFillRectangle(disp,wind,drawgc,badguys[i].xpos << 3,
77                    badguys[i].ypos << 3,16,16);
78   }
79 }
80 
81 /* Return 1 if the specified position overlaps a bad guy, 0 otherwise. */
82 /* Another parameter is provided so that this routine can ignore one */
83 /* bad guy. */
overlap_badguy(x,y,num)84 int overlap_badguy(x,y,num)
85 register int x,y;   /* Position which will be checked for overlap. */
86 register int num;   /* Number of bad guy to ignore.  Use a -1 for no */
87                     /* ignoring. */
88 {
89   register int i,d;
90 
91   /* Iterate through each bad guy */
92   for(i=0;i<numbadguy;++i) {
93     /* If this bad guy is the one that I am supposed to ignore, */
94     /* continue to the next */
95     if(i == num)
96       continue;
97     /* Compute horizontal distance between position and bad guy and */
98     /* check it.  Things are two positions wide in each direction */
99     d = x - badguys[i].xpos;
100     if(d < -1 || d > 1)
101       continue;
102     /* Check vertical distance */
103     d = y - badguys[i].ypos;
104     if(d < -1 || d > 1)
105       continue;
106     /* Found overlap, return a 1 */
107     return(1);
108   }
109   /* Could not find overlap */
110   return(0);
111 }
112 
113 /* Erase and redraw all badguys who have moved in the previous */
114 /* movement.  Movement is detected when (xpos,ypos) is different from */
115 /* (xold,yold). */
drawmove_badguys()116 void drawmove_badguys()
117 {
118   register int x,y,i;
119   GC drawgc;
120 
121   /* iterate through each bad guy */
122   for(i=0;i<numbadguy;++i) {
123     /* do not erase bad guys who did not move */
124     if(! badguys[i].redraw)
125       continue;
126     /* get position of bad guy in normal coordinates */
127     x = badguys[i].xold >> 1;
128     y = badguys[i].yold >> 1;
129     /* draw block underneath bad guy */
130     draw_block(x,y);
131     /* if horizontally offset, draw block to the right */
132     if(badguys[i].xold & 1)
133       draw_block(x + 1,y);
134     /* if vertically offset, draw block below */
135     if(badguys[i].yold & 1)
136       draw_block(x,y + 1);
137   }
138 
139   /* iterate through each bad guy */
140   for(i=0;i<numbadguy;++i) {
141     /* do not draw bad guys who did not move */
142     if(! badguys[i].redraw)
143       continue;
144     /* Put badguy coordinates in registers */
145     x = badguys[i].xpos;
146     y = badguys[i].ypos;
147     /* if bad guy is horizontally offset, use the second graphics */
148     /* cursor */
149     if(x & 1)
150       drawgc = badguy2gc;
151     /* If bad guy is vertically offset, use the third graphics cursor */
152     else if(y & 1)
153       drawgc = badguy3gc;
154     /* Otherwise use the normal graphics cursor */
155     else
156       drawgc = badguy1gc;
157     /* Fill rectangle surrounding bad guy */
158     XFillRectangle(disp,wind,drawgc,x << 3,y << 3,16,16);
159   }
160 }
161 
162 /* Maximum size for FIFO queue used by breadth first search algorithm */
163 #define QSIZE 1000
164 
165 /* Regenerate the movement tree used by bad guys when determining */
166 /* movement.  The basic algorithm is a breadth first search of the */
167 /* graph produced by interpreting the moveallow array as a directed */
168 /* graph.  The root of the tree is the player position.  The result of */
169 /* this algorithm is that the shortest path from each position to the */
170 /* player is described by the directions in the movement tree. */
regen_tree()171 void regen_tree()
172 {
173   register int head,tail,lpos,dist;
174   /* This array is used for the queue of graph nodes.  The head and */
175   /* tail variables describe the head and tail of the queue in the */
176   /* array. */
177   struct goals_s {
178     short x,y,dir;
179   } goals[QSIZE];
180 
181   /* Do a fast pre-initialization of the movement tree */
182   dist = xsize * ysize;
183   for(lpos=0;lpos<dist;++lpos) {
184     /* Zero out each position.  A 0 in a position signifies that the */
185     /* direction of movement for that position is unknown. */
186     movetree[lpos] = 0;
187     /* If can only move in one direction, set movetree value */
188     /* immediately.  Do not set it if is a force into a STOPBAD space */
189     /* to allow bad guys to try to run over holes.  This loop screws up the */
190     /* search algorithm and the result is that bad guys will not jump */
191     /* off of things.  It makes the search run much faster, and the */
192     /* bad guys were too smart otherwise. */
193     if((moveallow[lpos] & FORCEDOWN) &&
194        ! (fast_lookup[level[lpos + 1]].code & STOPBAD))
195       movetree[lpos] = MOVEDOWN;
196     if((moveallow[lpos] & FORCEUP) &&
197        ! (fast_lookup[level[lpos - 1]].code & STOPBAD))
198       movetree[lpos] = MOVEUP;
199     if((moveallow[lpos] & FORCERIGHT) &&
200        ! (fast_lookup[level[lpos + ysize]].code & STOPBAD))
201       movetree[lpos] = MOVERIGHT;
202     if((moveallow[lpos] & FORCELEFT) &&
203        ! (fast_lookup[level[lpos - ysize]].code & STOPBAD))
204       movetree[lpos] = MOVELEFT;
205     /* If no movement is possible, set a -1 in the movement tree. */
206     if(moveallow[lpos] == 0)
207       movetree[lpos] = -1;
208   }
209   /* Initialize the head and tail of the FIFO queue. */
210   head = 0;
211   tail = 1;
212   /* Set the first goal node to be the player */
213   goals[0].x = player.xpos >> 1;
214   goals[0].y = player.ypos >> 1;
215   goals[0].dir = -1;    /* Make sure every direction is possible */
216   /* While there are still goal nodes, continue */
217   while(head != tail) {
218     /* Compute position of position of goal */
219     lpos = goals[head].x * ysize + goals[head].y;
220     /* If the suggested movement direction is valid and the movement */
221     /* has for that position has not been set, set it. */
222     if(movetree[lpos] == 0 && (moveallow[lpos] & goals[head].dir) != 0) {
223       movetree[lpos] = goals[head].dir;
224       /* Suggest that the block to the left has to rightward pointer */
225       if(goals[head].x > 0 && movetree[lpos - ysize] == 0)
226 
227 /* Add a suggested movement direction to the FIFO queue */
228 #define ADDGOAL(dx,dy,ndir)  { goals[tail].x = goals[head].x + dx; \
229                              goals[tail].y = goals[head].y + dy; \
230                              goals[tail++].dir = ndir; \
231                              if(tail == QSIZE) tail = 0; }
232 
233         ADDGOAL(-1,0,MOVERIGHT)
234       /* Suggest that the block to the right has a leftware pointer */
235       if(goals[head].x < xsize - 1 && movetree[lpos + ysize] == 0)
236         ADDGOAL(1,0,MOVELEFT)
237       /* Suggest that the block above has a downward pointer */
238       if(goals[head].y > 0 && movetree[lpos - 1] == 0)
239         ADDGOAL(0,-1,MOVEDOWN)
240       /* Suggest that the block below has an upward pointer */
241       if(goals[head].y < ysize - 1 && movetree[lpos + 1] == 0)
242         ADDGOAL(0,1,MOVEUP)
243     }
244     /* Remove current goal node from head of queue */
245     head ++;
246     if(head == QSIZE)
247       head = 0;
248   }
249 }
250 
251 /* Move all the bad guys one position */
move_badguys()252 void move_badguys()
253 {
254   int i,x,y,allow;
255   register int lpos;
256   enum directs dir;
257   register unsigned char curchar;
258   register char below;
259 
260   /* Iterate through all the bad guys */
261   for(i=0;i<numbadguy;++i) {
262     /* Get old position for bad guys */
263     x = badguys[i].xold = badguys[i].xpos;
264     y = badguys[i].yold = badguys[i].ypos;
265     /* Initially assume that the badguy does not need to be redrawn */
266     badguys[i].redraw = 0;
267     /* Get the character underneath the bad guy */
268     lpos = (x >> 1)*ysize + (y >> 1);
269     curchar = level[lpos];
270     /* Get the character below the bad guy.  If it is off the level, */
271     /* assume it is a stone */
272     if(y < (ysize - 1) << 1)
273       below = level[lpos + 1];
274     else
275       below = STONE;
276 
277     /* If the current character is a killer block, move the bad guy to */
278     /* its starting position */
279     if(fast_lookup[curchar].code & KILLIN) {
280       /* Prevent getting too many points from kill bad guys on a */
281       /* single level */
282       if(badscore < MAXBADSCORE) {
283         /* Increment the score */
284         score += 2;
285         badscore += 2;
286       }
287       /* Redraw the score line */
288       draw_score();
289       /* Move the bad guy back to its start */
290       badguys[i].xpos = badguys[i].xstart;
291       badguys[i].ypos = badguys[i].ystart;
292       lpos = (badguys[i].xpos >> 1)*ysize + (badguys[i].ypos >> 1);
293       /* Redraw bad guy */
294       badguys[i].redraw = 1;
295       /* Destroy whatever the bad guy was holding */
296       if(badguys[i].hold != SPACE) {
297         if(fast_lookup[badguys[i].hold].code & TREASURE) {
298           goldleft --;
299           /* If that was the last gold piece, escape ladder and other */
300           /* stuff may need to appear. */
301           if(goldleft == 0) {
302             regen_allow();      /* Regenerate the allowable movement array */
303             redrawall();        /* Refresh the entire screen */
304           }
305         }
306         badguys[i].hold = SPACE;
307       }
308       /* Continue to the next bad guy */
309       continue;
310     }
311 
312     /* If the bad guy is stuck in a STOPBAD block, do not move him */
313     if((x & 1) == 0 && (y & 1) == 0 &&
314        (fast_lookup[curchar].code & STOPBAD)) {
315       /* Redraw bad guy since underlying block gets redrawn occasionally */
316       badguys[i].redraw = 1;
317       continue;
318     }
319 
320     /* Check if the bad guy is above a hole. */
321     if((x & 1) == 0 && (y & 1) == 0 && fast_lookup[below].code & STOPBAD) {
322       /* If the hole is premature, fill it */
323       if(below >= HOLE1 && below <= HOLE1+2)
324         fill_hole(x >> 1,(y >> 1) + 1);
325     }
326 
327     /* Complete previous movement */
328     if((x & 1) != 0 || (y & 1) != 0)
329       dir = badguys[i].dir;
330 
331     /* Can only drop things when at a non-offset position and when */
332     /* there is space underneath */
333     else if(curchar == SPACE && badguys[i].hold != SPACE &&
334        /* Drop stuff with a 1 in 16 chance.  Movement timing will only */
335        /* allow the badguy to be in an even spot every 4 ticks. */
336        ((curtick & 0x1f) <= 0x3))
337       dir = PUTDOWN;
338 
339     /* Compute next hopeful direction of movement, since badguy is at */
340     /* an even spot */
341     else {
342       /* Get allowable movement direction */
343       allow = moveallow[lpos];
344       /* Prevent bad guy from spontaneously switching direction */
345       if(badguys[i].dir == UP)
346         allow &= ~MOVEDOWN;
347       else if(badguys[i].dir == DOWN)
348         allow &= ~MOVEUP;
349       else if(badguys[i].dir == LEFT)
350         allow &= ~MOVERIGHT;
351       else if(badguys[i].dir == RIGHT)
352         allow &= ~MOVELEFT;
353 
354       /* Prevent bad guy from trying to run into somebody else */
355       if((allow & MOVEUP) &&
356          overlap_badguy(badguys[i].xpos,badguys[i].ypos - 2,i))
357         allow &= ~MOVEUP;
358       /* Prevent bad guy from trying to run into somebody else */
359       if((allow & MOVEDOWN) &&
360          overlap_badguy(badguys[i].xpos,badguys[i].ypos + 2,i))
361         allow &= ~MOVEDOWN;
362       /* Prevent bad guy from trying to run into somebody else */
363       if((allow & MOVELEFT) &&
364          overlap_badguy(badguys[i].xpos - 2,badguys[i].ypos,i))
365         allow &= ~MOVELEFT;
366       /* Prevent bad guy from trying to run into somebody else */
367       if((allow & MOVERIGHT) &&
368          overlap_badguy(badguys[i].xpos + 2,badguys[i].ypos,i))
369         allow &= ~MOVERIGHT;
370 
371       /* Try to move according to movement tree */
372       if((allow & MOVEUP) && movetree[lpos] == MOVEUP)
373         dir = UP;
374       else if((allow & MOVEDOWN) && movetree[lpos] == MOVEDOWN)
375         dir = DOWN;
376       else if((allow & MOVELEFT) && movetree[lpos] == MOVELEFT)
377         dir = LEFT;
378       else if((allow & MOVERIGHT) && movetree[lpos] == MOVERIGHT)
379         dir = RIGHT;
380 
381       /* Try circling clockwise around player */
382       else if((allow & MOVEUP) && badguys[i].xpos < player.xpos)
383         dir = UP;
384       else if((allow & MOVEDOWN) && badguys[i].xpos > player.xpos)
385         dir = DOWN;
386       else if((allow & MOVELEFT) && badguys[i].ypos > player.ypos)
387         dir = LEFT;
388       else if((allow & MOVERIGHT) && badguys[i].ypos < player.ypos)
389         dir = RIGHT;
390 
391       /* Try approaching player */
392       else if((allow & MOVEUP) && badguys[i].ypos > player.ypos)
393         dir = UP;
394       else if((allow & MOVEDOWN) && badguys[i].ypos < player.ypos)
395         dir = DOWN;
396       else if((allow & MOVELEFT) && badguys[i].xpos > player.xpos)
397         dir = LEFT;
398       else if((allow & MOVERIGHT) && badguys[i].xpos < player.xpos)
399         dir = RIGHT;
400 
401       /* Try moving in any possible direction */
402       else if(allow & MOVEUP)
403         dir = UP;
404       else if(allow & MOVEDOWN)
405         dir = DOWN;
406       else if(allow & MOVELEFT)
407         dir = LEFT;
408       else if(allow & MOVERIGHT)
409         dir = RIGHT;
410 
411       /* If totally stuck, just stand in place */
412       else
413         dir = STAND;
414     }
415 
416     /* Reverse bad guys direction if REVERSE item is held by player */
417     if((fast_lookup[player.hold].code & REVERSE) &&
418        (x & 1) == 0 && (y & 1) == 0)
419       switch(dir) {
420       case LEFT:  dir = RIGHT; break;
421       case RIGHT: dir = LEFT;  break;
422       case UP:    dir = DOWN;  break;
423       case DOWN:  dir = UP;    break;
424       case UNMOVE: case STAND: case DIGLEFT: case DIGRIGHT: case PUTDOWN: break;
425       }
426 
427     /* Execute computed movement. */
428     if(movething(&(badguys[i]),dir,i) == 3) {
429       /* If the bad guy dropped something, the block will have been */
430       /* overwritten and now the bad guy needs to be redrawn */
431       badguys[i].redraw = 1;
432       break;
433     }
434 
435     /* Redraw bad guy if it has moved */
436     if(x != badguys[i].xpos || y != badguys[i].ypos)
437       badguys[i].redraw = 1;
438   }
439   /* Redraw bad guys in new positions */
440   drawmove_badguys();
441 }
442 
443