/*
* File: los.cc
* Summary: Line-of-sight algorithm.
*
*
*
* == Definition of visibility ==
*
* Two cells are in view of each other if there is any straight
* line that meets both cells and that doesn't meet any opaque
* cell in between, and if the cells are in LOS range of each
* other.
*
* Here, to "meet" a cell means to intersect the interiour. In
* particular, rays can pass between to diagonally adjacent
* walls (as can the player).
*
* == Terminology ==
*
* A _ray_ is a line, specified by starting point (accx, accy)
* and slope. A ray determines its _footprint_: the sequence of
* cells whose interiour it meets.
*
* Any prefix of the footprint of a ray is called a _cellray_.
*
* For the purposes of LOS calculation, only the footprints
* are relevant, but rays are also used for shooting beams,
* which may travel beyond LOS and which can be reflected.
* See ray.cc.
*
* == Overview ==
*
* At first use, the LOS code makes some precomputations,
* filling a list of all relevant rays in one quadrant,
* and filling data structures that allow calculating LOS
* in a quadrant without checking each ray.
*
* The code provides functions for filling LOS information
* around a given center efficiently, and for querying rays
* between two given cells.
*/
#include "AppHdr.h"
#include "los.h"
#include <cmath>
#include <algorithm>
#include "bitary.h"
#include "coord.h"
#include "coord-circle.h"
#include "coordit.h"
#include "debug.h"
#include "externs.h"
#include "geom2d.h"
#include "losparam.h"
#include "player.h"
#include "ray.h"
#include "stuff.h"
#include "env.h"
#include "terrain.h"
// This determines which cells are considered out of range during
// precalculations (only positive quadrant used).
// For the LOS code to work correctly, any LOS shape that
// is used needs to be contained in bds_precalc.
const circle_def bds_precalc = circle_def(LOS_MAX_RANGE, C_ROUND);
// These determine what rays are cast in the precomputation,
// and affect start-up time significantly.
// XXX: Argue that these values are sufficient.
#define LOS_MAX_ANGLE (2*LOS_MAX_RANGE-2)
#define LOS_INTERCEPT_MULT (2)
// These store all unique (in terms of footprint) full rays.
// The footprint of ray=fullray[i] consists of ray.length cells,
// stored in ray_coords[ray.start..ray.length-1].
// These are filled during precomputation (_register_ray).
// XXX: fullrays is not needed anymore after precomputation.
struct los_ray;
std::vector<los_ray> fullrays;
std::vector<coord_def> ray_coords;
// These store all unique minimal cellrays. For each i,
// cellray i ends in cellray_ends[i] and passes through
// thoses cells p that have blockrays(p)[i] set. In other
// words, blockrays(p)[i] is set iff an opaque cell p blocks
// the cellray with index i.
std::vector<coord_def> cellray_ends;
typedef FixedArray<bit_array*, LOS_MAX_RANGE+1, LOS_MAX_RANGE+1> blockrays_t;
blockrays_t blockrays;
// We also store the minimal cellrays by target position
// for efficient retrieval by find_ray.
// XXX: Consider condensing this representation.
struct cellray;
FixedArray<std::vector<cellray>, LOS_MAX_RANGE+1, LOS_MAX_RANGE+1> min_cellrays;
// Temporary arrays used in losight() to track which rays
// are blocked or have seen a smoke cloud.
// Allocated when doing the precomputations.
bit_array *dead_rays = NULL;
bit_array *smoke_rays = NULL;
class quadrant_iterator : public rectangle_iterator
{
public:
quadrant_iterator()
: rectangle_iterator(coord_def(0,0),
coord_def(LOS_MAX_RANGE, LOS_MAX_RANGE))
{
}
};
void clear_rays_on_exit()
{
delete dead_rays;
delete smoke_rays;
for (quadrant_iterator qi; qi; qi++)
delete blockrays(*qi);
}
// Pre-squared LOS radius.
int _los_radius_sq = LOS_RADIUS_SQ;
void set_los_radius(int r)
{
ASSERT(r <= LOS_MAX_RADIUS);
_los_radius_sq = r * r + 1;
}
// XXX: just for monster_los
int get_los_radius_sq()
{
return _los_radius_sq;
}
bool double_is_zero(const double x)
{
return (x > -EPSILON_VALUE) && (x < EPSILON_VALUE);
}
struct los_ray : public ray_def
{
// The footprint of this ray is stored in
// ray_coords[start..start+length-1].
unsigned int start;
unsigned int length;
los_ray(geom::ray _r)
: ray_def(_r), start(0), length(0)
{
}
// Shoot a ray from the given start point (accx, accy) with the given
// slope, bounded by the pre-calc bounds shape.
// Returns the cells it travels through, excluding the origin.
// Returns an empty vector if this was a bad ray.
std::vector<coord_def> footprint()
{
std::vector<coord_def> cs;
los_ray copy = *this;
coord_def c;
coord_def old;
int cellnum;
for (cellnum = 0; true; ++cellnum)
{
old = c;
if (!copy.advance())
{
//#ifdef DEBUG_DIAGNOSTICS
// mprf(MSGCH_DIAGNOSTICS,
// "discarding corner ray (%f,%f) + t*(%f,%f)",
// r.start.x, r.start.y, r.dir.x, r.dir.y);
//#endif
cs.clear();
break;
}
c = copy.pos();
if (!bds_precalc.contains(c))
break;
cs.push_back(c);
ASSERT((c - old).rdist() == 1);
}
return cs;
}
coord_def operator[](unsigned int i)
{
ASSERT(0 <= i && i < length);
return ray_coords[start+i];
}
};
// Check if the passed rays have identical footprint.
static bool _is_same_ray(los_ray ray, std::vector<coord_def> newray)
{
if (ray.length != newray.size())
return false;
for (unsigned int i = 0; i < ray.length; i++)
if (ray[i] != newray[i])
return false;
return true;
}
// Check if the passed ray has already been created.
static bool _is_duplicate_ray(std::vector<coord_def> newray)
{
for (unsigned int i = 0; i < fullrays.size(); ++i)
if (_is_same_ray(fullrays[i], newray))
return true;
return false;
}
// A cellray given by fullray and index of end-point.
struct cellray
{
// A cellray passes through cells ray_coords[ray.start..ray.start+end].
los_ray ray;
unsigned int end; // Relative index (inside ray) of end cell.
cellray(const los_ray& r, unsigned int e)
: ray(r), end(e), imbalance(-1), first_diag(false)
{
}
// The end-point's index inside ray_coord.
int index() const { return (ray.start + end); }
// The end-point.
coord_def target() const { return ray_coords[index()]; }
// XXX: Currently ray/cellray[0] is the first point outside the origin.
coord_def operator[](unsigned int i)
{
ASSERT(0 <= i && i <= end);
return ray_coords[ray.start+i];
}
// Parameters used in find_ray. These need to be calculated
// only for the minimal cellrays.
int imbalance;
bool first_diag;
void calc_params();
};
// Compare two cellrays to the same target.
// This determines which ray is considered better by find_ray,
// used with list::sort.
// Returns true if a is strictly better than b, false else.
bool _is_better(const cellray& a, const cellray& b)
{
// Only compare cellrays with equal target.
ASSERT(a.target() == b.target());
// calc_params() has been called.
ASSERT(a.imbalance >= 0 && b.imbalance >= 0);
if (a.imbalance < b.imbalance)
return (true);
else if (a.imbalance > b.imbalance)
return (false);
else
return (a.first_diag);
}
enum compare_type
{
C_SUBRAY,
C_SUPERRAY,
C_NEITHER
};
// Check whether one of the passed cellrays is a subray of the
// other in terms of footprint.
compare_type _compare_cellrays(const cellray& a, const cellray& b)
{
if (a.target() != b.target())
return C_NEITHER;
int cura = a.ray.start;
int curb = b.ray.start;
int enda = cura + a.end;
int endb = curb + b.end;
bool maybe_sub = true;
bool maybe_super = true;
while (cura < enda && curb < endb && (maybe_sub || maybe_super))
{
coord_def pa = ray_coords[cura];
coord_def pb = ray_coords[curb];
if (pa.x > pb.x || pa.y > pb.y)
{
maybe_super = false;
curb++;
}
if (pa.x < pb.x || pa.y < pb.y)
{
maybe_sub = false;
cura++;
}
if (pa == pb)
{
cura++;
curb++;
}
}
maybe_sub = maybe_sub && (cura == enda);
maybe_super = maybe_super && (curb == endb);
if (maybe_sub)
return C_SUBRAY; // includes equality
else if (maybe_super)
return C_SUPERRAY;
else
return C_NEITHER;
}
// Determine all minimal cellrays.
// They're stored globally by target in min_cellrays,
// and returned as a list of indices into ray_coords.
static std::vector<int> _find_minimal_cellrays()
{
FixedArray<std::list<cellray>, LOS_MAX_RANGE+1, LOS_MAX_RANGE+1> minima;
std::list<cellray>::iterator min_it;
for (unsigned int r = 0; r < fullrays.size(); ++r)
{
los_ray ray = fullrays[r];
for (unsigned int i = 0; i < ray.length; ++i)
{
// Is the cellray ray[0..i] duplicated so far?
bool dup = false;
cellray c(ray, i);
std::list<cellray>& min = minima(c.target());
bool erased = false;
for (min_it = min.begin();
min_it != min.end() && !dup; )
{
switch(_compare_cellrays(*min_it, c))
{
case C_SUBRAY:
dup = true;
break;
case C_SUPERRAY:
min_it = min.erase(min_it);
erased = true;
// clear this should be added, but might have
// to erase more
break;
case C_NEITHER:
default:
break;
}
if (!erased)
min_it++;
else
erased = false;
}
if (!dup)
min.push_back(c);
}
}
std::vector<int> result;
for (quadrant_iterator qi; qi; qi++)
{
std::list<cellray>& min = minima(*qi);
for (min_it = min.begin(); min_it != min.end(); min_it++)
{
// Calculate imbalance and slope difference for sorting.
min_it->calc_params();
result.push_back(min_it->index());
}
min.sort(_is_better);
min_cellrays(*qi) = std::vector<cellray>(min.begin(), min.end());
}
return result;
}
// Create and register the ray defined by the arguments.
static void _register_ray(geom::ray r)
{
los_ray ray = los_ray(r);
std::vector<coord_def> coords = ray.footprint();
if (coords.empty() || _is_duplicate_ray(coords))
return;
ray.start = ray_coords.size();
ray.length = coords.size();
for (unsigned int i = 0; i < coords.size(); i++)
ray_coords.push_back(coords[i]);
fullrays.push_back(ray);
}
static void _create_blockrays()
{
// First, we calculate blocking information for all cell rays.
// Cellrays are numbered according to the index of their end
// cell in ray_coords.
const int n_cellrays = ray_coords.size();
blockrays_t all_blockrays;
for (quadrant_iterator qi; qi; qi++)
all_blockrays(*qi) = new bit_array(n_cellrays);
for (unsigned int r = 0; r < fullrays.size(); ++r)
{
los_ray ray = fullrays[r];
for (unsigned int i = 0; i < ray.length; ++i)
{
// Every cell is contained in (thus blocks)
// all following cellrays.
for (unsigned int j = i + 1; j < ray.length; ++j)
all_blockrays(ray[i])->set(ray.start + j);
}
}
// We've built the basic blockray array; now compress it, keeping
// only the nonduplicated cellrays.
// Determine minimal cellrays and store their indices in ray_coords.
std::vector<int> min_indices = _find_minimal_cellrays();
const int n_min_rays = min_indices.size();
cellray_ends.resize(n_min_rays);
for (int i = 0; i < n_min_rays; ++i)
cellray_ends[i] = ray_coords[min_indices[i]];
// Compress blockrays accordingly.
for (quadrant_iterator qi; qi; qi++)
{
blockrays(*qi) = new bit_array(n_min_rays);
for (int i = 0; i < n_min_rays; ++i)
blockrays(*qi)->set(i, all_blockrays(*qi)
->get(min_indices[i]));
}
// We can throw away all_blockrays now.
for (quadrant_iterator qi; qi; qi++)
delete all_blockrays(*qi);
dead_rays = new bit_array(n_min_rays);
smoke_rays = new bit_array(n_min_rays);
#ifdef DEBUG_DIAGNOSTICS
mprf( MSGCH_DIAGNOSTICS, "Cellrays: %d Fullrays: %u Minimal cellrays: %u",
n_cellrays, fullrays.size(), n_min_rays );
#endif
}
static int _gcd( int x, int y )
{
int tmp;
while (y != 0)
{
x %= y;
tmp = x;
x = y;
y = tmp;
}
return x;
}
bool complexity_lt( const std::pair<int,int>& lhs,
const std::pair<int,int>& rhs )
{
return lhs.first * lhs.second < rhs.first * rhs.second;
}
// Cast all rays
void raycast()
{
static bool done_raycast = false;
if (done_raycast)
return;
// Creating all rays for first quadrant
// We have a considerable amount of overkill.
done_raycast = true;
// register perpendiculars FIRST, to make them top choice
// when selecting beams
_register_ray(geom::ray(0.5, 0.5, 0.0, 1.0));
_register_ray(geom::ray(0.5, 0.5, 1.0, 0.0));
// For a slope of M = y/x, every x we move on the X axis means
// that we move y on the y axis. We want to look at the resolution
// of x/y: in that case, every step on the X axis means an increase
// of 1 in the Y axis at the intercept point. We can assume gcd(x,y)=1,
// so we look at steps of 1/y.
// Changing the order a bit. We want to order by the complexity
// of the beam, which is log(x) + log(y) ~ xy.
std::vector<std::pair<int,int> > xyangles;
for (int xangle = 1; xangle <= LOS_MAX_ANGLE; ++xangle)
for (int yangle = 1; yangle <= LOS_MAX_ANGLE; ++yangle)
{
if (_gcd(xangle, yangle) == 1)
xyangles.push_back(std::pair<int,int>(xangle, yangle));
}
std::sort(xyangles.begin(), xyangles.end(), complexity_lt);
for (unsigned int i = 0; i < xyangles.size(); ++i)
{
const int xangle = xyangles[i].first;
const int yangle = xyangles[i].second;
for (int intercept = 1; intercept < LOS_INTERCEPT_MULT*yangle; ++intercept )
{
double xstart = ((double)intercept) / (LOS_INTERCEPT_MULT*yangle);
double ystart = 0.5;
_register_ray(geom::ray(xstart, ystart, xangle, yangle));
// also draw the identical ray in octant 2
_register_ray(geom::ray(ystart, xstart, yangle, xangle));
}
}
// Now create the appropriate blockrays array
_create_blockrays();
}
static int _imbalance(ray_def ray, const coord_def& target)
{
int imb = 0;
int diags = 0, straights = 0;
while (ray.pos() != target)
{
coord_def old = ray.pos();
if (!ray.advance())
ASSERT(false);
switch((ray.pos() - old).abs())
{
case 1:
diags = 0;
if (++straights > imb)
imb = straights;
break;
case 2:
straights = 0;
if (++diags > imb)
imb = diags;
break;
default:
ASSERT(false);
break;
}
}
return imb;
}
void cellray::calc_params()
{
coord_def trg = target();
imbalance = _imbalance(ray, trg);
first_diag = ((*this)[0].abs() == 2);
}
// Find ray in positive quadrant.
// opc has been translated for this quadrant.
// XXX: Allow finding ray of minimum opacity.
bool _find_ray_se(const coord_def& target, ray_def& ray,
const opacity_func& opc, const circle_def& bds,
bool cycle)
{
ASSERT(target.x >= 0 && target.y >= 0 && !target.origin());
if (!bds.contains(target))
return false;
ASSERT(bds_precalc.contains(target));
// Ensure the precalculations have been done.
raycast();
const std::vector<cellray> &min = min_cellrays(target);
ASSERT(min.size() > 0);
cellray c = min[0]; // XXX: const cellray &c ?
unsigned int index = 0;
#ifdef DEBUG_DIAGNOSTICS
if (cycle)
mprf(MSGCH_DIAGNOSTICS, "cycling from %d (total %d)",
ray.cycle_idx, min.size());
#endif
unsigned int start = cycle ? ray.cycle_idx + 1 : 0;
ASSERT(0 <= start && start <= min.size());
int blocked = OPC_OPAQUE;
for (unsigned int i = start;
(blocked >= OPC_OPAQUE) && (i < start + min.size()); i++)
{
index = i % min.size();
c = min[index];
blocked = OPC_CLEAR;
// Check all inner points.
for (unsigned int j = 0; j < c.end && blocked < OPC_OPAQUE; j++)
blocked += opc(c[j]);
}
if (blocked >= OPC_OPAQUE)
return (false);
ray = c.ray;
ray.cycle_idx = index;
return (true);
}
// Coordinate transformation so we can find_ray quadrant-by-quadrant.
struct opacity_trans : opacity_func
{
const coord_def& source;
int signx, signy;
const opacity_func& orig;
opacity_trans(const opacity_func& opc, const coord_def& s, int sx, int sy)
: source(s), signx(sx), signy(sy), orig(opc)
{
}
CLONE(opacity_trans)
opacity_type operator()(const coord_def &l) const
{
return orig(transform(l));
}
coord_def transform(const coord_def &l) const
{
return coord_def(source.x + signx*l.x, source.y + signy*l.y);
}
};
// Find a nonblocked ray from source to target. Return false if no
// such ray could be found, otherwise return true and fill ray
// appropriately.
// if range is too great or all rays are blocked.
// If cycle is false, find the first fitting ray. If it is true,
// assume that ray is appropriately filled in, and look for the next
// ray. We only ever use ray.cycle_idx.
bool find_ray(const coord_def& source, const coord_def& target,
ray_def& ray, const opacity_func& opc, const circle_def &bds,
bool cycle)
{
if (target == source || !map_bounds(source) || !map_bounds(target))
return false;
const int signx = ((target.x - source.x >= 0) ? 1 : -1);
const int signy = ((target.y - source.y >= 0) ? 1 : -1);
const int absx = signx * (target.x - source.x);
const int absy = signy * (target.y - source.y);
const coord_def abs = coord_def(absx, absy);
opacity_trans opc_trans = opacity_trans(opc, source, signx, signy);
if (!_find_ray_se(abs, ray, opc_trans, bds, cycle))
return (false);
if (signx < 0)
ray.r.start.x = 1.0 - ray.r.start.x;
if (signy < 0)
ray.r.start.y = 1.0 - ray.r.start.y;
ray.r.dir.x *= signx;
ray.r.dir.y *= signy;
ray.r.start.x += source.x;
ray.r.start.y += source.y;
return (true);
}
bool exists_ray(const coord_def& source, const coord_def& target,
const opacity_func& opc, const circle_def &bds)
{
ray_def ray;
return (find_ray(source, target, ray, opc, bds));
}
// Assuming that target is in view of source, but line of
// fire is blocked, what is it blocked by?
dungeon_feature_type ray_blocker(const coord_def& source,
const coord_def& target)
{
ray_def ray;
if (!find_ray(source, target, ray, opc_default))
{
ASSERT (false);
return (NUM_FEATURES);
}
ray.advance();
int blocked = 0;
while (ray.pos() != target)
{
blocked += opc_solid(ray.pos());
if (blocked >= OPC_OPAQUE)
return (env.grid(ray.pos()));
ray.advance();
}
ASSERT (false);
return (NUM_FEATURES);
}
// Returns a straight ray from source to target.
void fallback_ray(const coord_def& source, const coord_def& target,
ray_def& ray)
{
ray.r.start.x = source.x + 0.5;
ray.r.start.y = source.y + 0.5;
coord_def diff = target - source;
ray.r.dir.x = diff.x;
ray.r.dir.y = diff.y;
ray.on_corner = false;
}
// Count the number of matching features between two points along
// a beam-like path; the path will pass through solid features.
// By default, it excludes end points from the count.
// If just_check is true, the function will return early once one
// such feature is encountered.
int num_feats_between(const coord_def& source, const coord_def& target,
dungeon_feature_type min_feat,
dungeon_feature_type max_feat,
bool exclude_endpoints, bool just_check)
{
ray_def ray;
int count = 0;
int max_dist = grid_distance(source, target);
ASSERT(map_bounds(source) && map_bounds(target));
if (source == target)
return (0); // XXX: might want to count the cell.
// We don't need to find the shortest beam, any beam will suffice.
fallback_ray(source, target, ray);
if (exclude_endpoints && ray.pos() == source)
{
ray.advance();
max_dist--;
}
int dist = 0;
bool reached_target = false;
while (dist++ <= max_dist)
{
const dungeon_feature_type feat = grd(ray.pos());
if (ray.pos() == target)
reached_target = true;
if (feat >= min_feat && feat <= max_feat
&& (!exclude_endpoints || !reached_target))
{
count++;
if (just_check) // Only needs to be > 0.
return (count);
}
if (reached_target)
break;
ray.advance();
}
return (count);
}
// Is p2 visible from p1, disregarding half-opaque objects?
bool cell_see_cell(const coord_def& p1, const coord_def& p2)
{
return exists_ray(p1, p2, opc_fullyopaque);
}
// We use raycasting. The algorithm:
// PRECOMPUTATION:
// Create a large bundle of rays and cast them.
// Mark, for each one, which cells kill it (and where.)
// Also, for each one, note which cells it passes.
// ACTUAL LOS:
// Unite the ray-killers for the given map; this tells you which rays
// are dead.
// Look up which cells the surviving rays have, and that's your LOS!
// OPTIMIZATIONS:
// WLOG, we can assume that we're in a specific quadrant - say the
// first quadrant - and just mirror everything after that. We can
// likely get away with a single octant, but we don't do that. (To
// do...)
// Rays are actually split by each cell they pass. So each "ray" only
// identifies a single cell, and we can do logical ORs. Once a cell
// kills a cellray, it will kill all remaining cellrays of that ray.
// Also, rays are checked to see if they are duplicates of each
// other. If they are, they're eliminated.
// Some cellrays can also be eliminated. In general, a cellray is
// unnecessary if there is another cellray with the same coordinates,
// and whose path (up to those coordinates) is a subset, not necessarily
// proper, of the original path. We still store the original cellrays
// fully for beam detection and such.
// PERFORMANCE:
// With reasonable values we have around 6000 cellrays, meaning
// around 600Kb (75 KB) of data. This gets cut down to 700 cellrays
// after removing duplicates. That means that we need to do
// around 22*100*4 ~ 9,000 memory reads + writes per LOS call on a
// 32-bit system. Not too bad.
// IMPROVEMENTS:
// Smoke will now only block LOS after two cells of smoke. This is
// done by updating with a second array.
void _losight_quadrant(los_grid& sh, const los_param& dat, int sx, int sy)
{
const unsigned int num_cellrays = cellray_ends.size();
dead_rays->reset();
smoke_rays->reset();
for (quadrant_iterator qi; qi; qi++)
{
coord_def p = coord_def(sx*(qi->x), sy*(qi->y));
if (!dat.los_bounds(p))
continue;
switch (dat.opacity(p))
{
case OPC_OPAQUE:
// Block the appropriate rays.
*dead_rays |= *blockrays(*qi);
break;
case OPC_HALF:
// Block rays which have already seen a cloud.
*dead_rays |= (*smoke_rays & *blockrays(*qi));
*smoke_rays |= *blockrays(*qi);
break;
default:
break;
}
}
// Ray calculation done. Now work out which cells in this
// quadrant are visible.
for (unsigned int rayidx = 0; rayidx < num_cellrays; ++rayidx)
{
// make the cells seen by this ray at this point visible
if (!dead_rays->get(rayidx))
{
// This ray is alive, thus the end cell is visible.
const coord_def p = coord_def(sx * cellray_ends[rayidx].x,
sy * cellray_ends[rayidx].y);
if (dat.los_bounds(p))
sh(p) = true;
}
}
}
void losight(los_grid& sh, const los_param& dat)
{
sh.init(false);
// Do precomputations if necessary.
raycast();
const int quadrant_x[4] = { 1, -1, -1, 1 };
const int quadrant_y[4] = { 1, 1, -1, -1 };
for (int q = 0; q < 4; ++q)
_losight_quadrant(sh, dat, quadrant_x[q], quadrant_y[q]);
// Center is always visible.
const coord_def o = coord_def(0,0);
sh(o) = true;
}
struct los_param_funcs : public los_param
{
coord_def center;
const opacity_func& opc;
const circle_def& bounds;
los_param_funcs(const coord_def& c,
const opacity_func& o, const circle_def& b)
: center(c), opc(o), bounds(b)
{
}
bool los_bounds(const coord_def& p) const
{
return (map_bounds(p + center) && bounds.contains(p));
}
opacity_type opacity(const coord_def& p) const
{
return (opc(p + center));
}
};
void losight(los_grid& sh, const coord_def& center,
const opacity_func& opc, const circle_def& bounds)
{
losight(sh, los_param_funcs(center, opc, bounds));
}