src/geometry.c

   1 #include "angband.h"
   2 #include "floor.h"
   3
   4
   5 /*!
   6  * @brief 2点間の距離をニュートン・ラプソン法で算出する / Distance between two points via Newton-Raphson technique
   7  * @param y1 1点目のy座標
   8  * @param x1 1点目のx座標
   9  * @param y2 2点目のy座標
  10  * @param x2 2点目のx座標
  11  * @return 2点間の距離
  12  */
  13 POSITION distance(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
  14 {
  15         POSITION dy = (y1 > y2) ? (y1 - y2) : (y2 - y1);
  16         POSITION dx = (x1 > x2) ? (x1 - x2) : (x2 - x1);
  17
  18         /* Squared distance */
  19         POSITION target = (dy * dy) + (dx * dx);
  20
  21         /* Approximate distance: hypot(dy,dx) = max(dy,dx) + min(dy,dx) / 2 */
  22         POSITION d = (dy > dx) ? (dy + (dx >> 1)) : (dx + (dy >> 1));
  23
  24         POSITION err;
  25
  26         /* Simple case */
  27         if (!dy || !dx) return d;
  28
  29         while (1)
  30         {
  31                 /* Approximate error */
  32                 err = (target - d * d) / (2 * d);
  33
  34                 /* No error - we are done */
  35                 if (!err) break;
  36
  37                 /* Adjust distance */
  38                 d += err;
  39         }
  40
  41         return d;
  42 }
  43
  44 /*!
  45  * @brief プレイヤーから指定の座標がどの方角にあるかを返す /
  46  * Convert an adjacent location to a direction.
  47  * @param y 方角を確認したY座標
  48  * @param x 方角を確認したX座標
  49  * @return 方向ID
  50  */
  51 DIRECTION coords_to_dir(POSITION y, POSITION x)
  52 {
  53         DIRECTION d[3][3] = { {7, 4, 1}, {8, 5, 2}, {9, 6, 3} };
  54         POSITION dy, dx;
  55
  56         dy = y - p_ptr->y;
  57         dx = x - p_ptr->x;
  58         if (ABS(dx) > 1 || ABS(dy) > 1) return (0);
  59
  60         return d[dx + 1][dy + 1];
  61 }
  62
  63 /*!
  64  * @brief 始点から終点への直線経路を返す /
  65  * Determine the path taken by a projection.
  66  * @param gp 経路座標リストを返す参照ポインタ
  67  * @param range 距離
  68  * @param y1 始点Y座標
  69  * @param x1 始点X座標
  70  * @param y2 終点Y座標
  71  * @param x2 終点X座標
  72  * @param flg フラグID
  73  * @return リストの長さ
  74  * @details
  75  * <pre>
  76  * The projection will always start from the grid (y1,x1), and will travel
  77  * towards the grid (y2,x2), touching one grid per unit of distance along
  78  * the major axis, and stopping when it enters the destination grid or a
  79  * wall grid, or has travelled the maximum legal distance of "range".
  80  *
  81  * Note that "distance" in this function (as in the "update_view()" code)
  82  * is defined as "MAX(dy,dx) + MIN(dy,dx)/2", which means that the player
  83  * actually has an "octagon of projection" not a "circle of projection".
  84  *
  85  * The path grids are saved into the grid array pointed to by "gp", and
  86  * there should be room for at least "range" grids in "gp".  Note that
  87  * due to the way in which distance is calculated, this function normally
  88  * uses fewer than "range" grids for the projection path, so the result
  89  * of this function should never be compared directly to "range".  Note
  90  * that the initial grid (y1,x1) is never saved into the grid array, not
  91  * even if the initial grid is also the final grid.
  92  *
  93  * The "flg" flags can be used to modify the behavior of this function.
  94  *
  95  * In particular, the "PROJECT_STOP" and "PROJECT_THRU" flags have the same
  96  * semantics as they do for the "project" function, namely, that the path
  97  * will stop as soon as it hits a monster, or that the path will continue
  98  * through the destination grid, respectively.
  99  *
 100  * The "PROJECT_JUMP" flag, which for the "project()" function means to
 101  * start at a special grid (which makes no sense in this function), means
 102  * that the path should be "angled" slightly if needed to avoid any wall
 103  * grids, allowing the player to "target" any grid which is in "view".
 104  * This flag is non-trivial and has not yet been implemented, but could
 105  * perhaps make use of the "vinfo" array (above).
 106  *
 107  * This function returns the number of grids (if any) in the path.  This
 108  * function will return zero if and only if (y1,x1) and (y2,x2) are equal.
 109  *
 110  * This algorithm is similar to, but slightly different from, the one used
 111  * by "update_view_los()", and very different from the one used by "los()".
 112  * </pre>
 113  */
 114 sint project_path(u16b *gp, POSITION range, POSITION y1, POSITION x1, POSITION y2, POSITION x2, BIT_FLAGS flg)
 115 {
 116         POSITION y, x;
 117
 118         int n = 0;
 119         int k = 0;
 120
 121         /* Absolute */
 122         POSITION ay, ax;
 123
 124         /* Offsets */
 125         POSITION sy, sx;
 126
 127         /* Fractions */
 128         int frac;
 129
 130         /* Scale factors */
 131         int full, half;
 132
 133         /* Slope */
 134         int m;
 135
 136         /* No path necessary (or allowed) */
 137         if ((x1 == x2) && (y1 == y2)) return (0);
 138
 139
 140         /* Analyze "dy" */
 141         if (y2 < y1)
 142         {
 143                 ay = (y1 - y2);
 144                 sy = -1;
 145         }
 146         else
 147         {
 148                 ay = (y2 - y1);
 149                 sy = 1;
 150         }
 151
 152         /* Analyze "dx" */
 153         if (x2 < x1)
 154         {
 155                 ax = (x1 - x2);
 156                 sx = -1;
 157         }
 158         else
 159         {
 160                 ax = (x2 - x1);
 161                 sx = 1;
 162         }
 163
 164
 165         /* Number of "units" in one "half" grid */
 166         half = (ay * ax);
 167
 168         /* Number of "units" in one "full" grid */
 169         full = half << 1;
 170
 171         /* Vertical */
 172         if (ay > ax)
 173         {
 174                 /* Let m = ((dx/dy) * full) = (dx * dx * 2) */
 175                 m = ax * ax * 2;
 176
 177                 /* Start */
 178                 y = y1 + sy;
 179                 x = x1;
 180
 181                 frac = m;
 182
 183                 if (frac > half)
 184                 {
 185                         /* Advance (X) part 2 */
 186                         x += sx;
 187
 188                         /* Advance (X) part 3 */
 189                         frac -= full;
 190
 191                         /* Track distance */
 192                         k++;
 193                 }
 194
 195                 /* Create the projection path */
 196                 while (1)
 197                 {
 198                         /* Save grid */
 199                         gp[n++] = GRID(y, x);
 200
 201                         /* Hack -- Check maximum range */
 202                         if ((n + (k >> 1)) >= range) break;
 203
 204                         /* Sometimes stop at destination grid */
 205                         if (!(flg & (PROJECT_THRU)))
 206                         {
 207                                 if ((x == x2) && (y == y2)) break;
 208                         }
 209
 210                         if (flg & (PROJECT_DISI))
 211                         {
 212                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 213                         }
 214                         else if (flg & (PROJECT_LOS))
 215                         {
 216                                 if ((n > 0) && !cave_los_bold(y, x)) break;
 217                         }
 218                         else if (!(flg & (PROJECT_PATH)))
 219                         {
 220                                 /* Always stop at non-initial wall grids */
 221                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 222                         }
 223
 224                         /* Sometimes stop at non-initial monsters/players */
 225                         if (flg & (PROJECT_STOP))
 226                         {
 227                                 if ((n > 0) &&
 228                                         (player_bold(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
 229                                         break;
 230                         }
 231
 232                         if (!in_bounds(y, x)) break;
 233
 234                         /* Slant */
 235                         if (m)
 236                         {
 237                                 /* Advance (X) part 1 */
 238                                 frac += m;
 239
 240                                 /* Horizontal change */
 241                                 if (frac > half)
 242                                 {
 243                                         /* Advance (X) part 2 */
 244                                         x += sx;
 245
 246                                         /* Advance (X) part 3 */
 247                                         frac -= full;
 248
 249                                         /* Track distance */
 250                                         k++;
 251                                 }
 252                         }
 253
 254                         /* Advance (Y) */
 255                         y += sy;
 256                 }
 257         }
 258
 259         /* Horizontal */
 260         else if (ax > ay)
 261         {
 262                 /* Let m = ((dy/dx) * full) = (dy * dy * 2) */
 263                 m = ay * ay * 2;
 264
 265                 /* Start */
 266                 y = y1;
 267                 x = x1 + sx;
 268
 269                 frac = m;
 270
 271                 /* Vertical change */
 272                 if (frac > half)
 273                 {
 274                         /* Advance (Y) part 2 */
 275                         y += sy;
 276
 277                         /* Advance (Y) part 3 */
 278                         frac -= full;
 279
 280                         /* Track distance */
 281                         k++;
 282                 }
 283
 284                 /* Create the projection path */
 285                 while (1)
 286                 {
 287                         /* Save grid */
 288                         gp[n++] = GRID(y, x);
 289
 290                         /* Hack -- Check maximum range */
 291                         if ((n + (k >> 1)) >= range) break;
 292
 293                         /* Sometimes stop at destination grid */
 294                         if (!(flg & (PROJECT_THRU)))
 295                         {
 296                                 if ((x == x2) && (y == y2)) break;
 297                         }
 298
 299                         if (flg & (PROJECT_DISI))
 300                         {
 301                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 302                         }
 303                         else if (flg & (PROJECT_LOS))
 304                         {
 305                                 if ((n > 0) && !cave_los_bold(y, x)) break;
 306                         }
 307                         else if (!(flg & (PROJECT_PATH)))
 308                         {
 309                                 /* Always stop at non-initial wall grids */
 310                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 311                         }
 312
 313                         /* Sometimes stop at non-initial monsters/players */
 314                         if (flg & (PROJECT_STOP))
 315                         {
 316                                 if ((n > 0) &&
 317                                         (player_bold(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
 318                                         break;
 319                         }
 320
 321                         if (!in_bounds(y, x)) break;
 322
 323                         /* Slant */
 324                         if (m)
 325                         {
 326                                 /* Advance (Y) part 1 */
 327                                 frac += m;
 328
 329                                 /* Vertical change */
 330                                 if (frac > half)
 331                                 {
 332                                         /* Advance (Y) part 2 */
 333                                         y += sy;
 334
 335                                         /* Advance (Y) part 3 */
 336                                         frac -= full;
 337
 338                                         /* Track distance */
 339                                         k++;
 340                                 }
 341                         }
 342
 343                         /* Advance (X) */
 344                         x += sx;
 345                 }
 346         }
 347
 348         /* Diagonal */
 349         else
 350         {
 351                 /* Start */
 352                 y = y1 + sy;
 353                 x = x1 + sx;
 354
 355                 /* Create the projection path */
 356                 while (1)
 357                 {
 358                         /* Save grid */
 359                         gp[n++] = GRID(y, x);
 360
 361                         /* Hack -- Check maximum range */
 362                         if ((n + (n >> 1)) >= range) break;
 363
 364                         /* Sometimes stop at destination grid */
 365                         if (!(flg & (PROJECT_THRU)))
 366                         {
 367                                 if ((x == x2) && (y == y2)) break;
 368                         }
 369
 370                         if (flg & (PROJECT_DISI))
 371                         {
 372                                 if ((n > 0) && cave_stop_disintegration(y, x)) break;
 373                         }
 374                         else if (flg & (PROJECT_LOS))
 375                         {
 376                                 if ((n > 0) && !cave_los_bold(y, x)) break;
 377                         }
 378                         else if (!(flg & (PROJECT_PATH)))
 379                         {
 380                                 /* Always stop at non-initial wall grids */
 381                                 if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
 382                         }
 383
 384                         /* Sometimes stop at non-initial monsters/players */
 385                         if (flg & (PROJECT_STOP))
 386                         {
 387                                 if ((n > 0) &&
 388                                         (player_bold(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
 389                                         break;
 390                         }
 391
 392                         if (!in_bounds(y, x)) break;
 393
 394                         /* Advance (Y) */
 395                         y += sy;
 396
 397                         /* Advance (X) */
 398                         x += sx;
 399                 }
 400         }
 401
 402         /* Length */
 403         return (n);
 404 }
 405
 406 /*!
 407  * @brief LOS(Line Of Sight / 視線が通っているか)の判定を行う。
 408  * @param y1 始点のy座標
 409  * @param x1 始点のx座標
 410  * @param y2 終点のy座標
 411  * @param x2 終点のx座標
 412  * @return LOSが通っているならTRUEを返す。
 413  * @details
 414  * A simple, fast, integer-based line-of-sight algorithm.  By Joseph Hall,\n
 415  * 4116 Brewster Drive, Raleigh NC 27606.  Email to jnh@ecemwl.ncsu.edu.\n
 416  *\n
 417  * Returns TRUE if a line of sight can be traced from (x1,y1) to (x2,y2).\n
 418  *\n
 419  * The LOS begins at the center of the tile (x1,y1) and ends at the center of\n
 420  * the tile (x2,y2).  If los() is to return TRUE, all of the tiles this line\n
 421  * passes through must be floor tiles, except for (x1,y1) and (x2,y2).\n
 422  *\n
 423  * We assume that the "mathematical corner" of a non-floor tile does not\n
 424  * block line of sight.\n
 425  *\n
 426  * Because this function uses (short) ints for all calculations, overflow may\n
 427  * occur if dx and dy exceed 90.\n
 428  *\n
 429  * Once all the degenerate cases are eliminated, the values "qx", "qy", and\n
 430  * "m" are multiplied by a scale factor "f1 = abs(dx * dy * 2)", so that\n
 431  * we can use integer arithmetic.\n
 432  *\n
 433  * We travel from start to finish along the longer axis, starting at the border\n
 434  * between the first and second tiles, where the y offset = .5 * slope, taking\n
 435  * into account the scale factor.  See below.\n
 436  *\n
 437  * Also note that this function and the "move towards target" code do NOT\n
 438  * share the same properties.  Thus, you can see someone, target them, and\n
 439  * then fire a bolt at them, but the bolt may hit a wall, not them.  However\n,
 440  * by clever choice of target locations, you can sometimes throw a "curve".\n
 441  *\n
 442  * Note that "line of sight" is not "reflexive" in all cases.\n
 443  *\n
 444  * Use the "projectable()" routine to test "spell/missile line of sight".\n
 445  *\n
 446  * Use the "update_view()" function to determine player line-of-sight.\n
 447  */
 448 bool los(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
 449 {
 450         /* Delta */
 451         POSITION dx, dy;
 452
 453         /* Absolute */
 454         POSITION ax, ay;
 455
 456         /* Signs */
 457         POSITION sx, sy;
 458
 459         /* Fractions */
 460         POSITION qx, qy;
 461
 462         /* Scanners */
 463         POSITION tx, ty;
 464
 465         /* Scale factors */
 466         POSITION f1, f2;
 467
 468         /* Slope, or 1/Slope, of LOS */
 469         POSITION m;
 470
 471
 472         /* Extract the offset */
 473         dy = y2 - y1;
 474         dx = x2 - x1;
 475
 476         /* Extract the absolute offset */
 477         ay = ABS(dy);
 478         ax = ABS(dx);
 479
 480
 481         /* Handle adjacent (or identical) grids */
 482         if ((ax < 2) && (ay < 2)) return TRUE;
 483
 484
 485         /* Paranoia -- require "safe" origin */
 486         /* if (!in_bounds(y1, x1)) return FALSE; */
 487         /* if (!in_bounds(y2, x2)) return FALSE; */
 488
 489
 490         /* Directly South/North */
 491         if (!dx)
 492         {
 493                 /* South -- check for walls */
 494                 if (dy > 0)
 495                 {
 496                         for (ty = y1 + 1; ty < y2; ty++)
 497                         {
 498                                 if (!cave_los_bold(ty, x1)) return FALSE;
 499                         }
 500                 }
 501
 502                 /* North -- check for walls */
 503                 else
 504                 {
 505                         for (ty = y1 - 1; ty > y2; ty--)
 506                         {
 507                                 if (!cave_los_bold(ty, x1)) return FALSE;
 508                         }
 509                 }
 510
 511                 /* Assume los */
 512                 return TRUE;
 513         }
 514
 515         /* Directly East/West */
 516         if (!dy)
 517         {
 518                 /* East -- check for walls */
 519                 if (dx > 0)
 520                 {
 521                         for (tx = x1 + 1; tx < x2; tx++)
 522                         {
 523                                 if (!cave_los_bold(y1, tx)) return FALSE;
 524                         }
 525                 }
 526
 527                 /* West -- check for walls */
 528                 else
 529                 {
 530                         for (tx = x1 - 1; tx > x2; tx--)
 531                         {
 532                                 if (!cave_los_bold(y1, tx)) return FALSE;
 533                         }
 534                 }
 535
 536                 /* Assume los */
 537                 return TRUE;
 538         }
 539
 540
 541         /* Extract some signs */
 542         sx = (dx < 0) ? -1 : 1;
 543         sy = (dy < 0) ? -1 : 1;
 544
 545
 546         /* Vertical "knights" */
 547         if (ax == 1)
 548         {
 549                 if (ay == 2)
 550                 {
 551                         if (cave_los_bold(y1 + sy, x1)) return TRUE;
 552                 }
 553         }
 554
 555         /* Horizontal "knights" */
 556         else if (ay == 1)
 557         {
 558                 if (ax == 2)
 559                 {
 560                         if (cave_los_bold(y1, x1 + sx)) return TRUE;
 561                 }
 562         }
 563
 564
 565         /* Calculate scale factor div 2 */
 566         f2 = (ax * ay);
 567
 568         /* Calculate scale factor */
 569         f1 = f2 << 1;
 570
 571
 572         /* Travel horizontally */
 573         if (ax >= ay)
 574         {
 575                 /* Let m = dy / dx * 2 * (dy * dx) = 2 * dy * dy */
 576                 qy = ay * ay;
 577                 m = qy << 1;
 578
 579                 tx = x1 + sx;
 580
 581                 /* Consider the special case where slope == 1. */
 582                 if (qy == f2)
 583                 {
 584                         ty = y1 + sy;
 585                         qy -= f1;
 586                 }
 587                 else
 588                 {
 589                         ty = y1;
 590                 }
 591
 592                 /* Note (below) the case (qy == f2), where */
 593                 /* the LOS exactly meets the corner of a tile. */
 594                 while (x2 - tx)
 595                 {
 596                         if (!cave_los_bold(ty, tx)) return FALSE;
 597
 598                         qy += m;
 599
 600                         if (qy < f2)
 601                         {
 602                                 tx += sx;
 603                         }
 604                         else if (qy > f2)
 605                         {
 606                                 ty += sy;
 607                                 if (!cave_los_bold(ty, tx)) return FALSE;
 608                                 qy -= f1;
 609                                 tx += sx;
 610                         }
 611                         else
 612                         {
 613                                 ty += sy;
 614                                 qy -= f1;
 615                                 tx += sx;
 616                         }
 617                 }
 618         }
 619
 620         /* Travel vertically */
 621         else
 622         {
 623                 /* Let m = dx / dy * 2 * (dx * dy) = 2 * dx * dx */
 624                 qx = ax * ax;
 625                 m = qx << 1;
 626
 627                 ty = y1 + sy;
 628
 629                 if (qx == f2)
 630                 {
 631                         tx = x1 + sx;
 632                         qx -= f1;
 633                 }
 634                 else
 635                 {
 636                         tx = x1;
 637                 }
 638
 639                 /* Note (below) the case (qx == f2), where */
 640                 /* the LOS exactly meets the corner of a tile. */
 641                 while (y2 - ty)
 642                 {
 643                         if (!cave_los_bold(ty, tx)) return FALSE;
 644
 645                         qx += m;
 646
 647                         if (qx < f2)
 648                         {
 649                                 ty += sy;
 650                         }
 651                         else if (qx > f2)
 652                         {
 653                                 tx += sx;
 654                                 if (!cave_los_bold(ty, tx)) return FALSE;
 655                                 qx -= f1;
 656                                 ty += sy;
 657                         }
 658                         else
 659                         {
 660                                 tx += sx;
 661                                 qx -= f1;
 662                                 ty += sy;
 663                         }
 664                 }
 665         }
 666
 667         /* Assume los */
 668         return TRUE;
 669 }
 670
 671 /*
 672  * Determine if a bolt spell cast from (y1,x1) to (y2,x2) will arrive
 673  * at the final destination, assuming no monster gets in the way.
 674  *
 675  * This is slightly (but significantly) different from "los(y1,x1,y2,x2)".
 676  */
 677 bool projectable(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
 678 {
 679         POSITION y, x;
 680
 681         int grid_n = 0;
 682         u16b grid_g[512];
 683
 684         /* Check the projection path */
 685         grid_n = project_path(grid_g, (project_length ? project_length : MAX_RANGE), y1, x1, y2, x2, 0);
 686
 687         /* Identical grid */
 688         if (!grid_n) return TRUE;
 689
 690         /* Final grid */
 691         y = GRID_Y(grid_g[grid_n - 1]);
 692         x = GRID_X(grid_g[grid_n - 1]);
 693
 694         /* May not end in an unrequested grid */
 695         if ((y != y2) || (x != x2)) return (FALSE);
 696
 697         /* Assume okay */
 698         return (TRUE);
 699 }
 700
 701
 702
 703 /*
 704  * Standard "find me a location" function
 705  *
 706  * Obtains a legal location within the given distance of the initial
 707  * location, and with "los()" from the source to destination location.
 708  *
 709  * This function is often called from inside a loop which searches for
 710  * locations while increasing the "d" distance.
 711  *
 712  * Currently the "m" parameter is unused.
 713  */
 714 void scatter(POSITION *yp, POSITION *xp, POSITION y, POSITION x, POSITION d, BIT_FLAGS mode)
 715 {
 716         POSITION nx, ny;
 717
 718         /* Pick a location */
 719         while (TRUE)
 720         {
 721                 /* Pick a new location */
 722                 ny = rand_spread(y, d);
 723                 nx = rand_spread(x, d);
 724
 725                 /* Ignore annoying locations */
 726                 if (!in_bounds(ny, nx)) continue;
 727
 728                 /* Ignore "excessively distant" locations */
 729                 if ((d > 1) && (distance(y, x, ny, nx) > d)) continue;
 730
 731                 if (mode & PROJECT_LOS)
 732                 {
 733                         if (los(y, x, ny, nx)) break;
 734                 }
 735                 else
 736                 {
 737                         if (projectable(y, x, ny, nx)) break;
 738                 }
 739
 740         }
 741
 742         /* Save the location */
 743         (*yp) = ny;
 744         (*xp) = nx;
 745 }
 746
 747 /*
 748  * Calculate "incremental motion". Used by project() and shoot().
 749  * Assumes that (*y,*x) lies on the path from (y1,x1) to (y2,x2).
 750  */
 751 void mmove2(POSITION *y, POSITION *x, POSITION y1, POSITION x1, POSITION y2, POSITION x2)
 752 {
 753         POSITION dy, dx, dist, shift;
 754
 755         /* Extract the distance travelled */
 756         dy = (*y < y1) ? y1 - *y : *y - y1;
 757         dx = (*x < x1) ? x1 - *x : *x - x1;
 758
 759         /* Number of steps */
 760         dist = (dy > dx) ? dy : dx;
 761
 762         /* We are calculating the next location */
 763         dist++;
 764
 765
 766         /* Calculate the total distance along each axis */
 767         dy = (y2 < y1) ? (y1 - y2) : (y2 - y1);
 768         dx = (x2 < x1) ? (x1 - x2) : (x2 - x1);
 769
 770         /* Paranoia -- Hack -- no motion */
 771         if (!dy && !dx) return;
 772
 773
 774         /* Move mostly vertically */
 775         if (dy > dx)
 776         {
 777                 /* Extract a shift factor */
 778                 shift = (dist * dx + (dy - 1) / 2) / dy;
 779
 780                 /* Sometimes move along the minor axis */
 781                 (*x) = (x2 < x1) ? (x1 - shift) : (x1 + shift);
 782
 783                 /* Always move along major axis */
 784                 (*y) = (y2 < y1) ? (y1 - dist) : (y1 + dist);
 785         }
 786
 787         /* Move mostly horizontally */
 788         else
 789         {
 790                 /* Extract a shift factor */
 791                 shift = (dist * dy + (dx - 1) / 2) / dx;
 792
 793                 /* Sometimes move along the minor axis */
 794                 (*y) = (y2 < y1) ? (y1 - shift) : (y1 + shift);
 795
 796                 /* Always move along major axis */
 797                 (*x) = (x2 < x1) ? (x1 - dist) : (x1 + dist);
 798         }
 799 }
 800