#include "angband.h"
+#include "floor.h"
+#include "spells.h"
+
+
+/*!
+ * キーパッドの方向を南から反時計回り順に列挙 / Global array for looping through the "keypad directions"
+ */
+const POSITION ddd[9] =
+{ 2, 8, 6, 4, 3, 1, 9, 7, 5 };
+
+/*!
+ * dddで定義した順にベクトルのX軸成分を定義 / Global arrays for converting "keypad direction" into offsets
+ */
+const POSITION ddx[10] =
+{ 0, -1, 0, 1, -1, 0, 1, -1, 0, 1 };
+
+/*!
+ * dddで定義した順にベクトルのY軸成分を定義 / Global arrays for converting "keypad direction" into offsets
+ */
+const POSITION ddy[10] =
+{ 0, 1, 1, 1, 0, 0, 0, -1, -1, -1 };
+
+/*!
+ * ddd越しにベクトルのX軸成分を定義 / Global arrays for optimizing "ddx[ddd[i]]" and "ddy[ddd[i]]"
+ */
+const POSITION ddx_ddd[9] =
+{ 0, 0, 1, -1, 1, -1, 1, -1, 0 };
+
+/*!
+ * ddd越しにベクトルのY軸成分を定義 / Global arrays for optimizing "ddx[ddd[i]]" and "ddy[ddd[i]]"
+ */
+const POSITION ddy_ddd[9] =
+{ 1, -1, 0, 0, 1, 1, -1, -1, 0 };
+
+
+/*!
+ * キーパッドの円環状方向配列 / Circular keypad direction array
+ */
+const POSITION cdd[8] =
+{ 2, 3, 6, 9, 8, 7, 4, 1 };
+
+/*!
+ * cdd越しにベクトルのX軸成分を定義 / Global arrays for optimizing "ddx[cdd[i]]" and "ddy[cdd[i]]"
+ */
+const POSITION ddx_cdd[8] =
+{ 0, 1, 1, 1, 0, -1, -1, -1 };
+
+/*!
+ * cdd越しにベクトルのY軸成分を定義 / Global arrays for optimizing "ddx[cdd[i]]" and "ddy[cdd[i]]"
+ */
+const POSITION ddy_cdd[8] =
+{ 1, 1, 0, -1, -1, -1, 0, 1 };
+
+
+/*!
+ * @brief 2点間の距離をニュートン・ラプソン法で算出する / Distance between two points via Newton-Raphson technique
+ * @param y1 1点目のy座標
+ * @param x1 1点目のx座標
+ * @param y2 2点目のy座標
+ * @param x2 2点目のx座標
+ * @return 2点間の距離
+ */
+POSITION distance(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
+{
+ POSITION dy = (y1 > y2) ? (y1 - y2) : (y2 - y1);
+ POSITION dx = (x1 > x2) ? (x1 - x2) : (x2 - x1);
+
+ /* Squared distance */
+ POSITION target = (dy * dy) + (dx * dx);
+
+ /* Approximate distance: hypot(dy,dx) = max(dy,dx) + min(dy,dx) / 2 */
+ POSITION d = (dy > dx) ? (dy + (dx >> 1)) : (dx + (dy >> 1));
+
+ POSITION err;
+
+ /* Simple case */
+ if (!dy || !dx) return d;
+
+ while (1)
+ {
+ /* Approximate error */
+ err = (target - d * d) / (2 * d);
+
+ /* No error - we are done */
+ if (!err) break;
+
+ /* Adjust distance */
+ d += err;
+ }
+
+ return d;
+}
/*!
* @brief プレイヤーから指定の座標がどの方角にあるかを返す /
return d[dx + 1][dy + 1];
}
+
+/*!
+ * @brief 始点から終点への直線経路を返す /
+ * Determine the path taken by a projection.
+ * @param gp 経路座標リストを返す参照ポインタ
+ * @param range 距離
+ * @param y1 始点Y座標
+ * @param x1 始点X座標
+ * @param y2 終点Y座標
+ * @param x2 終点X座標
+ * @param flg フラグID
+ * @return リストの長さ
+ * @details
+ * <pre>
+ * The projection will always start from the grid (y1,x1), and will travel
+ * towards the grid (y2,x2), touching one grid per unit of distance along
+ * the major axis, and stopping when it enters the destination grid or a
+ * wall grid, or has travelled the maximum legal distance of "range".
+ *
+ * Note that "distance" in this function (as in the "update_view()" code)
+ * is defined as "MAX(dy,dx) + MIN(dy,dx)/2", which means that the player
+ * actually has an "octagon of projection" not a "circle of projection".
+ *
+ * The path grids are saved into the grid array pointed to by "gp", and
+ * there should be room for at least "range" grids in "gp". Note that
+ * due to the way in which distance is calculated, this function normally
+ * uses fewer than "range" grids for the projection path, so the result
+ * of this function should never be compared directly to "range". Note
+ * that the initial grid (y1,x1) is never saved into the grid array, not
+ * even if the initial grid is also the final grid.
+ *
+ * The "flg" flags can be used to modify the behavior of this function.
+ *
+ * In particular, the "PROJECT_STOP" and "PROJECT_THRU" flags have the same
+ * semantics as they do for the "project" function, namely, that the path
+ * will stop as soon as it hits a monster, or that the path will continue
+ * through the destination grid, respectively.
+ *
+ * The "PROJECT_JUMP" flag, which for the "project()" function means to
+ * start at a special grid (which makes no sense in this function), means
+ * that the path should be "angled" slightly if needed to avoid any wall
+ * grids, allowing the player to "target" any grid which is in "view".
+ * This flag is non-trivial and has not yet been implemented, but could
+ * perhaps make use of the "vinfo" array (above).
+ *
+ * This function returns the number of grids (if any) in the path. This
+ * function will return zero if and only if (y1,x1) and (y2,x2) are equal.
+ *
+ * This algorithm is similar to, but slightly different from, the one used
+ * by "update_view_los()", and very different from the one used by "los()".
+ * </pre>
+ */
+sint project_path(u16b *gp, POSITION range, POSITION y1, POSITION x1, POSITION y2, POSITION x2, BIT_FLAGS flg)
+{
+ POSITION y, x;
+
+ int n = 0;
+ int k = 0;
+
+ /* Absolute */
+ POSITION ay, ax;
+
+ /* Offsets */
+ POSITION sy, sx;
+
+ /* Fractions */
+ int frac;
+
+ /* Scale factors */
+ int full, half;
+
+ /* Slope */
+ int m;
+
+ /* No path necessary (or allowed) */
+ if ((x1 == x2) && (y1 == y2)) return (0);
+
+
+ /* Analyze "dy" */
+ if (y2 < y1)
+ {
+ ay = (y1 - y2);
+ sy = -1;
+ }
+ else
+ {
+ ay = (y2 - y1);
+ sy = 1;
+ }
+
+ /* Analyze "dx" */
+ if (x2 < x1)
+ {
+ ax = (x1 - x2);
+ sx = -1;
+ }
+ else
+ {
+ ax = (x2 - x1);
+ sx = 1;
+ }
+
+
+ /* Number of "units" in one "half" grid */
+ half = (ay * ax);
+
+ /* Number of "units" in one "full" grid */
+ full = half << 1;
+
+ /* Vertical */
+ if (ay > ax)
+ {
+ /* Let m = ((dx/dy) * full) = (dx * dx * 2) */
+ m = ax * ax * 2;
+
+ /* Start */
+ y = y1 + sy;
+ x = x1;
+
+ frac = m;
+
+ if (frac > half)
+ {
+ /* Advance (X) part 2 */
+ x += sx;
+
+ /* Advance (X) part 3 */
+ frac -= full;
+
+ /* Track distance */
+ k++;
+ }
+
+ /* Create the projection path */
+ while (1)
+ {
+ /* Save grid */
+ gp[n++] = GRID(y, x);
+
+ /* Hack -- Check maximum range */
+ if ((n + (k >> 1)) >= range) break;
+
+ /* Sometimes stop at destination grid */
+ if (!(flg & (PROJECT_THRU)))
+ {
+ if ((x == x2) && (y == y2)) break;
+ }
+
+ if (flg & (PROJECT_DISI))
+ {
+ if ((n > 0) && cave_stop_disintegration(y, x)) break;
+ }
+ else if (flg & (PROJECT_LOS))
+ {
+ if ((n > 0) && !cave_los_bold(y, x)) break;
+ }
+ else if (!(flg & (PROJECT_PATH)))
+ {
+ /* Always stop at non-initial wall grids */
+ if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
+ }
+
+ /* Sometimes stop at non-initial monsters/players */
+ if (flg & (PROJECT_STOP))
+ {
+ if ((n > 0) &&
+ (player_bold(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
+ break;
+ }
+
+ if (!in_bounds(y, x)) break;
+
+ /* Slant */
+ if (m)
+ {
+ /* Advance (X) part 1 */
+ frac += m;
+
+ /* Horizontal change */
+ if (frac > half)
+ {
+ /* Advance (X) part 2 */
+ x += sx;
+
+ /* Advance (X) part 3 */
+ frac -= full;
+
+ /* Track distance */
+ k++;
+ }
+ }
+
+ /* Advance (Y) */
+ y += sy;
+ }
+ }
+
+ /* Horizontal */
+ else if (ax > ay)
+ {
+ /* Let m = ((dy/dx) * full) = (dy * dy * 2) */
+ m = ay * ay * 2;
+
+ /* Start */
+ y = y1;
+ x = x1 + sx;
+
+ frac = m;
+
+ /* Vertical change */
+ if (frac > half)
+ {
+ /* Advance (Y) part 2 */
+ y += sy;
+
+ /* Advance (Y) part 3 */
+ frac -= full;
+
+ /* Track distance */
+ k++;
+ }
+
+ /* Create the projection path */
+ while (1)
+ {
+ /* Save grid */
+ gp[n++] = GRID(y, x);
+
+ /* Hack -- Check maximum range */
+ if ((n + (k >> 1)) >= range) break;
+
+ /* Sometimes stop at destination grid */
+ if (!(flg & (PROJECT_THRU)))
+ {
+ if ((x == x2) && (y == y2)) break;
+ }
+
+ if (flg & (PROJECT_DISI))
+ {
+ if ((n > 0) && cave_stop_disintegration(y, x)) break;
+ }
+ else if (flg & (PROJECT_LOS))
+ {
+ if ((n > 0) && !cave_los_bold(y, x)) break;
+ }
+ else if (!(flg & (PROJECT_PATH)))
+ {
+ /* Always stop at non-initial wall grids */
+ if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
+ }
+
+ /* Sometimes stop at non-initial monsters/players */
+ if (flg & (PROJECT_STOP))
+ {
+ if ((n > 0) &&
+ (player_bold(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
+ break;
+ }
+
+ if (!in_bounds(y, x)) break;
+
+ /* Slant */
+ if (m)
+ {
+ /* Advance (Y) part 1 */
+ frac += m;
+
+ /* Vertical change */
+ if (frac > half)
+ {
+ /* Advance (Y) part 2 */
+ y += sy;
+
+ /* Advance (Y) part 3 */
+ frac -= full;
+
+ /* Track distance */
+ k++;
+ }
+ }
+
+ /* Advance (X) */
+ x += sx;
+ }
+ }
+
+ /* Diagonal */
+ else
+ {
+ /* Start */
+ y = y1 + sy;
+ x = x1 + sx;
+
+ /* Create the projection path */
+ while (1)
+ {
+ /* Save grid */
+ gp[n++] = GRID(y, x);
+
+ /* Hack -- Check maximum range */
+ if ((n + (n >> 1)) >= range) break;
+
+ /* Sometimes stop at destination grid */
+ if (!(flg & (PROJECT_THRU)))
+ {
+ if ((x == x2) && (y == y2)) break;
+ }
+
+ if (flg & (PROJECT_DISI))
+ {
+ if ((n > 0) && cave_stop_disintegration(y, x)) break;
+ }
+ else if (flg & (PROJECT_LOS))
+ {
+ if ((n > 0) && !cave_los_bold(y, x)) break;
+ }
+ else if (!(flg & (PROJECT_PATH)))
+ {
+ /* Always stop at non-initial wall grids */
+ if ((n > 0) && !cave_have_flag_bold(y, x, FF_PROJECT)) break;
+ }
+
+ /* Sometimes stop at non-initial monsters/players */
+ if (flg & (PROJECT_STOP))
+ {
+ if ((n > 0) &&
+ (player_bold(y, x) || current_floor_ptr->grid_array[y][x].m_idx != 0))
+ break;
+ }
+
+ if (!in_bounds(y, x)) break;
+
+ /* Advance (Y) */
+ y += sy;
+
+ /* Advance (X) */
+ x += sx;
+ }
+ }
+
+ /* Length */
+ return (n);
+}
+
+/*!
+ * @brief LOS(Line Of Sight / 視線が通っているか)の判定を行う。
+ * @param y1 始点のy座標
+ * @param x1 始点のx座標
+ * @param y2 終点のy座標
+ * @param x2 終点のx座標
+ * @return LOSが通っているならTRUEを返す。
+ * @details
+ * A simple, fast, integer-based line-of-sight algorithm. By Joseph Hall,\n
+ * 4116 Brewster Drive, Raleigh NC 27606. Email to jnh@ecemwl.ncsu.edu.\n
+ *\n
+ * Returns TRUE if a line of sight can be traced from (x1,y1) to (x2,y2).\n
+ *\n
+ * The LOS begins at the center of the tile (x1,y1) and ends at the center of\n
+ * the tile (x2,y2). If los() is to return TRUE, all of the tiles this line\n
+ * passes through must be floor tiles, except for (x1,y1) and (x2,y2).\n
+ *\n
+ * We assume that the "mathematical corner" of a non-floor tile does not\n
+ * block line of sight.\n
+ *\n
+ * Because this function uses (short) ints for all calculations, overflow may\n
+ * occur if dx and dy exceed 90.\n
+ *\n
+ * Once all the degenerate cases are eliminated, the values "qx", "qy", and\n
+ * "m" are multiplied by a scale factor "f1 = abs(dx * dy * 2)", so that\n
+ * we can use integer arithmetic.\n
+ *\n
+ * We travel from start to finish along the longer axis, starting at the border\n
+ * between the first and second tiles, where the y offset = .5 * slope, taking\n
+ * into account the scale factor. See below.\n
+ *\n
+ * Also note that this function and the "move towards target" code do NOT\n
+ * share the same properties. Thus, you can see someone, target them, and\n
+ * then fire a bolt at them, but the bolt may hit a wall, not them. However\n,
+ * by clever choice of target locations, you can sometimes throw a "curve".\n
+ *\n
+ * Note that "line of sight" is not "reflexive" in all cases.\n
+ *\n
+ * Use the "projectable()" routine to test "spell/missile line of sight".\n
+ *\n
+ * Use the "update_view()" function to determine player line-of-sight.\n
+ */
+bool los(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
+{
+ /* Delta */
+ POSITION dx, dy;
+
+ /* Absolute */
+ POSITION ax, ay;
+
+ /* Signs */
+ POSITION sx, sy;
+
+ /* Fractions */
+ POSITION qx, qy;
+
+ /* Scanners */
+ POSITION tx, ty;
+
+ /* Scale factors */
+ POSITION f1, f2;
+
+ /* Slope, or 1/Slope, of LOS */
+ POSITION m;
+
+
+ /* Extract the offset */
+ dy = y2 - y1;
+ dx = x2 - x1;
+
+ /* Extract the absolute offset */
+ ay = ABS(dy);
+ ax = ABS(dx);
+
+
+ /* Handle adjacent (or identical) grids */
+ if ((ax < 2) && (ay < 2)) return TRUE;
+
+
+ /* Paranoia -- require "safe" origin */
+ /* if (!in_bounds(y1, x1)) return FALSE; */
+ /* if (!in_bounds(y2, x2)) return FALSE; */
+
+
+ /* Directly South/North */
+ if (!dx)
+ {
+ /* South -- check for walls */
+ if (dy > 0)
+ {
+ for (ty = y1 + 1; ty < y2; ty++)
+ {
+ if (!cave_los_bold(ty, x1)) return FALSE;
+ }
+ }
+
+ /* North -- check for walls */
+ else
+ {
+ for (ty = y1 - 1; ty > y2; ty--)
+ {
+ if (!cave_los_bold(ty, x1)) return FALSE;
+ }
+ }
+
+ /* Assume los */
+ return TRUE;
+ }
+
+ /* Directly East/West */
+ if (!dy)
+ {
+ /* East -- check for walls */
+ if (dx > 0)
+ {
+ for (tx = x1 + 1; tx < x2; tx++)
+ {
+ if (!cave_los_bold(y1, tx)) return FALSE;
+ }
+ }
+
+ /* West -- check for walls */
+ else
+ {
+ for (tx = x1 - 1; tx > x2; tx--)
+ {
+ if (!cave_los_bold(y1, tx)) return FALSE;
+ }
+ }
+
+ /* Assume los */
+ return TRUE;
+ }
+
+
+ /* Extract some signs */
+ sx = (dx < 0) ? -1 : 1;
+ sy = (dy < 0) ? -1 : 1;
+
+
+ /* Vertical "knights" */
+ if (ax == 1)
+ {
+ if (ay == 2)
+ {
+ if (cave_los_bold(y1 + sy, x1)) return TRUE;
+ }
+ }
+
+ /* Horizontal "knights" */
+ else if (ay == 1)
+ {
+ if (ax == 2)
+ {
+ if (cave_los_bold(y1, x1 + sx)) return TRUE;
+ }
+ }
+
+
+ /* Calculate scale factor div 2 */
+ f2 = (ax * ay);
+
+ /* Calculate scale factor */
+ f1 = f2 << 1;
+
+
+ /* Travel horizontally */
+ if (ax >= ay)
+ {
+ /* Let m = dy / dx * 2 * (dy * dx) = 2 * dy * dy */
+ qy = ay * ay;
+ m = qy << 1;
+
+ tx = x1 + sx;
+
+ /* Consider the special case where slope == 1. */
+ if (qy == f2)
+ {
+ ty = y1 + sy;
+ qy -= f1;
+ }
+ else
+ {
+ ty = y1;
+ }
+
+ /* Note (below) the case (qy == f2), where */
+ /* the LOS exactly meets the corner of a tile. */
+ while (x2 - tx)
+ {
+ if (!cave_los_bold(ty, tx)) return FALSE;
+
+ qy += m;
+
+ if (qy < f2)
+ {
+ tx += sx;
+ }
+ else if (qy > f2)
+ {
+ ty += sy;
+ if (!cave_los_bold(ty, tx)) return FALSE;
+ qy -= f1;
+ tx += sx;
+ }
+ else
+ {
+ ty += sy;
+ qy -= f1;
+ tx += sx;
+ }
+ }
+ }
+
+ /* Travel vertically */
+ else
+ {
+ /* Let m = dx / dy * 2 * (dx * dy) = 2 * dx * dx */
+ qx = ax * ax;
+ m = qx << 1;
+
+ ty = y1 + sy;
+
+ if (qx == f2)
+ {
+ tx = x1 + sx;
+ qx -= f1;
+ }
+ else
+ {
+ tx = x1;
+ }
+
+ /* Note (below) the case (qx == f2), where */
+ /* the LOS exactly meets the corner of a tile. */
+ while (y2 - ty)
+ {
+ if (!cave_los_bold(ty, tx)) return FALSE;
+
+ qx += m;
+
+ if (qx < f2)
+ {
+ ty += sy;
+ }
+ else if (qx > f2)
+ {
+ tx += sx;
+ if (!cave_los_bold(ty, tx)) return FALSE;
+ qx -= f1;
+ ty += sy;
+ }
+ else
+ {
+ tx += sx;
+ qx -= f1;
+ ty += sy;
+ }
+ }
+ }
+
+ /* Assume los */
+ return TRUE;
+}
+
+/*
+ * Determine if a bolt spell cast from (y1,x1) to (y2,x2) will arrive
+ * at the final destination, assuming no monster gets in the way.
+ *
+ * This is slightly (but significantly) different from "los(y1,x1,y2,x2)".
+ */
+bool projectable(POSITION y1, POSITION x1, POSITION y2, POSITION x2)
+{
+ POSITION y, x;
+
+ int grid_n = 0;
+ u16b grid_g[512];
+
+ /* Check the projection path */
+ grid_n = project_path(grid_g, (project_length ? project_length : MAX_RANGE), y1, x1, y2, x2, 0);
+
+ /* Identical grid */
+ if (!grid_n) return TRUE;
+
+ /* Final grid */
+ y = GRID_Y(grid_g[grid_n - 1]);
+ x = GRID_X(grid_g[grid_n - 1]);
+
+ /* May not end in an unrequested grid */
+ if ((y != y2) || (x != x2)) return (FALSE);
+
+ /* Assume okay */
+ return (TRUE);
+}
+
+
+
+/*
+ * Standard "find me a location" function
+ *
+ * Obtains a legal location within the given distance of the initial
+ * location, and with "los()" from the source to destination location.
+ *
+ * This function is often called from inside a loop which searches for
+ * locations while increasing the "d" distance.
+ *
+ * Currently the "m" parameter is unused.
+ */
+void scatter(POSITION *yp, POSITION *xp, POSITION y, POSITION x, POSITION d, BIT_FLAGS mode)
+{
+ POSITION nx, ny;
+
+ /* Pick a location */
+ while (TRUE)
+ {
+ /* Pick a new location */
+ ny = rand_spread(y, d);
+ nx = rand_spread(x, d);
+
+ /* Ignore annoying locations */
+ if (!in_bounds(ny, nx)) continue;
+
+ /* Ignore "excessively distant" locations */
+ if ((d > 1) && (distance(y, x, ny, nx) > d)) continue;
+
+ if (mode & PROJECT_LOS)
+ {
+ if (los(y, x, ny, nx)) break;
+ }
+ else
+ {
+ if (projectable(y, x, ny, nx)) break;
+ }
+
+ }
+
+ /* Save the location */
+ (*yp) = ny;
+ (*xp) = nx;
+}
+
+/*
+ * Calculate "incremental motion". Used by project() and shoot().
+ * Assumes that (*y,*x) lies on the path from (y1,x1) to (y2,x2).
+ */
+void mmove2(POSITION *y, POSITION *x, POSITION y1, POSITION x1, POSITION y2, POSITION x2)
+{
+ POSITION dy, dx, dist, shift;
+
+ /* Extract the distance travelled */
+ dy = (*y < y1) ? y1 - *y : *y - y1;
+ dx = (*x < x1) ? x1 - *x : *x - x1;
+
+ /* Number of steps */
+ dist = (dy > dx) ? dy : dx;
+
+ /* We are calculating the next location */
+ dist++;
+
+
+ /* Calculate the total distance along each axis */
+ dy = (y2 < y1) ? (y1 - y2) : (y2 - y1);
+ dx = (x2 < x1) ? (x1 - x2) : (x2 - x1);
+
+ /* Paranoia -- Hack -- no motion */
+ if (!dy && !dx) return;
+
+
+ /* Move mostly vertically */
+ if (dy > dx)
+ {
+ /* Extract a shift factor */
+ shift = (dist * dx + (dy - 1) / 2) / dy;
+
+ /* Sometimes move along the minor axis */
+ (*x) = (x2 < x1) ? (x1 - shift) : (x1 + shift);
+
+ /* Always move along major axis */
+ (*y) = (y2 < y1) ? (y1 - dist) : (y1 + dist);
+ }
+
+ /* Move mostly horizontally */
+ else
+ {
+ /* Extract a shift factor */
+ shift = (dist * dy + (dx - 1) / 2) / dx;
+
+ /* Sometimes move along the minor axis */
+ (*y) = (y2 < y1) ? (y1 - shift) : (y1 + shift);
+
+ /* Always move along major axis */
+ (*x) = (x2 < x1) ? (x1 - dist) : (x1 + dist);
+ }
+}
+