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