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