src/vision.c

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