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