src/geometry.c

   1 #include "angband.h"
   2 #include "floor.h"
   3 #include "spells.h"
   4
   5
   6 /*!
   7  * キーパッドの方向を南から反時計回り順に列挙 / Global array for looping through the "keypad directions"
   8  */
   9 const POSITION ddd[9] =
  10 { 2, 8, 6, 4, 3, 1, 9, 7, 5 };
  11
  12 /*!
  13  * dddで定義した順にベクトルのX軸成分を定義 / Global arrays for converting "keypad direction" into offsets
  14  */
  15 const POSITION ddx[10] =
  16 { 0, -1, 0, 1, -1, 0, 1, -1, 0, 1 };
  17
  18 /*!
  19  * dddで定義した順にベクトルのY軸成分を定義 / Global arrays for converting "keypad direction" into offsets
  20  */
  21 const POSITION ddy[10] =
  22 { 0, 1, 1, 1, 0, 0, 0, -1, -1, -1 };
  23
  24 /*!
  25  * ddd越しにベクトルのX軸成分を定義 / Global arrays for optimizing "ddx[ddd[i]]" and "ddy[ddd[i]]"
  26  */
  27 const POSITION ddx_ddd[9] =
  28 { 0, 0, 1, -1, 1, -1, 1, -1, 0 };
  29
  30 /*!
  31  * ddd越しにベクトルのY軸成分を定義 / Global arrays for optimizing "ddx[ddd[i]]" and "ddy[ddd[i]]"
  32  */
  33 const POSITION ddy_ddd[9] =
  34 { 1, -1, 0, 0, 1, 1, -1, -1, 0 };
  35
  36
  37 /*!
  38  * キーパッドの円環状方向配列 / Circular keypad direction array
  39  */
  40 const POSITION cdd[8] =
  41 { 2, 3, 6, 9, 8, 7, 4, 1 };
  42
  43 /*!
  44  * cdd越しにベクトルのX軸成分を定義 / Global arrays for optimizing "ddx[cdd[i]]" and "ddy[cdd[i]]"
  45  */
  46 const POSITION ddx_cdd[8] =
  47 { 0, 1, 1, 1, 0, -1, -1, -1 };
  48
  49 /*!
  50  * cdd越しにベクトルのY軸成分を定義 / Global arrays for optimizing "ddx[cdd[i]]" and "ddy[cdd[i]]"
  51  */
  52 const POSITION ddy_cdd[8] =
  53 { 1, 1, 0, -1, -1, -1, 0, 1 };
  54
  55
  56 /*!
  57  * @brief 2点間の距離をニュートン・ラプソン法で算出する / Distance between two points via Newton-Raphson technique
  58  * @param y1 1点目のy座標
  59  * @param x1 1点目のx座標
  60  * @param y2 2点目のy座標
  61  * @param x2 2点目のx座標
  62  * @return 2点間の距離
  63  */
  64 POSITION distance(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
  65 {
  66         POSITION dy = (y1 > y2) ? (y1 - y2) : (y2 - y1);
  67         POSITION dx = (x1 > x2) ? (x1 - x2) : (x2 - x1);
  68
  69         /* Squared distance */
  70         POSITION target = (dy * dy) + (dx * dx);
  71
  72         /* Approximate distance: hypot(dy,dx) = max(dy,dx) + min(dy,dx) / 2 */
  73         POSITION d = (dy > dx) ? (dy + (dx >> 1)) : (dx + (dy >> 1));
  74
  75         POSITION err;
  76
  77         /* Simple case */
  78         if (!dy || !dx) return d;
  79
  80         while (1)
  81         {
  82                 /* Approximate error */
  83                 err = (target - d * d) / (2 * d);
  84
  85                 /* No error - we are done */
  86                 if (!err) break;
  87
  88                 /* Adjust distance */
  89                 d += err;
  90         }
  91
  92         return d;
  93 }
  94
  95 /*!
  96  * @brief プレイヤーから指定の座標がどの方角にあるかを返す /
  97  * Convert an adjacent location to a direction.
  98  * @param y 方角を確認したY座標
  99  * @param x 方角を確認したX座標
 100  * @return 方向ID
 101  */
 102 DIRECTION coords_to_dir(player_type *creature_ptr, POSITION y, POSITION x)
 103 {
 104         DIRECTION d[3][3] = { {7, 4, 1}, {8, 5, 2}, {9, 6, 3} };
 105         POSITION dy, dx;
 106
 107         dy = y - creature_ptr->y;
 108         dx = x - creature_ptr->x;
 109         if (ABS(dx) > 1 || ABS(dy) > 1) return (0);
 110
 111         return d[dx + 1][dy + 1];
 112 }
 113
 114 /*!
 115  * @brief 始点から終点への直線経路を返す /
 116  * Determine the path taken by a projection.
 117  * @param gp 経路座標リストを返す参照ポインタ
 118  * @param range 距離
 119  * @param y1 始点Y座標
 120  * @param x1 始点X座標
 121  * @param y2 終点Y座標
 122  * @param x2 終点X座標
 123  * @param flg フラグID
 124  * @return リストの長さ
 125  * @details
 126  * <pre>
 127  * The projection will always start from the grid (y1,x1), and will travel
 128  * towards the grid (y2,x2), touching one grid per unit of distance along
 129  * the major axis, and stopping when it enters the destination grid or a
 130  * wall grid, or has travelled the maximum legal distance of "range".
 131  *
 132  * Note that "distance" in this function (as in the "update_view()" code)
 133  * is defined as "MAX(dy,dx) + MIN(dy,dx)/2", which means that the player
 134  * actually has an "octagon of projection" not a "circle of projection".
 135  *
 136  * The path grids are saved into the grid array pointed to by "gp", and
 137  * there should be room for at least "range" grids in "gp".  Note that
 138  * due to the way in which distance is calculated, this function normally
 139  * uses fewer than "range" grids for the projection path, so the result
 140  * of this function should never be compared directly to "range".  Note
 141  * that the initial grid (y1,x1) is never saved into the grid array, not
 142  * even if the initial grid is also the final grid.
 143  *
 144  * The "flg" flags can be used to modify the behavior of this function.
 145  *
 146  * In particular, the "PROJECT_STOP" and "PROJECT_THRU" flags have the same
 147  * semantics as they do for the "project" function, namely, that the path
 148  * will stop as soon as it hits a monster, or that the path will continue
 149  * through the destination grid, respectively.
 150  *
 151  * The "PROJECT_JUMP" flag, which for the "project()" function means to
 152  * start at a special grid (which makes no sense in this function), means
 153  * that the path should be "angled" slightly if needed to avoid any wall
 154  * grids, allowing the player to "target" any grid which is in "view".
 155  * This flag is non-trivial and has not yet been implemented, but could
 156  * perhaps make use of the "vinfo" array (above).
 157  *
 158  * This function returns the number of grids (if any) in the path.  This
 159  * function will return zero if and only if (y1,x1) and (y2,x2) are equal.
 160  *
 161  * This algorithm is similar to, but slightly different from, the one used
 162  * by "update_view_los()", and very different from the one used by "los()".
 163  * </pre>
 164  */
 165 sint project_path(u16b *gp, POSITION range, POSITION y1, POSITION x1, POSITION y2, POSITION x2, BIT_FLAGS flg)
 166 {
 167         POSITION y, x;
 168
 169         int n = 0;
 170         int k = 0;
 171
 172         /* Absolute */
 173         POSITION ay, ax;
 174
 175         /* Offsets */
 176         POSITION sy, sx;
 177
 178         /* Fractions */
 179         int frac;
 180
 181         /* Scale factors */
 182         int full, half;
 183
 184         /* Slope */
 185         int m;
 186
 187         /* No path necessary (or allowed) */
 188         if ((x1 == x2) && (y1 == y2)) return (0);
 189
 190
 191         /* Analyze "dy" */
 192         if (y2 < y1)
 193         {
 194                 ay = (y1 - y2);
 195                 sy = -1;
 196         }
 197         else
 198         {
 199                 ay = (y2 - y1);
 200                 sy = 1;
 201         }
 202
 203         /* Analyze "dx" */
 204         if (x2 < x1)
 205         {
 206                 ax = (x1 - x2);
 207                 sx = -1;
 208         }
 209         else
 210         {
 211                 ax = (x2 - x1);
 212                 sx = 1;
 213         }
 214
 215
 216         /* Number of "units" in one "half" grid */
 217         half = (ay * ax);
 218
 219         /* Number of "units" in one "full" grid */
 220         full = half << 1;
 221
 222         /* Vertical */
 223         if (ay > ax)
 224         {
 225                 /* Let m = ((dx/dy) * full) = (dx * dx * 2) */
 226                 m = ax * ax * 2;
 227
 228                 /* Start */
 229                 y = y1 + sy;
 230                 x = x1;
 231
 232                 frac = m;
 233
 234                 if (frac > half)
 235                 {
 236                         /* Advance (X) part 2 */
 237                         x += sx;
 238
 239                         /* Advance (X) part 3 */
 240                         frac -= full;
 241
 242                         /* Track distance */
 243                         k++;
 244                 }
 245
 246                 /* Create the projection path */
 247                 while (1)
 248                 {
 249                         /* Save grid */
 250                         gp[n++] = GRID(y, x);
 251
 252                         /* Hack -- Check maximum range */
 253                         if ((n + (k >> 1)) >= range) break;
 254
 255                         /* Sometimes stop at destination grid */
 256                         if (!(flg & (PROJECT_THRU)))
 257                         {
 258                                 if ((x == x2) && (y == y2)) break;
 259                         }
 260
 261                         if (flg & (PROJECT_DISI))
 262                         {
 263                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 264                         }
 265                         else if (flg & (PROJECT_LOS))
 266                         {
 267                                 if ((n > 0) && !cave_los_bold(p_ptr->current_floor_ptr, y, x)) break;
 268                         }
 269                         else if (!(flg & (PROJECT_PATH)))
 270                         {
 271                                 /* Always stop at non-initial wall grids */
 272                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 273                         }
 274
 275                         /* Sometimes stop at non-initial monsters/players */
 276                         if (flg & (PROJECT_STOP))
 277                         {
 278                                 if ((n > 0) &&
 279                                         (player_bold(p_ptr, y, x) || p_ptr->current_floor_ptr->grid_array[y][x].m_idx != 0))
 280                                         break;
 281                         }
 282
 283                         if (!in_bounds(p_ptr->current_floor_ptr, y, x)) break;
 284
 285                         /* Slant */
 286                         if (m)
 287                         {
 288                                 /* Advance (X) part 1 */
 289                                 frac += m;
 290
 291                                 /* Horizontal change */
 292                                 if (frac > half)
 293                                 {
 294                                         /* Advance (X) part 2 */
 295                                         x += sx;
 296
 297                                         /* Advance (X) part 3 */
 298                                         frac -= full;
 299
 300                                         /* Track distance */
 301                                         k++;
 302                                 }
 303                         }
 304
 305                         /* Advance (Y) */
 306                         y += sy;
 307                 }
 308         }
 309
 310         /* Horizontal */
 311         else if (ax > ay)
 312         {
 313                 /* Let m = ((dy/dx) * full) = (dy * dy * 2) */
 314                 m = ay * ay * 2;
 315
 316                 /* Start */
 317                 y = y1;
 318                 x = x1 + sx;
 319
 320                 frac = m;
 321
 322                 /* Vertical change */
 323                 if (frac > half)
 324                 {
 325                         /* Advance (Y) part 2 */
 326                         y += sy;
 327
 328                         /* Advance (Y) part 3 */
 329                         frac -= full;
 330
 331                         /* Track distance */
 332                         k++;
 333                 }
 334
 335                 /* Create the projection path */
 336                 while (1)
 337                 {
 338                         /* Save grid */
 339                         gp[n++] = GRID(y, x);
 340
 341                         /* Hack -- Check maximum range */
 342                         if ((n + (k >> 1)) >= range) break;
 343
 344                         /* Sometimes stop at destination grid */
 345                         if (!(flg & (PROJECT_THRU)))
 346                         {
 347                                 if ((x == x2) && (y == y2)) break;
 348                         }
 349
 350                         if (flg & (PROJECT_DISI))
 351                         {
 352                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 353                         }
 354                         else if (flg & (PROJECT_LOS))
 355                         {
 356                                 if ((n > 0) && !cave_los_bold(p_ptr->current_floor_ptr, y, x)) break;
 357                         }
 358                         else if (!(flg & (PROJECT_PATH)))
 359                         {
 360                                 /* Always stop at non-initial wall grids */
 361                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 362                         }
 363
 364                         /* Sometimes stop at non-initial monsters/players */
 365                         if (flg & (PROJECT_STOP))
 366                         {
 367                                 if ((n > 0) &&
 368                                         (player_bold(p_ptr, y, x) || p_ptr->current_floor_ptr->grid_array[y][x].m_idx != 0))
 369                                         break;
 370                         }
 371
 372                         if (!in_bounds(p_ptr->current_floor_ptr, y, x)) break;
 373
 374                         /* Slant */
 375                         if (m)
 376                         {
 377                                 /* Advance (Y) part 1 */
 378                                 frac += m;
 379
 380                                 /* Vertical change */
 381                                 if (frac > half)
 382                                 {
 383                                         /* Advance (Y) part 2 */
 384                                         y += sy;
 385
 386                                         /* Advance (Y) part 3 */
 387                                         frac -= full;
 388
 389                                         /* Track distance */
 390                                         k++;
 391                                 }
 392                         }
 393
 394                         /* Advance (X) */
 395                         x += sx;
 396                 }
 397         }
 398
 399         /* Diagonal */
 400         else
 401         {
 402                 /* Start */
 403                 y = y1 + sy;
 404                 x = x1 + sx;
 405
 406                 /* Create the projection path */
 407                 while (1)
 408                 {
 409                         /* Save grid */
 410                         gp[n++] = GRID(y, x);
 411
 412                         /* Hack -- Check maximum range */
 413                         if ((n + (n >> 1)) >= range) break;
 414
 415                         /* Sometimes stop at destination grid */
 416                         if (!(flg & (PROJECT_THRU)))
 417                         {
 418                                 if ((x == x2) && (y == y2)) break;
 419                         }
 420
 421                         if (flg & (PROJECT_DISI))
 422                         {
 423                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 424                         }
 425                         else if (flg & (PROJECT_LOS))
 426                         {
 427                                 if ((n > 0) && !cave_los_bold(p_ptr->current_floor_ptr, y, x)) break;
 428                         }
 429                         else if (!(flg & (PROJECT_PATH)))
 430                         {
 431                                 /* Always stop at non-initial wall grids */
 432                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 433                         }
 434
 435                         /* Sometimes stop at non-initial monsters/players */
 436                         if (flg & (PROJECT_STOP))
 437                         {
 438                                 if ((n > 0) &&
 439                                         (player_bold(p_ptr, y, x) || p_ptr->current_floor_ptr->grid_array[y][x].m_idx != 0))
 440                                         break;
 441                         }
 442
 443                         if (!in_bounds(p_ptr->current_floor_ptr, y, x)) break;
 444
 445                         /* Advance (Y) */
 446                         y += sy;
 447
 448                         /* Advance (X) */
 449                         x += sx;
 450                 }
 451         }
 452
 453         /* Length */
 454         return (n);
 455 }
 456
 457
 458 /*
 459  * Standard "find me a location" function
 460  *
 461  * Obtains a legal location within the given distance of the initial
 462  * location, and with "los()" from the source to destination location.
 463  *
 464  * This function is often called from inside a loop which searches for
 465  * locations while increasing the "d" distance.
 466  *
 467  * Currently the "m" parameter is unused.
 468  */
 469 void scatter(POSITION *yp, POSITION *xp, POSITION y, POSITION x, POSITION d, BIT_FLAGS mode)
 470 {
 471         POSITION nx, ny;
 472
 473         /* Pick a location */
 474         while (TRUE)
 475         {
 476                 /* Pick a new location */
 477                 ny = rand_spread(y, d);
 478                 nx = rand_spread(x, d);
 479
 480                 /* Ignore annoying locations */
 481                 if (!in_bounds(p_ptr->current_floor_ptr, ny, nx)) continue;
 482
 483                 /* Ignore "excessively distant" locations */
 484                 if ((d > 1) && (distance(y, x, ny, nx) > d)) continue;
 485
 486                 if (mode & PROJECT_LOS)
 487                 {
 488                         if (los(p_ptr->current_floor_ptr, y, x, ny, nx)) break;
 489                 }
 490                 else
 491                 {
 492                         if (projectable(p_ptr->current_floor_ptr, y, x, ny, nx)) break;
 493                 }
 494
 495         }
 496
 497         /* Save the location */
 498         (*yp) = ny;
 499         (*xp) = nx;
 500 }
 501
 502
 503 /*!
 504  * @brief 指定された座標をプレイヤーが視覚に収められるかを返す。 / Can the player "see" the given grid in detail?
 505  * @param y y座標
 506  * @param x x座標
 507  * @return 視覚に収められる状態ならTRUEを返す
 508  * @details
 509  * He must have vision, illumination, and line of sight.\n
 510  * \n
 511  * Note -- "CAVE_LITE" is only set if the "torch" has "los()".\n
 512  * So, given "CAVE_LITE", we know that the grid is "fully visible".\n
 513  *\n
 514  * Note that "CAVE_GLOW" makes little sense for a wall, since it would mean\n
 515  * that a wall is visible from any direction.  That would be odd.  Except\n
 516  * under wizard light, which might make sense.  Thus, for walls, we require\n
 517  * not only that they be "CAVE_GLOW", but also, that they be adjacent to a\n
 518  * grid which is not only "CAVE_GLOW", but which is a non-wall, and which is\n
 519  * in line of sight of the player.\n
 520  *\n
 521  * This extra check is expensive, but it provides a more "correct" semantics.\n
 522  *\n
 523  * Note that we should not run this check on walls which are "outer walls" of\n
 524  * the dungeon, or we will induce a memory fault, but actually verifying all\n
 525  * of the locations would be extremely expensive.\n
 526  *\n
 527  * Thus, to speed up the function, we assume that all "perma-walls" which are\n
 528  * "CAVE_GLOW" are "illuminated" from all sides.  This is correct for all cases\n
 529  * except "vaults" and the "buildings" in town.  But the town is a hack anyway,\n
 530  * and the player has more important things on his mind when he is attacking a\n
 531  * monster vault.  It is annoying, but an extremely important optimization.\n
 532  *\n
 533  * Note that "glowing walls" are only considered to be "illuminated" if the\n
 534  * grid which is next to the wall in the direction of the player is also a\n
 535  * "glowing" grid.  This prevents the player from being able to "see" the\n
 536  * walls of illuminated rooms from a corridor outside the room.\n
 537  */
 538 bool player_can_see_bold(POSITION y, POSITION x)
 539 {
 540         grid_type *g_ptr;
 541
 542         /* Blind players see nothing */
 543         if (p_ptr->blind) return FALSE;
 544
 545         g_ptr = &p_ptr->current_floor_ptr->grid_array[y][x];
 546
 547         /* Note that "torch-lite" yields "illumination" */
 548         if (g_ptr->info & (CAVE_LITE | CAVE_MNLT)) return TRUE;
 549
 550         /* Require line of sight to the grid */
 551         if (!player_has_los_bold(p_ptr, y, x)) return FALSE;
 552
 553         /* Noctovision of Ninja */
 554         if (p_ptr->see_nocto) return TRUE;
 555
 556         /* Require "perma-lite" of the grid */
 557         if ((g_ptr->info & (CAVE_GLOW | CAVE_MNDK)) != CAVE_GLOW) return FALSE;
 558
 559         /* Feature code (applying "mimic" field) */
 560         /* Floors are simple */
 561         if (feat_supports_los(get_feat_mimic(g_ptr))) return TRUE;
 562
 563         /* Check for "local" illumination */
 564         return check_local_illumination(y, x);
 565 }
 566
 567 /*
 568  * Calculate "incremental motion". Used by project() and shoot().
 569  * Assumes that (*y,*x) lies on the path from (y1,x1) to (y2,x2).
 570  */
 571 void mmove2(POSITION *y, POSITION *x, POSITION y1, POSITION x1, POSITION y2, POSITION x2)
 572 {
 573         POSITION dy, dx, dist, shift;
 574
 575         /* Extract the distance travelled */
 576         dy = (*y < y1) ? y1 - *y : *y - y1;
 577         dx = (*x < x1) ? x1 - *x : *x - x1;
 578
 579         /* Number of steps */
 580         dist = (dy > dx) ? dy : dx;
 581
 582         /* We are calculating the next location */
 583         dist++;
 584
 585
 586         /* Calculate the total distance along each axis */
 587         dy = (y2 < y1) ? (y1 - y2) : (y2 - y1);
 588         dx = (x2 < x1) ? (x1 - x2) : (x2 - x1);
 589
 590         /* Paranoia -- Hack -- no motion */
 591         if (!dy && !dx) return;
 592
 593
 594         /* Move mostly vertically */
 595         if (dy > dx)
 596         {
 597                 /* Extract a shift factor */
 598                 shift = (dist * dx + (dy - 1) / 2) / dy;
 599
 600                 /* Sometimes move along the minor axis */
 601                 (*x) = (x2 < x1) ? (x1 - shift) : (x1 + shift);
 602
 603                 /* Always move along major axis */
 604                 (*y) = (y2 < y1) ? (y1 - dist) : (y1 + dist);
 605         }
 606
 607         /* Move mostly horizontally */
 608         else
 609         {
 610                 /* Extract a shift factor */
 611                 shift = (dist * dy + (dx - 1) / 2) / dx;
 612
 613                 /* Sometimes move along the minor axis */
 614                 (*y) = (y2 < y1) ? (y1 - shift) : (y1 + shift);
 615
 616                 /* Always move along major axis */
 617                 (*x) = (x2 < x1) ? (x1 - dist) : (x1 + dist);
 618         }
 619 }
 620