1 /* SCCS Id: @(#)vision.c 3.4 1999/02/18 */
2 /* Copyright (c) Dean Luick, with acknowledgements to Dave Cohrs, 1990. */
3 /* NetHack may be freely redistributed. See license for details. */
4
5 #include "hack.h"
6
7 /* Circles ==================================================================*/
8
9 /*
10 * These numbers are limit offsets for one quadrant of a circle of a given
11 * radius (the first number of each line) from the source. The number in
12 * the comment is the element number (so pointers can be set up). Each
13 * "circle" has as many elements as its radius+1. The radius is the number
14 * of points away from the source that the limit exists. The radius of the
15 * offset on the same row as the source *is* included so we don't have to
16 * make an extra check. For example, a circle of radius 4 has offsets:
17 *
18 * XXX +2
19 * ...X +3
20 * ....X +4
21 * ....X +4
22 * @...X +4
23 *
24 */
25 char circle_data[] = {
26 /* 0*/ 1, 1,
27 /* 2*/ 2, 2, 1,
28 /* 5*/ 3, 3, 2, 1,
29 /* 9*/ 4, 4, 4, 3, 2,
30 /* 14*/ 5, 5, 5, 4, 3, 2,
31 /* 20*/ 6, 6, 6, 5, 5, 4, 2,
32 /* 27*/ 7, 7, 7, 6, 6, 5, 4, 2,
33 /* 35*/ 8, 8, 8, 7, 7, 6, 6, 4, 2,
34 /* 44*/ 9, 9, 9, 9, 8, 8, 7, 6, 5, 3,
35 /* 54*/ 10,10,10,10, 9, 9, 8, 7, 6, 5, 3,
36 /* 65*/ 11,11,11,11,10,10, 9, 9, 8, 7, 5, 3,
37 /* 77*/ 12,12,12,12,11,11,10,10, 9, 8, 7, 5, 3,
38 /* 90*/ 13,13,13,13,12,12,12,11,10,10, 9, 7, 6, 3,
39 /*104*/ 14,14,14,14,13,13,13,12,12,11,10, 9, 8, 6, 3,
40 /*119*/ 15,15,15,15,14,14,14,13,13,12,11,10, 9, 8, 6, 3,
41 /*135*/ 16 /* should be MAX_RADIUS+1; used to terminate range loops -dlc */
42 };
43
44 /*
45 * These are the starting indexes into the circle_data[] array for a
46 * circle of a given radius.
47 */
48 char circle_start[] = {
49 /* */ 0, /* circles of radius zero are not used */
50 /* 1*/ 0,
51 /* 2*/ 2,
52 /* 3*/ 5,
53 /* 4*/ 9,
54 /* 5*/ 14,
55 /* 6*/ 20,
56 /* 7*/ 27,
57 /* 8*/ 35,
58 /* 9*/ 44,
59 /*10*/ 54,
60 /*11*/ 65,
61 /*12*/ 77,
62 /*13*/ 90,
63 /*14*/ 104,
64 /*15*/ 119,
65 };
66
67
68 /*===========================================================================*/
69 /* Vision (arbitrary line of sight) =========================================*/
70
71 /*------ global variables ------*/
72
73 #if 0 /* (moved to decl.c) */
74 /* True if we need to run a full vision recalculation. */
75 boolean vision_full_recalc = 0;
76
77 /* Pointers to the current vision array. */
78 char **viz_array;
79 #endif
80 char *viz_rmin, *viz_rmax; /* current vision cs bounds */
81
82
83 /*------ local variables ------*/
84
85
86 static char could_see[2][ROWNO][COLNO]; /* vision work space */
87 static char *cs_rows0[ROWNO], *cs_rows1[ROWNO];
88 static char cs_rmin0[ROWNO], cs_rmax0[ROWNO];
89 static char cs_rmin1[ROWNO], cs_rmax1[ROWNO];
90
91 static char viz_clear[ROWNO][COLNO]; /* vision clear/blocked map */
92 static char *viz_clear_rows[ROWNO];
93
94 static char left_ptrs[ROWNO][COLNO]; /* LOS algorithm helpers */
95 static char right_ptrs[ROWNO][COLNO];
96
97 /* Forward declarations. */
98 STATIC_DCL void FDECL(fill_point, (int,int));
99 STATIC_DCL void FDECL(dig_point, (int,int));
100 STATIC_DCL void NDECL(view_init);
101 STATIC_DCL void FDECL(view_from,(int,int,char **,char *,char *,int,
102 void (*)(int,int,genericptr_t),genericptr_t));
103 STATIC_DCL void FDECL(get_unused_cs, (char ***,char **,char **));
104 #ifdef REINCARNATION
105 STATIC_DCL void FDECL(rogue_vision, (char **,char *,char *));
106 #endif
107
108 /* Macro definitions that I can't find anywhere. */
109 #define sign(z) ((z) < 0 ? -1 : ((z) ? 1 : 0 ))
110 #define v_abs(z) ((z) < 0 ? -(z) : (z)) /* don't use abs -- it may exist */
111
112 /*
113 * vision_init()
114 *
115 * The one-time vision initialization routine.
116 *
117 * This must be called before mklev() is called in newgame() [allmain.c],
118 * or before a game restore. Else we die a horrible death.
119 */
120 void
vision_init()121 vision_init()
122 {
123 int i;
124
125 /* Set up the pointers. */
126 for (i = 0; i < ROWNO; i++) {
127 cs_rows0[i] = could_see[0][i];
128 cs_rows1[i] = could_see[1][i];
129 viz_clear_rows[i] = viz_clear[i];
130 }
131
132 /* Start out with cs0 as our current array */
133 viz_array = cs_rows0;
134 viz_rmin = cs_rmin0;
135 viz_rmax = cs_rmax0;
136
137 vision_full_recalc = 0;
138 (void) memset((genericptr_t) could_see, 0, sizeof(could_see));
139
140 /* Initialize the vision algorithm (currently C or D). */
141 view_init();
142
143 #ifdef VISION_TABLES
144 /* Note: this initializer doesn't do anything except guarantee that
145 we're linked properly.
146 */
147 vis_tab_init();
148 #endif
149 }
150
151 /*
152 * does_block()
153 *
154 * Returns true if the level feature, object, or monster at (x,y) blocks
155 * sight.
156 */
157 int
does_block(x,y,lev)158 does_block(x,y,lev)
159 int x, y;
160 register struct rm *lev;
161 {
162 struct obj *obj;
163 struct monst *mon;
164
165 /* Features that block . . */
166 if (IS_ROCK(lev->typ) || lev->typ == TREE || (IS_DOOR(lev->typ) &&
167 (lev->doormask & (D_CLOSED|D_LOCKED|D_TRAPPED) )))
168 return 1;
169
170 if (lev->typ == CLOUD || lev->typ == WATER ||
171 (lev->typ == MOAT && Underwater))
172 return 1;
173
174 /* Boulders block light. */
175 for (obj = level.objects[x][y]; obj; obj = obj->nexthere)
176 if (obj->otyp == BOULDER) return 1;
177
178 /* Mimics mimicing a door or boulder block light. */
179 if ((mon = m_at(x,y)) && (!mon->minvis || See_invisible) &&
180 ((mon->data == &mons[PM_GIANT_TURTLE]) ||
181 ((mon->m_ap_type == M_AP_FURNITURE &&
182 (mon->mappearance == S_hcdoor || mon->mappearance == S_vcdoor)) ||
183 (mon->m_ap_type == M_AP_OBJECT && mon->mappearance == BOULDER))))
184 return 1;
185
186 return 0;
187 }
188
189 /*
190 * vision_reset()
191 *
192 * This must be called *after* the levl[][] structure is set with the new
193 * level and the level monsters and objects are in place.
194 */
195 void
vision_reset()196 vision_reset()
197 {
198 int y;
199 register int x, i, dig_left, block;
200 register struct rm *lev;
201
202 /* Start out with cs0 as our current array */
203 viz_array = cs_rows0;
204 viz_rmin = cs_rmin0;
205 viz_rmax = cs_rmax0;
206
207 (void) memset((genericptr_t) could_see, 0, sizeof(could_see));
208
209 /* Reset the pointers and clear so that we have a "full" dungeon. */
210 (void) memset((genericptr_t) viz_clear, 0, sizeof(viz_clear));
211
212 /* Dig the level */
213 for (y = 0; y < ROWNO; y++) {
214 dig_left = 0;
215 block = TRUE; /* location (0,y) is always stone; it's !isok() */
216 lev = &levl[1][y];
217 for (x = 1; x < COLNO; x++, lev += ROWNO)
218 if (block != (IS_ROCK(lev->typ) || does_block(x,y,lev))) {
219 if(block) {
220 for(i=dig_left; i<x; i++) {
221 left_ptrs [y][i] = dig_left;
222 right_ptrs[y][i] = x-1;
223 }
224 } else {
225 i = dig_left;
226 if(dig_left) dig_left--; /* point at first blocked point */
227 for(; i<x; i++) {
228 left_ptrs [y][i] = dig_left;
229 right_ptrs[y][i] = x;
230 viz_clear[y][i] = 1;
231 }
232 }
233 dig_left = x;
234 block = !block;
235 }
236 /* handle right boundary; almost identical for blocked/unblocked */
237 i = dig_left;
238 if(!block && dig_left) dig_left--; /* point at first blocked point */
239 for(; i<COLNO; i++) {
240 left_ptrs [y][i] = dig_left;
241 right_ptrs[y][i] = (COLNO-1);
242 viz_clear[y][i] = !block;
243 }
244 }
245
246 iflags.vision_inited = 1; /* vision is ready */
247 vision_full_recalc = 1; /* we want to run vision_recalc() */
248 }
249
250
251 /*
252 * get_unused_cs()
253 *
254 * Called from vision_recalc() and at least one light routine. Get pointers
255 * to the unused vision work area.
256 */
257 STATIC_OVL void
get_unused_cs(rows,rmin,rmax)258 get_unused_cs(rows, rmin, rmax)
259 char ***rows;
260 char **rmin, **rmax;
261 {
262 register int row;
263 register char *nrmin, *nrmax;
264
265 if (viz_array == cs_rows0) {
266 *rows = cs_rows1;
267 *rmin = cs_rmin1;
268 *rmax = cs_rmax1;
269 } else {
270 *rows = cs_rows0;
271 *rmin = cs_rmin0;
272 *rmax = cs_rmax0;
273 }
274
275 /* return an initialized, unused work area */
276 nrmin = *rmin;
277 nrmax = *rmax;
278
279 (void) memset((genericptr_t)**rows, 0, ROWNO*COLNO); /* we see nothing */
280 for (row = 0; row < ROWNO; row++) { /* set row min & max */
281 *nrmin++ = COLNO-1;
282 *nrmax++ = 0;
283 }
284 }
285
286
287 #ifdef REINCARNATION
288 /*
289 * rogue_vision()
290 *
291 * Set the "could see" and in sight bits so vision acts just like the old
292 * rogue game:
293 *
294 * + If in a room, the hero can see to the room boundaries.
295 * + The hero can always see adjacent squares.
296 *
297 * We set the in_sight bit here as well to escape a bug that shows up
298 * due to the one-sided lit wall hack.
299 */
300 STATIC_OVL void
rogue_vision(next,rmin,rmax)301 rogue_vision(next, rmin, rmax)
302 char **next; /* could_see array pointers */
303 char *rmin, *rmax;
304 {
305 int rnum = levl[u.ux][u.uy].roomno - ROOMOFFSET; /* no SHARED... */
306 int start, stop, in_door, xhi, xlo, yhi, ylo;
307 register int zx, zy;
308
309 /* If in a lit room, we are able to see to its boundaries. */
310 /* If dark, set COULD_SEE so various spells work -dlc */
311 if (rnum >= 0) {
312 for (zy = rooms[rnum].ly-1; zy <= rooms[rnum].hy+1; zy++) {
313 rmin[zy] = start = rooms[rnum].lx-1;
314 rmax[zy] = stop = rooms[rnum].hx+1;
315
316 for (zx = start; zx <= stop; zx++) {
317 if (rooms[rnum].rlit) {
318 next[zy][zx] = COULD_SEE | IN_SIGHT;
319 levl[zx][zy].seenv = SVALL; /* see the walls */
320 } else
321 next[zy][zx] = COULD_SEE;
322 }
323 }
324 }
325
326 in_door = levl[u.ux][u.uy].typ == DOOR;
327
328 /* Can always see adjacent. */
329 ylo = max(u.uy - 1, 0);
330 yhi = min(u.uy + 1, ROWNO - 1);
331 xlo = max(u.ux - 1, 1);
332 xhi = min(u.ux + 1, COLNO - 1);
333 for (zy = ylo; zy <= yhi; zy++) {
334 if (xlo < rmin[zy]) rmin[zy] = xlo;
335 if (xhi > rmax[zy]) rmax[zy] = xhi;
336
337 for (zx = xlo; zx <= xhi; zx++) {
338 next[zy][zx] = COULD_SEE | IN_SIGHT;
339 /*
340 * Yuck, update adjacent non-diagonal positions when in a doorway.
341 * We need to do this to catch the case when we first step into
342 * a room. The room's walls were not seen from the outside, but
343 * now are seen (the seen bits are set just above). However, the
344 * positions are not updated because they were already in sight.
345 * So, we have to do it here.
346 */
347 if (in_door && (zx == u.ux || zy == u.uy)) newsym(zx,zy);
348 }
349 }
350 }
351 #endif /* REINCARNATION */
352
353 /*#define EXTEND_SPINE*/ /* possibly better looking wall-angle */
354
355 #ifdef EXTEND_SPINE
356
357 STATIC_DCL int FDECL(new_angle, (struct rm *, unsigned char *, int, int));
358 /*
359 * new_angle()
360 *
361 * Return the new angle seen by the hero for this location. The angle
362 * bit is given in the value pointed at by sv.
363 *
364 * For T walls and crosswall, just setting the angle bit, even though
365 * it is technically correct, doesn't look good. If we can see the
366 * next position beyond the current one and it is a wall that we can
367 * see, then we want to extend a spine of the T to connect with the wall
368 * that is beyond. Example:
369 *
370 * Correct, but ugly Extend T spine
371 *
372 * | ... | ...
373 * | ... <-- wall beyond & floor --> | ...
374 * | ... | ...
375 * Unseen --> ... | ...
376 * spine +-... <-- trwall & doorway --> +-...
377 * | ... | ...
378 *
379 *
380 * @ <-- hero --> @
381 *
382 *
383 * We fake the above check by only checking if the horizontal &
384 * vertical positions adjacent to the crosswall and T wall are
385 * unblocked. Then, _in general_ we can see beyond. Generally,
386 * this is good enough.
387 *
388 * + When this function is called we don't have all of the seen
389 * information (we're doing a top down scan in vision_recalc).
390 * We would need to scan once to set all IN_SIGHT and COULD_SEE
391 * bits, then again to correctly set the seenv bits.
392 * + I'm trying to make this as cheap as possible. The display &
393 * vision eat up too much CPU time.
394 *
395 *
396 * Note: Even as I write this, I'm still not convinced. There are too
397 * many exceptions. I may have to bite the bullet and do more
398 * checks. - Dean 2/11/93
399 */
400 STATIC_OVL int
new_angle(lev,sv,row,col)401 new_angle(lev, sv, row, col)
402 struct rm *lev;
403 unsigned char *sv;
404 int row, col;
405 {
406 register int res = *sv;
407
408 /*
409 * Do extra checks for crosswalls and T walls if we see them from
410 * an angle.
411 */
412 if (lev->typ >= CROSSWALL && lev->typ <= TRWALL) {
413 switch (res) {
414 case SV0:
415 if (col > 0 && viz_clear[row][col-1]) res |= SV7;
416 if (row > 0 && viz_clear[row-1][col]) res |= SV1;
417 break;
418 case SV2:
419 if (row > 0 && viz_clear[row-1][col]) res |= SV1;
420 if (col < COLNO-1 && viz_clear[row][col+1]) res |= SV3;
421 break;
422 case SV4:
423 if (col < COLNO-1 && viz_clear[row][col+1]) res |= SV3;
424 if (row < ROWNO-1 && viz_clear[row+1][col]) res |= SV5;
425 break;
426 case SV6:
427 if (row < ROWNO-1 && viz_clear[row+1][col]) res |= SV5;
428 if (col > 0 && viz_clear[row][col-1]) res |= SV7;
429 break;
430 }
431 }
432 return res;
433 }
434 #else
435 /*
436 * new_angle()
437 *
438 * Return the new angle seen by the hero for this location. The angle
439 * bit is given in the value pointed at by sv.
440 *
441 * The other parameters are not used.
442 */
443 #define new_angle(lev, sv, row, col) (*sv)
444
445 #endif
446
447
448 /*
449 * vision_recalc()
450 *
451 * Do all of the heavy vision work. Recalculate all locations that could
452 * possibly be seen by the hero --- if the location were lit, etc. Note
453 * which locations are actually seen because of lighting. Then add to
454 * this all locations that be seen by hero due to night vision and x-ray
455 * vision. Finally, compare with what the hero was able to see previously.
456 * Update the difference.
457 *
458 * This function is usually called only when the variable 'vision_full_recalc'
459 * is set. The following is a list of places where this function is called,
460 * with three valid values for the control flag parameter:
461 *
462 * Control flag = 0. A complete vision recalculation. Generate the vision
463 * tables from scratch. This is necessary to correctly set what the hero
464 * can see. (1) and (2) call this routine for synchronization purposes, (3)
465 * calls this routine so it can operate correctly.
466 *
467 * + After the monster move, before input from the player. [moveloop()]
468 * + At end of moveloop. [moveloop() ??? not sure why this is here]
469 * + Right before something is printed. [pline()]
470 * + Right before we do a vision based operation. [do_clear_area()]
471 * + screen redraw, so we can renew all positions in sight. [docrt()]
472 *
473 * Control flag = 1. An adjacent vision recalculation. The hero has moved
474 * one square. Knowing this, it might be possible to optimize the vision
475 * recalculation using the current knowledge. This is presently unimplemented
476 * and is treated as a control = 0 call.
477 *
478 * + Right after the hero moves. [domove()]
479 *
480 * Control flag = 2. Turn off the vision system. Nothing new will be
481 * displayed, since nothing is seen. This is usually done when you need
482 * a newsym() run on all locations in sight, or on some locations but you
483 * don't know which ones.
484 *
485 * + Before a screen redraw, so all positions are renewed. [docrt()]
486 * + Right before the hero arrives on a new level. [goto_level()]
487 * + Right after a scroll of light is read. [litroom()]
488 * + After an option has changed that affects vision [parseoptions()]
489 * + Right after the hero is swallowed. [gulpmu()]
490 * + Just before bubbles are moved. [movebubbles()]
491 */
492 void
vision_recalc(control)493 vision_recalc(control)
494 int control;
495 {
496 char **temp_array; /* points to the old vision array */
497 char **next_array; /* points to the new vision array */
498 char *next_row; /* row pointer for the new array */
499 char *old_row; /* row pointer for the old array */
500 char *next_rmin; /* min pointer for the new array */
501 char *next_rmax; /* max pointer for the new array */
502 char *ranges; /* circle ranges -- used for xray & night vision */
503 int row; /* row counter (outer loop) */
504 int start, stop; /* inner loop starting/stopping index */
505 int dx, dy; /* one step from a lit door or lit wall (see below) */
506 register int col; /* inner loop counter */
507 register struct rm *lev; /* pointer to current pos */
508 struct rm *flev; /* pointer to position in "front" of current pos */
509 extern unsigned char seenv_matrix[3][3]; /* from display.c */
510 static unsigned char colbump[COLNO+1]; /* cols to bump sv */
511 unsigned char *sv; /* ptr to seen angle bits */
512 int oldseenv; /* previous seenv value */
513
514 vision_full_recalc = 0; /* reset flag */
515 if (in_mklev || !iflags.vision_inited) return;
516
517 #ifdef GCC_WARN
518 row = 0;
519 #endif
520
521 /*
522 * Either the light sources have been taken care of, or we must
523 * recalculate them here.
524 */
525
526 /* Get the unused could see, row min, and row max arrays. */
527 get_unused_cs(&next_array, &next_rmin, &next_rmax);
528
529 /* You see nothing, nothing can see you --- if swallowed or refreshing. */
530 if (u.uswallow || control == 2) {
531 /* do nothing -- get_unused_cs() nulls out the new work area */
532
533 } else if (Blind) {
534 /*
535 * Calculate the could_see array even when blind so that monsters
536 * can see you, even if you can't see them. Note that the current
537 * setup allows:
538 *
539 * + Monsters to see with the "new" vision, even on the rogue
540 * level.
541 *
542 * + Monsters can see you even when you're in a pit.
543 */
544 view_from(u.uy, u.ux, next_array, next_rmin, next_rmax,
545 0, (void FDECL((*),(int,int,genericptr_t)))0, (genericptr_t)0);
546
547 /*
548 * Our own version of the update loop below. We know we can't see
549 * anything, so we only need update positions we used to be able
550 * to see.
551 */
552 temp_array = viz_array; /* set viz_array so newsym() will work */
553 viz_array = next_array;
554
555 for (row = 0; row < ROWNO; row++) {
556 old_row = temp_array[row];
557
558 /* Find the min and max positions on the row. */
559 start = min(viz_rmin[row], next_rmin[row]);
560 stop = max(viz_rmax[row], next_rmax[row]);
561
562 for (col = start; col <= stop; col++)
563 if (old_row[col] & IN_SIGHT) newsym(col,row);
564 }
565
566 /* skip the normal update loop */
567 goto skip;
568 }
569 #ifdef REINCARNATION
570 else if (Is_rogue_level(&u.uz)) {
571 rogue_vision(next_array,next_rmin,next_rmax);
572 }
573 #endif
574 else {
575 int has_night_vision = 1; /* hero has night vision */
576
577 if (Underwater && !Is_waterlevel(&u.uz)) {
578 /*
579 * The hero is under water. Only see surrounding locations if
580 * they are also underwater. This overrides night vision but
581 * does not override x-ray vision.
582 */
583 has_night_vision = 0;
584
585 for (row = u.uy-1; row <= u.uy+1; row++)
586 for (col = u.ux-1; col <= u.ux+1; col++) {
587 if (!isok(col,row) || !is_pool(col,row)) continue;
588
589 next_rmin[row] = min(next_rmin[row], col);
590 next_rmax[row] = max(next_rmax[row], col);
591 next_array[row][col] = IN_SIGHT | COULD_SEE;
592 }
593 }
594
595 /* if in a pit, just update for immediate locations */
596 else if (u.utrap && u.utraptype == TT_PIT) {
597 for (row = u.uy-1; row <= u.uy+1; row++) {
598 if (row < 0) continue; if (row >= ROWNO) break;
599
600 next_rmin[row] = max( 0, u.ux - 1);
601 next_rmax[row] = min(COLNO-1, u.ux + 1);
602 next_row = next_array[row];
603
604 for(col=next_rmin[row]; col <= next_rmax[row]; col++)
605 next_row[col] = IN_SIGHT | COULD_SEE;
606 }
607 } else
608 view_from(u.uy, u.ux, next_array, next_rmin, next_rmax,
609 0, (void FDECL((*),(int,int,genericptr_t)))0, (genericptr_t)0);
610
611 /*
612 * Set the IN_SIGHT bit for xray and night vision.
613 */
614 if (u.xray_range >= 0) {
615 if (u.xray_range) {
616 ranges = circle_ptr(u.xray_range);
617
618 for (row = u.uy-u.xray_range; row <= u.uy+u.xray_range; row++) {
619 if (row < 0) continue; if (row >= ROWNO) break;
620 dy = v_abs(u.uy-row); next_row = next_array[row];
621
622 start = max( 0, u.ux - ranges[dy]);
623 stop = min(COLNO-1, u.ux + ranges[dy]);
624
625 for (col = start; col <= stop; col++) {
626 char old_row_val = next_row[col];
627 next_row[col] |= IN_SIGHT;
628 oldseenv = levl[col][row].seenv;
629 levl[col][row].seenv = SVALL; /* see all! */
630 /* Update if previously not in sight or new angle. */
631 if (!(old_row_val & IN_SIGHT) || oldseenv != SVALL)
632 newsym(col,row);
633 }
634
635 next_rmin[row] = min(start, next_rmin[row]);
636 next_rmax[row] = max(stop, next_rmax[row]);
637 }
638
639 } else { /* range is 0 */
640 next_array[u.uy][u.ux] |= IN_SIGHT;
641 levl[u.ux][u.uy].seenv = SVALL;
642 next_rmin[u.uy] = min(u.ux, next_rmin[u.uy]);
643 next_rmax[u.uy] = max(u.ux, next_rmax[u.uy]);
644 }
645 }
646
647 if (has_night_vision && u.xray_range < u.nv_range) {
648 if (!u.nv_range) { /* range is 0 */
649 next_array[u.uy][u.ux] |= IN_SIGHT;
650 levl[u.ux][u.uy].seenv = SVALL;
651 next_rmin[u.uy] = min(u.ux, next_rmin[u.uy]);
652 next_rmax[u.uy] = max(u.ux, next_rmax[u.uy]);
653 } else if (u.nv_range > 0) {
654 ranges = circle_ptr(u.nv_range);
655
656 for (row = u.uy-u.nv_range; row <= u.uy+u.nv_range; row++) {
657 if (row < 0) continue; if (row >= ROWNO) break;
658 dy = v_abs(u.uy-row); next_row = next_array[row];
659
660 start = max( 0, u.ux - ranges[dy]);
661 stop = min(COLNO-1, u.ux + ranges[dy]);
662
663 for (col = start; col <= stop; col++)
664 if (next_row[col]) next_row[col] |= IN_SIGHT;
665
666 next_rmin[row] = min(start, next_rmin[row]);
667 next_rmax[row] = max(stop, next_rmax[row]);
668 }
669 }
670 }
671 }
672
673 /* Set the correct bits for all light sources. */
674 do_light_sources(next_array);
675
676
677 /*
678 * Make the viz_array the new array so that cansee() will work correctly.
679 */
680 temp_array = viz_array;
681 viz_array = next_array;
682
683 /*
684 * The main update loop. Here we do two things:
685 *
686 * + Set the IN_SIGHT bit for places that we could see and are lit.
687 * + Reset changed places.
688 *
689 * There is one thing that make deciding what the hero can see
690 * difficult:
691 *
692 * 1. Directional lighting. Items that block light create problems.
693 * The worst offenders are doors. Suppose a door to a lit room
694 * is closed. It is lit on one side, but not on the other. How
695 * do you know? You have to check the closest adjacent position.
696 * Even so, that is not entirely correct. But it seems close
697 * enough for now.
698 */
699 colbump[u.ux] = colbump[u.ux+1] = 1;
700 for (row = 0; row < ROWNO; row++) {
701 dy = u.uy - row; dy = sign(dy);
702 next_row = next_array[row]; old_row = temp_array[row];
703
704 /* Find the min and max positions on the row. */
705 start = min(viz_rmin[row], next_rmin[row]);
706 stop = max(viz_rmax[row], next_rmax[row]);
707 lev = &levl[start][row];
708
709 sv = &seenv_matrix[dy+1][start < u.ux ? 0 : (start > u.ux ? 2:1)];
710
711 for (col = start; col <= stop;
712 lev += ROWNO, sv += (int) colbump[++col]) {
713 if (next_row[col] & IN_SIGHT) {
714 /*
715 * We see this position because of night- or xray-vision.
716 */
717 oldseenv = lev->seenv;
718 lev->seenv |= new_angle(lev,sv,row,col); /* update seen angle */
719
720 /* Update pos if previously not in sight or new angle. */
721 if ( !(old_row[col] & IN_SIGHT) || oldseenv != lev->seenv)
722 newsym(col,row);
723 }
724
725 else if ((next_row[col] & COULD_SEE)
726 && (lev->lit || (next_row[col] & TEMP_LIT))) {
727 /*
728 * We see this position because it is lit.
729 */
730 if ((IS_DOOR(lev->typ) || lev->typ == SDOOR ||
731 IS_WALL(lev->typ)) && !viz_clear[row][col]) {
732 /*
733 * Make sure doors, walls, boulders or mimics don't show up
734 * at the end of dark hallways. We do this by checking
735 * the adjacent position. If it is lit, then we can see
736 * the door or wall, otherwise we can't.
737 */
738 dx = u.ux - col; dx = sign(dx);
739 flev = &(levl[col+dx][row+dy]);
740 if (flev->lit || next_array[row+dy][col+dx] & TEMP_LIT) {
741 next_row[col] |= IN_SIGHT; /* we see it */
742
743 oldseenv = lev->seenv;
744 lev->seenv |= new_angle(lev,sv,row,col);
745
746 /* Update pos if previously not in sight or new angle.*/
747 if (!(old_row[col] & IN_SIGHT) || oldseenv!=lev->seenv)
748 newsym(col,row);
749 } else
750 goto not_in_sight; /* we don't see it */
751
752 } else {
753 next_row[col] |= IN_SIGHT; /* we see it */
754
755 oldseenv = lev->seenv;
756 lev->seenv |= new_angle(lev,sv,row,col);
757
758 /* Update pos if previously not in sight or new angle. */
759 if ( !(old_row[col] & IN_SIGHT) || oldseenv != lev->seenv)
760 newsym(col,row);
761 }
762 } else if ((next_row[col] & COULD_SEE) && lev->waslit) {
763 /*
764 * If we make it here, the hero _could see_ the location,
765 * but doesn't see it (location is not lit).
766 * However, the hero _remembers_ it as lit (waslit is true).
767 * The hero can now see that it is not lit, so change waslit
768 * and update the location.
769 */
770 lev->waslit = 0; /* remember lit condition */
771 newsym(col,row);
772 }
773 /*
774 * At this point we know that the row position is *not* in normal
775 * sight. That is, the position is could be seen, but is dark
776 * or LOS is just plain blocked.
777 *
778 * Update the position if:
779 * o If the old one *was* in sight. We may need to clean up
780 * the glyph -- E.g. darken room spot, etc.
781 * o If we now could see the location (yet the location is not
782 * lit), but previously we couldn't see the location, or vice
783 * versa. Update the spot because there there may be an infared
784 * monster there.
785 */
786 else {
787 not_in_sight:
788 if ((old_row[col] & IN_SIGHT)
789 || ((next_row[col] & COULD_SEE)
790 ^ (old_row[col] & COULD_SEE)))
791 newsym(col,row);
792 }
793
794 } /* end for col . . */
795 } /* end for row . . */
796 colbump[u.ux] = colbump[u.ux+1] = 0;
797
798 skip:
799 /* This newsym() caused a crash delivering msg about failure to open
800 * dungeon file init_dungeons() -> panic() -> done(11) ->
801 * vision_recalc(2) -> newsym() -> crash! u.ux and u.uy are 0 and
802 * program_state.panicking == 1 under those circumstances
803 */
804 if (!program_state.panicking)
805 newsym(u.ux, u.uy); /* Make sure the hero shows up! */
806
807 /* Set the new min and max pointers. */
808 viz_rmin = next_rmin;
809 viz_rmax = next_rmax;
810
811 recalc_mapseen();
812 }
813
814
815 /*
816 * block_point()
817 *
818 * Make the location opaque to light.
819 */
820 void
block_point(x,y)821 block_point(x,y)
822 int x, y;
823 {
824 fill_point(y,x);
825
826 /* recalc light sources here? */
827
828 /*
829 * We have to do a full vision recalculation if we "could see" the
830 * location. Why? Suppose some monster opened a way so that the
831 * hero could see a lit room. However, the position of the opening
832 * was out of night-vision range of the hero. Suddenly the hero should
833 * see the lit room.
834 */
835 if (viz_array[y][x]) vision_full_recalc = 1;
836 }
837
838 /*
839 * unblock_point()
840 *
841 * Make the location transparent to light.
842 */
843 void
unblock_point(x,y)844 unblock_point(x,y)
845 int x, y;
846 {
847 dig_point(y,x);
848
849 /* recalc light sources here? */
850
851 if (viz_array[y][x]) vision_full_recalc = 1;
852 }
853
854
855 /*===========================================================================*\
856 | |
857 | Everything below this line uses (y,x) instead of (x,y) --- the |
858 | algorithms are faster if they are less recursive and can scan |
859 | on a row longer. |
860 | |
861 \*===========================================================================*/
862
863
864 /* ========================================================================= *\
865 Left and Right Pointer Updates
866 \* ========================================================================= */
867
868 /*
869 * LEFT and RIGHT pointer rules
870 *
871 *
872 * **NOTE** The rules changed on 4/4/90. This comment reflects the
873 * new rules. The change was so that the stone-wall optimization
874 * would work.
875 *
876 * OK, now the tough stuff. We must maintain our left and right
877 * row pointers. The rules are as follows:
878 *
879 * Left Pointers:
880 * ______________
881 *
882 * + If you are a clear spot, your left will point to the first
883 * stone to your left. If there is none, then point the first
884 * legal position in the row (0).
885 *
886 * + If you are a blocked spot, then your left will point to the
887 * left-most blocked spot to your left that is connected to you.
888 * This means that a left-edge (a blocked spot that has an open
889 * spot on its left) will point to itself.
890 *
891 *
892 * Right Pointers:
893 * ---------------
894 * + If you are a clear spot, your right will point to the first
895 * stone to your right. If there is none, then point the last
896 * legal position in the row (COLNO-1).
897 *
898 * + If you are a blocked spot, then your right will point to the
899 * right-most blocked spot to your right that is connected to you.
900 * This means that a right-edge (a blocked spot that has an open
901 * spot on its right) will point to itself.
902 */
903 STATIC_OVL void
dig_point(row,col)904 dig_point(row,col)
905 int row,col;
906 {
907 int i;
908
909 if (viz_clear[row][col]) return; /* already done */
910
911 viz_clear[row][col] = 1;
912
913 /*
914 * Boundary cases first.
915 */
916 if (col == 0) { /* left edge */
917 if (viz_clear[row][1]) {
918 right_ptrs[row][0] = right_ptrs[row][1];
919 } else {
920 right_ptrs[row][0] = 1;
921 for (i = 1; i <= right_ptrs[row][1]; i++)
922 left_ptrs[row][i] = 1;
923 }
924 } else if (col == (COLNO-1)) { /* right edge */
925
926 if (viz_clear[row][COLNO-2]) {
927 left_ptrs[row][COLNO-1] = left_ptrs[row][COLNO-2];
928 } else {
929 left_ptrs[row][COLNO-1] = COLNO-2;
930 for (i = left_ptrs[row][COLNO-2]; i < COLNO-1; i++)
931 right_ptrs[row][i] = COLNO-2;
932 }
933 }
934
935 /*
936 * At this point, we know we aren't on the boundaries.
937 */
938 else if (viz_clear[row][col-1] && viz_clear[row][col+1]) {
939 /* Both sides clear */
940 for (i = left_ptrs[row][col-1]; i <= col; i++) {
941 if (!viz_clear[row][i]) continue; /* catch non-end case */
942 right_ptrs[row][i] = right_ptrs[row][col+1];
943 }
944 for (i = col; i <= right_ptrs[row][col+1]; i++) {
945 if (!viz_clear[row][i]) continue; /* catch non-end case */
946 left_ptrs[row][i] = left_ptrs[row][col-1];
947 }
948
949 } else if (viz_clear[row][col-1]) {
950 /* Left side clear, right side blocked. */
951 for (i = col+1; i <= right_ptrs[row][col+1]; i++)
952 left_ptrs[row][i] = col+1;
953
954 for (i = left_ptrs[row][col-1]; i <= col; i++) {
955 if (!viz_clear[row][i]) continue; /* catch non-end case */
956 right_ptrs[row][i] = col+1;
957 }
958 left_ptrs[row][col] = left_ptrs[row][col-1];
959
960 } else if (viz_clear[row][col+1]) {
961 /* Right side clear, left side blocked. */
962 for (i = left_ptrs[row][col-1]; i < col; i++)
963 right_ptrs[row][i] = col-1;
964
965 for (i = col; i <= right_ptrs[row][col+1]; i++) {
966 if (!viz_clear[row][i]) continue; /* catch non-end case */
967 left_ptrs[row][i] = col-1;
968 }
969 right_ptrs[row][col] = right_ptrs[row][col+1];
970
971 } else {
972 /* Both sides blocked */
973 for (i = left_ptrs[row][col-1]; i < col; i++)
974 right_ptrs[row][i] = col-1;
975
976 for (i = col+1; i <= right_ptrs[row][col+1]; i++)
977 left_ptrs[row][i] = col+1;
978
979 left_ptrs[row][col] = col-1;
980 right_ptrs[row][col] = col+1;
981 }
982 }
983
984 STATIC_OVL void
fill_point(row,col)985 fill_point(row,col)
986 int row, col;
987 {
988 int i;
989
990 if (!viz_clear[row][col]) return;
991
992 viz_clear[row][col] = 0;
993
994 if (col == 0) {
995 if (viz_clear[row][1]) { /* adjacent is clear */
996 right_ptrs[row][0] = 0;
997 } else {
998 right_ptrs[row][0] = right_ptrs[row][1];
999 for (i = 1; i <= right_ptrs[row][1]; i++)
1000 left_ptrs[row][i] = 0;
1001 }
1002 } else if (col == COLNO-1) {
1003 if (viz_clear[row][COLNO-2]) { /* adjacent is clear */
1004 left_ptrs[row][COLNO-1] = COLNO-1;
1005 } else {
1006 left_ptrs[row][COLNO-1] = left_ptrs[row][COLNO-2];
1007 for (i = left_ptrs[row][COLNO-2]; i < COLNO-1; i++)
1008 right_ptrs[row][i] = COLNO-1;
1009 }
1010 }
1011
1012 /*
1013 * Else we know that we are not on an edge.
1014 */
1015 else if (viz_clear[row][col-1] && viz_clear[row][col+1]) {
1016 /* Both sides clear */
1017 for (i = left_ptrs[row][col-1]+1; i <= col; i++)
1018 right_ptrs[row][i] = col;
1019
1020 if (!left_ptrs[row][col-1]) /* catch the end case */
1021 right_ptrs[row][0] = col;
1022
1023 for (i = col; i < right_ptrs[row][col+1]; i++)
1024 left_ptrs[row][i] = col;
1025
1026 if (right_ptrs[row][col+1] == COLNO-1) /* catch the end case */
1027 left_ptrs[row][COLNO-1] = col;
1028
1029 } else if (viz_clear[row][col-1]) {
1030 /* Left side clear, right side blocked. */
1031 for (i = col; i <= right_ptrs[row][col+1]; i++)
1032 left_ptrs[row][i] = col;
1033
1034 for (i = left_ptrs[row][col-1]+1; i < col; i++)
1035 right_ptrs[row][i] = col;
1036
1037 if (!left_ptrs[row][col-1]) /* catch the end case */
1038 right_ptrs[row][i] = col;
1039
1040 right_ptrs[row][col] = right_ptrs[row][col+1];
1041
1042 } else if (viz_clear[row][col+1]) {
1043 /* Right side clear, left side blocked. */
1044 for (i = left_ptrs[row][col-1]; i <= col; i++)
1045 right_ptrs[row][i] = col;
1046
1047 for (i = col+1; i < right_ptrs[row][col+1]; i++)
1048 left_ptrs[row][i] = col;
1049
1050 if (right_ptrs[row][col+1] == COLNO-1) /* catch the end case */
1051 left_ptrs[row][i] = col;
1052
1053 left_ptrs[row][col] = left_ptrs[row][col-1];
1054
1055 } else {
1056 /* Both sides blocked */
1057 for (i = left_ptrs[row][col-1]; i <= col; i++)
1058 right_ptrs[row][i] = right_ptrs[row][col+1];
1059
1060 for (i = col; i <= right_ptrs[row][col+1]; i++)
1061 left_ptrs[row][i] = left_ptrs[row][col-1];
1062 }
1063 }
1064
1065
1066 /*===========================================================================*/
1067 /*===========================================================================*/
1068 /* Use either algorithm C or D. See the config.h for more details. =========*/
1069
1070 /*
1071 * Variables local to both Algorithms C and D.
1072 */
1073 static int start_row;
1074 static int start_col;
1075 static int step;
1076 static char **cs_rows;
1077 static char *cs_left;
1078 static char *cs_right;
1079
1080 static void FDECL((*vis_func), (int,int,genericptr_t));
1081 static genericptr_t varg;
1082
1083 /*
1084 * Both Algorithms C and D use the following macros.
1085 *
1086 * good_row(z) - Return TRUE if the argument is a legal row.
1087 * set_cs(rowp,col) - Set the local could see array.
1088 * set_min(z) - Save the min value of the argument and the current
1089 * row minimum.
1090 * set_max(z) - Save the max value of the argument and the current
1091 * row maximum.
1092 *
1093 * The last three macros depend on having local pointers row_min, row_max,
1094 * and rowp being set correctly.
1095 */
1096 #define set_cs(rowp,col) (rowp[col] = COULD_SEE)
1097 #define good_row(z) ((z) >= 0 && (z) < ROWNO)
1098 #define set_min(z) if (*row_min > (z)) *row_min = (z)
1099 #define set_max(z) if (*row_max < (z)) *row_max = (z)
1100 #define is_clear(row,col) viz_clear_rows[row][col]
1101
1102 /*
1103 * clear_path() expanded into 4 macros/functions:
1104 *
1105 * q1_path()
1106 * q2_path()
1107 * q3_path()
1108 * q4_path()
1109 *
1110 * "Draw" a line from the start to the given location. Stop if we hit
1111 * something that blocks light. The start and finish points themselves are
1112 * not checked, just the points between them. These routines do _not_
1113 * expect to be called with the same starting and stopping point.
1114 *
1115 * These routines use the generalized integer Bresenham's algorithm (fast
1116 * line drawing) for all quadrants. The algorithm was taken from _Procedural
1117 * Elements for Computer Graphics_, by David F. Rogers. McGraw-Hill, 1985.
1118 */
1119 #ifdef MACRO_CPATH /* quadrant calls are macros */
1120
1121 /*
1122 * When called, the result is in "result".
1123 * The first two arguments (srow,scol) are one end of the path. The next
1124 * two arguments (row,col) are the destination. The last argument is
1125 * used as a C language label. This means that it must be different
1126 * in each pair of calls.
1127 */
1128
1129 /*
1130 * Quadrant I (step < 0).
1131 */
1132 #define q1_path(srow,scol,y2,x2,label) \
1133 { \
1134 int dx, dy; \
1135 register int k, err, x, y, dxs, dys; \
1136 \
1137 x = (scol); y = (srow); \
1138 dx = (x2) - x; dy = y - (y2); \
1139 \
1140 result = 0; /* default to a blocked path */\
1141 \
1142 dxs = dx << 1; /* save the shifted values */\
1143 dys = dy << 1; \
1144 if (dy > dx) { \
1145 err = dxs - dy; \
1146 \
1147 for (k = dy-1; k; k--) { \
1148 if (err >= 0) { \
1149 x++; \
1150 err -= dys; \
1151 } \
1152 y--; \
1153 err += dxs; \
1154 if (!is_clear(y,x)) goto label;/* blocked */\
1155 } \
1156 } else { \
1157 err = dys - dx; \
1158 \
1159 for (k = dx-1; k; k--) { \
1160 if (err >= 0) { \
1161 y--; \
1162 err -= dxs; \
1163 } \
1164 x++; \
1165 err += dys; \
1166 if (!is_clear(y,x)) goto label;/* blocked */\
1167 } \
1168 } \
1169 \
1170 result = 1; \
1171 }
1172
1173 /*
1174 * Quadrant IV (step > 0).
1175 */
1176 #define q4_path(srow,scol,y2,x2,label) \
1177 { \
1178 int dx, dy; \
1179 register int k, err, x, y, dxs, dys; \
1180 \
1181 x = (scol); y = (srow); \
1182 dx = (x2) - x; dy = (y2) - y; \
1183 \
1184 result = 0; /* default to a blocked path */\
1185 \
1186 dxs = dx << 1; /* save the shifted values */\
1187 dys = dy << 1; \
1188 if (dy > dx) { \
1189 err = dxs - dy; \
1190 \
1191 for (k = dy-1; k; k--) { \
1192 if (err >= 0) { \
1193 x++; \
1194 err -= dys; \
1195 } \
1196 y++; \
1197 err += dxs; \
1198 if (!is_clear(y,x)) goto label;/* blocked */\
1199 } \
1200 \
1201 } else { \
1202 err = dys - dx; \
1203 \
1204 for (k = dx-1; k; k--) { \
1205 if (err >= 0) { \
1206 y++; \
1207 err -= dxs; \
1208 } \
1209 x++; \
1210 err += dys; \
1211 if (!is_clear(y,x)) goto label;/* blocked */\
1212 } \
1213 } \
1214 \
1215 result = 1; \
1216 }
1217
1218 /*
1219 * Quadrant II (step < 0).
1220 */
1221 #define q2_path(srow,scol,y2,x2,label) \
1222 { \
1223 int dx, dy; \
1224 register int k, err, x, y, dxs, dys; \
1225 \
1226 x = (scol); y = (srow); \
1227 dx = x - (x2); dy = y - (y2); \
1228 \
1229 result = 0; /* default to a blocked path */\
1230 \
1231 dxs = dx << 1; /* save the shifted values */\
1232 dys = dy << 1; \
1233 if (dy > dx) { \
1234 err = dxs - dy; \
1235 \
1236 for (k = dy-1; k; k--) { \
1237 if (err >= 0) { \
1238 x--; \
1239 err -= dys; \
1240 } \
1241 y--; \
1242 err += dxs; \
1243 if (!is_clear(y,x)) goto label;/* blocked */\
1244 } \
1245 } else { \
1246 err = dys - dx; \
1247 \
1248 for (k = dx-1; k; k--) { \
1249 if (err >= 0) { \
1250 y--; \
1251 err -= dxs; \
1252 } \
1253 x--; \
1254 err += dys; \
1255 if (!is_clear(y,x)) goto label;/* blocked */\
1256 } \
1257 } \
1258 \
1259 result = 1; \
1260 }
1261
1262 /*
1263 * Quadrant III (step > 0).
1264 */
1265 #define q3_path(srow,scol,y2,x2,label) \
1266 { \
1267 int dx, dy; \
1268 register int k, err, x, y, dxs, dys; \
1269 \
1270 x = (scol); y = (srow); \
1271 dx = x - (x2); dy = (y2) - y; \
1272 \
1273 result = 0; /* default to a blocked path */\
1274 \
1275 dxs = dx << 1; /* save the shifted values */\
1276 dys = dy << 1; \
1277 if (dy > dx) { \
1278 err = dxs - dy; \
1279 \
1280 for (k = dy-1; k; k--) { \
1281 if (err >= 0) { \
1282 x--; \
1283 err -= dys; \
1284 } \
1285 y++; \
1286 err += dxs; \
1287 if (!is_clear(y,x)) goto label;/* blocked */\
1288 } \
1289 \
1290 } else { \
1291 err = dys - dx; \
1292 \
1293 for (k = dx-1; k; k--) { \
1294 if (err >= 0) { \
1295 y++; \
1296 err -= dxs; \
1297 } \
1298 x--; \
1299 err += dys; \
1300 if (!is_clear(y,x)) goto label;/* blocked */\
1301 } \
1302 } \
1303 \
1304 result = 1; \
1305 }
1306
1307 #else /* quadrants are really functions */
1308
1309 STATIC_DCL int FDECL(_q1_path, (int,int,int,int));
1310 STATIC_DCL int FDECL(_q2_path, (int,int,int,int));
1311 STATIC_DCL int FDECL(_q3_path, (int,int,int,int));
1312 STATIC_DCL int FDECL(_q4_path, (int,int,int,int));
1313
1314 #define q1_path(sy,sx,y,x,dummy) result = _q1_path(sy,sx,y,x)
1315 #define q2_path(sy,sx,y,x,dummy) result = _q2_path(sy,sx,y,x)
1316 #define q3_path(sy,sx,y,x,dummy) result = _q3_path(sy,sx,y,x)
1317 #define q4_path(sy,sx,y,x,dummy) result = _q4_path(sy,sx,y,x)
1318
1319 /*
1320 * Quadrant I (step < 0).
1321 */
1322 STATIC_OVL int
_q1_path(srow,scol,y2,x2)1323 _q1_path(srow,scol,y2,x2)
1324 int scol, srow, y2, x2;
1325 {
1326 int dx, dy;
1327 register int k, err, x, y, dxs, dys;
1328
1329 x = scol; y = srow;
1330 dx = x2 - x; dy = y - y2;
1331
1332 dxs = dx << 1; /* save the shifted values */
1333 dys = dy << 1;
1334 if (dy > dx) {
1335 err = dxs - dy;
1336
1337 for (k = dy-1; k; k--) {
1338 if (err >= 0) {
1339 x++;
1340 err -= dys;
1341 }
1342 y--;
1343 err += dxs;
1344 if (!is_clear(y,x)) return 0; /* blocked */
1345 }
1346 } else {
1347 err = dys - dx;
1348
1349 for (k = dx-1; k; k--) {
1350 if (err >= 0) {
1351 y--;
1352 err -= dxs;
1353 }
1354 x++;
1355 err += dys;
1356 if (!is_clear(y,x)) return 0;/* blocked */
1357 }
1358 }
1359
1360 return 1;
1361 }
1362
1363 /*
1364 * Quadrant IV (step > 0).
1365 */
1366 STATIC_OVL int
_q4_path(srow,scol,y2,x2)1367 _q4_path(srow,scol,y2,x2)
1368 int scol, srow, y2, x2;
1369 {
1370 int dx, dy;
1371 register int k, err, x, y, dxs, dys;
1372
1373 x = scol; y = srow;
1374 dx = x2 - x; dy = y2 - y;
1375
1376 dxs = dx << 1; /* save the shifted values */
1377 dys = dy << 1;
1378 if (dy > dx) {
1379 err = dxs - dy;
1380
1381 for (k = dy-1; k; k--) {
1382 if (err >= 0) {
1383 x++;
1384 err -= dys;
1385 }
1386 y++;
1387 err += dxs;
1388 if (!is_clear(y,x)) return 0; /* blocked */
1389 }
1390 } else {
1391 err = dys - dx;
1392
1393 for (k = dx-1; k; k--) {
1394 if (err >= 0) {
1395 y++;
1396 err -= dxs;
1397 }
1398 x++;
1399 err += dys;
1400 if (!is_clear(y,x)) return 0;/* blocked */
1401 }
1402 }
1403
1404 return 1;
1405 }
1406
1407 /*
1408 * Quadrant II (step < 0).
1409 */
1410 STATIC_OVL int
_q2_path(srow,scol,y2,x2)1411 _q2_path(srow,scol,y2,x2)
1412 int scol, srow, y2, x2;
1413 {
1414 int dx, dy;
1415 register int k, err, x, y, dxs, dys;
1416
1417 x = scol; y = srow;
1418 dx = x - x2; dy = y - y2;
1419
1420 dxs = dx << 1; /* save the shifted values */
1421 dys = dy << 1;
1422 if (dy > dx) {
1423 err = dxs - dy;
1424
1425 for (k = dy-1; k; k--) {
1426 if (err >= 0) {
1427 x--;
1428 err -= dys;
1429 }
1430 y--;
1431 err += dxs;
1432 if (!is_clear(y,x)) return 0; /* blocked */
1433 }
1434 } else {
1435 err = dys - dx;
1436
1437 for (k = dx-1; k; k--) {
1438 if (err >= 0) {
1439 y--;
1440 err -= dxs;
1441 }
1442 x--;
1443 err += dys;
1444 if (!is_clear(y,x)) return 0;/* blocked */
1445 }
1446 }
1447
1448 return 1;
1449 }
1450
1451 /*
1452 * Quadrant III (step > 0).
1453 */
1454 STATIC_OVL int
_q3_path(srow,scol,y2,x2)1455 _q3_path(srow,scol,y2,x2)
1456 int scol, srow, y2, x2;
1457 {
1458 int dx, dy;
1459 register int k, err, x, y, dxs, dys;
1460
1461 x = scol; y = srow;
1462 dx = x - x2; dy = y2 - y;
1463
1464 dxs = dx << 1; /* save the shifted values */
1465 dys = dy << 1;
1466 if (dy > dx) {
1467 err = dxs - dy;
1468
1469 for (k = dy-1; k; k--) {
1470 if (err >= 0) {
1471 x--;
1472 err -= dys;
1473 }
1474 y++;
1475 err += dxs;
1476 if (!is_clear(y,x)) return 0; /* blocked */
1477 }
1478 } else {
1479 err = dys - dx;
1480
1481 for (k = dx-1; k; k--) {
1482 if (err >= 0) {
1483 y++;
1484 err -= dxs;
1485 }
1486 x--;
1487 err += dys;
1488 if (!is_clear(y,x)) return 0;/* blocked */
1489 }
1490 }
1491
1492 return 1;
1493 }
1494
1495 #endif /* quadrants are functions */
1496
1497 /*
1498 * Use vision tables to determine if there is a clear path from
1499 * (col1,row1) to (col2,row2). This is used by:
1500 * m_cansee()
1501 * m_canseeu()
1502 * do_light_sources()
1503 */
1504 boolean
clear_path(col1,row1,col2,row2)1505 clear_path(col1,row1,col2,row2)
1506 int col1, row1, col2, row2;
1507 {
1508 int result;
1509
1510 if(col1 < col2) {
1511 if(row1 > row2) {
1512 q1_path(row1,col1,row2,col2,cleardone);
1513 } else {
1514 q4_path(row1,col1,row2,col2,cleardone);
1515 }
1516 } else {
1517 if(row1 > row2) {
1518 q2_path(row1,col1,row2,col2,cleardone);
1519 } else if(row1 == row2 && col1 == col2) {
1520 result = 1;
1521 } else {
1522 q3_path(row1,col1,row2,col2,cleardone);
1523 }
1524 }
1525 #ifdef MACRO_CPATH
1526 cleardone:
1527 #endif
1528 return((boolean)result);
1529 }
1530
1531 #ifdef VISION_TABLES
1532 /*===========================================================================*\
1533 GENERAL LINE OF SIGHT
1534 Algorithm D
1535 \*===========================================================================*/
1536
1537
1538 /*
1539 * Indicate caller for the shadow routines.
1540 */
1541 #define FROM_RIGHT 0
1542 #define FROM_LEFT 1
1543
1544
1545 /*
1546 * Include the table definitions.
1547 */
1548 #include "vis_tab.h"
1549
1550
1551 /* 3D table pointers. */
1552 static close2d *close_dy[CLOSE_MAX_BC_DY];
1553 static far2d *far_dy[FAR_MAX_BC_DY];
1554
1555 STATIC_DCL void FDECL(right_side, (int,int,int,int,int,int,int,char*));
1556 STATIC_DCL void FDECL(left_side, (int,int,int,int,int,int,int,char*));
1557 STATIC_DCL int FDECL(close_shadow, (int,int,int,int));
1558 STATIC_DCL int FDECL(far_shadow, (int,int,int,int));
1559
1560 /*
1561 * Initialize algorithm D's table pointers. If we don't have these,
1562 * then we do 3D table lookups. Verrrry slow.
1563 */
1564 STATIC_OVL void
view_init()1565 view_init()
1566 {
1567 int i;
1568
1569 for (i = 0; i < CLOSE_MAX_BC_DY; i++)
1570 close_dy[i] = &close_table[i];
1571
1572 for (i = 0; i < FAR_MAX_BC_DY; i++)
1573 far_dy[i] = &far_table[i];
1574 }
1575
1576
1577 /*
1578 * If the far table has an entry of OFF_TABLE, then the far block prevents
1579 * us from seeing the location just above/below it. I.e. the first visible
1580 * location is one *before* the block.
1581 */
1582 #define OFF_TABLE 0xff
1583
1584 STATIC_OVL int
close_shadow(side,this_row,block_row,block_col)1585 close_shadow(side,this_row,block_row,block_col)
1586 int side,this_row,block_row,block_col;
1587 {
1588 register int sdy, sdx, pdy, offset;
1589
1590 /*
1591 * If on the same column (block_row = -1), then we can see it.
1592 */
1593 if (block_row < 0) return block_col;
1594
1595 /* Take explicit absolute values. Adjust. */
1596 if ((sdy = (start_row-block_row)) < 0) sdy = -sdy; --sdy; /* src dy */
1597 if ((sdx = (start_col-block_col)) < 0) sdx = -sdx; /* src dx */
1598 if ((pdy = (block_row-this_row)) < 0) pdy = -pdy; /* point dy */
1599
1600 if (sdy < 0 || sdy >= CLOSE_MAX_SB_DY || sdx >= CLOSE_MAX_SB_DX ||
1601 pdy >= CLOSE_MAX_BC_DY) {
1602 impossible("close_shadow: bad value");
1603 return block_col;
1604 }
1605 offset = close_dy[sdy]->close[sdx][pdy];
1606 if (side == FROM_RIGHT)
1607 return block_col + offset;
1608
1609 return block_col - offset;
1610 }
1611
1612
1613 STATIC_OVL int
far_shadow(side,this_row,block_row,block_col)1614 far_shadow(side,this_row,block_row,block_col)
1615 int side,this_row,block_row,block_col;
1616 {
1617 register int sdy, sdx, pdy, offset;
1618
1619 /*
1620 * Take care of a bug that shows up only on the borders.
1621 *
1622 * If the block is beyond the border, then the row is negative. Return
1623 * the block's column number (should be 0 or COLNO-1).
1624 *
1625 * Could easily have the column be -1, but then wouldn't know if it was
1626 * the left or right border.
1627 */
1628 if (block_row < 0) return block_col;
1629
1630 /* Take explicit absolute values. Adjust. */
1631 if ((sdy = (start_row-block_row)) < 0) sdy = -sdy; /* src dy */
1632 if ((sdx = (start_col-block_col)) < 0) sdx = -sdx; --sdx; /* src dx */
1633 if ((pdy = (block_row-this_row)) < 0) pdy = -pdy; --pdy; /* point dy */
1634
1635 if (sdy >= FAR_MAX_SB_DY || sdx < 0 || sdx >= FAR_MAX_SB_DX ||
1636 pdy < 0 || pdy >= FAR_MAX_BC_DY) {
1637 impossible("far_shadow: bad value");
1638 return block_col;
1639 }
1640 if ((offset = far_dy[sdy]->far_q[sdx][pdy]) == OFF_TABLE) offset = -1;
1641 if (side == FROM_RIGHT)
1642 return block_col + offset;
1643
1644 return block_col - offset;
1645 }
1646
1647
1648 /*
1649 * right_side()
1650 *
1651 * Figure out what could be seen on the right side of the source.
1652 */
1653 STATIC_OVL void
right_side(row,cb_row,cb_col,fb_row,fb_col,left,right_mark,limits)1654 right_side(row, cb_row, cb_col, fb_row, fb_col, left, right_mark, limits)
1655 int row; /* current row */
1656 int cb_row, cb_col; /* close block row and col */
1657 int fb_row, fb_col; /* far block row and col */
1658 int left; /* left mark of the previous row */
1659 int right_mark; /* right mark of previous row */
1660 char *limits; /* points at range limit for current row, or NULL */
1661 {
1662 register int i;
1663 register char *rowp;
1664 int hit_stone = 0;
1665 int left_shadow, right_shadow, loc_right;
1666 int lblock_col; /* local block column (current row) */
1667 int nrow, deeper;
1668 char *row_min; /* left most */
1669 char *row_max; /* right most */
1670 int lim_max; /* right most limit of circle */
1671
1672 #ifdef GCC_WARN
1673 rowp = 0;
1674 #endif
1675 nrow = row + step;
1676 deeper = good_row(nrow) && (!limits || (*limits >= *(limits+1)));
1677 if(!vis_func) {
1678 rowp = cs_rows[row];
1679 row_min = &cs_left[row];
1680 row_max = &cs_right[row];
1681 }
1682 if(limits) {
1683 lim_max = start_col + *limits;
1684 if(lim_max > COLNO-1) lim_max = COLNO-1;
1685 if(right_mark > lim_max) right_mark = lim_max;
1686 limits++; /* prepare for next row */
1687 } else
1688 lim_max = COLNO-1;
1689
1690 /*
1691 * Get the left shadow from the close block. This value could be
1692 * illegal.
1693 */
1694 left_shadow = close_shadow(FROM_RIGHT,row,cb_row,cb_col);
1695
1696 /*
1697 * Mark all stone walls as seen before the left shadow. All this work
1698 * for a special case.
1699 *
1700 * NOTE. With the addition of this code in here, it is now *required*
1701 * for the algorithm to work correctly. If this is commented out,
1702 * change the above assignment so that left and not left_shadow is the
1703 * variable that gets the shadow.
1704 */
1705 while (left <= right_mark) {
1706 loc_right = right_ptrs[row][left];
1707 if(loc_right > lim_max) loc_right = lim_max;
1708 if (viz_clear_rows[row][left]) {
1709 if (loc_right >= left_shadow) {
1710 left = left_shadow; /* opening ends beyond shadow */
1711 break;
1712 }
1713 left = loc_right;
1714 loc_right = right_ptrs[row][left];
1715 if(loc_right > lim_max) loc_right = lim_max;
1716 if (left == loc_right) return; /* boundary */
1717
1718 /* Shadow covers opening, beyond right mark */
1719 if (left == right_mark && left_shadow > right_mark) return;
1720 }
1721
1722 if (loc_right > right_mark) /* can't see stone beyond the mark */
1723 loc_right = right_mark;
1724
1725 if(vis_func) {
1726 for (i = left; i <= loc_right; i++) (*vis_func)(i, row, varg);
1727 } else {
1728 for (i = left; i <= loc_right; i++) set_cs(rowp,i);
1729 set_min(left); set_max(loc_right);
1730 }
1731
1732 if (loc_right == right_mark) return; /* all stone */
1733 if (loc_right >= left_shadow) hit_stone = 1;
1734 left = loc_right + 1;
1735 }
1736
1737 /*
1738 * At this point we are at the first visible clear spot on or beyond
1739 * the left shadow, unless the left shadow is an illegal value. If we
1740 * have "hit stone" then we have a stone wall just to our left.
1741 */
1742
1743 /*
1744 * Get the right shadow. Make sure that it is a legal value.
1745 */
1746 if ((right_shadow = far_shadow(FROM_RIGHT,row,fb_row,fb_col)) >= COLNO)
1747 right_shadow = COLNO-1;
1748 /*
1749 * Make vertical walls work the way we want them. In this case, we
1750 * note when the close block blocks the column just above/beneath
1751 * it (right_shadow < fb_col [actually right_shadow == fb_col-1]). If
1752 * the location is filled, then we want to see it, so we put the
1753 * right shadow back (same as fb_col).
1754 */
1755 if (right_shadow < fb_col && !viz_clear_rows[row][fb_col])
1756 right_shadow = fb_col;
1757 if(right_shadow > lim_max) right_shadow = lim_max;
1758
1759 /*
1760 * Main loop. Within the range of sight of the previous row, mark all
1761 * stone walls as seen. Follow open areas recursively.
1762 */
1763 while (left <= right_mark) {
1764 /* Get the far right of the opening or wall */
1765 loc_right = right_ptrs[row][left];
1766 if(loc_right > lim_max) loc_right = lim_max;
1767
1768 if (!viz_clear_rows[row][left]) {
1769 hit_stone = 1; /* use stone on this row as close block */
1770 /*
1771 * We can see all of the wall until the next open spot or the
1772 * start of the shadow caused by the far block (right).
1773 *
1774 * Can't see stone beyond the right mark.
1775 */
1776 if (loc_right > right_mark) loc_right = right_mark;
1777
1778 if(vis_func) {
1779 for (i = left; i <= loc_right; i++) (*vis_func)(i, row, varg);
1780 } else {
1781 for (i = left; i <= loc_right; i++) set_cs(rowp,i);
1782 set_min(left); set_max(loc_right);
1783 }
1784
1785 if (loc_right == right_mark) return; /* hit the end */
1786 left = loc_right + 1;
1787 loc_right = right_ptrs[row][left];
1788 if(loc_right > lim_max) loc_right = lim_max;
1789 /* fall through... we know at least one position is visible */
1790 }
1791
1792 /*
1793 * We are in an opening.
1794 *
1795 * If this is the first open spot since the could see area (this is
1796 * true if we have hit stone), get the shadow generated by the wall
1797 * just to our left.
1798 */
1799 if (hit_stone) {
1800 lblock_col = left-1; /* local block column */
1801 left = close_shadow(FROM_RIGHT,row,row,lblock_col);
1802 if (left > lim_max) break; /* off the end */
1803 }
1804
1805 /*
1806 * Check if the shadow covers the opening. If it does, then
1807 * move to end of the opening. A shadow generated on from a
1808 * wall on this row does *not* cover the wall on the right
1809 * of the opening.
1810 */
1811 if (left >= loc_right) {
1812 if (loc_right == lim_max) { /* boundary */
1813 if (left == lim_max) {
1814 if(vis_func) (*vis_func)(lim_max, row, varg);
1815 else {
1816 set_cs(rowp,lim_max); /* last pos */
1817 set_max(lim_max);
1818 }
1819 }
1820 return; /* done */
1821 }
1822 left = loc_right;
1823 continue;
1824 }
1825
1826 /*
1827 * If the far wall of the opening (loc_right) is closer than the
1828 * shadow limit imposed by the far block (right) then use the far
1829 * wall as our new far block when we recurse.
1830 *
1831 * If the limits are the the same, and the far block really exists
1832 * (fb_row >= 0) then do the same as above.
1833 *
1834 * Normally, the check would be for the far wall being closer OR EQUAL
1835 * to the shadow limit. However, there is a bug that arises from the
1836 * fact that the clear area pointers end in an open space (if it
1837 * exists) on a boundary. This then makes a far block exist where it
1838 * shouldn't --- on a boundary. To get around that, I had to
1839 * introduce the concept of a non-existent far block (when the
1840 * row < 0). Next I have to check for it. Here is where that check
1841 * exists.
1842 */
1843 if ((loc_right < right_shadow) ||
1844 (fb_row >= 0 && loc_right == right_shadow)) {
1845 if(vis_func) {
1846 for (i = left; i <= loc_right; i++) (*vis_func)(i, row, varg);
1847 } else {
1848 for (i = left; i <= loc_right; i++) set_cs(rowp,i);
1849 set_min(left); set_max(loc_right);
1850 }
1851
1852 if (deeper) {
1853 if (hit_stone)
1854 right_side(nrow,row,lblock_col,row,loc_right,
1855 left,loc_right,limits);
1856 else
1857 right_side(nrow,cb_row,cb_col,row,loc_right,
1858 left,loc_right,limits);
1859 }
1860
1861 /*
1862 * The following line, setting hit_stone, is needed for those
1863 * walls that are only 1 wide. If hit stone is *not* set and
1864 * the stone is only one wide, then the close block is the old
1865 * one instead one on the current row. A way around having to
1866 * set it here is to make left = loc_right (not loc_right+1) and
1867 * let the outer loop take care of it. However, if we do that
1868 * then we then have to check for boundary conditions here as
1869 * well.
1870 */
1871 hit_stone = 1;
1872
1873 left = loc_right+1;
1874 }
1875 /*
1876 * The opening extends beyond the right mark. This means that
1877 * the next far block is the current far block.
1878 */
1879 else {
1880 if(vis_func) {
1881 for (i=left; i <= right_shadow; i++) (*vis_func)(i, row, varg);
1882 } else {
1883 for (i = left; i <= right_shadow; i++) set_cs(rowp,i);
1884 set_min(left); set_max(right_shadow);
1885 }
1886
1887 if (deeper) {
1888 if (hit_stone)
1889 right_side(nrow, row,lblock_col,fb_row,fb_col,
1890 left,right_shadow,limits);
1891 else
1892 right_side(nrow,cb_row, cb_col,fb_row,fb_col,
1893 left,right_shadow,limits);
1894 }
1895
1896 return; /* we're outta here */
1897 }
1898 }
1899 }
1900
1901
1902 /*
1903 * left_side()
1904 *
1905 * This routine is the mirror image of right_side(). Please see right_side()
1906 * for blow by blow comments.
1907 */
1908 STATIC_OVL void
left_side(row,cb_row,cb_col,fb_row,fb_col,left_mark,right,limits)1909 left_side(row, cb_row, cb_col, fb_row, fb_col, left_mark, right, limits)
1910 int row; /* the current row */
1911 int cb_row, cb_col; /* close block row and col */
1912 int fb_row, fb_col; /* far block row and col */
1913 int left_mark; /* left mark of previous row */
1914 int right; /* right mark of the previous row */
1915 char *limits;
1916 {
1917 register int i;
1918 register char *rowp;
1919 int hit_stone = 0;
1920 int left_shadow, right_shadow, loc_left;
1921 int lblock_col; /* local block column (current row) */
1922 int nrow, deeper;
1923 char *row_min; /* left most */
1924 char *row_max; /* right most */
1925 int lim_min;
1926
1927 #ifdef GCC_WARN
1928 rowp = 0;
1929 #endif
1930 nrow = row + step;
1931 deeper = good_row(nrow) && (!limits || (*limits >= *(limits+1)));
1932 if(!vis_func) {
1933 rowp = cs_rows[row];
1934 row_min = &cs_left[row];
1935 row_max = &cs_right[row];
1936 }
1937 if(limits) {
1938 lim_min = start_col - *limits;
1939 if(lim_min < 0) lim_min = 0;
1940 if(left_mark < lim_min) left_mark = lim_min;
1941 limits++; /* prepare for next row */
1942 } else
1943 lim_min = 0;
1944
1945 /* This value could be illegal. */
1946 right_shadow = close_shadow(FROM_LEFT,row,cb_row,cb_col);
1947
1948 while ( right >= left_mark ) {
1949 loc_left = left_ptrs[row][right];
1950 if(loc_left < lim_min) loc_left = lim_min;
1951 if (viz_clear_rows[row][right]) {
1952 if (loc_left <= right_shadow) {
1953 right = right_shadow; /* opening ends beyond shadow */
1954 break;
1955 }
1956 right = loc_left;
1957 loc_left = left_ptrs[row][right];
1958 if(loc_left < lim_min) loc_left = lim_min;
1959 if (right == loc_left) return; /* boundary */
1960 }
1961
1962 if (loc_left < left_mark) /* can't see beyond the left mark */
1963 loc_left = left_mark;
1964
1965 if(vis_func) {
1966 for (i = loc_left; i <= right; i++) (*vis_func)(i, row, varg);
1967 } else {
1968 for (i = loc_left; i <= right; i++) set_cs(rowp,i);
1969 set_min(loc_left); set_max(right);
1970 }
1971
1972 if (loc_left == left_mark) return; /* all stone */
1973 if (loc_left <= right_shadow) hit_stone = 1;
1974 right = loc_left - 1;
1975 }
1976
1977 /* At first visible clear spot on or beyond the right shadow. */
1978
1979 if ((left_shadow = far_shadow(FROM_LEFT,row,fb_row,fb_col)) < 0)
1980 left_shadow = 0;
1981
1982 /* Do vertical walls as we want. */
1983 if (left_shadow > fb_col && !viz_clear_rows[row][fb_col])
1984 left_shadow = fb_col;
1985 if(left_shadow < lim_min) left_shadow = lim_min;
1986
1987 while (right >= left_mark) {
1988 loc_left = left_ptrs[row][right];
1989
1990 if (!viz_clear_rows[row][right]) {
1991 hit_stone = 1; /* use stone on this row as close block */
1992
1993 /* We can only see walls until the left mark */
1994 if (loc_left < left_mark) loc_left = left_mark;
1995
1996 if(vis_func) {
1997 for (i = loc_left; i <= right; i++) (*vis_func)(i, row, varg);
1998 } else {
1999 for (i = loc_left; i <= right; i++) set_cs(rowp,i);
2000 set_min(loc_left); set_max(right);
2001 }
2002
2003 if (loc_left == left_mark) return; /* hit end */
2004 right = loc_left - 1;
2005 loc_left = left_ptrs[row][right];
2006 if (loc_left < lim_min) loc_left = lim_min;
2007 /* fall through...*/
2008 }
2009
2010 /* We are in an opening. */
2011 if (hit_stone) {
2012 lblock_col = right+1; /* stone block (local) */
2013 right = close_shadow(FROM_LEFT,row,row,lblock_col);
2014 if (right < lim_min) return; /* off the end */
2015 }
2016
2017 /* Check if the shadow covers the opening. */
2018 if (right <= loc_left) {
2019 /* Make a boundary condition work. */
2020 if (loc_left == lim_min) { /* at boundary */
2021 if (right == lim_min) {
2022 if(vis_func) (*vis_func)(lim_min, row, varg);
2023 else {
2024 set_cs(rowp,lim_min); /* caught the last pos */
2025 set_min(lim_min);
2026 }
2027 }
2028 return; /* and break out the loop */
2029 }
2030
2031 right = loc_left;
2032 continue;
2033 }
2034
2035 /* If the far wall of the opening is closer than the shadow limit. */
2036 if ((loc_left > left_shadow) ||
2037 (fb_row >= 0 && loc_left == left_shadow)) {
2038 if(vis_func) {
2039 for (i = loc_left; i <= right; i++) (*vis_func)(i, row, varg);
2040 } else {
2041 for (i = loc_left; i <= right; i++) set_cs(rowp,i);
2042 set_min(loc_left); set_max(right);
2043 }
2044
2045 if (deeper) {
2046 if (hit_stone)
2047 left_side(nrow,row,lblock_col,row,loc_left,
2048 loc_left,right,limits);
2049 else
2050 left_side(nrow,cb_row,cb_col,row,loc_left,
2051 loc_left,right,limits);
2052 }
2053
2054 hit_stone = 1; /* needed for walls of width 1 */
2055 right = loc_left-1;
2056 }
2057 /* The opening extends beyond the left mark. */
2058 else {
2059 if(vis_func) {
2060 for (i=left_shadow; i <= right; i++) (*vis_func)(i, row, varg);
2061 } else {
2062 for (i = left_shadow; i <= right; i++) set_cs(rowp,i);
2063 set_min(left_shadow); set_max(right);
2064 }
2065
2066 if (deeper) {
2067 if (hit_stone)
2068 left_side(nrow,row,lblock_col,fb_row,fb_col,
2069 left_shadow,right,limits);
2070 else
2071 left_side(nrow,cb_row,cb_col,fb_row,fb_col,
2072 left_shadow,right,limits);
2073 }
2074
2075 return; /* we're outta here */
2076 }
2077
2078 }
2079 }
2080
2081 /*
2082 * view_from
2083 *
2084 * Calculate a view from the given location. Initialize and fill a
2085 * ROWNOxCOLNO array (could_see) with all the locations that could be
2086 * seen from the source location. Initialize and fill the left most
2087 * and right most boundaries of what could be seen.
2088 */
2089 STATIC_OVL void
view_from(srow,scol,loc_cs_rows,left_most,right_most,range,func,arg)2090 view_from(srow,scol,loc_cs_rows,left_most,right_most, range, func, arg)
2091 int srow, scol; /* source row and column */
2092 char **loc_cs_rows; /* could_see array (row pointers) */
2093 char *left_most, *right_most; /* limits of what could be seen */
2094 int range; /* 0 if unlimited */
2095 void FDECL((*func), (int,int,genericptr_t));
2096 genericptr_t arg;
2097 {
2098 register int i;
2099 char *rowp;
2100 int nrow, left, right, left_row, right_row;
2101 char *limits;
2102
2103 /* Set globals for near_shadow(), far_shadow(), etc. to use. */
2104 start_col = scol;
2105 start_row = srow;
2106 cs_rows = loc_cs_rows;
2107 cs_left = left_most;
2108 cs_right = right_most;
2109 vis_func = func;
2110 varg = arg;
2111
2112 /* Find the left and right limits of sight on the starting row. */
2113 if (viz_clear_rows[srow][scol]) {
2114 left = left_ptrs[srow][scol];
2115 right = right_ptrs[srow][scol];
2116 } else {
2117 left = (!scol) ? 0 :
2118 (viz_clear_rows[srow][scol-1] ? left_ptrs[srow][scol-1] : scol-1);
2119 right = (scol == COLNO-1) ? COLNO-1 :
2120 (viz_clear_rows[srow][scol+1] ? right_ptrs[srow][scol+1] : scol+1);
2121 }
2122
2123 if(range) {
2124 if(range > MAX_RADIUS || range < 1)
2125 panic("view_from called with range %d", range);
2126 limits = circle_ptr(range) + 1; /* start at next row */
2127 if(left < scol - range) left = scol - range;
2128 if(right > scol + range) right = scol + range;
2129 } else
2130 limits = (char*) 0;
2131
2132 if(func) {
2133 for (i = left; i <= right; i++) (*func)(i, srow, arg);
2134 } else {
2135 /* Row optimization */
2136 rowp = cs_rows[srow];
2137
2138 /* We know that we can see our row. */
2139 for (i = left; i <= right; i++) set_cs(rowp,i);
2140 cs_left[srow] = left;
2141 cs_right[srow] = right;
2142 }
2143
2144 /* The far block has a row number of -1 if we are on an edge. */
2145 right_row = (right == COLNO-1) ? -1 : srow;
2146 left_row = (!left) ? -1 : srow;
2147
2148 /*
2149 * Check what could be seen in quadrants.
2150 */
2151 if ( (nrow = srow+1) < ROWNO ) {
2152 step = 1; /* move down */
2153 if (scol<COLNO-1)
2154 right_side(nrow,-1,scol,right_row,right,scol,right,limits);
2155 if (scol)
2156 left_side(nrow,-1,scol,left_row, left, left, scol,limits);
2157 }
2158
2159 if ( (nrow = srow-1) >= 0 ) {
2160 step = -1; /* move up */
2161 if (scol<COLNO-1)
2162 right_side(nrow,-1,scol,right_row,right,scol,right,limits);
2163 if (scol)
2164 left_side(nrow,-1,scol,left_row, left, left, scol,limits);
2165 }
2166 }
2167
2168
2169 #else /*===== End of algorithm D =====*/
2170
2171
2172 /*===========================================================================*\
2173 GENERAL LINE OF SIGHT
2174 Algorithm C
2175 \*===========================================================================*/
2176
2177 /*
2178 * Defines local to Algorithm C.
2179 */
2180 STATIC_DCL void FDECL(right_side, (int,int,int,char*));
2181 STATIC_DCL void FDECL(left_side, (int,int,int,char*));
2182
2183 /* Initialize algorithm C (nothing). */
2184 STATIC_OVL void
view_init()2185 view_init()
2186 {
2187 }
2188
2189 /*
2190 * Mark positions as visible on one quadrant of the right side. The
2191 * quadrant is determined by the value of the global variable step.
2192 */
2193 STATIC_OVL void
right_side(row,left,right_mark,limits)2194 right_side(row, left, right_mark, limits)
2195 int row; /* current row */
2196 int left; /* first (left side) visible spot on prev row */
2197 int right_mark; /* last (right side) visible spot on prev row */
2198 char *limits; /* points at range limit for current row, or NULL */
2199 {
2200 int right; /* right limit of "could see" */
2201 int right_edge; /* right edge of an opening */
2202 int nrow; /* new row (calculate once) */
2203 int deeper; /* if TRUE, call self as needed */
2204 int result; /* set by q?_path() */
2205 register int i; /* loop counter */
2206 register char *rowp; /* row optimization */
2207 char *row_min; /* left most [used by macro set_min()] */
2208 char *row_max; /* right most [used by macro set_max()] */
2209 int lim_max; /* right most limit of circle */
2210
2211 rowp = row_min = row_max = 0;
2212 nrow = row + step;
2213 /*
2214 * Can go deeper if the row is in bounds and the next row is within
2215 * the circle's limit. We tell the latter by checking to see if the next
2216 * limit value is the start of a new circle radius (meaning we depend
2217 * on the structure of circle_data[]).
2218 */
2219 deeper = good_row(nrow) && (!limits || (*limits >= *(limits+1)));
2220 if(!vis_func) {
2221 rowp = cs_rows[row]; /* optimization */
2222 row_min = &cs_left[row];
2223 row_max = &cs_right[row];
2224 }
2225 if(limits) {
2226 lim_max = start_col + *limits;
2227 if(lim_max > COLNO-1) lim_max = COLNO-1;
2228 if(right_mark > lim_max) right_mark = lim_max;
2229 limits++; /* prepare for next row */
2230 } else
2231 lim_max = COLNO-1;
2232
2233 while (left <= right_mark) {
2234 right_edge = right_ptrs[row][left];
2235 if(right_edge > lim_max) right_edge = lim_max;
2236
2237 if (!is_clear(row,left)) {
2238 /*
2239 * Jump to the far side of a stone wall. We can set all
2240 * the points in between as seen.
2241 *
2242 * If the right edge goes beyond the right mark, check to see
2243 * how much we can see.
2244 */
2245 if (right_edge > right_mark) {
2246 /*
2247 * If the mark on the previous row was a clear position,
2248 * the odds are that we can actually see part of the wall
2249 * beyond the mark on this row. If so, then see one beyond
2250 * the mark. Otherwise don't. This is a kludge so corners
2251 * with an adjacent doorway show up in nethack.
2252 */
2253 right_edge = is_clear(row-step,right_mark) ?
2254 right_mark+1 : right_mark;
2255 }
2256 if(vis_func) {
2257 for (i = left; i <= right_edge; i++) (*vis_func)(i, row, varg);
2258 } else {
2259 for (i = left; i <= right_edge; i++) set_cs(rowp,i);
2260 set_min(left); set_max(right_edge);
2261 }
2262 left = right_edge + 1; /* no limit check necessary */
2263 continue;
2264 }
2265
2266 /* No checking needed if our left side is the start column. */
2267 if (left != start_col) {
2268 /*
2269 * Find the left side. Move right until we can see it or we run
2270 * into a wall.
2271 */
2272 for (; left <= right_edge; left++) {
2273 if (step < 0) {
2274 q1_path(start_row,start_col,row,left,rside1);
2275 } else {
2276 q4_path(start_row,start_col,row,left,rside1);
2277 }
2278 rside1: /* used if q?_path() is a macro */
2279 if (result) break;
2280 }
2281
2282 /*
2283 * Check for boundary conditions. We *need* check (2) to break
2284 * an infinite loop where:
2285 *
2286 * left == right_edge == right_mark == lim_max.
2287 *
2288 */
2289 if (left > lim_max) return; /* check (1) */
2290 if (left == lim_max) { /* check (2) */
2291 if(vis_func) (*vis_func)(lim_max, row, varg);
2292 else {
2293 set_cs(rowp,lim_max);
2294 set_max(lim_max);
2295 }
2296 return;
2297 }
2298 /*
2299 * Check if we can see any spots in the opening. We might
2300 * (left == right_edge) or might not (left == right_edge+1) have
2301 * been able to see the far wall. Make sure we *can* see the
2302 * wall (remember, we can see the spot above/below this one)
2303 * by backing up.
2304 */
2305 if (left >= right_edge) {
2306 left = right_edge; /* for the case left == right_edge+1 */
2307 continue;
2308 }
2309 }
2310
2311 /*
2312 * Find the right side. If the marker from the previous row is
2313 * closer than the edge on this row, then we have to check
2314 * how far we can see around the corner (under the overhang). Stop
2315 * at the first non-visible spot or we actually hit the far wall.
2316 *
2317 * Otherwise, we know we can see the right edge of the current row.
2318 *
2319 * This must be a strict less than so that we can always see a
2320 * horizontal wall, even if it is adjacent to us.
2321 */
2322 if (right_mark < right_edge) {
2323 for (right = right_mark; right <= right_edge; right++) {
2324 if (step < 0) {
2325 q1_path(start_row,start_col,row,right,rside2);
2326 } else {
2327 q4_path(start_row,start_col,row,right,rside2);
2328 }
2329 rside2: /* used if q?_path() is a macro */
2330 if (!result) break;
2331 }
2332 --right; /* get rid of the last increment */
2333 }
2334 else
2335 right = right_edge;
2336
2337 /*
2338 * We have the range that we want. Set the bits. Note that
2339 * there is no else --- we no longer handle splinters.
2340 */
2341 if (left <= right) {
2342 /*
2343 * An ugly special case. If you are adjacent to a vertical wall
2344 * and it has a break in it, then the right mark is set to be
2345 * start_col. We *want* to be able to see adjacent vertical
2346 * walls, so we have to set it back.
2347 */
2348 if (left == right && left == start_col &&
2349 start_col < (COLNO-1) && !is_clear(row,start_col+1))
2350 right = start_col+1;
2351
2352 if(right > lim_max) right = lim_max;
2353 /* set the bits */
2354 if(vis_func)
2355 for (i = left; i <= right; i++) (*vis_func)(i, row, varg);
2356 else {
2357 for (i = left; i <= right; i++) set_cs(rowp,i);
2358 set_min(left); set_max(right);
2359 }
2360
2361 /* recursive call for next finger of light */
2362 if (deeper) right_side(nrow,left,right,limits);
2363 left = right + 1; /* no limit check necessary */
2364 }
2365 }
2366 }
2367
2368
2369 /*
2370 * This routine is the mirror image of right_side(). See right_side() for
2371 * extensive comments.
2372 */
2373 STATIC_OVL void
left_side(row,left_mark,right,limits)2374 left_side(row, left_mark, right, limits)
2375 int row, left_mark, right;
2376 char *limits;
2377 {
2378 int left, left_edge, nrow, deeper, result;
2379 register int i;
2380 register char *rowp;
2381 char *row_min, *row_max;
2382 int lim_min;
2383
2384 rowp = row_min = row_max = 0;
2385 nrow = row+step;
2386 deeper = good_row(nrow) && (!limits || (*limits >= *(limits+1)));
2387 if(!vis_func) {
2388 rowp = cs_rows[row];
2389 row_min = &cs_left[row];
2390 row_max = &cs_right[row];
2391 }
2392 if(limits) {
2393 lim_min = start_col - *limits;
2394 if(lim_min < 0) lim_min = 0;
2395 if(left_mark < lim_min) left_mark = lim_min;
2396 limits++; /* prepare for next row */
2397 } else
2398 lim_min = 0;
2399
2400 while (right >= left_mark) {
2401 left_edge = left_ptrs[row][right];
2402 if(left_edge < lim_min) left_edge = lim_min;
2403
2404 if (!is_clear(row,right)) {
2405 /* Jump to the far side of a stone wall. */
2406 if (left_edge < left_mark) {
2407 /* Maybe see more (kludge). */
2408 left_edge = is_clear(row-step,left_mark) ?
2409 left_mark-1 : left_mark;
2410 }
2411 if(vis_func) {
2412 for (i = left_edge; i <= right; i++) (*vis_func)(i, row, varg);
2413 } else {
2414 for (i = left_edge; i <= right; i++) set_cs(rowp,i);
2415 set_min(left_edge); set_max(right);
2416 }
2417 right = left_edge - 1; /* no limit check necessary */
2418 continue;
2419 }
2420
2421 if (right != start_col) {
2422 /* Find the right side. */
2423 for (; right >= left_edge; right--) {
2424 if (step < 0) {
2425 q2_path(start_row,start_col,row,right,lside1);
2426 } else {
2427 q3_path(start_row,start_col,row,right,lside1);
2428 }
2429 lside1: /* used if q?_path() is a macro */
2430 if (result) break;
2431 }
2432
2433 /* Check for boundary conditions. */
2434 if (right < lim_min) return;
2435 if (right == lim_min) {
2436 if(vis_func) (*vis_func)(lim_min, row, varg);
2437 else {
2438 set_cs(rowp,lim_min);
2439 set_min(lim_min);
2440 }
2441 return;
2442 }
2443 /* Check if we can see any spots in the opening. */
2444 if (right <= left_edge) {
2445 right = left_edge;
2446 continue;
2447 }
2448 }
2449
2450 /* Find the left side. */
2451 if (left_mark > left_edge) {
2452 for (left = left_mark; left >= left_edge; --left) {
2453 if (step < 0) {
2454 q2_path(start_row,start_col,row,left,lside2);
2455 } else {
2456 q3_path(start_row,start_col,row,left,lside2);
2457 }
2458 lside2: /* used if q?_path() is a macro */
2459 if (!result) break;
2460 }
2461 left++; /* get rid of the last decrement */
2462 }
2463 else
2464 left = left_edge;
2465
2466 if (left <= right) {
2467 /* An ugly special case. */
2468 if (left == right && right == start_col &&
2469 start_col > 0 && !is_clear(row,start_col-1))
2470 left = start_col-1;
2471
2472 if(left < lim_min) left = lim_min;
2473 if(vis_func)
2474 for (i = left; i <= right; i++) (*vis_func)(i, row, varg);
2475 else {
2476 for (i = left; i <= right; i++) set_cs(rowp,i);
2477 set_min(left); set_max(right);
2478 }
2479
2480 /* Recurse */
2481 if (deeper) left_side(nrow,left,right,limits);
2482 right = left - 1; /* no limit check necessary */
2483 }
2484 }
2485 }
2486
2487
2488 /*
2489 * Calculate all possible visible locations from the given location
2490 * (srow,scol). NOTE this is (y,x)! Mark the visible locations in the
2491 * array provided.
2492 */
2493 STATIC_OVL void
view_from(srow,scol,loc_cs_rows,left_most,right_most,range,func,arg)2494 view_from(srow, scol, loc_cs_rows, left_most, right_most, range, func, arg)
2495 int srow, scol; /* starting row and column */
2496 char **loc_cs_rows; /* pointers to the rows of the could_see array */
2497 char *left_most; /* min mark on each row */
2498 char *right_most; /* max mark on each row */
2499 int range; /* 0 if unlimited */
2500 void FDECL((*func), (int,int,genericptr_t));
2501 genericptr_t arg;
2502 {
2503 register int i; /* loop counter */
2504 char *rowp; /* optimization for setting could_see */
2505 int nrow; /* the next row */
2506 int left; /* the left-most visible column */
2507 int right; /* the right-most visible column */
2508 char *limits; /* range limit for next row */
2509
2510 /* Set globals for q?_path(), left_side(), and right_side() to use. */
2511 start_col = scol;
2512 start_row = srow;
2513 cs_rows = loc_cs_rows; /* 'could see' rows */
2514 cs_left = left_most;
2515 cs_right = right_most;
2516 vis_func = func;
2517 varg = arg;
2518
2519 /*
2520 * Determine extent of sight on the starting row.
2521 */
2522 if (is_clear(srow,scol)) {
2523 left = left_ptrs[srow][scol];
2524 right = right_ptrs[srow][scol];
2525 } else {
2526 /*
2527 * When in stone, you can only see your adjacent squares, unless
2528 * you are on an array boundary or a stone/clear boundary.
2529 */
2530 left = (!scol) ? 0 :
2531 (is_clear(srow,scol-1) ? left_ptrs[srow][scol-1] : scol-1);
2532 right = (scol == COLNO-1) ? COLNO-1 :
2533 (is_clear(srow,scol+1) ? right_ptrs[srow][scol+1] : scol+1);
2534 }
2535
2536 if(range) {
2537 if(range > MAX_RADIUS || range < 1)
2538 panic("view_from called with range %d", range);
2539 limits = circle_ptr(range) + 1; /* start at next row */
2540 if(left < scol - range) left = scol - range;
2541 if(right > scol + range) right = scol + range;
2542 } else
2543 limits = (char*) 0;
2544
2545 if(func) {
2546 for (i = left; i <= right; i++) (*func)(i, srow, arg);
2547 } else {
2548 /* Row pointer optimization. */
2549 rowp = cs_rows[srow];
2550
2551 /* We know that we can see our row. */
2552 for (i = left; i <= right; i++) set_cs(rowp,i);
2553 cs_left[srow] = left;
2554 cs_right[srow] = right;
2555 }
2556
2557 /*
2558 * Check what could be seen in quadrants. We need to check for valid
2559 * rows here, since we don't do it in the routines right_side() and
2560 * left_side() [ugliness to remove extra routine calls].
2561 */
2562 if ( (nrow = srow+1) < ROWNO ) { /* move down */
2563 step = 1;
2564 if (scol < COLNO-1) right_side(nrow, scol, right, limits);
2565 if (scol) left_side (nrow, left, scol, limits);
2566 }
2567
2568 if ( (nrow = srow-1) >= 0 ) { /* move up */
2569 step = -1;
2570 if (scol < COLNO-1) right_side(nrow, scol, right, limits);
2571 if (scol) left_side (nrow, left, scol, limits);
2572 }
2573 }
2574
2575 #endif /*===== End of algorithm C =====*/
2576
2577 /*
2578 * AREA OF EFFECT "ENGINE"
2579 *
2580 * Calculate all possible visible locations as viewed from the given location
2581 * (srow,scol) within the range specified. Perform "func" with (x, y) args and
2582 * additional argument "arg" for each square.
2583 *
2584 * If not centered on the hero, just forward arguments to view_from(); it
2585 * will call "func" when necessary. If the hero is the center, use the
2586 * vision matrix and reduce extra work.
2587 */
2588 void
do_clear_area(scol,srow,range,func,arg)2589 do_clear_area(scol,srow,range,func,arg)
2590 int scol, srow, range;
2591 void FDECL((*func), (int,int,genericptr_t));
2592 genericptr_t arg;
2593 {
2594 /* If not centered on hero, do the hard work of figuring the area */
2595 if (scol != u.ux || srow != u.uy)
2596 view_from(srow, scol, (char **)0, (char *)0, (char *)0,
2597 range, func, arg);
2598 else {
2599 register int x;
2600 int y, min_x, max_x, max_y, offset;
2601 char *limits;
2602
2603 if (range > MAX_RADIUS || range < 1)
2604 panic("do_clear_area: illegal range %d", range);
2605 if(vision_full_recalc)
2606 vision_recalc(0); /* recalc vision if dirty */
2607 limits = circle_ptr(range);
2608 if ((max_y = (srow + range)) >= ROWNO) max_y = ROWNO-1;
2609 if ((y = (srow - range)) < 0) y = 0;
2610 for (; y <= max_y; y++) {
2611 offset = limits[v_abs(y-srow)];
2612 if((min_x = (scol - offset)) < 0) min_x = 0;
2613 if((max_x = (scol + offset)) >= COLNO) max_x = COLNO-1;
2614 for (x = min_x; x <= max_x; x++)
2615 if (couldsee(x, y))
2616 (*func)(x, y, arg);
2617 }
2618 }
2619 }
2620
2621 /*vision.c*/
2622