src/floor/line-of-sight.cpp

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