| abstract
| - Below is the full text to vision.c from the source code of NetHack 3.2.0. To link to a particular line, write [[NetHack 3.2.0/vision.c#line123]], for example. Warning! This is the source code from an old release. For the latest release, see Source code 1. /* SCCS Id: @(#)vision.c 3.2 96/02/14 */ 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 void FDECL(fill_point, (int,int)); 99. static void FDECL(dig_point, (int,int)); 100. static void NDECL(view_init); 101. static void FDECL(view_from,(int,int,char **,char *,char *,int, 102. void (*)(int,int,genericptr_t),genericptr_t)); 103. static void FDECL(get_unused_cs, (char ***,char **,char **)); 104. #ifdef REINCARNATION 105. static 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 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 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) || (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 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 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 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 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 void 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 void 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 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 int 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 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(*)())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(*)())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. next_row[col] |= IN_SIGHT; 625. levl[col][row].seenv = SVALL; /* see all! */ 626. } 627. 628. next_rmin[row] = min(start, next_rmin[row]); 629. next_rmax[row] = max(stop, next_rmax[row]); 630. } 631. 632. } else { /* range is 0 */ 633. next_array[u.uy][u.ux] |= IN_SIGHT; 634. levl[u.ux][u.uy].seenv = SVALL; 635. next_rmin[u.uy] = min(u.ux, next_rmin[u.uy]); 636. next_rmax[u.uy] = max(u.ux, next_rmax[u.uy]); 637. } 638. } 639. 640. if (has_night_vision && u.xray_range < u.nv_range) { 641. if (!u.nv_range) { /* range is 0 */ 642. next_array[u.uy][u.ux] |= IN_SIGHT; 643. levl[u.ux][u.uy].seenv = SVALL; 644. next_rmin[u.uy] = min(u.ux, next_rmin[u.uy]); 645. next_rmax[u.uy] = max(u.ux, next_rmax[u.uy]); 646. } else if (u.nv_range > 0) { 647. ranges = circle_ptr(u.nv_range); 648. 649. for (row = u.uy-u.nv_range; row <= u.uy+u.nv_range; row++) { 650. if (row < 0) continue; if (row >= ROWNO) break; 651. dy = v_abs(u.uy-row); next_row = next_array[row]; 652. 653. start = max( 0, u.ux - ranges[dy]); 654. stop = min(COLNO-1, u.ux + ranges[dy]); 655. 656. for (col = start; col <= stop; col++) 657. if (next_row[col]) next_row[col] |= IN_SIGHT; 658. 659. next_rmin[row] = min(start, next_rmin[row]); 660. next_rmax[row] = max(stop, next_rmax[row]); 661. } 662. } 663. } 664. } 665. 666. /* Set the correct bits for all light sources. */ 667. do_light_sources(next_array); 668. 669. 670. /* 671. * Make the viz_array the new array so that cansee() will work correctly. 672. */ 673. temp_array = viz_array; 674. viz_array = next_array; 675. 676. /* 677. * The main update loop. Here we do two things: 678. * 679. * + Set the IN_SIGHT bit for places that we could see and are lit. 680. * + Reset changed places. 681. * 682. * There is one thing that make deciding what the hero can see 683. * difficult: 684. * 685. * 1. Directional lighting. Items that block light create problems. 686. * The worst offenders are doors. Suppose a door to a lit room 687. * is closed. It is lit on one side, but not on the other. How 688. * do you know? You have to check the closest adjacent position. 689. * Even so, that is not entirely correct. But it seems close 690. * enough for now. 691. */ 692. colbump[u.ux] = colbump[u.ux+1] = 1; 693. for (row = 0; row < ROWNO; row++) { 694. dy = u.uy - row; dy = sign(dy); 695. next_row = next_array[row]; old_row = temp_array[row]; 696. 697. /* Find the min and max positions on the row. */ 698. start = min(viz_rmin[row], next_rmin[row]); 699. stop = max(viz_rmax[row], next_rmax[row]); 700. lev = &levl[start][row]; 701. 702. sv = &seenv_matrix[dy+1][start < u.ux ? 0 : (start > u.ux ? 2:1)]; 703. 704. for (col = start; col <= stop; 705. lev += ROWNO, sv += (int) colbump[++col]) { 706. if (next_row[col] & IN_SIGHT) { 707. /* 708. * We see this position because of night- or xray-vision. 709. */ 710. oldseenv = lev->seenv; 711. lev->seenv |= new_angle(lev,sv,row,col); /* update seen angle */ 712. 713. /* Update pos if previously not in sight or new angle. */ 714. if ( !(old_row[col] & IN_SIGHT) || oldseenv != lev->seenv) 715. newsym(col,row); 716. } 717. 718. else if (next_row[col] & COULD_SEE 719. && (lev->lit || next_row[col] & TEMP_LIT)) { 720. /* 721. * We see this position because it is lit. 722. */ 723. if (IS_DOOR(lev->typ) && !viz_clear[row][col]) { 724. /* 725. * Make sure doors, boulders or mimics don't show up 726. * at the end of dark hallways. We do this by checking 727. * the adjacent position. If it is lit, then we can see 728. * the door, otherwise we can't. 729. */ 730. dx = u.ux - col; dx = sign(dx); 731. flev = &(levl[col+dx][row+dy]); 732. if (flev->lit || next_array[row+dy][col+dx] & TEMP_LIT) { 733. next_row[col] |= IN_SIGHT; /* we see it */ 734. 735. oldseenv = lev->seenv; 736. lev->seenv |= new_angle(lev,sv,row,col); 737. 738. /* Update pos if previously not in sight or new angle.*/ 739. if (!(old_row[col] & IN_SIGHT) || oldseenv!=lev->seenv) 740. newsym(col,row); 741. } else 742. goto not_in_sight; /* we don't see it */ 743. 744. } else { 745. next_row[col] |= IN_SIGHT; /* we see it */ 746. 747. oldseenv = lev->seenv; 748. lev->seenv |= new_angle(lev,sv,row,col); 749. 750. /* Update pos if previously not in sight or new angle. */ 751. if ( !(old_row[col] & IN_SIGHT) || oldseenv != lev->seenv) 752. newsym(col,row); 753. } 754. } else if (next_row[col] & COULD_SEE && lev->waslit) { 755. /* 756. * If we make it here, the hero _could see_ the location, 757. * but doesn't see it (location is not lit). 758. * However, the hero _remembers_ it as lit (waslit is true). 759. * The hero can now see that it is not lit, so change waslit 760. * and update the location. 761. */ 762. lev->waslit = 0; /* remember lit condition */ 763. newsym(col,row); 764. } 765. /* 766. * At this point we know that the row position is *not* in 767. * sight. If the old one *was* in sight, then clean up the 768. * position. 769. */ 770. else { 771. not_in_sight: 772. if (old_row[col] & IN_SIGHT) newsym(col,row); 773. } 774. 775. } /* end for col . . */ 776. } /* end for row . . */ 777. colbump[u.ux] = colbump[u.ux+1] = 0; 778. 779. skip: 780. newsym(u.ux,u.uy); /* Make sure the hero shows up! */ 781. 782. /* Set the new min and max pointers. */ 783. viz_rmin = next_rmin; 784. viz_rmax = next_rmax; 785. } 786. 787. 788. /* 789. * block_point() 790. * 791. * Make the location opaque to light. 792. */ 793. void 794. block_point(x,y) 795. int x, y; 796. { 797. fill_point(y,x); 798. 799. /* recalc light sources here? */ 800. 801. /* 802. * We have to do a full vision recalculation if we "could see" the 803. * location. Why? Suppose some monster opened a way so that the 804. * hero could see a lit room. However, the position of the opening 805. * was out of night-vision range of the hero. Suddenly the hero should 806. * see the lit room. 807. */ 808. if (viz_array[y][x]) vision_full_recalc = 1; 809. } 810. 811. /* 812. * unblock_point() 813. * 814. * Make the location transparent to light. 815. */ 816. void 817. unblock_point(x,y) 818. int x, y; 819. { 820. dig_point(y,x); 821. 822. /* recalc light sources here? */ 823. 824. if (viz_array[y][x]) vision_full_recalc = 1; 825. } 826. 827. 828. /*===========================================================================*\ 829. | | 830. | Everything below this line uses (y,x) instead of (x,y) --- the | 831. | algorithms are faster if they are less recursive and can scan | 832. | on a row longer. | 833. | | 834. \*===========================================================================*/ 835. 836. 837. /* ========================================================================= *\ 838. Left and Right Pointer Updates 839. \* ========================================================================= */ 840. 841. /* 842. * LEFT and RIGHT pointer rules 843. * 844. * 845. * **NOTE** The rules changed on 4/4/90. This comment reflects the 846. * new rules. The change was so that the stone-wall optimization 847. * would work. 848. * 849. * OK, now the tough stuff. We must maintain our left and right 850. * row pointers. The rules are as follows: 851. * 852. * Left Pointers: 853. * ______________ 854. * 855. * + If you are a clear spot, your left will point to the first 856. * stone to your left. If there is none, then point the first 857. * legal position in the row (0). 858. * 859. * + If you are a blocked spot, then your left will point to the 860. * left-most blocked spot to your left that is connected to you. 861. * This means that a left-edge (a blocked spot that has an open 862. * spot on its left) will point to itself. 863. * 864. * 865. * Right Pointers: 866. * --------------- 867. * + If you are a clear spot, your right will point to the first 868. * stone to your right. If there is none, then point the last 869. * legal position in the row (COLNO-1). 870. * 871. * + If you are a blocked spot, then your right will point to the 872. * right-most blocked spot to your right that is connected to you. 873. * This means that a right-edge (a blocked spot that has an open 874. * spot on its right) will point to itself. 875. */ 876. static void 877. dig_point(row,col) 878. int row,col; 879. { 880. int i; 881. 882. if (viz_clear[row][col]) return; /* already done */ 883. 884. viz_clear[row][col] = 1; 885. 886. /* 887. * Boundary cases first. 888. */ 889. if (col == 0) { /* left edge */ 890. if (viz_clear[row][1]) { 891. right_ptrs[row][0] = right_ptrs[row][1]; 892. } else { 893. right_ptrs[row][0] = 1; 894. for (i = 1; i <= right_ptrs[row][1]; i++) 895. left_ptrs[row][i] = 1; 896. } 897. } else if (col == (COLNO-1)) { /* right edge */ 898. 899. if (viz_clear[row][COLNO-2]) { 900. left_ptrs[row][COLNO-1] = left_ptrs[row][COLNO-2]; 901. } else { 902. left_ptrs[row][COLNO-1] = COLNO-2; 903. for (i = left_ptrs[row][COLNO-2]; i < COLNO-1; i++) 904. right_ptrs[row][i] = COLNO-2; 905. } 906. } 907. 908. /* 909. * At this point, we know we aren't on the boundaries. 910. */ 911. else if (viz_clear[row][col-1] && viz_clear[row][col+1]) { 912. /* Both sides clear */ 913. for (i = left_ptrs[row][col-1]; i <= col; i++) { 914. if (!viz_clear[row][i]) continue; /* catch non-end case */ 915. right_ptrs[row][i] = right_ptrs[row][col+1]; 916. } 917. for (i = col; i <= right_ptrs[row][col+1]; i++) { 918. if (!viz_clear[row][i]) continue; /* catch non-end case */ 919. left_ptrs[row][i] = left_ptrs[row][col-1]; 920. } 921. 922. } else if (viz_clear[row][col-1]) { 923. /* Left side clear, right side blocked. */ 924. for (i = col+1; i <= right_ptrs[row][col+1]; i++) 925. left_ptrs[row][i] = col+1; 926. 927. for (i = left_ptrs[row][col-1]; i <= col; i++) { 928. if (!viz_clear[row][i]) continue; /* catch non-end case */ 929. right_ptrs[row][i] = col+1; 930. } 931. left_ptrs[row][col] = left_ptrs[row][col-1]; 932. 933. } else if (viz_clear[row][col+1]) { 934. /* Right side clear, left side blocked. */ 935. for (i = left_ptrs[row][col-1]; i < col; i++) 936. right_ptrs[row][i] = col-1; 937. 938. for (i = col; i <= right_ptrs[row][col+1]; i++) { 939. if (!viz_clear[row][i]) continue; /* catch non-end case */ 940. left_ptrs[row][i] = col-1; 941. } 942. right_ptrs[row][col] = right_ptrs[row][col+1]; 943. 944. } else { 945. /* Both sides blocked */ 946. for (i = left_ptrs[row][col-1]; i < col; i++) 947. right_ptrs[row][i] = col-1; 948. 949. for (i = col+1; i <= right_ptrs[row][col+1]; i++) 950. left_ptrs[row][i] = col+1; 951. 952. left_ptrs[row][col] = col-1; 953. right_ptrs[row][col] = col+1; 954. } 955. } 956. 957. static void 958. fill_point(row,col) 959. int row, col; 960. { 961. int i; 962. 963. if (!viz_clear[row][col]) return; 964. 965. viz_clear[row][col] = 0; 966. 967. if (col == 0) { 968. if (viz_clear[row][1]) { /* adjacent is clear */ 969. right_ptrs[row][0] = 0; 970. } else { 971. right_ptrs[row][0] = right_ptrs[row][1]; 972. for (i = 1; i <= right_ptrs[row][1]; i++) 973. left_ptrs[row][i] = 0; 974. } 975. } else if (col == COLNO-1) { 976. if (viz_clear[row][COLNO-2]) { /* adjacent is clear */ 977. left_ptrs[row][COLNO-1] = COLNO-1; 978. } else { 979. left_ptrs[row][COLNO-1] = left_ptrs[row][COLNO-2]; 980. for (i = left_ptrs[row][COLNO-2]; i < COLNO-1; i++) 981. right_ptrs[row][i] = COLNO-1; 982. } 983. } 984. 985. /* 986. * Else we know that we are not on an edge. 987. */ 988. else if (viz_clear[row][col-1] && viz_clear[row][col+1]) { 989. /* Both sides clear */ 990. for (i = left_ptrs[row][col-1]+1; i <= col; i++) 991. right_ptrs[row][i] = col; 992. 993. if (!left_ptrs[row][col-1]) /* catch the end case */ 994. right_ptrs[row][0] = col; 995. 996. for (i = col; i < right_ptrs[row][col+1]; i++) 997. left_ptrs[row][i] = col; 998. 999. if (right_ptrs[row][col+1] == COLNO-1) /* catch the end case */ 1000. left_ptrs[row][COLNO-1] = col; 1001. 1002. } else if (viz_clear[row][col-1]) { 1003. /* Left side clear, right side blocked. */ 1004. for (i = col; i <= right_ptrs[row][col+1]; i++) 1005. left_ptrs[row][i] = col; 1006. 1007. for (i = left_ptrs[row][col-1]+1; i < col; i++) 1008. right_ptrs[row][i] = col; 1009. 1010. if (!left_ptrs[row][col-1]) /* catch the end case */ 1011. right_ptrs[row][i] = col; 1012. 1013. right_ptrs[row][col] = right_ptrs[row][col+1]; 1014. 1015. } else if (viz_clear[row][col+1]) { 1016. /* Right side clear, left side blocked. */ 1017. for (i = left_ptrs[row][col-1]; i <= col; i++) 1018. right_ptrs[row][i] = col; 1019. 1020. for (i = col+1; 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][i] = col; 1025. 1026. left_ptrs[row][col] = left_ptrs[row][col-1]; 1027. 1028. } else { 1029. /* Both sides blocked */ 1030. for (i = left_ptrs[row][col-1]; i <= col; i++) 1031. right_ptrs[row][i] = right_ptrs[row][col+1]; 1032. 1033. for (i = col; i <= right_ptrs[row][col+1]; i++) 1034. left_ptrs[row][i] = left_ptrs[row][col-1]; 1035. } 1036. } 1037. 1038. 1039. /*===========================================================================*/ 1040. /*===========================================================================*/ 1041. /* Use either algorithm C or D. See the config.h for more details. =========*/ 1042. 1043. /* 1044. * Variables local to both Algorithms C and D. 1045. */ 1046. static int start_row; 1047. static int start_col; 1048. static int step; 1049. static char **cs_rows; 1050. static char *cs_left; 1051. static char *cs_right; 1052. 1053. static void FDECL((*vis_func), (int,int,genericptr_t)); 1054. static genericptr_t varg; 1055. 1056. /* 1057. * Both Algorithms C and D use the following macros. 1058. * 1059. * good_row(z) - Return TRUE if the argument is a legal row. 1060. * set_cs(rowp,col) - Set the local could see array. 1061. * set_min(z) - Save the min value of the argument and the current 1062. * row minimum. 1063. * set_max(z) - Save the max value of the argument and the current 1064. * row maximum. 1065. * 1066. * The last three macros depend on having local pointers row_min, row_max, 1067. * and rowp being set correctly. 1068. */ 1069. #define set_cs(rowp,col) (rowp[col] = COULD_SEE) 1070. #define good_row(z) ((z) >= 0 && (z) < ROWNO) 1071. #define set_min(z) if (*row_min > (z)) *row_min = (z) 1072. #define set_max(z) if (*row_max < (z)) *row_max = (z) 1073. #define is_clear(row,col) viz_clear_rows[row][col] 1074. 1075. /* 1076. * clear_path() expanded into 4 macros/functions: 1077. * 1078. * q1_path() 1079. * q2_path() 1080. * q3_path() 1081. * q4_path() 1082. * 1083. * "Draw" a line from the start to the given location. Stop if we hit 1084. * something that blocks light. The start and finish points themselves are 1085. * not checked, just the points between them. These routines do _not_ 1086. * expect to be called with the same starting and stopping point. 1087. * 1088. * These routines use the generalized integer Bresenham's algorithm (fast 1089. * line drawing) for all quadrants. The algorithm was taken from _Procedural 1090. * Elements for Computer Graphics_, by David F. Rogers. McGraw-Hill, 1985. 1091. */ 1092. #ifdef MACRO_CPATH /* quadrant calls are macros */ 1093. 1094. /* 1095. * When called, the result is in "result". 1096. * The first two arguments (srow,scol) are one end of the path. The next 1097. * two arguments (row,col) are the destination. The last argument is 1098. * used as a C language label. This means that it must be different 1099. * in each pair of calls. 1100. */ 1101. 1102. /* 1103. * Quadrant I (step < 0). 1104. */ 1105. #define q1_path(srow,scol,y2,x2,label) \ 1106. { \ 1107. int dx, dy; \ 1108. register int k, err, x, y, dxs, dys; \ 1109. \ 1110. x = (scol); y = (srow); \ 1111. dx = (x2) - x; dy = y - (y2); \ 1112. \ 1113. result = 0; /* default to a blocked path */\ 1114. \ 1115. dxs = dx << 1; /* save the shifted values */\ 1116. dys = dy << 1; \ 1117. if (dy > dx) { \ 1118. err = dxs - dy; \ 1119. \ 1120. for (k = dy-1; k; k--) { \ 1121. if (err >= 0) { \ 1122. x++; \ 1123. err -= dys; \ 1124. } \ 1125. y--; \ 1126. err += dxs; \ 1127. if (!is_clear(y,x)) goto label;/* blocked */\ 1128. } \ 1129. } else { \ 1130. err = dys - dx; \ 1131. \ 1132. for (k = dx-1; k; k--) { \ 1133. if (err >= 0) { \ 1134. y--; \ 1135. err -= dxs; \ 1136. } \ 1137. x++; \ 1138. err += dys; \ 1139. if (!is_clear(y,x)) goto label;/* blocked */\ 1140. } \ 1141. } \ 1142. \ 1143. result = 1; \ 1144. } 1145. 1146. /* 1147. * Quadrant IV (step > 0). 1148. */ 1149. #define q4_path(srow,scol,y2,x2,label) \ 1150. { \ 1151. int dx, dy; \ 1152. register int k, err, x, y, dxs, dys; \ 1153. \ 1154. x = (scol); y = (srow); \ 1155. dx = (x2) - x; dy = (y2) - y; \ 1156. \ 1157. result = 0; /* default to a blocked path */\ 1158. \ 1159. dxs = dx << 1; /* save the shifted values */\ 1160. dys = dy << 1; \ 1161. if (dy > dx) { \ 1162. err = dxs - dy; \ 1163. \ 1164. for (k = dy-1; k; k--) { \ 1165. if (err >= 0) { \ 1166. x++; \ 1167. err -= dys; \ 1168. } \ 1169. y++; \ 1170. err += dxs; \ 1171. if (!is_clear(y,x)) goto label;/* blocked */\ 1172. } \ 1173. \ 1174. } else { \ 1175. err = dys - dx; \ 1176. \ 1177. for (k = dx-1; k; k--) { \ 1178. if (err >= 0) { \ 1179. y++; \ 1180. err -= dxs; \ 1181. } \ 1182. x++; \ 1183. err += dys; \ 1184. if (!is_clear(y,x)) goto label;/* blocked */\ 1185. } \ 1186. } \ 1187. \ 1188. result = 1; \ 1189. } 1190. 1191. /* 1192. * Quadrant II (step < 0). 1193. */ 1194. #define q2_path(srow,scol,y2,x2,label) \ 1195. { \ 1196. int dx, dy; \ 1197. register int k, err, x, y, dxs, dys; \ 1198. \ 1199. x = (scol); y = (srow); \ 1200. dx = x - (x2); dy = y - (y2); \ 1201. \ 1202. result = 0; /* default to a blocked path */\ 1203. \ 1204. dxs = dx << 1; /* save the shifted values */\ 1205. dys = dy << 1; \ 1206. if (dy > dx) { \ 1207. err = dxs - dy; \ 1208. \ 1209. for (k = dy-1; k; k--) { \ 1210. if (err >= 0) { \ 1211. x--; \ 1212. err -= dys; \ 1213. } \ 1214. y--; \ 1215. err += dxs; \ 1216. if (!is_clear(y,x)) goto label;/* blocked */\ 1217. } \ 1218. } else { \ 1219. err = dys - dx; \ 1220. \ 1221. for (k = dx-1; k; k--) { \ 1222. if (err >= 0) { \ 1223. y--; \ 1224. err -= dxs; \ 1225. } \ 1226. x--; \ 1227. err += dys; \ 1228. if (!is_clear(y,x)) goto label;/* blocked */\ 1229. } \ 1230. } \ 1231. \ 1232. result = 1; \ 1233. } 1234. 1235. /* 1236. * Quadrant III (step > 0). 1237. */ 1238. #define q3_path(srow,scol,y2,x2,label) \ 1239. { \ 1240. int dx, dy; \ 1241. register int k, err, x, y, dxs, dys; \ 1242. \ 1243. x = (scol); y = (srow); \ 1244. dx = x - (x2); dy = (y2) - y; \ 1245. \ 1246. result = 0; /* default to a blocked path */\ 1247. \ 1248. dxs = dx << 1; /* save the shifted values */\ 1249. dys = dy << 1; \ 1250. if (dy > dx) { \ 1251. err = dxs - dy; \ 1252. \ 1253. for (k = dy-1; k; k--) { \ 1254. if (err >= 0) { \ 1255. x--; \ 1256. err -= dys; \ 1257. } \ 1258. y++; \ 1259. err += dxs; \ 1260. if (!is_clear(y,x)) goto label;/* blocked */\ 1261. } \ 1262. \ 1263. } else { \ 1264. err = dys - dx; \ 1265. \ 1266. for (k = dx-1; k; k--) { \ 1267. if (err >= 0) { \ 1268. y++; \ 1269. err -= dxs; \ 1270. } \ 1271. x--; \ 1272. err += dys; \ 1273. if (!is_clear(y,x)) goto label;/* blocked */\ 1274. } \ 1275. } \ 1276. \ 1277. result = 1; \ 1278. } 1279. 1280. #else /* quadrants are really functions */ 1281. 1282. static int FDECL(_q1_path, (int,int,int,int)); 1283. static int FDECL(_q2_path, (int,int,int,int)); 1284. static int FDECL(_q3_path, (int,int,int,int)); 1285. static int FDECL(_q4_path, (int,int,int,int)); 1286. 1287. #define q1_path(sy,sx,y,x,dummy) result = _q1_path(sy,sx,y,x) 1288. #define q2_path(sy,sx,y,x,dummy) result = _q2_path(sy,sx,y,x) 1289. #define q3_path(sy,sx,y,x,dummy) result = _q3_path(sy,sx,y,x) 1290. #define q4_path(sy,sx,y,x,dummy) result = _q4_path(sy,sx,y,x) 1291. 1292. /* 1293. * Quadrant I (step < 0). 1294. */ 1295. static int 1296. _q1_path(srow,scol,y2,x2) 1297. int scol, srow, y2, x2; 1298. { 1299. int dx, dy; 1300. register int k, err, x, y, dxs, dys; 1301. 1302. x = scol; y = srow; 1303. dx = x2 - x; dy = y - y2; 1304. 1305. dxs = dx << 1; /* save the shifted values */ 1306. dys = dy << 1; 1307. if (dy > dx) { 1308. err = dxs - dy; 1309. 1310. for (k = dy-1; k; k--) { 1311. if (err >= 0) { 1312. x++; 1313. err -= dys; 1314. } 1315. y--; 1316. err += dxs; 1317. if (!is_clear(y,x)) return 0; /* blocked */ 1318. } 1319. } else { 1320. err = dys - dx; 1321. 1322. for (k = dx-1; k; k--) { 1323. if (err >= 0) { 1324. y--; 1325. err -= dxs; 1326. } 1327. x++; 1328. err += dys; 1329. if (!is_clear(y,x)) return 0;/* blocked */ 1330. } 1331. } 1332. 1333. return 1; 1334. } 1335. 1336. /* 1337. * Quadrant IV (step > 0). 1338. */ 1339. static int 1340. _q4_path(srow,scol,y2,x2) 1341. int scol, srow, y2, x2; 1342. { 1343. int dx, dy; 1344. register int k, err, x, y, dxs, dys; 1345. 1346. x = scol; y = srow; 1347. dx = x2 - x; dy = y2 - y; 1348. 1349. dxs = dx << 1; /* save the shifted values */ 1350. dys = dy << 1; 1351. if (dy > dx) { 1352. err = dxs - dy; 1353. 1354. for (k = dy-1; k; k--) { 1355. if (err >= 0) { 1356. x++; 1357. err -= dys; 1358. } 1359. y++; 1360. err += dxs; 1361. if (!is_clear(y,x)) return 0; /* blocked */ 1362. } 1363. } else { 1364. err = dys - dx; 1365. 1366. for (k = dx-1; k; k--) { 1367. if (err >= 0) { 1368. y++; 1369. err -= dxs; 1370. } 1371. x++; 1372. err += dys; 1373. if (!is_clear(y,x)) return 0;/* blocked */ 1374. } 1375. } 1376. 1377. return 1; 1378. } 1379. 1380. /* 1381. * Quadrant II (step < 0). 1382. */ 1383. static int 1384. _q2_path(srow,scol,y2,x2) 1385. int scol, srow, y2, x2; 1386. { 1387. int dx, dy; 1388. register int k, err, x, y, dxs, dys; 1389. 1390. x = scol; y = srow; 1391. dx = x - x2; dy = y - y2; 1392. 1393. dxs = dx << 1; /* save the shifted values */ 1394. dys = dy << 1; 1395. if (dy > dx) { 1396. err = dxs - dy; 1397. 1398. for (k = dy-1; k; k--) { 1399. if (err >= 0) { 1400. x--; 1401. err -= dys; 1402. } 1403. y--; 1404. err += dxs; 1405. if (!is_clear(y,x)) return 0; /* blocked */ 1406. } 1407. } else { 1408. err = dys - dx; 1409. 1410. for (k = dx-1; k; k--) { 1411. if (err >= 0) { 1412. y--; 1413. err -= dxs; 1414. } 1415. x--; 1416. err += dys; 1417. if (!is_clear(y,x)) return 0;/* blocked */ 1418. } 1419. } 1420. 1421. return 1; 1422. } 1423. 1424. /* 1425. * Quadrant III (step > 0). 1426. */ 1427. static int 1428. _q3_path(srow,scol,y2,x2) 1429. int scol, srow, y2, x2; 1430. { 1431. int dx, dy; 1432. register int k, err, x, y, dxs, dys; 1433. 1434. x = scol; y = srow; 1435. dx = x - x2; dy = y2 - y; 1436. 1437. dxs = dx << 1; /* save the shifted values */ 1438. dys = dy << 1; 1439. if (dy > dx) { 1440. err = dxs - dy; 1441. 1442. for (k = dy-1; k; k--) { 1443. if (err >= 0) { 1444. x--; 1445. err -= dys; 1446. } 1447. y++; 1448. err += dxs; 1449. if (!is_clear(y,x)) return 0; /* blocked */ 1450. } 1451. } else { 1452. err = dys - dx; 1453. 1454. for (k = dx-1; k; k--) { 1455. if (err >= 0) { 1456. y++; 1457. err -= dxs; 1458. } 1459. x--; 1460. err += dys; 1461. if (!is_clear(y,x)) return 0;/* blocked */ 1462. } 1463. } 1464. 1465. return 1; 1466. } 1467. 1468. #endif /* quadrants are functions */ 1469. 1470. /* 1471. * Use vision tables to determine if there is a clear path from 1472. * (col1,row1) to (col2,row2). This is used by: 1473. * m_cansee() 1474. * m_canseeu() 1475. * do_light_sources() 1476. */ 1477. boolean 1478. clear_path(col1,row1,col2,row2) 1479. int col1, row1, col2, row2; 1480. { 1481. int result; 1482. 1483. if(col1 < col2) { 1484. if(row1 > row2) { 1485. q1_path(row1,col1,row2,col2,cleardone); 1486. } else { 1487. q4_path(row1,col1,row2,col2,cleardone); 1488. } 1489. } else { 1490. if(row1 > row2) { 1491. q2_path(row1,col1,row2,col2,cleardone); 1492. } else if(row1 == row2 && col1 == col2) { 1493. result = 1; 1494. } else { 1495. q3_path(row1,col1,row2,col2,cleardone); 1496. } 1497. } 1498. cleardone: 1499. return((boolean)result); 1500. } 1501. 1502. #ifdef VISION_TABLES 1503. /*===========================================================================*\ 1504. GENERAL LINE OF SIGHT 1505. Algorithm D 1506. \*===========================================================================*/ 1507. 1508. 1509. /* 1510. * Indicate caller for the shadow routines. 1511. */ 1512. #define FROM_RIGHT 0 1513. #define FROM_LEFT 1 1514. 1515. 1516. /* 1517. * Include the table definitions. 1518. */ 1519. #include "vis_tab.h" 1520. 1521. 1522. /* 3D table pointers. */ 1523. static close2d *close_dy[CLOSE_MAX_BC_DY]; 1524. static far2d *far_dy[FAR_MAX_BC_DY]; 1525. 1526. static void FDECL(right_side, (int,int,int,int,int,int,int,char*)); 1527. static void FDECL(left_side, (int,int,int,int,int,int,int,char*)); 1528. static int FDECL(close_shadow, (int,int,int,int)); 1529. static int FDECL(far_shadow, (int,int,int,int)); 1530. 1531. /* 1532. * Initialize algorithm D's table pointers. If we don't have these, 1533. * then we do 3D table lookups. Verrrry slow. 1534. */ 1535. static void 1536. view_init() 1537. { 1538. int i; 1539. 1540. for (i = 0; i < CLOSE_MAX_BC_DY; i++) 1541. close_dy[i] = &close_table[i]; 1542. 1543. for (i = 0; i < FAR_MAX_BC_DY; i++) 1544. far_dy[i] = &far_table[i]; 1545. } 1546. 1547. 1548. /* 1549. * If the far table has an entry of OFF_TABLE, then the far block prevents 1550. * us from seeing the location just above/below it. I.e. the first visible 1551. * location is one *before* the block. 1552. */ 1553. #define OFF_TABLE 0xff 1554. 1555. static int 1556. close_shadow(side,this_row,block_row,block_col) 1557. int side,this_row,block_row,block_col; 1558. { 1559. register int sdy, sdx, pdy, offset; 1560. 1561. /* 1562. * If on the same column (block_row = -1), then we can see it. 1563. */ 1564. if (block_row < 0) return block_col; 1565. 1566. /* Take explicit absolute values. Adjust. */ 1567. if ((sdy = (start_row-block_row)) < 0) sdy = -sdy; --sdy; /* src dy */ 1568. if ((sdx = (start_col-block_col)) < 0) sdx = -sdx; /* src dx */ 1569. if ((pdy = (block_row-this_row)) < 0) pdy = -pdy; /* point dy */ 1570. 1571. if (sdy < 0 || sdy >= CLOSE_MAX_SB_DY || sdx >= CLOSE_MAX_SB_DX || 1572. pdy >= CLOSE_MAX_BC_DY) { 1573. impossible("close_shadow: bad value"); 1574. return block_col; 1575. } 1576. offset = close_dy[sdy]->close[sdx][pdy]; 1577. if (side == FROM_RIGHT) 1578. return block_col + offset; 1579. 1580. return block_col - offset; 1581. } 1582. 1583. 1584. static int 1585. far_shadow(side,this_row,block_row,block_col) 1586. int side,this_row,block_row,block_col; 1587. { 1588. register int sdy, sdx, pdy, offset; 1589. 1590. /* 1591. * Take care of a bug that shows up only on the borders. 1592. * 1593. * If the block is beyond the border, then the row is negative. Return 1594. * the block's column number (should be 0 or COLNO-1). 1595. * 1596. * Could easily have the column be -1, but then wouldn't know if it was 1597. * the left or right border. 1598. */ 1599. if (block_row < 0) return block_col; 1600. 1601. /* Take explicit absolute values. Adjust. */ 1602. if ((sdy = (start_row-block_row)) < 0) sdy = -sdy; /* src dy */ 1603. if ((sdx = (start_col-block_col)) < 0) sdx = -sdx; --sdx; /* src dx */ 1604. if ((pdy = (block_row-this_row)) < 0) pdy = -pdy; --pdy; /* point dy */ 1605. 1606. if (sdy >= FAR_MAX_SB_DY || sdx < 0 || sdx >= FAR_MAX_SB_DX || 1607. pdy < 0 || pdy >= FAR_MAX_BC_DY) { 1608. impossible("far_shadow: bad value"); 1609. return block_col; 1610. } 1611. if ((offset = far_dy[sdy]->far_q[sdx][pdy]) == OFF_TABLE) offset = -1; 1612. if (side == FROM_RIGHT) 1613. return block_col + offset; 1614. 1615. return block_col - offset; 1616. } 1617. 1618. 1619. /* 1620. * right_side() 1621. * 1622. * Figure out what could be seen on the right side of the source. 1623. */ 1624. static void 1625. right_side(row, cb_row, cb_col, fb_row, fb_col, left, right_mark, limits) 1626. int row; /* current row */ 1627. int cb_row, cb_col; /* close block row and col */ 1628. int fb_row, fb_col; /* far block row and col */ 1629. int left; /* left mark of the previous row */ 1630. int right_mark; /* right mark of previous row */ 1631. char *limits; /* points at range limit for current row, or NULL */ 1632. { 1633. register int i; 1634. register char *rowp; 1635. int hit_stone = 0; 1636. int left_shadow, right_shadow, loc_right; 1637. int lblock_col; /* local block column (current row) */ 1638. int nrow, deeper; 1639. char *row_min; /* left most */ 1640. char *row_max; /* right most */ 1641. int lim_max; /* right most limit of circle */ 1642. 1643. nrow = row + step; 1644. deeper = good_row(nrow) && (!limits || (*limits >= *(limits+1))); 1645. if(!vis_func) { 1646. rowp = cs_rows[row]; 1647. row_min = &cs_left[row]; 1648. row_max = &cs_right[row]; 1649. } 1650. if(limits) { 1651. lim_max = start_col + *limits; 1652. if(lim_max > COLNO-1) lim_max = COLNO-1; 1653. if(right_mark > lim_max) right_mark = lim_max; 1654. limits++; /* prepare for next row */ 1655. } else 1656. lim_max = COLNO-1; 1657. 1658. /* 1659. * Get the left shadow from the close block. This value could be 1660. * illegal. 1661. */ 1662. left_shadow = close_shadow(FROM_RIGHT,row,cb_row,cb_col); 1663. 1664. /* 1665. * Mark all stone walls as seen before the left shadow. All this work 1666. * for a special case. 1667. * 1668. * NOTE. With the addition of this code in here, it is now *required* 1669. * for the algorithm to work correctly. If this is commented out, 1670. * change the above assignment so that left and not left_shadow is the 1671. * variable that gets the shadow. 1672. */ 1673. while (left <= right_mark) { 1674. loc_right = right_ptrs[row][left]; 1675. if(loc_right > lim_max) loc_right = lim_max; 1676. if (viz_clear_rows[row][left]) { 1677. if (loc_right >= left_shadow) { 1678. left = left_shadow; /* opening ends beyond shadow */ 1679. break; 1680. } 1681. left = loc_right; 1682. loc_right = right_ptrs[row][left]; 1683. if(loc_right > lim_max) loc_right = lim_max; 1684. if (left == loc_right) return; /* boundary */ 1685. 1686. /* Shadow covers opening, beyond right mark */ 1687. if (left == right_mark && left_shadow > right_mark) return; 1688. } 1689. 1690. if (loc_right > right_mark) /* can't see stone beyond the mark */ 1691. loc_right = right_mark; 1692. 1693. if(vis_func) { 1694. for (i = left; i <= loc_right; i++) (*vis_func)(i, row, varg); 1695. } else { 1696. for (i = left; i <= loc_right; i++) set_cs(rowp,i); 1697. set_min(left); set_max(loc_right); 1698. } 1699. 1700. if (loc_right == right_mark) return; /* all stone */ 1701. if (loc_right >= left_shadow) hit_stone = 1; 1702. left = loc_right + 1; 1703. } 1704. 1705. /* 1706. * At this point we are at the first visible clear spot on or beyond 1707. * the left shadow, unless the left shadow is an illegal value. If we 1708. * have "hit stone" then we have a stone wall just to our left. 1709. */ 1710. 1711. /* 1712. * Get the right shadow. Make sure that it is a legal value. 1713. */ 1714. if ((right_shadow = far_shadow(FROM_RIGHT,row,fb_row,fb_col)) >= COLNO) 1715. right_shadow = COLNO-1; 1716. /* 1717. * Make vertical walls work the way we want them. In this case, we 1718. * note when the close block blocks the column just above/beneath 1719. * it (right_shadow < fb_col [actually right_shadow == fb_col-1]). If 1720. * the location is filled, then we want to see it, so we put the 1721. * right shadow back (same as fb_col). 1722. */ 1723. if (right_shadow < fb_col && !viz_clear_rows[row][fb_col]) 1724. right_shadow = fb_col; 1725. if(right_shadow > lim_max) right_shadow = lim_max; 1726. 1727. /* 1728. * Main loop. Within the range of sight of the previous row, mark all 1729. * stone walls as seen. Follow open areas recursively. 1730. */ 1731. while (left <= right_mark) { 1732. /* Get the far right of the opening or wall */ 1733. loc_right = right_ptrs[row][left]; 1734. if(loc_right > lim_max) loc_right = lim_max; 1735. 1736. if (!viz_clear_rows[row][left]) { 1737. hit_stone = 1; /* use stone on this row as close block */ 1738. /* 1739. * We can see all of the wall until the next open spot or the 1740. * start of the shadow caused by the far block (right). 1741. * 1742. * Can't see stone beyond the right mark. 1743. */ 1744. if (loc_right > right_mark) loc_right = right_mark; 1745. 1746. if(vis_func) { 1747. for (i = left; i <= loc_right; i++) (*vis_func)(i, row, varg); 1748. } else { 1749. for (i = left; i <= loc_right; i++) set_cs(rowp,i); 1750. set_min(left); set_max(loc_right); 1751. } 1752. 1753. if (loc_right == right_mark) return; /* hit the end */ 1754. left = loc_right + 1; 1755. loc_right = right_ptrs[row][left]; 1756. if(loc_right > lim_max) loc_right = lim_max; 1757. /* fall through... we know at least one position is visible */ 1758. } 1759. 1760. /* 1761. * We are in an opening. 1762. * 1763. * If this is the first open spot since the could see area (this is 1764. * true if we have hit stone), get the shadow generated by the wall 1765. * just to our left. 1766. */ 1767. if (hit_stone) { 1768. lblock_col = left-1; /* local block column */ 1769. left = close_shadow(FROM_RIGHT,row,row,lblock_col); 1770. if (left > lim_max) break; /* off the end */ 1771. } 1772. 1773. /* 1774. * Check if the shadow covers the opening. If it does, then 1775. * move to end of the opening. A shadow generated on from a 1776. * wall on this row does *not* cover the wall on the right 1777. * of the opening. 1778. */ 1779. if (left >= loc_right) { 1780. if (loc_right == lim_max) { /* boundary */ 1781. if (left == lim_max) { 1782. if(vis_func) (*vis_func)(lim_max, row, varg); 1783. else { 1784. set_cs(rowp,lim_max); /* last pos */ 1785. set_max(lim_max); 1786. } 1787. } 1788. return; /* done */ 1789. } 1790. left = loc_right; 1791. continue; 1792. } 1793. 1794. /* 1795. * If the far wall of the opening (loc_right) is closer than the 1796. * shadow limit imposed by the far block (right) then use the far 1797. * wall as our new far block when we recurse. 1798. * 1799. * If the limits are the the same, and the far block really exists 1800. * (fb_row >= 0) then do the same as above. 1801. * 1802. * Normally, the check would be for the far wall being closer OR EQUAL 1803. * to the shadow limit. However, there is a bug that arises from the 1804. * fact that the clear area pointers end in an open space (if it 1805. * exists) on a boundary. This then makes a far block exist where it 1806. * shouldn't --- on a boundary. To get around that, I had to 1807. * introduce the concept of a non-existent far block (when the 1808. * row < 0). Next I have to check for it. Here is where that check 1809. * exists. 1810. */ 1811. if ((loc_right < right_shadow) || 1812. (fb_row >= 0 && loc_right == right_shadow)) { 1813. if(vis_func) { 1814. for (i = left; i <= loc_right; i++) (*vis_func)(i, row, varg); 1815. } else { 1816. for (i = left; i <= loc_right; i++) set_cs(rowp,i); 1817. set_min(left); set_max(loc_right); 1818. } 1819. 1820. if (deeper) { 1821. if (hit_stone) 1822. right_side(nrow,row,lblock_col,row,loc_right, 1823. left,loc_right,limits); 1824. else 1825. right_side(nrow,cb_row,cb_col,row,loc_right, 1826. left,loc_right,limits); 1827. } 1828. 1829. /* 1830. * The following line, setting hit_stone, is needed for those 1831. * walls that are only 1 wide. If hit stone is *not* set and 1832. * the stone is only one wide, then the close block is the old 1833. * one instead one on the current row. A way around having to 1834. * set it here is to make left = loc_right (not loc_right+1) and 1835. * let the outer loop take care of it. However, if we do that 1836. * then we then have to check for boundary conditions here as 1837. * well. 1838. */ 1839. hit_stone = 1; 1840. 1841. left = loc_right+1; 1842. } 1843. /* 1844. * The opening extends beyond the right mark. This means that 1845. * the next far block is the current far block. 1846. */ 1847. else { 1848. if(vis_func) { 1849. for (i=left; i <= right_shadow; i++) (*vis_func)(i, row, varg); 1850. } else { 1851. for (i = left; i <= right_shadow; i++) set_cs(rowp,i); 1852. set_min(left); set_max(right_shadow); 1853. } 1854. 1855. if (deeper) { 1856. if (hit_stone) 1857. right_side(nrow, row,lblock_col,fb_row,fb_col, 1858. left,right_shadow,limits); 1859. else 1860. right_side(nrow,cb_row, cb_col,fb_row,fb_col, 1861. left,right_shadow,limits); 1862. } 1863. 1864. return; /* we're outta here */ 1865. } 1866. } 1867. } 1868. 1869. 1870. /* 1871. * left_side() 1872. * 1873. * This routine is the mirror image of right_side(). Please see right_side() 1874. * for blow by blow comments. 1875. */ 1876. static void 1877. left_side(row, cb_row, cb_col, fb_row, fb_col, left_mark, right, limits) 1878. int row; /* the current row */ 1879. int cb_row, cb_col; /* close block row and col */ 1880. int fb_row, fb_col; /* far block row and col */ 1881. int left_mark; /* left mark of previous row */ 1882. int right; /* right mark of the previous row */ 1883. char *limits; 1884. { 1885. register int i; 1886. register char *rowp; 1887. int hit_stone = 0; 1888. int left_shadow, right_shadow, loc_left; 1889. int lblock_col; /* local block column (current row) */ 1890. int nrow, deeper; 1891. char *row_min; /* left most */ 1892. char *row_max; /* right most */ 1893. int lim_min; 1894. 1895. nrow = row + step; 1896. deeper = good_row(nrow) && (!limits || (*limits >= *(limits+1))); 1897. if(!vis_func) { 1898. rowp = cs_rows[row]; 1899. row_min = &cs_left[row]; 1900. row_max = &cs_right[row]; 1901. } 1902. if(limits) { 1903. lim_min = start_col - *limits; 1904. if(lim_min < 0) lim_min = 0; 1905. if(left_mark < lim_min) left_mark = lim_min; 1906. limits++; /* prepare for next row */ 1907. } else 1908. lim_min = 0; 1909. 1910. /* This value could be illegal. */ 1911. right_shadow = close_shadow(FROM_LEFT,row,cb_row,cb_col); 1912. 1913. while ( right >= left_mark ) { 1914. loc_left = left_ptrs[row][right]; 1915. if(loc_left < lim_min) loc_left = lim_min; 1916. if (viz_clear_rows[row][right]) { 1917. if (loc_left <= right_shadow) { 1918. right = right_shadow; /* opening ends beyond shadow */ 1919. break; 1920. } 1921. right = loc_left; 1922. loc_left = left_ptrs[row][right]; 1923. if(loc_left < lim_min) loc_left = lim_min; 1924. if (right == loc_left) return; /* boundary */ 1925. } 1926. 1927. if (loc_left < left_mark) /* can't see beyond the left mark */ 1928. loc_left = left_mark; 1929. 1930. if(vis_func) { 1931. for (i = loc_left; i <= right; i++) (*vis_func)(i, row, varg); 1932. } else { 1933. for (i = loc_left; i <= right; i++) set_cs(rowp,i); 1934. set_min(loc_left); set_max(right); 1935. } 1936. 1937. if (loc_left == left_mark) return; /* all stone */ 1938. if (loc_left <= right_shadow) hit_stone = 1; 1939. right = loc_left - 1; 1940. } 1941. 1942. /* At first visible clear spot on or beyond the right shadow. */ 1943. 1944. if ((left_shadow = far_shadow(FROM_LEFT,row,fb_row,fb_col)) < 0) 1945. left_shadow = 0; 1946. 1947. /* Do vertical walls as we want. */ 1948. if (left_shadow > fb_col && !viz_clear_rows[row][fb_col]) 1949. left_shadow = fb_col; 1950. if(left_shadow < lim_min) left_shadow = lim_min; 1951. 1952. while (right >= left_mark) { 1953. loc_left = left_ptrs[row][right]; 1954. 1955. if (!viz_clear_rows[row][right]) { 1956. hit_stone = 1; /* use stone on this row as close block */ 1957. 1958. /* We can only see walls until the left mark */ 1959. if (loc_left < left_mark) loc_left = left_mark; 1960. 1961. if(vis_func) { 1962. for (i = loc_left; i <= right; i++) (*vis_func)(i, row, varg); 1963. } else { 1964. for (i = loc_left; i <= right; i++) set_cs(rowp,i); 1965. set_min(loc_left); set_max(right); 1966. } 1967. 1968. if (loc_left == left_mark) return; /* hit end */ 1969. right = loc_left - 1; 1970. loc_left = left_ptrs[row][right]; 1971. if (loc_left < lim_min) loc_left = lim_min; 1972. /* fall through...*/ 1973. } 1974. 1975. /* We are in an opening. */ 1976. if (hit_stone) { 1977. lblock_col = right+1; /* stone block (local) */ 1978. right = close_shadow(FROM_LEFT,row,row,lblock_col); 1979. if (right < lim_min) return; /* off the end */ 1980. } 1981. 1982. /* Check if the shadow covers the opening. */ 1983. if (right <= loc_left) { 1984. /* Make a boundary condition work. */ 1985. if (loc_left == lim_min) { /* at boundary */ 1986. if (right == lim_min) { 1987. if(vis_func) (*vis_func)(lim_min, row, varg); 1988. else { 1989. set_cs(rowp,lim_min); /* caught the last pos */ 1990. set_min(lim_min); 1991. } 1992. } 1993. return; /* and break out the loop */ 1994. } 1995. 1996. right = loc_left; 1997. continue; 1998. } 1999. 2000. /* If the far wall of the opening is closer than the shadow limit. */ 2001. if ((loc_left > left_shadow) || 2002. (fb_row >= 0 && loc_left == left_shadow)) { 2003. if(vis_func) { 2004. for (i = loc_left; i <= right; i++) (*vis_func)(i, row, varg); 2005. } else { 2006. for (i = loc_left; i <= right; i++) set_cs(rowp,i); 2007. set_min(loc_left); set_max(right); 2008. } 2009. 2010. if (deeper) { 2011. if (hit_stone) 2012. left_side(nrow,row,lblock_col,row,loc_left, 2013. loc_left,right,limits); 2014. else 2015. left_side(nrow,cb_row,cb_col,row,loc_left, 2016. loc_left,right,limits); 2017. } 2018. 2019. hit_stone = 1; /* needed for walls of width 1 */ 2020. right = loc_left-1; 2021. } 2022. /* The opening extends beyond the left mark. */ 2023. else { 2024. if(vis_func) { 2025. for (i=left_shadow; i <= right; i++) (*vis_func)(i, row, varg); 2026. } else { 2027. for (i = left_shadow; i <= right; i++) set_cs(rowp,i); 2028. set_min(left_shadow); set_max(right); 2029. } 2030. 2031. if (deeper) { 2032. if (hit_stone) 2033. left_side(nrow,row,lblock_col,fb_row,fb_col, 2034. left_shadow,right,limits); 2035. else 2036. left_side(nrow,cb_row,cb_col,fb_row,fb_col, 2037. left_shadow,right,limits); 2038. } 2039. 2040. return; /* we're outta here */ 2041. } 2042. 2043. } 2044. } 2045. 2046. /* 2047. * view_from 2048. * 2049. * Calculate a view from the given location. Initialize and fill a 2050. * ROWNOxCOLNO array (could_see) with all the locations that could be 2051. * seen from the source location. Initialize and fill the left most 2052. * and right most boundaries of what could be seen. 2053. */ 2054. static void 2055. view_from(srow,scol,loc_cs_rows,left_most,right_most, range, func, arg) 2056. int srow, scol; /* source row and column */ 2057. char **loc_cs_rows; /* could_see array (row pointers) */ 2058. char *left_most, *right_most; /* limits of what could be seen */ 2059. int range; /* 0 if unlimited */ 2060. void FDECL((*func), (int,int,genericptr_t)); 2061. genericptr_t arg; 2062. { 2063. register int i; 2064. char *rowp; 2065. int nrow, left, right, left_row, right_row; 2066. char *limits; 2067. 2068. /* Set globals for near_shadow(), far_shadow(), etc. to use. */ 2069. start_col = scol; 2070. start_row = srow; 2071. cs_rows = loc_cs_rows; 2072. cs_left = left_most; 2073. cs_right = right_most; 2074. vis_func = func; 2075. varg = arg; 2076. 2077. /* Find the left and right limits of sight on the starting row. */ 2078. if (viz_clear_rows[srow][scol]) { 2079. left = left_ptrs[srow][scol]; 2080. right = right_ptrs[srow][scol]; 2081. } else { 2082. left = (!scol) ? 0 : 2083. (viz_clear_rows[srow][scol-1] ? left_ptrs[srow][scol-1] : scol-1); 2084. right = (scol == COLNO-1) ? COLNO-1 : 2085. (viz_clear_rows[srow][scol+1] ? right_ptrs[srow][scol+1] : scol+1); 2086. } 2087. 2088. if(range) { 2089. if(range > MAX_RADIUS || range < 1) 2090. panic("view_from called with range %d", range); 2091. limits = circle_ptr(range) + 1; /* start at next row */ 2092. if(left < scol - range) left = scol - range; 2093. if(right > scol + range) right = scol + range; 2094. } else 2095. limits = (char*) 0; 2096. 2097. if(func) { 2098. for (i = left; i <= right; i++) (*func)(i, srow, arg); 2099. } else { 2100. /* Row optimization */ 2101. rowp = cs_rows[srow]; 2102. 2103. /* We know that we can see our row. */ 2104. for (i = left; i <= right; i++) set_cs(rowp,i); 2105. cs_left[srow] = left; 2106. cs_right[srow] = right; 2107. } 2108. 2109. /* The far block has a row number of -1 if we are on an edge. */ 2110. right_row = (right == COLNO-1) ? -1 : srow; 2111. left_row = (!left) ? -1 : srow; 2112. 2113. /* 2114. * Check what could be seen in quadrants. 2115. */ 2116. if ( (nrow = srow+1) < ROWNO ) { 2117. step = 1; /* move down */ 2118. if (scol 2119. right_side(nrow,-1,scol,right_row,right,scol,right,limits); 2120. if (scol) 2121. left_side(nrow,-1,scol,left_row, left, left, scol,limits); 2122. } 2123. 2124. if ( (nrow = srow-1) >= 0 ) { 2125. step = -1; /* move up */ 2126. if (scol 2127. right_side(nrow,-1,scol,right_row,right,scol,right,limits); 2128. if (scol) 2129. left_side(nrow,-1,scol,left_row, left, left, scol,limits); 2130. } 2131. } 2132. 2133. 2134. #else /*===== End of algorithm D =====*/ 2135. 2136. 2137. /*===========================================================================*\ 2138. GENERAL LINE OF SIGHT 2139. Algorithm C 2140. \*===========================================================================*/ 2141. 2142. /* 2143. * Defines local to Algorithm C. 2144. */ 2145. static void FDECL(right_side, (int,int,int,char*)); 2146. static void FDECL(left_side, (int,int,int,char*)); 2147. 2148. /* Initialize algorithm C (nothing). */ 2149. static void 2150. view_init() 2151. { 2152. } 2153. 2154. /* 2155. * Mark positions as visible on one quadrant of the right side. The 2156. * quadrant is determined by the value of the global variable step. 2157. */ 2158. static void 2159. right_side(row, left, right_mark, limits) 2160. int row; /* current row */ 2161. int left; /* first (left side) visible spot on prev row */ 2162. int right_mark; /* last (right side) visible spot on prev row */ 2163. char *limits; /* points at range limit for current row, or NULL */ 2164. { 2165. int right; /* right limit of "could see" */ 2166. int right_edge; /* right edge of an opening */ 2167. int nrow; /* new row (calculate once) */ 2168. int deeper; /* if TRUE, call self as needed */ 2169. int result; /* set by q?_path() */ 2170. register int i; /* loop counter */ 2171. register char *rowp; /* row optimization */ 2172. char *row_min; /* left most [used by macro set_min()] */ 2173. char *row_max; /* right most [used by macro set_max()] */ 2174. int lim_max; /* right most limit of circle */ 2175. 2176. #ifdef GCC_WARN 2177. rowp = row_min = row_max = 0; 2178. #endif 2179. nrow = row + step; 2180. /* 2181. * Can go deeper if the row is in bounds and the next row is within 2182. * the circle's limit. We tell the latter by checking to see if the next 2183. * limit value is the start of a new circle radius (meaning we depend 2184. * on the structure of circle_data[]). 2185. */ 2186. deeper = good_row(nrow) && (!limits || (*limits >= *(limits+1))); 2187. if(!vis_func) { 2188. rowp = cs_rows[row]; /* optimization */ 2189. row_min = &cs_left[row]; 2190. row_max = &cs_right[row]; 2191. } 2192. if(limits) { 2193. lim_max = start_col + *limits; 2194. if(lim_max > COLNO-1) lim_max = COLNO-1; 2195. if(right_mark > lim_max) right_mark = lim_max; 2196. limits++; /* prepare for next row */ 2197. } else 2198. lim_max = COLNO-1; 2199. 2200. while (left <= right_mark) { 2201. right_edge = right_ptrs[row][left]; 2202. if(right_edge > lim_max) right_edge = lim_max; 2203. 2204. if (!is_clear(row,left)) { 2205. /* 2206. * Jump to the far side of a stone wall. We can set all 2207. * the points in between as seen. 2208. * 2209. * If the right edge goes beyond the right mark, check to see 2210. * how much we can see. 2211. */ 2212. if (right_edge > right_mark) { 2213. /* 2214. * If the mark on the previous row was a clear position, 2215. * the odds are that we can actually see part of the wall 2216. * beyond the mark on this row. If so, then see one beyond 2217. * the mark. Otherwise don't. This is a kludge so corners 2218. * with an adjacent doorway show up in nethack. 2219. */ 2220. right_edge = is_clear(row-step,right_mark) ? 2221. right_mark+1 : right_mark; 2222. } 2223. if(vis_func) { 2224. for (i = left; i <= right_edge; i++) (*vis_func)(i, row, varg); 2225. } else { 2226. for (i = left; i <= right_edge; i++) set_cs(rowp,i); 2227. set_min(left); set_max(right_edge); 2228. } 2229. left = right_edge + 1; /* no limit check necessary */ 2230. continue; 2231. } 2232. 2233. /* No checking needed if our left side is the start column. */ 2234. if (left != start_col) { 2235. /* 2236. * Find the left side. Move right until we can see it or we run 2237. * into a wall. 2238. */ 2239. for (; left <= right_edge; left++) { 2240. if (step < 0) { 2241. q1_path(start_row,start_col,row,left,rside1); 2242. } else { 2243. q4_path(start_row,start_col,row,left,rside1); 2244. } 2245. rside1: /* used if q?_path() is a macro */ 2246. if (result) break; 2247. } 2248. 2249. /* 2250. * Check for boundary conditions. We *need* check (2) to break 2251. * an infinite loop where: 2252. * 2253. * left == right_edge == right_mark == lim_max. 2254. * 2255. */ 2256. if (left > lim_max) return; /* check (1) */ 2257. if (left == lim_max) { /* check (2) */ 2258. if(vis_func) (*vis_func)(lim_max, row, varg); 2259. else { 2260. set_cs(rowp,lim_max); 2261. set_max(lim_max); 2262. } 2263. return; 2264. } 2265. /* 2266. * Check if we can see any spots in the opening. We might 2267. * (left == right_edge) or might not (left == right_edge+1) have 2268. * been able to see the far wall. Make sure we *can* see the 2269. * wall (remember, we can see the spot above/below this one) 2270. * by backing up. 2271. */ 2272. if (left >= right_edge) { 2273. left = right_edge; /* for the case left == right_edge+1 */ 2274. continue; 2275. } 2276. } 2277. 2278. /* 2279. * Find the right side. If the marker from the previous row is 2280. * closer than the edge on this row, then we have to check 2281. * how far we can see around the corner (under the overhang). Stop 2282. * at the first non-visible spot or we actually hit the far wall. 2283. * 2284. * Otherwise, we know we can see the right edge of the current row. 2285. * 2286. * This must be a strict less than so that we can always see a 2287. * horizontal wall, even if it is adjacent to us. 2288. */ 2289. if (right_mark < right_edge) { 2290. for (right = right_mark; right <= right_edge; right++) { 2291. if (step < 0) { 2292. q1_path(start_row,start_col,row,right,rside2); 2293. } else { 2294. q4_path(start_row,start_col,row,right,rside2); 2295. } 2296. rside2: /* used if q?_path() is a macro */ 2297. if (!result) break; 2298. } 2299. --right; /* get rid of the last increment */ 2300. } 2301. else 2302. right = right_edge; 2303. 2304. /* 2305. * We have the range that we want. Set the bits. Note that 2306. * there is no else --- we no longer handle splinters. 2307. */ 2308. if (left <= right) { 2309. /* 2310. * An ugly special case. If you are adjacent to a vertical wall 2311. * and it has a break in it, then the right mark is set to be 2312. * start_col. We *want* to be able to see adjacent vertical 2313. * walls, so we have to set it back. 2314. */ 2315. if (left == right && left == start_col && 2316. start_col < (COLNO-1) && !is_clear(row,start_col+1)) 2317. right = start_col+1; 2318. 2319. if(right > lim_max) right = lim_max; 2320. /* set the bits */ 2321. if(vis_func) 2322. for (i = left; i <= right; i++) (*vis_func)(i, row, varg); 2323. else { 2324. for (i = left; i <= right; i++) set_cs(rowp,i); 2325. set_min(left); set_max(right); 2326. } 2327. 2328. /* recursive call for next finger of light */ 2329. if (deeper) right_side(nrow,left,right,limits); 2330. left = right + 1; /* no limit check necessary */ 2331. } 2332. } 2333. } 2334. 2335. 2336. /* 2337. * This routine is the mirror image of right_side(). See right_side() for 2338. * extensive comments. 2339. */ 2340. static void 2341. left_side(row, left_mark, right, limits) 2342. int row, left_mark, right; 2343. char *limits; 2344. { 2345. int left, left_edge, nrow, deeper, result; 2346. register int i; 2347. register char *rowp; 2348. char *row_min, *row_max; 2349. int lim_min; 2350. 2351. #ifdef GCC_WARN 2352. rowp = row_min = row_max = 0; 2353. #endif 2354. nrow = row+step; 2355. deeper = good_row(nrow) && (!limits || (*limits >= *(limits+1))); 2356. if(!vis_func) { 2357. rowp = cs_rows[row]; 2358. row_min = &cs_left[row]; 2359. row_max = &cs_right[row]; 2360. } 2361. if(limits) { 2362. lim_min = start_col - *limits; 2363. if(lim_min < 0) lim_min = 0; 2364. if(left_mark < lim_min) left_mark = lim_min; 2365. limits++; /* prepare for next row */ 2366. } else 2367. lim_min = 0; 2368. 2369. while (right >= left_mark) { 2370. left_edge = left_ptrs[row][right]; 2371. if(left_edge < lim_min) left_edge = lim_min; 2372. 2373. if (!is_clear(row,right)) { 2374. /* Jump to the far side of a stone wall. */ 2375. if (left_edge < left_mark) { 2376. /* Maybe see more (kludge). */ 2377. left_edge = is_clear(row-step,left_mark) ? 2378. left_mark-1 : left_mark; 2379. } 2380. if(vis_func) { 2381. for (i = left_edge; i <= right; i++) (*vis_func)(i, row, varg); 2382. } else { 2383. for (i = left_edge; i <= right; i++) set_cs(rowp,i); 2384. set_min(left_edge); set_max(right); 2385. } 2386. right = left_edge - 1; /* no limit check necessary */ 2387. continue; 2388. } 2389. 2390. if (right != start_col) { 2391. /* Find the right side. */ 2392. for (; right >= left_edge; right--) { 2393. if (step < 0) { 2394. q2_path(start_row,start_col,row,right,lside1); 2395. } else { 2396. q3_path(start_row,start_col,row,right,lside1); 2397. } 2398. lside1: /* used if q?_path() is a macro */ 2399. if (result) break; 2400. } 2401. 2402. /* Check for boundary conditions. */ 2403. if (right < lim_min) return; 2404. if (right == lim_min) { 2405. if(vis_func) (*vis_func)(lim_min, row, varg); 2406. else { 2407. set_cs(rowp,lim_min); 2408. set_min(lim_min); 2409. } 2410. return; 2411. } 2412. /* Check if we can see any spots in the opening. */ 2413. if (right <= left_edge) { 2414. right = left_edge; 2415. continue; 2416. } 2417. } 2418. 2419. /* Find the left side. */ 2420. if (left_mark > left_edge) { 2421. for (left = left_mark; left >= left_edge; --left) { 2422. if (step < 0) { 2423. q2_path(start_row,start_col,row,left,lside2); 2424. } else { 2425. q3_path(start_row,start_col,row,left,lside2); 2426. } 2427. lside2: /* used if q?_path() is a macro */ 2428. if (!result) break; 2429. } 2430. left++; /* get rid of the last decrement */ 2431. } 2432. else 2433. left = left_edge; 2434. 2435. if (left <= right) { 2436. /* An ugly special case. */ 2437. if (left == right && right == start_col && 2438. start_col > 0 && !is_clear(row,start_col-1)) 2439. left = start_col-1; 2440. 2441. if(left < lim_min) left = lim_min; 2442. if(vis_func) 2443. for (i = left; i <= right; i++) (*vis_func)(i, row, varg); 2444. else { 2445. for (i = left; i <= right; i++) set_cs(rowp,i); 2446. set_min(left); set_max(right); 2447. } 2448. 2449. /* Recurse */ 2450. if (deeper) left_side(nrow,left,right,limits); 2451. right = left - 1; /* no limit check necessary */ 2452. } 2453. } 2454. } 2455. 2456. 2457. /* 2458. * Calculate all possible visible locations from the given location 2459. * (srow,scol). NOTE this is (y,x)! Mark the visible locations in the 2460. * array provided. 2461. */ 2462. static void 2463. view_from(srow, scol, loc_cs_rows, left_most, right_most, range, func, arg) 2464. int srow, scol; /* starting row and column */ 2465. char **loc_cs_rows; /* pointers to the rows of the could_see array */ 2466. char *left_most; /* min mark on each row */ 2467. char *right_most; /* max mark on each row */ 2468. int range; /* 0 if unlimited */ 2469. void FDECL((*func), (int,int,genericptr_t)); 2470. genericptr_t arg; 2471. { 2472. register int i; /* loop counter */ 2473. char *rowp; /* optimization for setting could_see */ 2474. int nrow; /* the next row */ 2475. int left; /* the left-most visible column */ 2476. int right; /* the right-most visible column */ 2477. char *limits; /* range limit for next row */ 2478. 2479. /* Set globals for q?_path(), left_side(), and right_side() to use. */ 2480. start_col = scol; 2481. start_row = srow; 2482. cs_rows = loc_cs_rows; /* 'could see' rows */ 2483. cs_left = left_most; 2484. cs_right = right_most; 2485. vis_func = func; 2486. varg = arg; 2487. 2488. /* 2489. * Determine extent of sight on the starting row. 2490. */ 2491. if (is_clear(srow,scol)) { 2492. left = left_ptrs[srow][scol]; 2493. right = right_ptrs[srow][scol]; 2494. } else { 2495. /* 2496. * When in stone, you can only see your adjacent squares, unless 2497. * you are on an array boundary or a stone/clear boundary. 2498. */ 2499. left = (!scol) ? 0 : 2500. (is_clear(srow,scol-1) ? left_ptrs[srow][scol-1] : scol-1); 2501. right = (scol == COLNO-1) ? COLNO-1 : 2502. (is_clear(srow,scol+1) ? right_ptrs[srow][scol+1] : scol+1); 2503. } 2504. 2505. if(range) { 2506. if(range > MAX_RADIUS || range < 1) 2507. panic("view_from called with range %d", range); 2508. limits = circle_ptr(range) + 1; /* start at next row */ 2509. if(left < scol - range) left = scol - range; 2510. if(right > scol + range) right = scol + range; 2511. } else 2512. limits = (char*) 0; 2513. 2514. if(func) { 2515. for (i = left; i <= right; i++) (*func)(i, srow, arg); 2516. } else { 2517. /* Row pointer optimization. */ 2518. rowp = cs_rows[srow]; 2519. 2520. /* We know that we can see our row. */ 2521. for (i = left; i <= right; i++) set_cs(rowp,i); 2522. cs_left[srow] = left; 2523. cs_right[srow] = right; 2524. } 2525. 2526. /* 2527. * Check what could be seen in quadrants. We need to check for valid 2528. * rows here, since we don't do it in the routines right_side() and 2529. * left_side() [ugliness to remove extra routine calls]. 2530. */ 2531. if ( (nrow = srow+1) < ROWNO ) { /* move down */ 2532. step = 1; 2533. if (scol < COLNO-1) right_side(nrow, scol, right, limits); 2534. if (scol) left_side (nrow, left, scol, limits); 2535. } 2536. 2537. if ( (nrow = srow-1) >= 0 ) { /* move up */ 2538. step = -1; 2539. if (scol < COLNO-1) right_side(nrow, scol, right, limits); 2540. if (scol) left_side (nrow, left, scol, limits); 2541. } 2542. } 2543. 2544. #endif /*===== End of algorithm C =====*/ 2545. 2546. /* 2547. * AREA OF EFFECT "ENGINE" 2548. * 2549. * Calculate all possible visible locations as viewed from the given location 2550. * (srow,scol) within the range specified. Perform "func" with (x, y) args and 2551. * additional argument "arg" for each square. 2552. * 2553. * If not centered on the hero, just forward arguments to view_from(); it 2554. * will call "func" when necessary. If the hero is the center, use the 2555. * vision matrix and reduce extra work. 2556. */ 2557. void 2558. do_clear_area(scol,srow,range,func,arg) 2559. int scol, srow, range; 2560. void FDECL((*func), (int,int,genericptr_t)); 2561. genericptr_t arg; 2562. { 2563. /* If not centered on hero, do the hard work of figuring the area */ 2564. if (scol != u.ux || srow != u.uy) 2565. view_from(srow, scol, (char **)0, (char *)0, (char *)0, 2566. range, func, arg); 2567. else { 2568. register int x; 2569. int y, min_x, max_x, max_y, offset; 2570. char *limits; 2571. 2572. if (range > MAX_RADIUS || range < 1) 2573. panic("do_clear_area: illegal range %d", range); 2574. if(vision_full_recalc) 2575. vision_recalc(0); /* recalc vision if dirty */ 2576. limits = circle_ptr(range); 2577. if ((max_y = (srow + range)) >= ROWNO) max_y = ROWNO-1; 2578. if ((y = (srow - range)) < 0) y = 0; 2579. for (; y <= max_y; y++) { 2580. offset = limits[v_abs(y-srow)]; 2581. if((min_x = (scol - offset)) < 0) min_x = 0; 2582. if((max_x = (scol + offset)) >= COLNO) max_x = COLNO-1; 2583. for (x = min_x; x <= max_x; x++) 2584. if (couldsee(x, y)) 2585. (*func)(x, y, arg); 2586. } 2587. } 2588. } 2589. 2590. /*vision.c*/
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)