src/projection.c

   1 #include "angband.h"
   2 #include "projection.h"
   3
   4 /*!
   5  * @brief 始点から終点への経路を返す /
   6  * Determine the path taken by a projection.
   7  * @param gp 経路座標リストを返す参照ポインタ
   8  * @param range 距離
   9  * @param y1 始点Y座標
  10  * @param x1 始点X座標
  11  * @param y2 終点Y座標
  12  * @param x2 終点X座標
  13  * @param flg フラグID
  14  * @return リストの長さ
  15  * @details
  16  * <pre>
  17  * The projection will always start from the grid (y1,x1), and will travel
  18  * towards the grid (y2,x2), touching one grid per unit of distance along
  19  * the major axis, and stopping when it enters the destination grid or a
  20  * wall grid, or has travelled the maximum legal distance of "range".
  21  *
  22  * Note that "distance" in this function (as in the "update_view()" code)
  23  * is defined as "MAX(dy,dx) + MIN(dy,dx)/2", which means that the player
  24  * actually has an "octagon of projection" not a "circle of projection".
  25  *
  26  * The path grids are saved into the grid array pointed to by "gp", and
  27  * there should be room for at least "range" grids in "gp".  Note that
  28  * due to the way in which distance is calculated, this function normally
  29  * uses fewer than "range" grids for the projection path, so the result
  30  * of this function should never be compared directly to "range".  Note
  31  * that the initial grid (y1,x1) is never saved into the grid array, not
  32  * even if the initial grid is also the final grid.
  33  *
  34  * The "flg" flags can be used to modify the behavior of this function.
  35  *
  36  * In particular, the "PROJECT_STOP" and "PROJECT_THRU" flags have the same
  37  * semantics as they do for the "project" function, namely, that the path
  38  * will stop as soon as it hits a monster, or that the path will continue
  39  * through the destination grid, respectively.
  40  *
  41  * The "PROJECT_JUMP" flag, which for the "project()" function means to
  42  * start at a special grid (which makes no sense in this function), means
  43  * that the path should be "angled" slightly if needed to avoid any wall
  44  * grids, allowing the player to "target" any grid which is in "view".
  45  * This flag is non-trivial and has not yet been implemented, but could
  46  * perhaps make use of the "vinfo" array (above).
  47  *
  48  * This function returns the number of grids (if any) in the path.  This
  49  * function will return zero if and only if (y1,x1) and (y2,x2) are equal.
  50  *
  51  * This algorithm is similar to, but slightly different from, the one used
  52  * by "update_view_los()", and very different from the one used by "los()".
  53  * </pre>
  54  */
  55 sint project_path(u16b *gp, POSITION range, POSITION y1, POSITION x1, POSITION y2, POSITION x2, BIT_FLAGS flg)
  56 {
  57         POSITION y, x;
  58
  59         int n = 0;
  60         int k = 0;
  61
  62         /* Absolute */
  63         POSITION ay, ax;
  64
  65         /* Offsets */
  66         POSITION sy, sx;
  67
  68         /* Fractions */
  69         int frac;
  70
  71         /* Scale factors */
  72         int full, half;
  73
  74         /* Slope */
  75         int m;
  76
  77         /* No path necessary (or allowed) */
  78         if ((x1 == x2) && (y1 == y2)) return (0);
  79
  80
  81         /* Analyze "dy" */
  82         if (y2 < y1)
  83         {
  84                 ay = (y1 - y2);
  85                 sy = -1;
  86         }
  87         else
  88         {
  89                 ay = (y2 - y1);
  90                 sy = 1;
  91         }
  92
  93         /* Analyze "dx" */
  94         if (x2 < x1)
  95         {
  96                 ax = (x1 - x2);
  97                 sx = -1;
  98         }
  99         else
 100         {
 101                 ax = (x2 - x1);
 102                 sx = 1;
 103         }
 104
 105
 106         /* Number of "units" in one "half" grid */
 107         half = (ay * ax);
 108
 109         /* Number of "units" in one "full" grid */
 110         full = half << 1;
 111
 112         /* Vertical */
 113         if (ay > ax)
 114         {
 115                 /* Let m = ((dx/dy) * full) = (dx * dx * 2) */
 116                 m = ax * ax * 2;
 117
 118                 /* Start */
 119                 y = y1 + sy;
 120                 x = x1;
 121
 122                 frac = m;
 123
 124                 if (frac > half)
 125                 {
 126                         /* Advance (X) part 2 */
 127                         x += sx;
 128
 129                         /* Advance (X) part 3 */
 130                         frac -= full;
 131
 132                         /* Track distance */
 133                         k++;
 134                 }
 135
 136                 /* Create the projection path */
 137                 while (1)
 138                 {
 139                         /* Save grid */
 140                         gp[n++] = GRID(y, x);
 141
 142                         /* Hack -- Check maximum range */
 143                         if ((n + (k >> 1)) >= range) break;
 144
 145                         /* Sometimes stop at destination grid */
 146                         if (!(flg & (PROJECT_THRU)))
 147                         {
 148                                 if ((x == x2) && (y == y2)) break;
 149                         }
 150
 151                         if (flg & (PROJECT_DISI))
 152                         {
 153                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 154                         }
 155                         else if (flg & (PROJECT_LOS))
 156                         {
 157                                 if ((n > 0) && !cave_los_bold(y, x)) break;
 158                         }
 159                         else if (!(flg & (PROJECT_PATH)))
 160                         {
 161                                 /* Always stop at non-initial wall grids */
 162                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 163                         }
 164
 165                         /* Sometimes stop at non-initial monsters/players */
 166                         if (flg & (PROJECT_STOP))
 167                         {
 168                                 if ((n > 0) &&
 169                                         (player_bold(y, x) || cave[y][x].m_idx != 0))
 170                                         break;
 171                         }
 172
 173                         if (!in_bounds(y, x)) break;
 174
 175                         /* Slant */
 176                         if (m)
 177                         {
 178                                 /* Advance (X) part 1 */
 179                                 frac += m;
 180
 181                                 /* Horizontal change */
 182                                 if (frac > half)
 183                                 {
 184                                         /* Advance (X) part 2 */
 185                                         x += sx;
 186
 187                                         /* Advance (X) part 3 */
 188                                         frac -= full;
 189
 190                                         /* Track distance */
 191                                         k++;
 192                                 }
 193                         }
 194
 195                         /* Advance (Y) */
 196                         y += sy;
 197                 }
 198         }
 199
 200         /* Horizontal */
 201         else if (ax > ay)
 202         {
 203                 /* Let m = ((dy/dx) * full) = (dy * dy * 2) */
 204                 m = ay * ay * 2;
 205
 206                 /* Start */
 207                 y = y1;
 208                 x = x1 + sx;
 209
 210                 frac = m;
 211
 212                 /* Vertical change */
 213                 if (frac > half)
 214                 {
 215                         /* Advance (Y) part 2 */
 216                         y += sy;
 217
 218                         /* Advance (Y) part 3 */
 219                         frac -= full;
 220
 221                         /* Track distance */
 222                         k++;
 223                 }
 224
 225                 /* Create the projection path */
 226                 while (1)
 227                 {
 228                         /* Save grid */
 229                         gp[n++] = GRID(y, x);
 230
 231                         /* Hack -- Check maximum range */
 232                         if ((n + (k >> 1)) >= range) break;
 233
 234                         /* Sometimes stop at destination grid */
 235                         if (!(flg & (PROJECT_THRU)))
 236                         {
 237                                 if ((x == x2) && (y == y2)) break;
 238                         }
 239
 240                         if (flg & (PROJECT_DISI))
 241                         {
 242                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 243                         }
 244                         else if (flg & (PROJECT_LOS))
 245                         {
 246                                 if ((n > 0) && !cave_los_bold(y, x)) break;
 247                         }
 248                         else if (!(flg & (PROJECT_PATH)))
 249                         {
 250                                 /* Always stop at non-initial wall grids */
 251                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 252                         }
 253
 254                         /* Sometimes stop at non-initial monsters/players */
 255                         if (flg & (PROJECT_STOP))
 256                         {
 257                                 if ((n > 0) &&
 258                                         (player_bold(y, x) || cave[y][x].m_idx != 0))
 259                                         break;
 260                         }
 261
 262                         if (!in_bounds(y, x)) break;
 263
 264                         /* Slant */
 265                         if (m)
 266                         {
 267                                 /* Advance (Y) part 1 */
 268                                 frac += m;
 269
 270                                 /* Vertical change */
 271                                 if (frac > half)
 272                                 {
 273                                         /* Advance (Y) part 2 */
 274                                         y += sy;
 275
 276                                         /* Advance (Y) part 3 */
 277                                         frac -= full;
 278
 279                                         /* Track distance */
 280                                         k++;
 281                                 }
 282                         }
 283
 284                         /* Advance (X) */
 285                         x += sx;
 286                 }
 287         }
 288
 289         /* Diagonal */
 290         else
 291         {
 292                 /* Start */
 293                 y = y1 + sy;
 294                 x = x1 + sx;
 295
 296                 /* Create the projection path */
 297                 while (1)
 298                 {
 299                         /* Save grid */
 300                         gp[n++] = GRID(y, x);
 301
 302                         /* Hack -- Check maximum range */
 303                         if ((n + (n >> 1)) >= range) break;
 304
 305                         /* Sometimes stop at destination grid */
 306                         if (!(flg & (PROJECT_THRU)))
 307                         {
 308                                 if ((x == x2) && (y == y2)) break;
 309                         }
 310
 311                         if (flg & (PROJECT_DISI))
 312                         {
 313                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 314                         }
 315                         else if (flg & (PROJECT_LOS))
 316                         {
 317                                 if ((n > 0) && !cave_los_bold(y, x)) break;
 318                         }
 319                         else if (!(flg & (PROJECT_PATH)))
 320                         {
 321                                 /* Always stop at non-initial wall grids */
 322                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 323                         }
 324
 325                         /* Sometimes stop at non-initial monsters/players */
 326                         if (flg & (PROJECT_STOP))
 327                         {
 328                                 if ((n > 0) &&
 329                                         (player_bold(y, x) || cave[y][x].m_idx != 0))
 330                                         break;
 331                         }
 332
 333                         if (!in_bounds(y, x)) break;
 334
 335                         /* Advance (Y) */
 336                         y += sy;
 337
 338                         /* Advance (X) */
 339                         x += sx;
 340                 }
 341         }
 342
 343         /* Length */
 344         return (n);
 345 }
 346