20 de Enero de 2021, 05:21:57 pm
 Bienvenido(a), Visitante. Por favor, ingresa o regístrate. 1 Hora 1 Día 1 Semana 1 Mes Siempre Ingresar con nombre de usuario, contraseña y duración de la sesión
 Noticias:
 Inicio Ayuda Buscar Ingresar Registrarse
 Páginas: [1]
 Autor Tema: A simple, fast, integer-based line-of-sight algorithm. By Joseph Hall  (Leído 19003 veces) 0 Usuarios y 1 Visitante están viendo este tema.
ARTRAG
Visitante
 « : 22 de Mayo de 2008, 01:50:53 pm »

Código:
/*
* 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);
}

 En línea
 Páginas: [1]
Ir a: