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(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 - p_ptr->y;
 108         dx = x - p_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(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(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
 280                                         break;
 281                         }
 282
 283                         if (!in_bounds(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(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(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
 369                                         break;
 370                         }
 371
 372                         if (!in_bounds(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(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(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
 440                                         break;
 441                         }
 442
 443                         if (!in_bounds(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  * @brief LOS(Line Of Sight / 視線が通っているか)の判定を行う。
 459  * @param y1 始点のy座標
 460  * @param x1 始点のx座標
 461  * @param y2 終点のy座標
 462  * @param x2 終点のx座標
 463  * @return LOSが通っているならTRUEを返す。
 464  * @details
 465  * A simple, fast, integer-based line-of-sight algorithm.  By Joseph Hall,\n
 466  * 4116 Brewster Drive, Raleigh NC 27606.  Email to jnh@ecemwl.ncsu.edu.\n
 467  *\n
 468  * Returns TRUE if a line of sight can be traced from (x1,y1) to (x2,y2).\n
 469  *\n
 470  * The LOS begins at the center of the tile (x1,y1) and ends at the center of\n
 471  * the tile (x2,y2).  If los() is to return TRUE, all of the tiles this line\n
 472  * passes through must be floor tiles, except for (x1,y1) and (x2,y2).\n
 473  *\n
 474  * We assume that the "mathematical corner" of a non-floor tile does not\n
 475  * block line of sight.\n
 476  *\n
 477  * Because this function uses (short) ints for all calculations, overflow may\n
 478  * occur if dx and dy exceed 90.\n
 479  *\n
 480  * Once all the degenerate cases are eliminated, the values "qx", "qy", and\n
 481  * "m" are multiplied by a scale factor "f1 = abs(dx * dy * 2)", so that\n
 482  * we can use integer arithmetic.\n
 483  *\n
 484  * We travel from start to finish along the longer axis, starting at the border\n
 485  * between the first and second tiles, where the y offset = .5 * slope, taking\n
 486  * into account the scale factor.  See below.\n
 487  *\n
 488  * Also note that this function and the "move towards target" code do NOT\n
 489  * share the same properties.  Thus, you can see someone, target them, and\n
 490  * then fire a bolt at them, but the bolt may hit a wall, not them.  However\n,
 491  * by clever choice of target locations, you can sometimes throw a "curve".\n
 492  *\n
 493  * Note that "line of sight" is not "reflexive" in all cases.\n
 494  *\n
 495  * Use the "projectable()" routine to test "spell/missile line of sight".\n
 496  *\n
 497  * Use the "update_view()" function to determine player line-of-sight.\n
 498  */
 499 bool los(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
 500 {
 501         /* Delta */
 502         POSITION dx, dy;
 503
 504         /* Absolute */
 505         POSITION ax, ay;
 506
 507         /* Signs */
 508         POSITION sx, sy;
 509
 510         /* Fractions */
 511         POSITION qx, qy;
 512
 513         /* Scanners */
 514         POSITION tx, ty;
 515
 516         /* Scale factors */
 517         POSITION f1, f2;
 518
 519         /* Slope, or 1/Slope, of LOS */
 520         POSITION m;
 521
 522
 523         /* Extract the offset */
 524         dy = y2 - y1;
 525         dx = x2 - x1;
 526
 527         /* Extract the absolute offset */
 528         ay = ABS(dy);
 529         ax = ABS(dx);
 530
 531
 532         /* Handle adjacent (or identical) grids */
 533         if ((ax < 2) && (ay < 2)) return TRUE;
 534
 535
 536         /* Paranoia -- require "safe" origin */
 537         /* if (!in_bounds(current_floor_ptr, y1, x1)) return FALSE; */
 538         /* if (!in_bounds(current_floor_ptr, y2, x2)) return FALSE; */
 539
 540
 541         /* Directly South/North */
 542         if (!dx)
 543         {
 544                 /* South -- check for walls */
 545                 if (dy > 0)
 546                 {
 547                         for (ty = y1 + 1; ty < y2; ty++)
 548                         {
 549                                 if (!cave_los_bold(ty, x1)) return FALSE;
 550                         }
 551                 }
 552
 553                 /* North -- check for walls */
 554                 else
 555                 {
 556                         for (ty = y1 - 1; ty > y2; ty--)
 557                         {
 558                                 if (!cave_los_bold(ty, x1)) return FALSE;
 559                         }
 560                 }
 561
 562                 /* Assume los */
 563                 return TRUE;
 564         }
 565
 566         /* Directly East/West */
 567         if (!dy)
 568         {
 569                 /* East -- check for walls */
 570                 if (dx > 0)
 571                 {
 572                         for (tx = x1 + 1; tx < x2; tx++)
 573                         {
 574                                 if (!cave_los_bold(y1, tx)) return FALSE;
 575                         }
 576                 }
 577
 578                 /* West -- check for walls */
 579                 else
 580                 {
 581                         for (tx = x1 - 1; tx > x2; tx--)
 582                         {
 583                                 if (!cave_los_bold(y1, tx)) return FALSE;
 584                         }
 585                 }
 586
 587                 /* Assume los */
 588                 return TRUE;
 589         }
 590
 591
 592         /* Extract some signs */
 593         sx = (dx < 0) ? -1 : 1;
 594         sy = (dy < 0) ? -1 : 1;
 595
 596
 597         /* Vertical "knights" */
 598         if (ax == 1)
 599         {
 600                 if (ay == 2)
 601                 {
 602                         if (cave_los_bold(y1 + sy, x1)) return TRUE;
 603                 }
 604         }
 605
 606         /* Horizontal "knights" */
 607         else if (ay == 1)
 608         {
 609                 if (ax == 2)
 610                 {
 611                         if (cave_los_bold(y1, x1 + sx)) return TRUE;
 612                 }
 613         }
 614
 615
 616         /* Calculate scale factor div 2 */
 617         f2 = (ax * ay);
 618
 619         /* Calculate scale factor */
 620         f1 = f2 << 1;
 621
 622
 623         /* Travel horizontally */
 624         if (ax >= ay)
 625         {
 626                 /* Let m = dy / dx * 2 * (dy * dx) = 2 * dy * dy */
 627                 qy = ay * ay;
 628                 m = qy << 1;
 629
 630                 tx = x1 + sx;
 631
 632                 /* Consider the special case where slope == 1. */
 633                 if (qy == f2)
 634                 {
 635                         ty = y1 + sy;
 636                         qy -= f1;
 637                 }
 638                 else
 639                 {
 640                         ty = y1;
 641                 }
 642
 643                 /* Note (below) the case (qy == f2), where */
 644                 /* the LOS exactly meets the corner of a tile. */
 645                 while (x2 - tx)
 646                 {
 647                         if (!cave_los_bold(ty, tx)) return FALSE;
 648
 649                         qy += m;
 650
 651                         if (qy < f2)
 652                         {
 653                                 tx += sx;
 654                         }
 655                         else if (qy > f2)
 656                         {
 657                                 ty += sy;
 658                                 if (!cave_los_bold(ty, tx)) return FALSE;
 659                                 qy -= f1;
 660                                 tx += sx;
 661                         }
 662                         else
 663                         {
 664                                 ty += sy;
 665                                 qy -= f1;
 666                                 tx += sx;
 667                         }
 668                 }
 669         }
 670
 671         /* Travel vertically */
 672         else
 673         {
 674                 /* Let m = dx / dy * 2 * (dx * dy) = 2 * dx * dx */
 675                 qx = ax * ax;
 676                 m = qx << 1;
 677
 678                 ty = y1 + sy;
 679
 680                 if (qx == f2)
 681                 {
 682                         tx = x1 + sx;
 683                         qx -= f1;
 684                 }
 685                 else
 686                 {
 687                         tx = x1;
 688                 }
 689
 690                 /* Note (below) the case (qx == f2), where */
 691                 /* the LOS exactly meets the corner of a tile. */
 692                 while (y2 - ty)
 693                 {
 694                         if (!cave_los_bold(ty, tx)) return FALSE;
 695
 696                         qx += m;
 697
 698                         if (qx < f2)
 699                         {
 700                                 ty += sy;
 701                         }
 702                         else if (qx > f2)
 703                         {
 704                                 tx += sx;
 705                                 if (!cave_los_bold(ty, tx)) return FALSE;
 706                                 qx -= f1;
 707                                 ty += sy;
 708                         }
 709                         else
 710                         {
 711                                 tx += sx;
 712                                 qx -= f1;
 713                                 ty += sy;
 714                         }
 715                 }
 716         }
 717
 718         /* Assume los */
 719         return TRUE;
 720 }
 721
 722 /*
 723  * Determine if a bolt spell cast from (y1,x1) to (y2,x2) will arrive
 724  * at the final destination, assuming no monster gets in the way.
 725  *
 726  * This is slightly (but significantly) different from "los(y1,x1,y2,x2)".
 727  */
 728 bool projectable(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
 729 {
 730         POSITION y, x;
 731
 732         int grid_n = 0;
 733         u16b grid_g[512];
 734
 735         /* Check the projection path */
 736         grid_n = project_path(grid_g, (project_length ? project_length : MAX_RANGE), y1, x1, y2, x2, 0);
 737
 738         /* Identical grid */
 739         if (!grid_n) return TRUE;
 740
 741         /* Final grid */
 742         y = GRID_Y(grid_g[grid_n - 1]);
 743         x = GRID_X(grid_g[grid_n - 1]);
 744
 745         /* May not end in an unrequested grid */
 746         if ((y != y2) || (x != x2)) return (FALSE);
 747
 748         /* Assume okay */
 749         return (TRUE);
 750 }
 751
 752
 753
 754 /*
 755  * Standard "find me a location" function
 756  *
 757  * Obtains a legal location within the given distance of the initial
 758  * location, and with "los()" from the source to destination location.
 759  *
 760  * This function is often called from inside a loop which searches for
 761  * locations while increasing the "d" distance.
 762  *
 763  * Currently the "m" parameter is unused.
 764  */
 765 void scatter(POSITION *yp, POSITION *xp, POSITION y, POSITION x, POSITION d, BIT_FLAGS mode)
 766 {
 767         POSITION nx, ny;
 768
 769         /* Pick a location */
 770         while (TRUE)
 771         {
 772                 /* Pick a new location */
 773                 ny = rand_spread(y, d);
 774                 nx = rand_spread(x, d);
 775
 776                 /* Ignore annoying locations */
 777                 if (!in_bounds(current_floor_ptr, ny, nx)) continue;
 778
 779                 /* Ignore "excessively distant" locations */
 780                 if ((d > 1) && (distance(y, x, ny, nx) > d)) continue;
 781
 782                 if (mode & PROJECT_LOS)
 783                 {
 784                         if (los(y, x, ny, nx)) break;
 785                 }
 786                 else
 787                 {
 788                         if (projectable(y, x, ny, nx)) break;
 789                 }
 790
 791         }
 792
 793         /* Save the location */
 794         (*yp) = ny;
 795         (*xp) = nx;
 796 }
 797
 798 /*
 799  * Calculate "incremental motion". Used by project() and shoot().
 800  * Assumes that (*y,*x) lies on the path from (y1,x1) to (y2,x2).
 801  */
 802 void mmove2(POSITION *y, POSITION *x, POSITION y1, POSITION x1, POSITION y2, POSITION x2)
 803 {
 804         POSITION dy, dx, dist, shift;
 805
 806         /* Extract the distance travelled */
 807         dy = (*y < y1) ? y1 - *y : *y - y1;
 808         dx = (*x < x1) ? x1 - *x : *x - x1;
 809
 810         /* Number of steps */
 811         dist = (dy > dx) ? dy : dx;
 812
 813         /* We are calculating the next location */
 814         dist++;
 815
 816
 817         /* Calculate the total distance along each axis */
 818         dy = (y2 < y1) ? (y1 - y2) : (y2 - y1);
 819         dx = (x2 < x1) ? (x1 - x2) : (x2 - x1);
 820
 821         /* Paranoia -- Hack -- no motion */
 822         if (!dy && !dx) return;
 823
 824
 825         /* Move mostly vertically */
 826         if (dy > dx)
 827         {
 828                 /* Extract a shift factor */
 829                 shift = (dist * dx + (dy - 1) / 2) / dy;
 830
 831                 /* Sometimes move along the minor axis */
 832                 (*x) = (x2 < x1) ? (x1 - shift) : (x1 + shift);
 833
 834                 /* Always move along major axis */
 835                 (*y) = (y2 < y1) ? (y1 - dist) : (y1 + dist);
 836         }
 837
 838         /* Move mostly horizontally */
 839         else
 840         {
 841                 /* Extract a shift factor */
 842                 shift = (dist * dy + (dx - 1) / 2) / dx;
 843
 844                 /* Sometimes move along the minor axis */
 845                 (*y) = (y2 < y1) ? (y1 - shift) : (y1 + shift);
 846
 847                 /* Always move along major axis */
 848                 (*x) = (x2 < x1) ? (x1 - dist) : (x1 + dist);
 849         }
 850 }
 851