src/floor/line-of-sight.c

   1 #include "floor/line-of-sight.h"
   2 #include "floor/cave.h"
   3 #include "system/floor-type-definition.h"
   4
   5 /*!
   6  * @brief LOS(Line Of Sight / 視線が通っているか)の判定を行う。
   7  * @param player_ptr プレーヤーへの参照ポインタ
   8  * @param y1 始点のy座標
   9  * @param x1 始点のx座標
  10  * @param y2 終点のy座標
  11  * @param x2 終点のx座標
  12  * @return LOSが通っているならTRUEを返す。
  13  * @details
  14  * A simple, fast, integer-based line-of-sight algorithm.  By Joseph Hall,\n
  15  * 4116 Brewster Drive, Raleigh NC 27606.  Email to jnh@ecemwl.ncsu.edu.\n
  16  *\n
  17  * Returns TRUE if a line of sight can be traced from (x1,y1) to (x2,y2).\n
  18  *\n
  19  * The LOS begins at the center of the tile (x1,y1) and ends at the center of\n
  20  * the tile (x2,y2).  If los() is to return TRUE, all of the tiles this line\n
  21  * passes through must be floor tiles, except for (x1,y1) and (x2,y2).\n
  22  *\n
  23  * We assume that the "mathematical corner" of a non-floor tile does not\n
  24  * block line of sight.\n
  25  *\n
  26  * Because this function uses (short) ints for all calculations, overflow may\n
  27  * occur if dx and dy exceed 90.\n
  28  *\n
  29  * Once all the degenerate cases are eliminated, the values "qx", "qy", and\n
  30  * "m" are multiplied by a scale factor "f1 = abs(dx * dy * 2)", so that\n
  31  * we can use integer arithmetic.\n
  32  *\n
  33  * We travel from start to finish along the longer axis, starting at the border\n
  34  * between the first and second tiles, where the y offset = .5 * slope, taking\n
  35  * into account the scale factor.  See below.\n
  36  *\n
  37  * Also note that this function and the "move towards target" code do NOT\n
  38  * share the same properties.  Thus, you can see someone, target them, and\n
  39  * then fire a bolt at them, but the bolt may hit a wall, not them.  However\n,
  40  * by clever choice of target locations, you can sometimes throw a "curve".\n
  41  *\n
  42  * Note that "line of sight" is not "reflexive" in all cases.\n
  43  *\n
  44  * Use the "projectable()" routine to test "spell/missile line of sight".\n
  45  *\n
  46  * Use the "update_view()" function to determine player line-of-sight.\n
  47  */
  48 bool los(player_type *player_ptr, POSITION y1, POSITION x1, POSITION y2, POSITION x2)
  49 {
  50     POSITION dy = y2 - y1;
  51     POSITION dx = x2 - x1;
  52     POSITION ay = ABS(dy);
  53     POSITION ax = ABS(dx);
  54     if ((ax < 2) && (ay < 2))
  55         return TRUE;
  56
  57     /* Directly South/North */
  58     floor_type *floor_ptr = player_ptr->current_floor_ptr;
  59     POSITION tx, ty;
  60     if (!dx) {
  61         /* South -- check for walls */
  62         if (dy > 0) {
  63             for (ty = y1 + 1; ty < y2; ty++) {
  64                 if (!cave_los_bold(floor_ptr, ty, x1))
  65                     return FALSE;
  66             }
  67         }
  68
  69         /* North -- check for walls */
  70         else {
  71             for (ty = y1 - 1; ty > y2; ty--) {
  72                 if (!cave_los_bold(floor_ptr, ty, x1))
  73                     return FALSE;
  74             }
  75         }
  76
  77         /* Assume los */
  78         return TRUE;
  79     }
  80
  81     /* Directly East/West */
  82     if (!dy) {
  83         /* East -- check for walls */
  84         if (dx > 0) {
  85             for (tx = x1 + 1; tx < x2; tx++) {
  86                 if (!cave_los_bold(floor_ptr, y1, tx))
  87                     return FALSE;
  88             }
  89         }
  90
  91         /* West -- check for walls */
  92         else {
  93             for (tx = x1 - 1; tx > x2; tx--) {
  94                 if (!cave_los_bold(floor_ptr, y1, tx))
  95                     return FALSE;
  96             }
  97         }
  98
  99         return TRUE;
 100     }
 101
 102     POSITION sx = (dx < 0) ? -1 : 1;
 103     POSITION sy = (dy < 0) ? -1 : 1;
 104
 105     if (ax == 1) {
 106         if (ay == 2) {
 107             if (cave_los_bold(floor_ptr, y1 + sy, x1))
 108                 return TRUE;
 109         }
 110     } else if (ay == 1) {
 111         if (ax == 2) {
 112             if (cave_los_bold(floor_ptr, y1, x1 + sx))
 113                 return TRUE;
 114         }
 115     }
 116
 117     POSITION f2 = (ax * ay);
 118     POSITION f1 = f2 << 1;
 119     POSITION qy;
 120     POSITION m;
 121     if (ax >= ay) {
 122         qy = ay * ay;
 123         m = qy << 1;
 124         tx = x1 + sx;
 125         if (qy == f2) {
 126             ty = y1 + sy;
 127             qy -= f1;
 128         } else {
 129             ty = y1;
 130         }
 131
 132         /* Note (below) the case (qy == f2), where */
 133         /* the LOS exactly meets the corner of a tile. */
 134         while (x2 - tx) {
 135             if (!cave_los_bold(floor_ptr, ty, tx))
 136                 return FALSE;
 137
 138             qy += m;
 139
 140             if (qy < f2) {
 141                 tx += sx;
 142                 continue;
 143             }
 144
 145             if (qy > f2) {
 146                 ty += sy;
 147                 if (!cave_los_bold(floor_ptr, ty, tx))
 148                     return FALSE;
 149                 qy -= f1;
 150                 tx += sx;
 151                 continue;
 152             }
 153
 154             ty += sy;
 155             qy -= f1;
 156             tx += sx;
 157         }
 158
 159         return TRUE;
 160     }
 161
 162     /* Travel vertically */
 163     POSITION qx = ax * ax;
 164     m = qx << 1;
 165     ty = y1 + sy;
 166     if (qx == f2) {
 167         tx = x1 + sx;
 168         qx -= f1;
 169     } else {
 170         tx = x1;
 171     }
 172
 173     /* Note (below) the case (qx == f2), where */
 174     /* the LOS exactly meets the corner of a tile. */
 175     while (y2 - ty) {
 176         if (!cave_los_bold(floor_ptr, ty, tx))
 177             return FALSE;
 178
 179         qx += m;
 180
 181         if (qx < f2) {
 182             ty += sy;
 183             continue;
 184         }
 185
 186         if (qx > f2) {
 187             tx += sx;
 188             if (!cave_los_bold(floor_ptr, ty, tx))
 189                 return FALSE;
 190             qx -= f1;
 191             ty += sy;
 192             continue;
 193         }
 194
 195         tx += sx;
 196         qx -= f1;
 197         ty += sy;
 198     }
 199
 200     return TRUE;
 201 }