/*
 * A simple, fast, integer-based line-of-sight algorithm.  By Joseph Hall,
 * 4116 Brewster Drive, Raleigh NC 27606.  Email to jnh@ecemwl.ncsu.edu.
 *
 * Returns TRUE if a line of sight can be traced from (x1,y1) to (x2,y2).
 *
 * The LOS begins at the center of the tile (x1,y1) and ends at the center of
 * the tile (x2,y2).  If los() is to return TRUE, all of the tiles this line
 * passes through must be floor tiles, except for (x1,y1) and (x2,y2).
 *
 * We assume that the "mathematical corner" of a non-floor tile does not
 * block line of sight.
 *
 * Because this function uses (short) ints for all calculations, overflow may
 * occur if dx and dy exceed 90.
 *
 * Once all the degenerate cases are eliminated, the values "qx", "qy", and
 * "m" are multiplied by a scale factor "f1 = abs(dx * dy * 2)", so that
 * we can use integer arithmetic.
 *
 * We travel from start to finish along the longer axis, starting at the border
 * between the first and second tiles, where the y offset = .5 * slope, taking
 * into account the scale factor.  See below.
 *
 * Also note that this function and the "move towards target" code do NOT
 * share the same properties.  Thus, you can see someone, target them, and
 * then fire a bolt at them, but the bolt may hit a wall, not them.  However,
 * by clever choice of target locations, you can sometimes throw a "curve".
 *
 * Note that "line of sight" is not "reflexive" in all cases.
 *
 * Use the "projectable()" routine to test "spell/missile line of sight".
 *
 * Use the "update_view()" function to determine player line-of-sight.
 */
bool los(int y1, int x1, int y2, int x2)
{
/* Delta */
int dx, dy;

/* Absolute */
int ax, ay;

/* Signs */
int sx, sy;

/* Fractions */
int qx, qy;

/* Scanners */
int tx, ty;

/* Scale factors */
int f1, f2;

/* Slope, or 1/Slope, of LOS */
int 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); */


/* Directly South/North */
if (!dx)
{
/* South -- check for walls */
if (dy > 0)
{
for (ty = y1 + 1; ty < y2; ty++)
{
if (!cave_sight_bold(ty, x1)) return (FALSE);
}
}

/* North -- check for walls */
else
{
for (ty = y1 - 1; ty > y2; ty--)
{
if (!cave_sight_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_sight_bold(y1, tx)) return (FALSE);
}
}

/* West -- check for walls */
else
{
for (tx = x1 - 1; tx > x2; tx--)
{
if (!cave_sight_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_sight_bold(y1 + sy, x1)) return (TRUE);
}
}

/* Horizontal "knights" */
else if (ay == 1)
{
if (ax == 2)
{
if (cave_sight_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_sight_bold(ty, tx)) return (FALSE);

qy += m;

if (qy < f2)
{
tx += sx;
}
else if (qy > f2)
{
ty += sy;
if (!cave_sight_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_sight_bold(ty, tx)) return (FALSE);

qx += m;

if (qx < f2)
{
ty += sy;
}
else if (qx > f2)
{
tx += sx;
if (!cave_sight_bold(ty, tx)) return (FALSE);
qx -= f1;
ty += sy;
}
else
{
tx += sx;
qx -= f1;
ty += sy;
}
}
}

/* Assume los */
return (TRUE);
}