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