diff options
42 files changed, 1825 insertions, 1701 deletions
diff --git a/crawl-ref/source/abyss.cc b/crawl-ref/source/abyss.cc index 31103b1369..9effca870f 100644 --- a/crawl-ref/source/abyss.cc +++ b/crawl-ref/source/abyss.cc @@ -27,6 +27,7 @@ REVISION("$Rev$"); #include "dungeon.h" #include "items.h" #include "lev-pand.h" +#include "los.h" #include "religion.h" #include "stuff.h" #include "spells3.h" diff --git a/crawl-ref/source/acr.cc b/crawl-ref/source/acr.cc index 5eba12bae5..4eb680190f 100644 --- a/crawl-ref/source/acr.cc +++ b/crawl-ref/source/acr.cc @@ -73,6 +73,7 @@ REVISION("$Rev$"); #include "itemprop.h" #include "items.h" #include "lev-pand.h" +#include "los.h" #include "luadgn.h" #include "macro.h" #include "makeitem.h" diff --git a/crawl-ref/source/beam.cc b/crawl-ref/source/beam.cc index 195e40d20e..477dabc980 100644 --- a/crawl-ref/source/beam.cc +++ b/crawl-ref/source/beam.cc @@ -37,6 +37,7 @@ REVISION("$Rev$"); #include "items.h" #include "itemname.h" #include "itemprop.h" +#include "los.h" #include "message.h" #include "misc.h" #include "monplace.h" diff --git a/crawl-ref/source/decks.cc b/crawl-ref/source/decks.cc index 190cf60ad3..19378ab9b2 100644 --- a/crawl-ref/source/decks.cc +++ b/crawl-ref/source/decks.cc @@ -25,6 +25,7 @@ REVISION("$Rev$"); #include "item_use.h" #include "itemprop.h" #include "items.h" +#include "los.h" #include "maps.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/directn.cc b/crawl-ref/source/directn.cc index 6e5ce8f30b..1882388af6 100644 --- a/crawl-ref/source/directn.cc +++ b/crawl-ref/source/directn.cc @@ -33,6 +33,7 @@ REVISION("$Rev$"); #include "invent.h" #include "itemname.h" #include "items.h" +#include "los.h" #include "mapmark.h" #include "message.h" #include "menu.h" diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc index c6c4bb3a84..ee1571569b 100644 --- a/crawl-ref/source/dungeon.cc +++ b/crawl-ref/source/dungeon.cc @@ -31,6 +31,7 @@ REVISION("$Rev$"); #include "itemname.h" #include "itemprop.h" #include "items.h" +#include "los.h" #include "makeitem.h" #include "mapdef.h" #include "mapmark.h" diff --git a/crawl-ref/source/effects.cc b/crawl-ref/source/effects.cc index 1a87e9a86c..7385a352a9 100644 --- a/crawl-ref/source/effects.cc +++ b/crawl-ref/source/effects.cc @@ -35,6 +35,7 @@ REVISION("$Rev$"); #include "itemname.h" #include "itemprop.h" #include "items.h" +#include "los.h" #include "makeitem.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/fight.cc b/crawl-ref/source/fight.cc index 6a579ff73f..ef190433ea 100644 --- a/crawl-ref/source/fight.cc +++ b/crawl-ref/source/fight.cc @@ -35,6 +35,7 @@ REVISION("$Rev$"); #include "itemprop.h" #include "item_use.h" #include "kills.h" +#include "los.h" #include "macro.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/files.cc b/crawl-ref/source/files.cc index 172c5e3fc7..b6a87e8cd3 100644 --- a/crawl-ref/source/files.cc +++ b/crawl-ref/source/files.cc @@ -56,6 +56,7 @@ REVISION("$Rev$"); #include "items.h" #include "kills.h" #include "libutil.h" +#include "los.h" #include "mapmark.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/it_use3.cc b/crawl-ref/source/it_use3.cc index 38944398e5..e76cc41675 100644 --- a/crawl-ref/source/it_use3.cc +++ b/crawl-ref/source/it_use3.cc @@ -30,6 +30,7 @@ REVISION("$Rev$"); #include "it_use2.h" #include "itemname.h" #include "itemprop.h" +#include "los.h" #include "mapmark.h" #include "message.h" #include "monplace.h" diff --git a/crawl-ref/source/los.cc b/crawl-ref/source/los.cc new file mode 100644 index 0000000000..aec61afa23 --- /dev/null +++ b/crawl-ref/source/los.cc @@ -0,0 +1,908 @@ +/* + * File: los.cc + * Summary: Line-of-sight algorithm. + */ + +#include "AppHdr.h" +REVISION("$Rev$"); + +#include "los.h" + +#include <cmath> + +#include "cloud.h" +#include "debug.h" +#include "directn.h" +#include "externs.h" +#include "ray.h" +#include "state.h" +#include "stuff.h" +#include "terrain.h" + +// The LOS code now uses raycasting -- haranp + +#define LONGSIZE (sizeof(unsigned long)*8) +#define LOS_MAX_RANGE_X 9 +#define LOS_MAX_RANGE_Y 9 +#define LOS_MAX_RANGE 9 + +// the following two constants represent the 'middle' of the sh array. +// since the current shown area is 19x19, centering the view at (9,9) +// means it will be exactly centered. +// This is done to accomodate possible future changes in viewable screen +// area - simply change sh_xo and sh_yo to the new view center. + +const int sh_xo = 9; // X and Y origins for the sh array +const int sh_yo = 9; + +unsigned long* los_blockrays = NULL; +unsigned long* dead_rays = NULL; +unsigned long* smoke_rays = NULL; +std::vector<short> ray_coord_x; +std::vector<short> ray_coord_y; +std::vector<short> compressed_ray_x; +std::vector<short> compressed_ray_y; +std::vector<int> raylengths; +std::vector<ray_def> fullrays; + +void clear_rays_on_exit() +{ + delete[] dead_rays; + delete[] smoke_rays; + delete[] los_blockrays; +} + +int _los_radius_squared = LOS_RADIUS * LOS_RADIUS + 1; + +void setLOSRadius(int newLR) +{ + _los_radius_squared = newLR * newLR + 1*1; +} + +// XXX: just for monster_los +int get_los_radius_squared() +{ + return _los_radius_squared; +} + +bool _get_bit_in_long_array( const unsigned long* data, int where ) +{ + int wordloc = where / LONGSIZE; + int bitloc = where % LONGSIZE; + return ((data[wordloc] & (1UL << bitloc)) != 0); +} + +static void _set_bit_in_long_array( unsigned long* data, int where ) +{ + int wordloc = where / LONGSIZE; + int bitloc = where % LONGSIZE; + data[wordloc] |= (1UL << bitloc); +} + +bool double_is_zero( const double x ) +{ + return (x > -EPSILON_VALUE) && (x < EPSILON_VALUE); +} + +// Check if the passed ray has already been created. +static bool _is_duplicate_ray( int len, int xpos[], int ypos[] ) +{ + int cur_offset = 0; + for (unsigned int i = 0; i < raylengths.size(); ++i) + { + // Only compare equal-length rays. + if (raylengths[i] != len) + { + cur_offset += raylengths[i]; + continue; + } + + int j; + for (j = 0; j < len; ++j) + { + if (ray_coord_x[j + cur_offset] != xpos[j] + || ray_coord_y[j + cur_offset] != ypos[j]) + { + break; + } + } + + // Exact duplicate? + if (j == len) + return (true); + + // Move to beginning of next ray. + cur_offset += raylengths[i]; + } + return (false); +} + +// Is starta...lengtha a subset of startb...lengthb? +static bool _is_subset( int starta, int startb, int lengtha, int lengthb ) +{ + int cura = starta, curb = startb; + int enda = starta + lengtha, endb = startb + lengthb; + + while (cura < enda && curb < endb) + { + if (ray_coord_x[curb] > ray_coord_x[cura]) + return (false); + if (ray_coord_y[curb] > ray_coord_y[cura]) + return (false); + + if (ray_coord_x[cura] == ray_coord_x[curb] + && ray_coord_y[cura] == ray_coord_y[curb]) + { + ++cura; + } + + ++curb; + } + + return (cura == enda); +} + +// Returns a vector which lists all the nonduped cellrays (by index). +static std::vector<int> _find_nonduped_cellrays() +{ + // A cellray c in a fullray f is duped if there is a fullray g + // such that g contains c and g[:c] is a subset of f[:c]. + int raynum, cellnum, curidx, testidx, testray, testcell; + bool is_duplicate; + + std::vector<int> result; + for (curidx = 0, raynum = 0; + raynum < static_cast<int>(raylengths.size()); + curidx += raylengths[raynum++]) + { + for (cellnum = 0; cellnum < raylengths[raynum]; ++cellnum) + { + // Is the cellray raynum[cellnum] duplicated? + is_duplicate = false; + // XXX: We should really check everything up to now + // completely, and all further rays to see if they're + // proper subsets. + const int curx = ray_coord_x[curidx + cellnum]; + const int cury = ray_coord_y[curidx + cellnum]; + for (testidx = 0, testray = 0; testray < raynum; + testidx += raylengths[testray++]) + { + // Scan ahead to see if there's an intersect. + for (testcell = 0; testcell < raylengths[raynum]; ++testcell) + { + const int testx = ray_coord_x[testidx + testcell]; + const int testy = ray_coord_y[testidx + testcell]; + // We can short-circuit sometimes. + if (testx > curx || testy > cury) + break; + + // Bingo! + if (testx == curx && testy == cury) + { + is_duplicate = _is_subset(testidx, curidx, + testcell, cellnum); + break; + } + } + if (is_duplicate) + break; // No point in checking further rays. + } + if (!is_duplicate) + result.push_back(curidx + cellnum); + } + } + return result; +} + +// Create and register the ray defined by the arguments. +// Return true if the ray was actually registered (i.e., not a duplicate.) +static bool _register_ray( double accx, double accy, double slope ) +{ + int xpos[LOS_MAX_RANGE * 2 + 1], ypos[LOS_MAX_RANGE * 2 + 1]; + int raylen = shoot_ray( accx, accy, slope, LOS_MAX_RANGE, xpos, ypos ); + + // Early out if ray already exists. + if (_is_duplicate_ray(raylen, xpos, ypos)) + return (false); + + // Not duplicate, register. + for (int i = 0; i < raylen; ++i) + { + // Create the cellrays. + ray_coord_x.push_back(xpos[i]); + ray_coord_y.push_back(ypos[i]); + } + + // Register the fullray. + raylengths.push_back(raylen); + ray_def ray; + ray.accx = accx; + ray.accy = accy; + ray.slope = slope; + ray.quadrant = 0; + fullrays.push_back(ray); + + return (true); +} + +static void _create_blockrays() +{ + // determine nonduplicated rays + std::vector<int> nondupe_cellrays = _find_nonduped_cellrays(); + const unsigned int num_nondupe_rays = nondupe_cellrays.size(); + const unsigned int num_nondupe_words = + (num_nondupe_rays + LONGSIZE - 1) / LONGSIZE; + const unsigned int num_cellrays = ray_coord_x.size(); + const unsigned int num_words = (num_cellrays + LONGSIZE - 1) / LONGSIZE; + + // first build all the rays: easier to do blocking calculations there + unsigned long* full_los_blockrays; + full_los_blockrays = new unsigned long[num_words * (LOS_MAX_RANGE_X+1) * + (LOS_MAX_RANGE_Y+1)]; + memset((void*)full_los_blockrays, 0, sizeof(unsigned long) * num_words * + (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y+1)); + + int cur_offset = 0; + + for (unsigned int ray = 0; ray < raylengths.size(); ++ray) + { + for (int i = 0; i < raylengths[ray]; ++i) + { + // every cell blocks... + unsigned long* const inptr = full_los_blockrays + + (ray_coord_x[i + cur_offset] * (LOS_MAX_RANGE_Y + 1) + + ray_coord_y[i + cur_offset]) * num_words; + + // ...all following cellrays + for (int j = i+1; j < raylengths[ray]; ++j) + _set_bit_in_long_array( inptr, j + cur_offset ); + + } + cur_offset += raylengths[ray]; + } + + // we've built the basic blockray array; now compress it, keeping + // only the nonduplicated cellrays. + + // allocate and clear memory + los_blockrays = new unsigned long[num_nondupe_words * (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y + 1)]; + memset((void*)los_blockrays, 0, sizeof(unsigned long) * num_nondupe_words * + (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y+1)); + + // we want to only keep the cellrays from nondupe_cellrays. + compressed_ray_x.resize(num_nondupe_rays); + compressed_ray_y.resize(num_nondupe_rays); + for (unsigned int i = 0; i < num_nondupe_rays; ++i) + { + compressed_ray_x[i] = ray_coord_x[nondupe_cellrays[i]]; + compressed_ray_y[i] = ray_coord_y[nondupe_cellrays[i]]; + } + unsigned long* oldptr = full_los_blockrays; + unsigned long* newptr = los_blockrays; + for (int x = 0; x <= LOS_MAX_RANGE_X; ++x) + for (int y = 0; y <= LOS_MAX_RANGE_Y; ++y) + { + for (unsigned int i = 0; i < num_nondupe_rays; ++i) + if (_get_bit_in_long_array(oldptr, nondupe_cellrays[i])) + _set_bit_in_long_array(newptr, i); + + oldptr += num_words; + newptr += num_nondupe_words; + } + + // we can throw away full_los_blockrays now + delete[] full_los_blockrays; + + dead_rays = new unsigned long[num_nondupe_words]; + smoke_rays = new unsigned long[num_nondupe_words]; + +#ifdef DEBUG_DIAGNOSTICS + mprf( MSGCH_DIAGNOSTICS, "Cellrays: %d Fullrays: %u Compressed: %u", + num_cellrays, raylengths.size(), num_nondupe_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( 0.5, 0.5, 1000.0 ); + _register_ray( 0.5, 0.5, 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 <= 2*LOS_MAX_RANGE; ++xangle ) + for ( int yangle = 1; yangle <= 2*LOS_MAX_RANGE; ++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; + + const double slope = ((double)(yangle)) / xangle; + const double rslope = ((double)(xangle)) / yangle; + for ( int intercept = 1; intercept <= 2*yangle; ++intercept ) + { + double xstart = ((double)(intercept)) / (2*yangle); + double ystart = 1; + + // now move back just inside the cell + // y should be "about to change" + xstart -= EPSILON_VALUE * xangle; + ystart -= EPSILON_VALUE * yangle; + + _register_ray( xstart, ystart, slope ); + // also draw the identical ray in octant 2 + _register_ray( ystart, xstart, rslope ); + } + } + + // Now create the appropriate blockrays array + _create_blockrays(); +} + +static void _set_ray_quadrant( ray_def& ray, int sx, int sy, int tx, int ty ) +{ + if ( tx >= sx && ty >= sy ) + ray.quadrant = 0; + else if ( tx < sx && ty >= sy ) + ray.quadrant = 1; + else if ( tx < sx && ty < sy ) + ray.quadrant = 2; + else if ( tx >= sx && ty < sy ) + ray.quadrant = 3; + else + mpr("Bad ray quadrant!", MSGCH_DIAGNOSTICS); +} + +static int _cyclic_offset( unsigned int ui, int cycle_dir, int startpoint, + int maxvalue ) +{ + const int i = (int)ui; + if ( startpoint < 0 ) + return i; + switch ( cycle_dir ) + { + case 1: + return (i + startpoint + 1) % maxvalue; + case -1: + return (i - 1 - startpoint + maxvalue) % maxvalue; + case 0: + default: + return i; + } +} + +static const double VERTICAL_SLOPE = 10000.0; +static double _calc_slope(double x, double y) +{ + if (double_is_zero(x)) + return (VERTICAL_SLOPE); + + const double slope = y / x; + return (slope > VERTICAL_SLOPE? VERTICAL_SLOPE : slope); +} + +static double _slope_factor(const ray_def &ray) +{ + double xdiff = fabs(ray.accx - 0.5), ydiff = fabs(ray.accy - 0.5); + + if (double_is_zero(xdiff) && double_is_zero(ydiff)) + return ray.slope; + + const double slope = _calc_slope(ydiff, xdiff); + return (slope + ray.slope) / 2.0; +} + +static bool _superior_ray(int shortest, int imbalance, + int raylen, int rayimbalance, + double slope_diff, double ray_slope_diff) +{ + if (shortest != raylen) + return (shortest > raylen); + + if (imbalance != rayimbalance) + return (imbalance > rayimbalance); + + return (slope_diff > ray_slope_diff); +} + +// 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 allow_fallback is true, fall back to a center-to-center ray +// if range is too great or all rays are blocked. +// If cycle_dir is 0, find the first fitting ray. If it is 1 or -1, +// assume that ray is appropriately filled in, and look for the next +// ray in that cycle direction. +// If find_shortest is true, examine all rays that hit the target and +// take the shortest (starting at ray.fullray_idx). + +bool find_ray( const coord_def& source, const coord_def& target, + bool allow_fallback, ray_def& ray, int cycle_dir, + bool find_shortest, bool ignore_solid ) +{ + int cellray, inray; + + const int sourcex = source.x; + const int sourcey = source.y; + const int targetx = target.x; + const int targety = target.y; + + const int signx = ((targetx - sourcex >= 0) ? 1 : -1); + const int signy = ((targety - sourcey >= 0) ? 1 : -1); + const int absx = signx * (targetx - sourcex); + const int absy = signy * (targety - sourcey); + + int cur_offset = 0; + int shortest = INFINITE_DISTANCE; + int imbalance = INFINITE_DISTANCE; + const double want_slope = _calc_slope(absx, absy); + double slope_diff = VERTICAL_SLOPE * 10.0; + std::vector<coord_def> unaliased_ray; + + for ( unsigned int fray = 0; fray < fullrays.size(); ++fray ) + { + const int fullray = _cyclic_offset( fray, cycle_dir, ray.fullray_idx, + fullrays.size() ); + // Yeah, yeah, this is O(n^2). I know. + cur_offset = 0; + for (int i = 0; i < fullray; ++i) + cur_offset += raylengths[i]; + + for (cellray = 0; cellray < raylengths[fullray]; ++cellray) + { + if (ray_coord_x[cellray + cur_offset] == absx + && ray_coord_y[cellray + cur_offset] == absy) + { + if (find_shortest) + { + unaliased_ray.clear(); + unaliased_ray.push_back(coord_def(0, 0)); + } + + // Check if we're blocked so far. + bool blocked = false; + coord_def c1, c3; + int real_length = 0; + for (inray = 0; inray <= cellray; ++inray) + { + const int xi = signx * ray_coord_x[inray + cur_offset]; + const int yi = signy * ray_coord_y[inray + cur_offset]; + if (inray < cellray && !ignore_solid + && grid_is_solid(grd[sourcex + xi][sourcey + yi])) + { + blocked = true; + break; + } + + if (find_shortest) + { + c3 = coord_def(xi, yi); + + // We've moved at least two steps if inray > 0. + if (inray) + { + // Check for a perpendicular corner on the ray and + // pretend that it's a diagonal. + if ((c3 - c1).abs() != 2) + ++real_length; + else + { + // c2 was a dud move, pop it off + unaliased_ray.pop_back(); + } + } + else + ++real_length; + + unaliased_ray.push_back(c3); + c1 = unaliased_ray[real_length - 1]; + } + } + + int cimbalance = 0; + // If this ray is a candidate for shortest, calculate + // the imbalance. I'm defining 'imbalance' as the + // number of consecutive diagonal or orthogonal moves + // in the ray. This is a reasonable measure of deviation from + // the Bresenham line between our selected source and + // destination. + if (!blocked && find_shortest && shortest >= real_length) + { + int diags = 0, straights = 0; + for (int i = 1, size = unaliased_ray.size(); i < size; ++i) + { + const int dist = + (unaliased_ray[i] - unaliased_ray[i - 1]).abs(); + + if (dist == 2) + { + straights = 0; + if (++diags > cimbalance) + cimbalance = diags; + } + else + { + diags = 0; + if (++straights > cimbalance) + cimbalance = straights; + } + } + } + + const double ray_slope_diff = find_shortest ? + fabs(_slope_factor(fullrays[fullray]) - want_slope) : 0.0; + + if (!blocked + && (!find_shortest + || _superior_ray(shortest, imbalance, + real_length, cimbalance, + slope_diff, ray_slope_diff))) + { + // Success! + ray = fullrays[fullray]; + ray.fullray_idx = fullray; + + shortest = real_length; + imbalance = cimbalance; + slope_diff = ray_slope_diff; + + if (sourcex > targetx) + ray.accx = 1.0 - ray.accx; + if (sourcey > targety) + ray.accy = 1.0 - ray.accy; + + ray.accx += sourcex; + ray.accy += sourcey; + + _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety); + if (!find_shortest) + return (true); + } + } + } + } + + if (find_shortest && shortest != INFINITE_DISTANCE) + return (true); + + if (allow_fallback) + { + ray.accx = sourcex + 0.5; + ray.accy = sourcey + 0.5; + if (targetx == sourcex) + ray.slope = VERTICAL_SLOPE; + else + { + ray.slope = targety - sourcey; + ray.slope /= targetx - sourcex; + if (ray.slope < 0) + ray.slope = -ray.slope; + } + _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety); + ray.fullray_idx = -1; + return (true); + } + return (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); + + ray.fullray_idx = -1; // to quiet valgrind + + // We don't need to find the shortest beam, any beam will suffice. + find_ray( source, target, true, ray, 0, false, true ); + + if (exclude_endpoints && ray.pos() == source) + { + ray.advance(true); + 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(true); + } + + return (count); +} + +// Usually calculates whether from one grid someone could see the other. +// Depending on the viewer's habitat, 'allowed' can be set to DNGN_FLOOR, +// DNGN_SHALLOW_WATER or DNGN_DEEP_WATER. +// Yes, this ignores lava-loving monsters. +// XXX: It turns out the beams are not symmetrical, i.e. switching +// pos1 and pos2 may result in small variations. +bool grid_see_grid(const coord_def& p1, const coord_def& p2, + dungeon_feature_type allowed) +{ + if (distance(p1, p2) > _los_radius_squared) + return (false); + + dungeon_feature_type max_disallowed = DNGN_MAXOPAQUE; + if (allowed != DNGN_UNSEEN) + max_disallowed = static_cast<dungeon_feature_type>(allowed - 1); + + // XXX: Ignoring clouds for now. + return (!num_feats_between(p1, p2, DNGN_UNSEEN, max_disallowed, + true, true)); +} + +// The rule behind LOS is: +// Two cells can see each other if there is any line from some point +// of the first to some point of the second ("generous" LOS.) +// +// 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(env_show_grid &sh, + feature_grid &gr, const coord_def& center, + bool clear_walls_block, bool ignore_clouds) +{ + raycast(); + const int x_p = center.x; + const int y_p = center.y; + // go quadrant by quadrant + const int quadrant_x[4] = { 1, -1, -1, 1 }; + const int quadrant_y[4] = { 1, 1, -1, -1 }; + + // clear out sh + sh.init(0); + + if (crawl_state.arena || crawl_state.arena_suspended) + { + for (int y = -ENV_SHOW_OFFSET; y <= ENV_SHOW_OFFSET; ++y) + for (int x = -ENV_SHOW_OFFSET; x <= ENV_SHOW_OFFSET; ++x) + { + const coord_def pos = center + coord_def(x, y); + if (map_bounds(pos)) + sh[x + sh_xo][y + sh_yo] = gr(pos); + } + return; + } + + const unsigned int num_cellrays = compressed_ray_x.size(); + const unsigned int num_words = (num_cellrays + LONGSIZE - 1) / LONGSIZE; + + for (int quadrant = 0; quadrant < 4; ++quadrant) + { + const int xmult = quadrant_x[quadrant]; + const int ymult = quadrant_y[quadrant]; + + // clear out the dead rays array + memset( (void*)dead_rays, 0, sizeof(unsigned long) * num_words); + memset( (void*)smoke_rays, 0, sizeof(unsigned long) * num_words); + + // kill all blocked rays + const unsigned long* inptr = los_blockrays; + + for (int xdiff = 0; xdiff <= LOS_MAX_RANGE_X; ++xdiff) + for (int ydiff = 0; ydiff <= LOS_MAX_RANGE_Y; + ++ydiff, inptr += num_words) + { + + const int realx = x_p + xdiff * xmult; + const int realy = y_p + ydiff * ymult; + + if (!map_bounds(realx, realy)) + continue; + + coord_def real(realx, realy); + dungeon_feature_type dfeat = grid_appearance(gr, real); + + // if this cell is opaque... + // ... or something you can see but not walk through ... + if (grid_is_opaque(dfeat) + || clear_walls_block && dfeat < DNGN_MINMOVE) + { + // then block the appropriate rays + for (unsigned int i = 0; i < num_words; ++i) + dead_rays[i] |= inptr[i]; + } + else if (!ignore_clouds + && is_opaque_cloud(env.cgrid[realx][realy])) + { + // block rays which have already seen a cloud + for (unsigned int i = 0; i < num_words; ++i) + { + dead_rays[i] |= (smoke_rays[i] & inptr[i]); + smoke_rays[i] |= inptr[i]; + } + } + } + + // ray calculation done, now work out which cells in this + // quadrant are visible + unsigned int rayidx = 0; + for (unsigned int wordloc = 0; wordloc < num_words; ++wordloc) + { + const unsigned long curword = dead_rays[wordloc]; + // Note: the last word may be incomplete + for (unsigned int bitloc = 0; bitloc < LONGSIZE; ++bitloc) + { + // make the cells seen by this ray at this point visible + if ( ((curword >> bitloc) & 1UL) == 0 ) + { + // this ray is alive! + const int realx = xmult * compressed_ray_x[rayidx]; + const int realy = ymult * compressed_ray_y[rayidx]; + // update shadow map + if (x_p + realx >= 0 && x_p + realx < GXM + && y_p + realy >= 0 && y_p + realy < GYM + && realx * realx + realy * realy <= _los_radius_squared) + { + sh[sh_xo+realx][sh_yo+realy] = gr[x_p+realx][y_p+realy]; + } + } + ++rayidx; + if (rayidx == num_cellrays) + break; + } + } + } + + // [dshaligram] The player's current position is always visible. + sh[sh_xo][sh_yo] = gr[x_p][y_p]; + + *dead_rays = NULL; + *smoke_rays = NULL; + *los_blockrays = NULL; +} + +void calc_show_los() +{ + if (!crawl_state.arena && !crawl_state.arena_suspended) + { + // Must be done first. + losight(env.show, grd, you.pos()); + + // What would be visible, if all of the translucent walls were + // made opaque. + losight(env.no_trans_show, grd, you.pos(), true); + } + else + { + losight(env.show, grd, crawl_view.glosc()); + } +} + +bool see_grid( const env_show_grid &show, + const coord_def &c, + const coord_def &pos ) +{ + if (c == pos) + return (true); + + const coord_def ip = pos - c; + if (ip.rdist() < ENV_SHOW_OFFSET) + { + const coord_def sp(ip + coord_def(ENV_SHOW_OFFSET, ENV_SHOW_OFFSET)); + if (show(sp)) + return (true); + } + return (false); +} + +// Answers the question: "Is a grid within character's line of sight?" +bool see_grid( const coord_def &p ) +{ + return ((crawl_state.arena || crawl_state.arena_suspended) + && crawl_view.in_grid_los(p)) + || see_grid(env.show, you.pos(), p); +} + +// Answers the question: "Would a grid be within character's line of sight, +// even if all translucent/clear walls were made opaque?" +bool see_grid_no_trans( const coord_def &p ) +{ + return see_grid(env.no_trans_show, you.pos(), p); +} + +// Is the grid visible, but a translucent wall is in the way? +bool trans_wall_blocking( const coord_def &p ) +{ + return see_grid(p) && !see_grid_no_trans(p); +} + diff --git a/crawl-ref/source/los.h b/crawl-ref/source/los.h new file mode 100644 index 0000000000..301806b8c6 --- /dev/null +++ b/crawl-ref/source/los.h @@ -0,0 +1,60 @@ +/* + * File: los.h + * Summary: Line-of-sight algorithm. + */ + +#ifndef LOS_H +#define LOS_H + +#include "externs.h" + +#define EPSILON_VALUE 0.00001 + +bool double_is_zero(const double x); + + +void setLOSRadius(int newLR); +int get_los_radius_squared(); // XXX + +struct ray_def; +bool find_ray( const coord_def& source, const coord_def& target, + bool allow_fallback, ray_def& ray, int cycle_dir = 0, + bool find_shortest = false, bool ignore_solid = false ); + +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 = true, + bool just_check = false); +bool grid_see_grid(const coord_def& p1, const coord_def& p2, + dungeon_feature_type allowed = DNGN_UNSEEN); + +void clear_rays_on_exit(); +void losight(env_show_grid &sh, feature_grid &gr, + const coord_def& center, bool clear_walls_block = false, + bool ignore_clouds = false); +void calc_show_los(); + +bool see_grid( const env_show_grid &show, + const coord_def &c, + const coord_def &pos ); +bool see_grid(const coord_def &p); +bool see_grid_no_trans( const coord_def &p ); +bool trans_wall_blocking( const coord_def &p ); + +inline bool see_grid( int grx, int gry ) +{ + return see_grid(coord_def(grx, gry)); +} + +inline bool see_grid_no_trans(int x, int y) +{ + return see_grid_no_trans(coord_def(x, y)); +} + +inline bool trans_wall_blocking(int x, int y) +{ + return trans_wall_blocking(coord_def(x, y)); +} + +#endif diff --git a/crawl-ref/source/luadgn.cc b/crawl-ref/source/luadgn.cc index c932ac39c0..8a33b2873a 100644 --- a/crawl-ref/source/luadgn.cc +++ b/crawl-ref/source/luadgn.cc @@ -23,6 +23,7 @@ REVISION("$Rev$"); #include "hiscores.h" #include "initfile.h" #include "items.h" +#include "los.h" #include "luadgn.h" #include "mapdef.h" #include "mapmark.h" diff --git a/crawl-ref/source/makefile.obj b/crawl-ref/source/makefile.obj index ee549702ba..0cd08afa04 100644 --- a/crawl-ref/source/makefile.obj +++ b/crawl-ref/source/makefile.obj @@ -36,6 +36,7 @@ itemprop.o \ items.o \ lev-pand.o \ libutil.o \ +los.o \ luadgn.o \ macro.o \ makeitem.o \ @@ -46,6 +47,7 @@ menu.o \ message.o \ mgrow.o \ misc.o \ +mon-los.o \ monplace.o \ mon-pick.o \ monstuff.o \ @@ -62,6 +64,7 @@ overmap.o \ place.o \ player.o \ quiver.o \ +ray.o \ religion.o \ sha256.o \ shopping.o \ diff --git a/crawl-ref/source/misc.cc b/crawl-ref/source/misc.cc index ec4de2ca8f..e0e49b5f83 100644 --- a/crawl-ref/source/misc.cc +++ b/crawl-ref/source/misc.cc @@ -51,6 +51,7 @@ REVISION("$Rev$"); #include "itemprop.h" #include "items.h" #include "lev-pand.h" +#include "los.h" #include "macro.h" #include "makeitem.h" #include "mapmark.h" diff --git a/crawl-ref/source/mon-los.cc b/crawl-ref/source/mon-los.cc new file mode 100644 index 0000000000..17ad5c3e16 --- /dev/null +++ b/crawl-ref/source/mon-los.cc @@ -0,0 +1,407 @@ +/* + * File: mon-los.cc + * Summary: Monster line-of-sight. + */ + +#include "AppHdr.h" +REVISION("$Rev$"); +#include "mon-los.h" + +#include "los.h" +#include "ray.h" +#include "stuff.h" + +// Static class members must be initialised outside of the class +// declaration, or gcc won't define them in view.o and we'll get a +// linking error. +const int monster_los::LSIZE = _monster_los_LSIZE; +const int monster_los::L_VISIBLE = 1; +const int monster_los::L_UNKNOWN = 0; +const int monster_los::L_BLOCKED = -1; + +///////////////////////////////////////////////////////////////////////////// +// monster_los + +monster_los::monster_los() + : gridx(0), gridy(0), mons(), range(LOS_RADIUS), los_field() +{ +} + +monster_los::~monster_los() +{ +} + +void monster_los::set_monster(monsters *mon) +{ + mons = mon; + set_los_centre(mon->pos()); +} + +void monster_los::set_los_centre(int x, int y) +{ + if (!in_bounds(x, y)) + return; + + gridx = x; + gridy = y; +} + +void monster_los::set_los_range(int r) +{ + ASSERT (r >= 1 && r <= LOS_RADIUS); + range = r; +} + +coord_def monster_los::pos_to_index(coord_def &p) +{ + int ix = LOS_RADIUS + p.x - gridx; + int iy = LOS_RADIUS + p.y - gridy; + + ASSERT(ix >= 0 && ix < LSIZE); + ASSERT(iy >= 0 && iy < LSIZE); + + return (coord_def(ix, iy)); +} + +coord_def monster_los::index_to_pos(coord_def &i) +{ + int px = i.x + gridx - LOS_RADIUS; + int py = i.y + gridy - LOS_RADIUS; + + ASSERT(in_bounds(px, py)); + return (coord_def(px, py)); +} + +void monster_los::set_los_value(int x, int y, bool blocked, bool override) +{ + if (!override && !is_unknown(x,y)) + return; + + coord_def c(x,y); + coord_def lpos = pos_to_index(c); + + int value = (blocked ? L_BLOCKED : L_VISIBLE); + + if (value != los_field[lpos.x][lpos.y]) + los_field[lpos.x][lpos.y] = value; +} + +int monster_los::get_los_value(int x, int y) +{ + // Too far away -> definitely out of sight! + if (distance(x, y, gridx, gridy) > get_los_radius_squared()) + return (L_BLOCKED); + + coord_def c(x,y); + coord_def lpos = pos_to_index(c); + return (los_field[lpos.x][lpos.y]); +} + +bool monster_los::in_sight(int x, int y) +{ + // Is the path to (x,y) clear? + return (get_los_value(x,y) == L_VISIBLE); +} + +bool monster_los::is_blocked(int x, int y) +{ + // Is the path to (x,y) blocked? + return (get_los_value(x, y) == L_BLOCKED); +} + +bool monster_los::is_unknown(int x, int y) +{ + return (get_los_value(x, y) == L_UNKNOWN); +} + +static bool _blocks_movement_sight(monsters *mon, dungeon_feature_type feat) +{ + if (feat < DNGN_MINMOVE) + return (true); + + if (!mon) // No monster defined? + return (false); + + if (!mon->can_pass_through_feat(feat)) + return (true); + + return (false); +} + +void monster_los::fill_los_field() +{ + int pos_x, pos_y; + for (int k = 1; k <= range; k++) + for (int i = -1; i <= 1; i++) + for (int j = -1; j <= 1; j++) + { + if (i == 0 && j == 0) // Ignore centre grid. + continue; + + pos_x = gridx + k*i; + pos_y = gridy + k*j; + + if (!in_bounds(pos_x, pos_y)) + continue; + + if (!_blocks_movement_sight(mons, grd[pos_x][pos_y])) + set_los_value(pos_x, pos_y, false); + else + { + set_los_value(pos_x, pos_y, true); + // Check all beam potentially going through a blocked grid. + check_los_beam(pos_x, pos_y); + } + } +} + +// (cx, cy) is the centre point +// (dx, dy) is the target we're aiming *through* +// target1 and target2 are targets we'll be aiming *at* to fire through (dx,dy) +static bool _set_beam_target(int cx, int cy, int dx, int dy, + int &target1_x, int &target1_y, + int &target2_x, int &target2_y, + int range) +{ + const int xdist = dx - cx; + const int ydist = dy - cy; + + if (xdist == 0 && ydist == 0) + return (false); // Nothing to be done. + + if (xdist <= -range || xdist >= range + || ydist <= -range || ydist >= range) + { + // Grids on the edge of a monster's LOS don't block sight any further. + return (false); + } + +/* + * The following code divides the field into eights of different directions. + * + * \ NW | NE / + * \ | / + * WN \ | / EN + * ---------------- + * WS / | \ ES + * / | \ + * / SW | SE \ + * + * target1_x and target1_y mark the base line target, so the base beam ends + * on the diagonal line closest to the target (or on one of the straight + * lines if cx == dx or dx == dy). + * + * target2_x and target2_y then mark the second target our beam finder should + * cycle through. It'll always be target2_x = dx or target2_y = dy, the other + * being on the edge of LOS, which one depending on the quadrant. + * + * The beam finder can then cycle from the nearest corner (target1) to the + * second edge target closest to (dx,dy). + */ + + if (xdist == 0) + { + target1_x = cx; + target1_y = (ydist > 0 ? cy + range + : cy - range); + + target2_x = target1_x; + target2_y = target1_y; + } + else if (ydist == 0) + { + target1_x = (xdist > 0 ? cx + range + : cx - range); + target1_y = cy; + + target2_x = target1_x; + target2_y = target1_y; + } + else if (xdist < 0 && ydist < 0 || xdist > 0 && ydist > 0) + { + if (xdist < 0) + { + target1_x = cx - range; + target1_y = cy - range; + } + else + { + target1_x = cx + range; + target1_y = cy + range; + } + + if (xdist == ydist) + { + target2_x = target1_x; + target2_y = target1_y; + } + else + { + if (xdist < 0) // both are negative (upper left corner) + { + if (dx > dy) + { + target2_x = dx; + target2_y = cy - range; + } + else + { + target2_x = cx - range; + target2_y = dy; + } + } + else // both are positive (lower right corner) + { + if (dx > dy) + { + target2_x = cx + range; + target2_y = dy; + } + else + { + target2_x = dx; + target2_y = cy + range; + } + } + } + } + else if (xdist < 0 && ydist > 0 || xdist > 0 && ydist < 0) + { + if (xdist < 0) // lower left corner + { + target1_x = cx - range; + target1_y = cy + range; + } + else // upper right corner + { + target1_x = cx + range; + target1_y = cy - range; + } + + if (xdist == -ydist) + { + target2_x = target1_x; + target2_y = target1_y; + } + else + { + if (xdist < 0) // ydist > 0 + { + if (-xdist > ydist) + { + target2_x = cx - range; + target2_y = dy; + } + else + { + target2_x = dx; + target2_y = cy + range; + } + } + else // xdist > 0, ydist < 0 + { + if (-xdist > ydist) + { + target2_x = dx; + target2_y = cy - range; + } + else + { + target2_x = cx + range; + target2_y = dy; + } + } + } + } + else + { + // Everything should have been handled above. + ASSERT(false); + } + + return (true); +} + +void monster_los::check_los_beam(int dx, int dy) +{ + ray_def ray; + + int target1_x = 0, target1_y = 0, target2_x = 0, target2_y = 0; + if (!_set_beam_target(gridx, gridy, dx, dy, target1_x, target1_y, + target2_x, target2_y, range)) + { + // Nothing to be done. + return; + } + + if (target1_x > target2_x || target1_y > target2_y) + { + // Swap the two targets so our loop will work correctly. + int help = target1_x; + target1_x = target2_x; + target2_x = help; + + help = target1_y; + target1_y = target2_y; + target2_y = help; + } + + const int max_dist = range; + int dist; + bool blocked = false; + for (int tx = target1_x; tx <= target2_x; tx++) + for (int ty = target1_y; ty <= target2_y; ty++) + { + // If (tx, ty) lies outside the level boundaries, there's nothing + // that shooting a ray into that direction could bring us, esp. + // as earlier grids in the ray will already have been handled, and + // out of bounds grids are simply skipped in any LoS check. + if (!map_bounds(tx, ty)) + continue; + + // Already calculated a beam to (tx, ty), don't do so again. + if (!is_unknown(tx, ty)) + continue; + + dist = 0; + ray.fullray_idx = -1; // to quiet valgrind + find_ray( coord_def(gridx, gridy), coord_def(tx, ty), + true, ray, 0, true, true ); + + if (ray.x() == gridx && ray.y() == gridy) + ray.advance(true); + + while (dist++ <= max_dist) + { + // The ray brings us out of bounds of the level map. + // Since we're always shooting outwards there's nothing more + // to look at in that direction, and we can break the loop. + if (!map_bounds(ray.x(), ray.y())) + break; + + if (blocked) + { + // Earlier grid blocks this beam, set to blocked if + // unknown, but don't overwrite visible grids. + set_los_value(ray.x(), ray.y(), true); + } + else if (_blocks_movement_sight(mons, grd[ray.x()][ray.y()])) + { + set_los_value(ray.x(), ray.y(), true); + // The rest of the beam will now be blocked. + blocked = true; + } + else + { + // Allow overriding in case another beam has marked this + // field as blocked, because we've found a solution where + // that isn't the case. + set_los_value(ray.x(), ray.y(), false, true); + } + if (ray.x() == tx && ray.y() == ty) + break; + + ray.advance(true); + } + } +} diff --git a/crawl-ref/source/mon-los.h b/crawl-ref/source/mon-los.h new file mode 100644 index 0000000000..1d2921aecc --- /dev/null +++ b/crawl-ref/source/mon-los.h @@ -0,0 +1,64 @@ +#ifndef MON_LOS_H +/* + * File: mon-los.cc + * Summary: Monster line-of-sight. + */ + +#define MON_LOS_H + +#define _monster_los_LSIZE (2 * LOS_RADIUS + 1) + +// This class can be used to fill the entire surroundings (los_range) +// of a monster or other position with seen/unseen values, so as to be able +// to compare several positions within this range. +class monster_los +{ +public: + monster_los(); + virtual ~monster_los(); + + // public methods + void set_monster(monsters *mon); + void set_los_centre(int x, int y); + void set_los_centre(const coord_def& p) { this->set_los_centre(p.x, p.y); } + void set_los_range(int r); + void fill_los_field(void); + bool in_sight(int x, int y); + bool in_sight(const coord_def& p) { return this->in_sight(p.x, p.y); } + +protected: + // protected methods + coord_def pos_to_index(coord_def &p); + coord_def index_to_pos(coord_def &i); + + void set_los_value(int x, int y, bool blocked, bool override = false); + int get_los_value(int x, int y); + bool is_blocked(int x, int y); + bool is_unknown(int x, int y); + + void check_los_beam(int dx, int dy); + + // The (fixed) size of the array. + static const int LSIZE; + + static const int L_VISIBLE; + static const int L_UNKNOWN; + static const int L_BLOCKED; + + // The centre of our los field. + int gridx, gridy; + + // Habitat checks etc. should be done for this monster. + // Usually the monster whose LOS we're trying to calculate + // (if mon->x == gridx, mon->y == gridy). + // Else, any monster trying to move around within this los field. + monsters *mons; + + // Range may never be greater than LOS_RADIUS! + int range; + + // The array to store the LOS values. + int los_field[_monster_los_LSIZE][_monster_los_LSIZE]; +}; + +#endif diff --git a/crawl-ref/source/mon-util.cc b/crawl-ref/source/mon-util.cc index da6a84acde..fd542f0d53 100644 --- a/crawl-ref/source/mon-util.cc +++ b/crawl-ref/source/mon-util.cc @@ -36,6 +36,7 @@ REVISION("$Rev$"); #include "items.h" #include "it_use2.h" #include "kills.h" +#include "los.h" #include "message.h" #include "misc.h" #include "monplace.h" diff --git a/crawl-ref/source/monplace.cc b/crawl-ref/source/monplace.cc index 5b92e4f855..0e4f5be852 100644 --- a/crawl-ref/source/monplace.cc +++ b/crawl-ref/source/monplace.cc @@ -17,6 +17,7 @@ REVISION("$Rev$"); #include "externs.h" #include "ghost.h" #include "lev-pand.h" +#include "los.h" #include "makeitem.h" #include "message.h" #include "monstuff.h" diff --git a/crawl-ref/source/monstuff.cc b/crawl-ref/source/monstuff.cc index bb2c797f5b..5aeb730834 100644 --- a/crawl-ref/source/monstuff.cc +++ b/crawl-ref/source/monstuff.cc @@ -37,12 +37,14 @@ REVISION("$Rev$"); #include "items.h" #include "itemprop.h" #include "kills.h" +#include "los.h" #include "makeitem.h" #include "mapmark.h" #include "message.h" #include "misc.h" #include "monplace.h" #include "monspeak.h" +#include "mon-los.h" #include "mon-pick.h" #include "mon-util.h" #include "mutation.h" diff --git a/crawl-ref/source/mstuff2.cc b/crawl-ref/source/mstuff2.cc index 420d8782a4..a4ad05224b 100644 --- a/crawl-ref/source/mstuff2.cc +++ b/crawl-ref/source/mstuff2.cc @@ -29,6 +29,7 @@ REVISION("$Rev$"); #include "itemprop.h" #include "items.h" #include "kills.h" +#include "los.h" #include "message.h" #include "misc.h" #include "monplace.h" diff --git a/crawl-ref/source/ouch.cc b/crawl-ref/source/ouch.cc index de3c34b55d..205f9b2286 100644 --- a/crawl-ref/source/ouch.cc +++ b/crawl-ref/source/ouch.cc @@ -45,6 +45,7 @@ REVISION("$Rev$"); #include "itemname.h" #include "itemprop.h" #include "items.h" +#include "los.h" #include "macro.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/player.cc b/crawl-ref/source/player.cc index 4035a97a61..72bf5841b7 100644 --- a/crawl-ref/source/player.cc +++ b/crawl-ref/source/player.cc @@ -38,6 +38,7 @@ REVISION("$Rev$"); #include "items.h" #include "it_use2.h" #include "kills.h" +#include "los.h" #include "macro.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/ray.cc b/crawl-ref/source/ray.cc new file mode 100644 index 0000000000..5196ba5cff --- /dev/null +++ b/crawl-ref/source/ray.cc @@ -0,0 +1,345 @@ +/* + * File: ray.cc + * Summary: Ray definition + */ + +#include "AppHdr.h" +REVISION("$Rev$"); + +#include "ray.h" + +#include <cmath> + +#include "los.h" +#include "terrain.h" + +// note that slope must be nonnegative! +// returns 0 if the advance was in x, 1 if it was in y, 2 if it was +// the diagonal +static int _find_next_intercept(double* accx, double* accy, const double slope) +{ + + // handle perpendiculars + if ( double_is_zero(slope) ) + { + *accx += 1.0; + return 0; + } + if ( slope > 100.0 ) + { + *accy += 1.0; + return 1; + } + + const double xtarget = (static_cast<int>(*accx) + 1); + const double ytarget = (static_cast<int>(*accy) + 1); + const double xdistance = xtarget - *accx; + const double ydistance = ytarget - *accy; + double distdiff = (xdistance * slope - ydistance); + + // exact corner + if ( double_is_zero( distdiff ) ) + { + // move somewhat away from the corner + if ( slope > 1.0 ) + { + *accx = xtarget + EPSILON_VALUE * 2; + *accy = ytarget + EPSILON_VALUE * 2 * slope; + } + else + { + *accx = xtarget + EPSILON_VALUE * 2 / slope; + *accy = ytarget + EPSILON_VALUE * 2; + } + return 2; + } + + // move to the boundary + double traveldist; + int rc = -1; + if ( distdiff > 0.0 ) + { + traveldist = ydistance / slope; + rc = 1; + } + else + { + traveldist = xdistance; + rc = 0; + } + + // and a little into the next cell, taking care + // not to go too far + if ( distdiff < 0.0 ) + distdiff = -distdiff; + traveldist += std::min(EPSILON_VALUE * 10.0, 0.5 * distdiff / slope); + + *accx += traveldist; + *accy += traveldist * slope; + return rc; +} + +// Shoot a ray from the given start point (accx, accy) with the given +// slope, with a maximum distance (in either x or y coordinate) of +// maxrange. Store the visited cells in xpos[] and ypos[], and +// return the number of cells visited. +int shoot_ray( double accx, double accy, const double slope, + int maxrange, int xpos[], int ypos[] ) +{ + int curx, cury; + int cellnum; + for (cellnum = 0; true; ++cellnum) + { + _find_next_intercept( &accx, &accy, slope ); + curx = static_cast<int>(accx); + cury = static_cast<int>(accy); + if (curx*curx + cury*cury > get_los_radius_squared()) + break; + + // Work with the new square. + xpos[cellnum] = curx; + ypos[cellnum] = cury; + } + return cellnum; +} + + + +ray_def::ray_def() : accx(0.0), accy(0.0), slope(0.0), quadrant(0), + fullray_idx(0) +{ +} + +double ray_def::reflect(double p, double c) const +{ + return (c + c - p); +} + +double ray_def::reflect(bool rx, double oldx, double newx) const +{ + if (rx? fabs(slope) > 1.0 : fabs(slope) < 1.0) + return (reflect(oldx, floor(oldx) + 0.5)); + + const double flnew = floor(newx); + const double flold = floor(oldx); + return (reflect(oldx, + flnew > flold? flnew : + flold > flnew? flold : + (newx + oldx) / 2)); +} + +void ray_def::set_reflect_point(const double oldx, const double oldy, + double *newx, double *newy, + bool blocked_x, bool blocked_y) +{ + if (blocked_x == blocked_y) + { + // What to do? + *newx = oldx; + *newy = oldy; + return; + } + + if (blocked_x) + { + ASSERT(int(oldy) != int(*newy)); + *newy = oldy; + *newx = reflect(true, oldx, *newx); + } + else + { + ASSERT(int(oldx) != int(*newx)); + *newx = oldx; + *newy = reflect(false, oldy, *newy); + } +} + +void ray_def::advance_and_bounce() +{ + // 0 = down-right, 1 = down-left, 2 = up-left, 3 = up-right + int bouncequad[4][3] = + { + { 1, 3, 2 }, { 0, 2, 3 }, { 3, 1, 0 }, { 2, 0, 1 } + }; + int oldx = x(), oldy = y(); + const double oldaccx = accx, oldaccy = accy; + int rc = advance(false); + int newx = x(), newy = y(); + ASSERT( grid_is_solid(grd[newx][newy]) ); + + const bool blocked_x = grid_is_solid(grd[oldx][newy]); + const bool blocked_y = grid_is_solid(grd[newx][oldy]); + + if ( double_is_zero(slope) || slope > 100.0 ) + quadrant = bouncequad[quadrant][2]; + else if ( rc != 2 ) + quadrant = bouncequad[quadrant][rc]; + else + { + ASSERT( (oldx != newx) && (oldy != newy) ); + if ( blocked_x && blocked_y ) + quadrant = bouncequad[quadrant][rc]; + else if ( blocked_x ) + quadrant = bouncequad[quadrant][1]; + else + quadrant = bouncequad[quadrant][0]; + } + + set_reflect_point(oldaccx, oldaccy, &accx, &accy, blocked_x, blocked_y); +} + +double ray_def::get_degrees() const +{ + if (slope > 100.0) + { + if (quadrant == 3 || quadrant == 2) + return (90.0); + else + return (270.0); + } + else if (double_is_zero(slope)) + { + if (quadrant == 0 || quadrant == 3) + return (0.0); + else + return (180.0); + } + + double deg = atan(slope) * 180.0 / M_PI; + + switch (quadrant) + { + case 0: + return (360.0 - deg); + + case 1: + return (180.0 + deg); + + case 2: + return (180.0 - deg); + + case 3: + return (deg); + } + ASSERT(!"ray has illegal quadrant"); + return (0.0); +} + +void ray_def::set_degrees(double deg) +{ + while (deg < 0.0) + deg += 360.0; + while (deg >= 360.0) + deg -= 360.0; + + double _slope = tan(deg / 180.0 * M_PI); + + if (double_is_zero(_slope)) + { + slope = 0.0; + + if (deg < 90.0 || deg > 270.0) + quadrant = 0; // right/east + else + quadrant = 1; // left/west + } + else if (_slope > 0) + { + slope = _slope; + + if (deg >= 180.0 && deg <= 270.0) + quadrant = 1; + else + quadrant = 3; + } + else + { + slope = -_slope; + + if (deg >= 90 && deg <= 180) + quadrant = 2; + else + quadrant = 0; + } + + if (slope > 1000.0) + slope = 1000.0; +} + +void ray_def::regress() +{ + int opp_quadrant[4] = { 2, 3, 0, 1 }; + quadrant = opp_quadrant[quadrant]; + advance(false); + quadrant = opp_quadrant[quadrant]; +} + +int ray_def::advance_through(const coord_def &target) +{ + return (advance(true, &target)); +} + +int ray_def::advance(bool shortest_possible, const coord_def *target) +{ + if (!shortest_possible) + return (raw_advance()); + + // If we want to minimise the number of moves on the ray, look one + // step ahead and see if we can get a diagonal. + + const coord_def old(static_cast<int>(accx), static_cast<int>(accy)); + const int ret = raw_advance(); + + if (ret == 2 || (target && pos() == *target)) + return (ret); + + const double maccx = accx, maccy = accy; + if (raw_advance() != 2) + { + const coord_def second(static_cast<int>(accx), static_cast<int>(accy)); + // If we can convert to a diagonal, do so. + if ((second - old).abs() == 2) + return (2); + } + + // No diagonal, so roll back. + accx = maccx; + accy = maccy; + + return (ret); +} + +int ray_def::raw_advance() +{ + int rc; + switch ( quadrant ) + { + case 0: + // going down-right + rc = _find_next_intercept( &accx, &accy, slope ); + return rc; + case 1: + // going down-left + accx = 100.0 - EPSILON_VALUE/10.0 - accx; + rc = _find_next_intercept( &accx, &accy, slope ); + accx = 100.0 - EPSILON_VALUE/10.0 - accx; + return rc; + case 2: + // going up-left + accx = 100.0 - EPSILON_VALUE/10.0 - accx; + accy = 100.0 - EPSILON_VALUE/10.0 - accy; + rc = _find_next_intercept( &accx, &accy, slope ); + accx = 100.0 - EPSILON_VALUE/10.0 - accx; + accy = 100.0 - EPSILON_VALUE/10.0 - accy; + return rc; + case 3: + // going up-right + accy = 100.0 - EPSILON_VALUE/10.0 - accy; + rc = _find_next_intercept( &accx, &accy, slope ); + accy = 100.0 - EPSILON_VALUE/10.0 - accy; + return rc; + default: + return -1; + } +} + diff --git a/crawl-ref/source/ray.h b/crawl-ref/source/ray.h index fabaa8bf82..617385f5eb 100644 --- a/crawl-ref/source/ray.h +++ b/crawl-ref/source/ray.h @@ -7,6 +7,9 @@ #ifndef RAY_H #define RAY_H +int shoot_ray(double accx, double accy, const double slope, + int maxrange, int xpos[], int ypos[]); + struct ray_def { public: diff --git a/crawl-ref/source/religion.cc b/crawl-ref/source/religion.cc index f88e8a342f..842202c414 100644 --- a/crawl-ref/source/religion.cc +++ b/crawl-ref/source/religion.cc @@ -44,6 +44,7 @@ REVISION("$Rev$"); #include "item_use.h" #include "items.h" #include "kills.h" +#include "los.h" #include "macro.h" #include "makeitem.h" #include "message.h" diff --git a/crawl-ref/source/spells1.cc b/crawl-ref/source/spells1.cc index 399d38d4e7..ba43290b3e 100644 --- a/crawl-ref/source/spells1.cc +++ b/crawl-ref/source/spells1.cc @@ -28,6 +28,7 @@ REVISION("$Rev$"); #include "it_use2.h" #include "itemname.h" #include "itemprop.h" +#include "los.h" #include "message.h" #include "misc.h" #include "monplace.h" diff --git a/crawl-ref/source/spells2.cc b/crawl-ref/source/spells2.cc index a534f0f862..ce26de1e21 100644 --- a/crawl-ref/source/spells2.cc +++ b/crawl-ref/source/spells2.cc @@ -30,6 +30,7 @@ REVISION("$Rev$"); #include "itemprop.h" #include "items.h" #include "it_use2.h" +#include "los.h" #include "message.h" #include "misc.h" #include "monplace.h" diff --git a/crawl-ref/source/spells3.cc b/crawl-ref/source/spells3.cc index d3c8a02047..71c4cbfa5f 100644 --- a/crawl-ref/source/spells3.cc +++ b/crawl-ref/source/spells3.cc @@ -31,6 +31,7 @@ REVISION("$Rev$"); #include "itemprop.h" #include "items.h" #include "item_use.h" +#include "los.h" #include "message.h" #include "misc.h" #include "monplace.h" diff --git a/crawl-ref/source/spells4.cc b/crawl-ref/source/spells4.cc index 6c3652c025..406047cff1 100644 --- a/crawl-ref/source/spells4.cc +++ b/crawl-ref/source/spells4.cc @@ -31,6 +31,7 @@ REVISION("$Rev$"); #include "itemname.h" #include "itemprop.h" #include "items.h" +#include "los.h" #include "makeitem.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/spl-cast.cc b/crawl-ref/source/spl-cast.cc index 5add5f332e..56ea04f0d0 100644 --- a/crawl-ref/source/spl-cast.cc +++ b/crawl-ref/source/spl-cast.cc @@ -26,6 +26,7 @@ REVISION("$Rev$"); #include "item_use.h" #include "itemname.h" #include "itemprop.h" +#include "los.h" #include "macro.h" #include "menu.h" #include "misc.h" diff --git a/crawl-ref/source/spl-util.cc b/crawl-ref/source/spl-util.cc index 5a9d6e5d2b..716dce7479 100644 --- a/crawl-ref/source/spl-util.cc +++ b/crawl-ref/source/spl-util.cc @@ -24,6 +24,7 @@ REVISION("$Rev$"); #include "debug.h" #include "stuff.h" #include "itemname.h" +#include "los.h" #include "macro.h" #include "misc.h" #include "monstuff.h" diff --git a/crawl-ref/source/stash.cc b/crawl-ref/source/stash.cc index 549ede3af6..ead169d16f 100644 --- a/crawl-ref/source/stash.cc +++ b/crawl-ref/source/stash.cc @@ -23,6 +23,7 @@ REVISION("$Rev$"); #include "items.h" #include "kills.h" #include "libutil.h" +#include "los.h" #include "menu.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/state.cc b/crawl-ref/source/state.cc index e8fcbd251c..e5fb1362d5 100644 --- a/crawl-ref/source/state.cc +++ b/crawl-ref/source/state.cc @@ -11,6 +11,7 @@ REVISION("$Rev$"); #include "delay.h" #include "directn.h" +#include "los.h" #include "macro.h" #include "misc.h" #include "menu.h" // For print_formatted_paragraph() diff --git a/crawl-ref/source/stuff.cc b/crawl-ref/source/stuff.cc index af9245fb7b..94a44ec5e2 100644 --- a/crawl-ref/source/stuff.cc +++ b/crawl-ref/source/stuff.cc @@ -11,6 +11,7 @@ REVISION("$Rev$"); #include "cio.h" #include "database.h" #include "directn.h" +#include "los.h" #include "message.h" #include "misc.h" #include "monplace.h" diff --git a/crawl-ref/source/terrain.cc b/crawl-ref/source/terrain.cc index cdd0ef6a43..5d831713bb 100644 --- a/crawl-ref/source/terrain.cc +++ b/crawl-ref/source/terrain.cc @@ -18,6 +18,7 @@ REVISION("$Rev$"); #include "directn.h" #include "itemprop.h" #include "items.h" +#include "los.h" #include "message.h" #include "misc.h" #include "monplace.h" diff --git a/crawl-ref/source/traps.cc b/crawl-ref/source/traps.cc index 93b838a9a6..398c2c0625 100644 --- a/crawl-ref/source/traps.cc +++ b/crawl-ref/source/traps.cc @@ -22,6 +22,7 @@ REVISION("$Rev$"); #include "itemname.h" #include "itemprop.h" #include "items.h" +#include "los.h" #include "makeitem.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/travel.cc b/crawl-ref/source/travel.cc index 8531fd2ca1..8b62fbbbc5 100644 --- a/crawl-ref/source/travel.cc +++ b/crawl-ref/source/travel.cc @@ -24,6 +24,7 @@ REVISION("$Rev$"); #include "itemname.h" #include "itemprop.h" #include "items.h" +#include "los.h" #include "message.h" #include "misc.h" #include "mon-util.h" diff --git a/crawl-ref/source/tutorial.cc b/crawl-ref/source/tutorial.cc index 9bd6d898df..7844de77c7 100644 --- a/crawl-ref/source/tutorial.cc +++ b/crawl-ref/source/tutorial.cc @@ -30,6 +30,7 @@ REVISION("$Rev$"); #include "itemprop.h" #include "items.h" #include "kills.h" +#include "los.h" #include "menu.h" #include "message.h" #include "misc.h" diff --git a/crawl-ref/source/view.cc b/crawl-ref/source/view.cc index c41dc758ef..5fea829d23 100644 --- a/crawl-ref/source/view.cc +++ b/crawl-ref/source/view.cc @@ -35,6 +35,7 @@ REVISION("$Rev$"); #include "ghost.h" #include "initfile.h" #include "itemprop.h" +#include "los.h" #include "luadgn.h" #include "macro.h" #include "message.h" @@ -78,14 +79,6 @@ REVISION("$Rev$"); #define MC_ITEM 0x01 #define MC_MONS 0x02 -// Static class members must be initialised outside of the class -// declaration, or gcc won't define them in view.o and we'll get a -// linking error. -const int monster_los::LSIZE = _monster_los_LSIZE; -const int monster_los::L_VISIBLE = 1; -const int monster_los::L_UNKNOWN = 0; -const int monster_los::L_BLOCKED = -1; - static FixedVector<feature_def, NUM_FEATURES> Feature; crawl_view_geometry crawl_view; @@ -1935,1141 +1928,6 @@ void blood_smell( int strength, const coord_def& where ) } } -// The LOS code now uses raycasting -- haranp - -#define LONGSIZE (sizeof(unsigned long)*8) -#define LOS_MAX_RANGE_X 9 -#define LOS_MAX_RANGE_Y 9 -#define LOS_MAX_RANGE 9 - -// the following two constants represent the 'middle' of the sh array. -// since the current shown area is 19x19, centering the view at (9,9) -// means it will be exactly centered. -// This is done to accomodate possible future changes in viewable screen -// area - simply change sh_xo and sh_yo to the new view center. - -const int sh_xo = 9; // X and Y origins for the sh array -const int sh_yo = 9; - -// Data used for the LOS algorithm -int los_radius_squared = 8*8 + 1; - -unsigned long* los_blockrays = NULL; -unsigned long* dead_rays = NULL; -unsigned long* smoke_rays = NULL; -std::vector<short> ray_coord_x; -std::vector<short> ray_coord_y; -std::vector<short> compressed_ray_x; -std::vector<short> compressed_ray_y; -std::vector<int> raylengths; -std::vector<ray_def> fullrays; - -void clear_rays_on_exit() -{ - delete[] dead_rays; - delete[] smoke_rays; - delete[] los_blockrays; -} - -void setLOSRadius(int newLR) -{ - los_radius_squared = newLR * newLR + 1*1; -} - -bool get_bit_in_long_array( const unsigned long* data, int where ) -{ - int wordloc = where / LONGSIZE; - int bitloc = where % LONGSIZE; - return ((data[wordloc] & (1UL << bitloc)) != 0); -} - -static void _set_bit_in_long_array( unsigned long* data, int where ) -{ - int wordloc = where / LONGSIZE; - int bitloc = where % LONGSIZE; - data[wordloc] |= (1UL << bitloc); -} - -#define EPSILON_VALUE 0.00001 -bool double_is_zero( const double x ) -{ - return (x > -EPSILON_VALUE) && (x < EPSILON_VALUE); -} - -// note that slope must be nonnegative! -// returns 0 if the advance was in x, 1 if it was in y, 2 if it was -// the diagonal -static int _find_next_intercept(double* accx, double* accy, const double slope) -{ - - // handle perpendiculars - if ( double_is_zero(slope) ) - { - *accx += 1.0; - return 0; - } - if ( slope > 100.0 ) - { - *accy += 1.0; - return 1; - } - - const double xtarget = (static_cast<int>(*accx) + 1); - const double ytarget = (static_cast<int>(*accy) + 1); - const double xdistance = xtarget - *accx; - const double ydistance = ytarget - *accy; - double distdiff = (xdistance * slope - ydistance); - - // exact corner - if ( double_is_zero( distdiff ) ) - { - // move somewhat away from the corner - if ( slope > 1.0 ) - { - *accx = xtarget + EPSILON_VALUE * 2; - *accy = ytarget + EPSILON_VALUE * 2 * slope; - } - else - { - *accx = xtarget + EPSILON_VALUE * 2 / slope; - *accy = ytarget + EPSILON_VALUE * 2; - } - return 2; - } - - // move to the boundary - double traveldist; - int rc = -1; - if ( distdiff > 0.0 ) - { - traveldist = ydistance / slope; - rc = 1; - } - else - { - traveldist = xdistance; - rc = 0; - } - - // and a little into the next cell, taking care - // not to go too far - if ( distdiff < 0.0 ) - distdiff = -distdiff; - traveldist += std::min(EPSILON_VALUE * 10.0, 0.5 * distdiff / slope); - - *accx += traveldist; - *accy += traveldist * slope; - return rc; -} - -ray_def::ray_def() : accx(0.0), accy(0.0), slope(0.0), quadrant(0), - fullray_idx(0) -{ -} - -double ray_def::reflect(double p, double c) const -{ - return (c + c - p); -} - -double ray_def::reflect(bool rx, double oldx, double newx) const -{ - if (rx? fabs(slope) > 1.0 : fabs(slope) < 1.0) - return (reflect(oldx, floor(oldx) + 0.5)); - - const double flnew = floor(newx); - const double flold = floor(oldx); - return (reflect(oldx, - flnew > flold? flnew : - flold > flnew? flold : - (newx + oldx) / 2)); -} - -void ray_def::set_reflect_point(const double oldx, const double oldy, - double *newx, double *newy, - bool blocked_x, bool blocked_y) -{ - if (blocked_x == blocked_y) - { - // What to do? - *newx = oldx; - *newy = oldy; - return; - } - - if (blocked_x) - { - ASSERT(int(oldy) != int(*newy)); - *newy = oldy; - *newx = reflect(true, oldx, *newx); - } - else - { - ASSERT(int(oldx) != int(*newx)); - *newx = oldx; - *newy = reflect(false, oldy, *newy); - } -} - -void ray_def::advance_and_bounce() -{ - // 0 = down-right, 1 = down-left, 2 = up-left, 3 = up-right - int bouncequad[4][3] = - { - { 1, 3, 2 }, { 0, 2, 3 }, { 3, 1, 0 }, { 2, 0, 1 } - }; - int oldx = x(), oldy = y(); - const double oldaccx = accx, oldaccy = accy; - int rc = advance(false); - int newx = x(), newy = y(); - ASSERT( grid_is_solid(grd[newx][newy]) ); - - const bool blocked_x = grid_is_solid(grd[oldx][newy]); - const bool blocked_y = grid_is_solid(grd[newx][oldy]); - - if ( double_is_zero(slope) || slope > 100.0 ) - quadrant = bouncequad[quadrant][2]; - else if ( rc != 2 ) - quadrant = bouncequad[quadrant][rc]; - else - { - ASSERT( (oldx != newx) && (oldy != newy) ); - if ( blocked_x && blocked_y ) - quadrant = bouncequad[quadrant][rc]; - else if ( blocked_x ) - quadrant = bouncequad[quadrant][1]; - else - quadrant = bouncequad[quadrant][0]; - } - - set_reflect_point(oldaccx, oldaccy, &accx, &accy, blocked_x, blocked_y); -} - -double ray_def::get_degrees() const -{ - if (slope > 100.0) - { - if (quadrant == 3 || quadrant == 2) - return (90.0); - else - return (270.0); - } - else if (double_is_zero(slope)) - { - if (quadrant == 0 || quadrant == 3) - return (0.0); - else - return (180.0); - } - - double deg = atan(slope) * 180.0 / M_PI; - - switch (quadrant) - { - case 0: - return (360.0 - deg); - - case 1: - return (180.0 + deg); - - case 2: - return (180.0 - deg); - - case 3: - return (deg); - } - ASSERT(!"ray has illegal quadrant"); - return (0.0); -} - -void ray_def::set_degrees(double deg) -{ - while (deg < 0.0) - deg += 360.0; - while (deg >= 360.0) - deg -= 360.0; - - double _slope = tan(deg / 180.0 * M_PI); - - if (double_is_zero(_slope)) - { - slope = 0.0; - - if (deg < 90.0 || deg > 270.0) - quadrant = 0; // right/east - else - quadrant = 1; // left/west - } - else if (_slope > 0) - { - slope = _slope; - - if (deg >= 180.0 && deg <= 270.0) - quadrant = 1; - else - quadrant = 3; - } - else - { - slope = -_slope; - - if (deg >= 90 && deg <= 180) - quadrant = 2; - else - quadrant = 0; - } - - if (slope > 1000.0) - slope = 1000.0; -} - -void ray_def::regress() -{ - int opp_quadrant[4] = { 2, 3, 0, 1 }; - quadrant = opp_quadrant[quadrant]; - advance(false); - quadrant = opp_quadrant[quadrant]; -} - -int ray_def::advance_through(const coord_def &target) -{ - return (advance(true, &target)); -} - -int ray_def::advance(bool shortest_possible, const coord_def *target) -{ - if (!shortest_possible) - return (raw_advance()); - - // If we want to minimise the number of moves on the ray, look one - // step ahead and see if we can get a diagonal. - - const coord_def old(static_cast<int>(accx), static_cast<int>(accy)); - const int ret = raw_advance(); - - if (ret == 2 || (target && pos() == *target)) - return (ret); - - const double maccx = accx, maccy = accy; - if (raw_advance() != 2) - { - const coord_def second(static_cast<int>(accx), static_cast<int>(accy)); - // If we can convert to a diagonal, do so. - if ((second - old).abs() == 2) - return (2); - } - - // No diagonal, so roll back. - accx = maccx; - accy = maccy; - - return (ret); -} - -int ray_def::raw_advance() -{ - int rc; - switch ( quadrant ) - { - case 0: - // going down-right - rc = _find_next_intercept( &accx, &accy, slope ); - return rc; - case 1: - // going down-left - accx = 100.0 - EPSILON_VALUE/10.0 - accx; - rc = _find_next_intercept( &accx, &accy, slope ); - accx = 100.0 - EPSILON_VALUE/10.0 - accx; - return rc; - case 2: - // going up-left - accx = 100.0 - EPSILON_VALUE/10.0 - accx; - accy = 100.0 - EPSILON_VALUE/10.0 - accy; - rc = _find_next_intercept( &accx, &accy, slope ); - accx = 100.0 - EPSILON_VALUE/10.0 - accx; - accy = 100.0 - EPSILON_VALUE/10.0 - accy; - return rc; - case 3: - // going up-right - accy = 100.0 - EPSILON_VALUE/10.0 - accy; - rc = _find_next_intercept( &accx, &accy, slope ); - accy = 100.0 - EPSILON_VALUE/10.0 - accy; - return rc; - default: - return -1; - } -} - -// Shoot a ray from the given start point (accx, accy) with the given -// slope, with a maximum distance (in either x or y coordinate) of -// maxrange. Store the visited cells in xpos[] and ypos[], and -// return the number of cells visited. -static int _shoot_ray( double accx, double accy, const double slope, - int maxrange, int xpos[], int ypos[] ) -{ - int curx, cury; - int cellnum; - for (cellnum = 0; true; ++cellnum) - { - _find_next_intercept( &accx, &accy, slope ); - curx = static_cast<int>(accx); - cury = static_cast<int>(accy); - if (curx*curx + cury*cury > los_radius_squared) - break; - - // Work with the new square. - xpos[cellnum] = curx; - ypos[cellnum] = cury; - } - return cellnum; -} - -// Check if the passed ray has already been created. -static bool _is_duplicate_ray( int len, int xpos[], int ypos[] ) -{ - int cur_offset = 0; - for (unsigned int i = 0; i < raylengths.size(); ++i) - { - // Only compare equal-length rays. - if (raylengths[i] != len) - { - cur_offset += raylengths[i]; - continue; - } - - int j; - for (j = 0; j < len; ++j) - { - if (ray_coord_x[j + cur_offset] != xpos[j] - || ray_coord_y[j + cur_offset] != ypos[j]) - { - break; - } - } - - // Exact duplicate? - if (j == len) - return (true); - - // Move to beginning of next ray. - cur_offset += raylengths[i]; - } - return (false); -} - -// Is starta...lengtha a subset of startb...lengthb? -static bool _is_subset( int starta, int startb, int lengtha, int lengthb ) -{ - int cura = starta, curb = startb; - int enda = starta + lengtha, endb = startb + lengthb; - - while (cura < enda && curb < endb) - { - if (ray_coord_x[curb] > ray_coord_x[cura]) - return (false); - if (ray_coord_y[curb] > ray_coord_y[cura]) - return (false); - - if (ray_coord_x[cura] == ray_coord_x[curb] - && ray_coord_y[cura] == ray_coord_y[curb]) - { - ++cura; - } - - ++curb; - } - - return (cura == enda); -} - -// Returns a vector which lists all the nonduped cellrays (by index). -static std::vector<int> _find_nonduped_cellrays() -{ - // A cellray c in a fullray f is duped if there is a fullray g - // such that g contains c and g[:c] is a subset of f[:c]. - int raynum, cellnum, curidx, testidx, testray, testcell; - bool is_duplicate; - - std::vector<int> result; - for (curidx = 0, raynum = 0; - raynum < static_cast<int>(raylengths.size()); - curidx += raylengths[raynum++]) - { - for (cellnum = 0; cellnum < raylengths[raynum]; ++cellnum) - { - // Is the cellray raynum[cellnum] duplicated? - is_duplicate = false; - // XXX: We should really check everything up to now - // completely, and all further rays to see if they're - // proper subsets. - const int curx = ray_coord_x[curidx + cellnum]; - const int cury = ray_coord_y[curidx + cellnum]; - for (testidx = 0, testray = 0; testray < raynum; - testidx += raylengths[testray++]) - { - // Scan ahead to see if there's an intersect. - for (testcell = 0; testcell < raylengths[raynum]; ++testcell) - { - const int testx = ray_coord_x[testidx + testcell]; - const int testy = ray_coord_y[testidx + testcell]; - // We can short-circuit sometimes. - if (testx > curx || testy > cury) - break; - - // Bingo! - if (testx == curx && testy == cury) - { - is_duplicate = _is_subset(testidx, curidx, - testcell, cellnum); - break; - } - } - if (is_duplicate) - break; // No point in checking further rays. - } - if (!is_duplicate) - result.push_back(curidx + cellnum); - } - } - return result; -} - -// Create and register the ray defined by the arguments. -// Return true if the ray was actually registered (i.e., not a duplicate.) -static bool _register_ray( double accx, double accy, double slope ) -{ - int xpos[LOS_MAX_RANGE * 2 + 1], ypos[LOS_MAX_RANGE * 2 + 1]; - int raylen = _shoot_ray( accx, accy, slope, LOS_MAX_RANGE, xpos, ypos ); - - // Early out if ray already exists. - if (_is_duplicate_ray(raylen, xpos, ypos)) - return (false); - - // Not duplicate, register. - for (int i = 0; i < raylen; ++i) - { - // Create the cellrays. - ray_coord_x.push_back(xpos[i]); - ray_coord_y.push_back(ypos[i]); - } - - // Register the fullray. - raylengths.push_back(raylen); - ray_def ray; - ray.accx = accx; - ray.accy = accy; - ray.slope = slope; - ray.quadrant = 0; - fullrays.push_back(ray); - - return (true); -} - -static void _create_blockrays() -{ - // determine nonduplicated rays - std::vector<int> nondupe_cellrays = _find_nonduped_cellrays(); - const unsigned int num_nondupe_rays = nondupe_cellrays.size(); - const unsigned int num_nondupe_words = - (num_nondupe_rays + LONGSIZE - 1) / LONGSIZE; - const unsigned int num_cellrays = ray_coord_x.size(); - const unsigned int num_words = (num_cellrays + LONGSIZE - 1) / LONGSIZE; - - // first build all the rays: easier to do blocking calculations there - unsigned long* full_los_blockrays; - full_los_blockrays = new unsigned long[num_words * (LOS_MAX_RANGE_X+1) * - (LOS_MAX_RANGE_Y+1)]; - memset((void*)full_los_blockrays, 0, sizeof(unsigned long) * num_words * - (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y+1)); - - int cur_offset = 0; - - for (unsigned int ray = 0; ray < raylengths.size(); ++ray) - { - for (int i = 0; i < raylengths[ray]; ++i) - { - // every cell blocks... - unsigned long* const inptr = full_los_blockrays + - (ray_coord_x[i + cur_offset] * (LOS_MAX_RANGE_Y + 1) + - ray_coord_y[i + cur_offset]) * num_words; - - // ...all following cellrays - for (int j = i+1; j < raylengths[ray]; ++j) - _set_bit_in_long_array( inptr, j + cur_offset ); - - } - cur_offset += raylengths[ray]; - } - - // we've built the basic blockray array; now compress it, keeping - // only the nonduplicated cellrays. - - // allocate and clear memory - los_blockrays = new unsigned long[num_nondupe_words * (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y + 1)]; - memset((void*)los_blockrays, 0, sizeof(unsigned long) * num_nondupe_words * - (LOS_MAX_RANGE_X+1) * (LOS_MAX_RANGE_Y+1)); - - // we want to only keep the cellrays from nondupe_cellrays. - compressed_ray_x.resize(num_nondupe_rays); - compressed_ray_y.resize(num_nondupe_rays); - for (unsigned int i = 0; i < num_nondupe_rays; ++i) - { - compressed_ray_x[i] = ray_coord_x[nondupe_cellrays[i]]; - compressed_ray_y[i] = ray_coord_y[nondupe_cellrays[i]]; - } - unsigned long* oldptr = full_los_blockrays; - unsigned long* newptr = los_blockrays; - for (int x = 0; x <= LOS_MAX_RANGE_X; ++x) - for (int y = 0; y <= LOS_MAX_RANGE_Y; ++y) - { - for (unsigned int i = 0; i < num_nondupe_rays; ++i) - if (get_bit_in_long_array(oldptr, nondupe_cellrays[i])) - _set_bit_in_long_array(newptr, i); - - oldptr += num_words; - newptr += num_nondupe_words; - } - - // we can throw away full_los_blockrays now - delete[] full_los_blockrays; - - dead_rays = new unsigned long[num_nondupe_words]; - smoke_rays = new unsigned long[num_nondupe_words]; - -#ifdef DEBUG_DIAGNOSTICS - mprf( MSGCH_DIAGNOSTICS, "Cellrays: %d Fullrays: %u Compressed: %u", - num_cellrays, raylengths.size(), num_nondupe_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( 0.5, 0.5, 1000.0 ); - _register_ray( 0.5, 0.5, 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 <= 2*LOS_MAX_RANGE; ++xangle ) - for ( int yangle = 1; yangle <= 2*LOS_MAX_RANGE; ++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; - - const double slope = ((double)(yangle)) / xangle; - const double rslope = ((double)(xangle)) / yangle; - for ( int intercept = 1; intercept <= 2*yangle; ++intercept ) - { - double xstart = ((double)(intercept)) / (2*yangle); - double ystart = 1; - - // now move back just inside the cell - // y should be "about to change" - xstart -= EPSILON_VALUE * xangle; - ystart -= EPSILON_VALUE * yangle; - - _register_ray( xstart, ystart, slope ); - // also draw the identical ray in octant 2 - _register_ray( ystart, xstart, rslope ); - } - } - - // Now create the appropriate blockrays array - _create_blockrays(); -} - -static void _set_ray_quadrant( ray_def& ray, int sx, int sy, int tx, int ty ) -{ - if ( tx >= sx && ty >= sy ) - ray.quadrant = 0; - else if ( tx < sx && ty >= sy ) - ray.quadrant = 1; - else if ( tx < sx && ty < sy ) - ray.quadrant = 2; - else if ( tx >= sx && ty < sy ) - ray.quadrant = 3; - else - mpr("Bad ray quadrant!", MSGCH_DIAGNOSTICS); -} - -static int _cyclic_offset( unsigned int ui, int cycle_dir, int startpoint, - int maxvalue ) -{ - const int i = (int)ui; - if ( startpoint < 0 ) - return i; - switch ( cycle_dir ) - { - case 1: - return (i + startpoint + 1) % maxvalue; - case -1: - return (i - 1 - startpoint + maxvalue) % maxvalue; - case 0: - default: - return i; - } -} - -static const double VERTICAL_SLOPE = 10000.0; -static double _calc_slope(double x, double y) -{ - if (double_is_zero(x)) - return (VERTICAL_SLOPE); - - const double slope = y / x; - return (slope > VERTICAL_SLOPE? VERTICAL_SLOPE : slope); -} - -static double _slope_factor(const ray_def &ray) -{ - double xdiff = fabs(ray.accx - 0.5), ydiff = fabs(ray.accy - 0.5); - - if (double_is_zero(xdiff) && double_is_zero(ydiff)) - return ray.slope; - - const double slope = _calc_slope(ydiff, xdiff); - return (slope + ray.slope) / 2.0; -} - -static bool _superior_ray(int shortest, int imbalance, - int raylen, int rayimbalance, - double slope_diff, double ray_slope_diff) -{ - if (shortest != raylen) - return (shortest > raylen); - - if (imbalance != rayimbalance) - return (imbalance > rayimbalance); - - return (slope_diff > ray_slope_diff); -} - -// 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 allow_fallback is true, fall back to a center-to-center ray -// if range is too great or all rays are blocked. -// If cycle_dir is 0, find the first fitting ray. If it is 1 or -1, -// assume that ray is appropriately filled in, and look for the next -// ray in that cycle direction. -// If find_shortest is true, examine all rays that hit the target and -// take the shortest (starting at ray.fullray_idx). - -bool find_ray( const coord_def& source, const coord_def& target, - bool allow_fallback, ray_def& ray, int cycle_dir, - bool find_shortest, bool ignore_solid ) -{ - int cellray, inray; - - const int sourcex = source.x; - const int sourcey = source.y; - const int targetx = target.x; - const int targety = target.y; - - const int signx = ((targetx - sourcex >= 0) ? 1 : -1); - const int signy = ((targety - sourcey >= 0) ? 1 : -1); - const int absx = signx * (targetx - sourcex); - const int absy = signy * (targety - sourcey); - - int cur_offset = 0; - int shortest = INFINITE_DISTANCE; - int imbalance = INFINITE_DISTANCE; - const double want_slope = _calc_slope(absx, absy); - double slope_diff = VERTICAL_SLOPE * 10.0; - std::vector<coord_def> unaliased_ray; - - for ( unsigned int fray = 0; fray < fullrays.size(); ++fray ) - { - const int fullray = _cyclic_offset( fray, cycle_dir, ray.fullray_idx, - fullrays.size() ); - // Yeah, yeah, this is O(n^2). I know. - cur_offset = 0; - for (int i = 0; i < fullray; ++i) - cur_offset += raylengths[i]; - - for (cellray = 0; cellray < raylengths[fullray]; ++cellray) - { - if (ray_coord_x[cellray + cur_offset] == absx - && ray_coord_y[cellray + cur_offset] == absy) - { - if (find_shortest) - { - unaliased_ray.clear(); - unaliased_ray.push_back(coord_def(0, 0)); - } - - // Check if we're blocked so far. - bool blocked = false; - coord_def c1, c3; - int real_length = 0; - for (inray = 0; inray <= cellray; ++inray) - { - const int xi = signx * ray_coord_x[inray + cur_offset]; - const int yi = signy * ray_coord_y[inray + cur_offset]; - if (inray < cellray && !ignore_solid - && grid_is_solid(grd[sourcex + xi][sourcey + yi])) - { - blocked = true; - break; - } - - if (find_shortest) - { - c3 = coord_def(xi, yi); - - // We've moved at least two steps if inray > 0. - if (inray) - { - // Check for a perpendicular corner on the ray and - // pretend that it's a diagonal. - if ((c3 - c1).abs() != 2) - ++real_length; - else - { - // c2 was a dud move, pop it off - unaliased_ray.pop_back(); - } - } - else - ++real_length; - - unaliased_ray.push_back(c3); - c1 = unaliased_ray[real_length - 1]; - } - } - - int cimbalance = 0; - // If this ray is a candidate for shortest, calculate - // the imbalance. I'm defining 'imbalance' as the - // number of consecutive diagonal or orthogonal moves - // in the ray. This is a reasonable measure of deviation from - // the Bresenham line between our selected source and - // destination. - if (!blocked && find_shortest && shortest >= real_length) - { - int diags = 0, straights = 0; - for (int i = 1, size = unaliased_ray.size(); i < size; ++i) - { - const int dist = - (unaliased_ray[i] - unaliased_ray[i - 1]).abs(); - - if (dist == 2) - { - straights = 0; - if (++diags > cimbalance) - cimbalance = diags; - } - else - { - diags = 0; - if (++straights > cimbalance) - cimbalance = straights; - } - } - } - - const double ray_slope_diff = find_shortest ? - fabs(_slope_factor(fullrays[fullray]) - want_slope) : 0.0; - - if (!blocked - && (!find_shortest - || _superior_ray(shortest, imbalance, - real_length, cimbalance, - slope_diff, ray_slope_diff))) - { - // Success! - ray = fullrays[fullray]; - ray.fullray_idx = fullray; - - shortest = real_length; - imbalance = cimbalance; - slope_diff = ray_slope_diff; - - if (sourcex > targetx) - ray.accx = 1.0 - ray.accx; - if (sourcey > targety) - ray.accy = 1.0 - ray.accy; - - ray.accx += sourcex; - ray.accy += sourcey; - - _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety); - if (!find_shortest) - return (true); - } - } - } - } - - if (find_shortest && shortest != INFINITE_DISTANCE) - return (true); - - if (allow_fallback) - { - ray.accx = sourcex + 0.5; - ray.accy = sourcey + 0.5; - if (targetx == sourcex) - ray.slope = VERTICAL_SLOPE; - else - { - ray.slope = targety - sourcey; - ray.slope /= targetx - sourcex; - if (ray.slope < 0) - ray.slope = -ray.slope; - } - _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety); - ray.fullray_idx = -1; - return (true); - } - return (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); - - ray.fullray_idx = -1; // to quiet valgrind - - // We don't need to find the shortest beam, any beam will suffice. - find_ray( source, target, true, ray, 0, false, true ); - - if (exclude_endpoints && ray.pos() == source) - { - ray.advance(true); - 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(true); - } - - return (count); -} - -// The rule behind LOS is: -// Two cells can see each other if there is any line from some point -// of the first to some point of the second ("generous" LOS.) -// -// 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(env_show_grid &sh, - feature_grid &gr, const coord_def& center, - bool clear_walls_block, bool ignore_clouds) -{ - raycast(); - const int x_p = center.x; - const int y_p = center.y; - // go quadrant by quadrant - const int quadrant_x[4] = { 1, -1, -1, 1 }; - const int quadrant_y[4] = { 1, 1, -1, -1 }; - - // clear out sh - sh.init(0); - - if (crawl_state.arena || crawl_state.arena_suspended) - { - for (int y = -ENV_SHOW_OFFSET; y <= ENV_SHOW_OFFSET; ++y) - for (int x = -ENV_SHOW_OFFSET; x <= ENV_SHOW_OFFSET; ++x) - { - const coord_def pos = center + coord_def(x, y); - if (map_bounds(pos)) - sh[x + sh_xo][y + sh_yo] = gr(pos); - } - return; - } - - const unsigned int num_cellrays = compressed_ray_x.size(); - const unsigned int num_words = (num_cellrays + LONGSIZE - 1) / LONGSIZE; - - for (int quadrant = 0; quadrant < 4; ++quadrant) - { - const int xmult = quadrant_x[quadrant]; - const int ymult = quadrant_y[quadrant]; - - // clear out the dead rays array - memset( (void*)dead_rays, 0, sizeof(unsigned long) * num_words); - memset( (void*)smoke_rays, 0, sizeof(unsigned long) * num_words); - - // kill all blocked rays - const unsigned long* inptr = los_blockrays; - - for (int xdiff = 0; xdiff <= LOS_MAX_RANGE_X; ++xdiff) - for (int ydiff = 0; ydiff <= LOS_MAX_RANGE_Y; - ++ydiff, inptr += num_words) - { - - const int realx = x_p + xdiff * xmult; - const int realy = y_p + ydiff * ymult; - - if (!map_bounds(realx, realy)) - continue; - - coord_def real(realx, realy); - dungeon_feature_type dfeat = grid_appearance(gr, real); - - // if this cell is opaque... - // ... or something you can see but not walk through ... - if (grid_is_opaque(dfeat) - || clear_walls_block && dfeat < DNGN_MINMOVE) - { - // then block the appropriate rays - for (unsigned int i = 0; i < num_words; ++i) - dead_rays[i] |= inptr[i]; - } - else if (!ignore_clouds - && is_opaque_cloud(env.cgrid[realx][realy])) - { - // block rays which have already seen a cloud - for (unsigned int i = 0; i < num_words; ++i) - { - dead_rays[i] |= (smoke_rays[i] & inptr[i]); - smoke_rays[i] |= inptr[i]; - } - } - } - - // ray calculation done, now work out which cells in this - // quadrant are visible - unsigned int rayidx = 0; - for (unsigned int wordloc = 0; wordloc < num_words; ++wordloc) - { - const unsigned long curword = dead_rays[wordloc]; - // Note: the last word may be incomplete - for (unsigned int bitloc = 0; bitloc < LONGSIZE; ++bitloc) - { - // make the cells seen by this ray at this point visible - if ( ((curword >> bitloc) & 1UL) == 0 ) - { - // this ray is alive! - const int realx = xmult * compressed_ray_x[rayidx]; - const int realy = ymult * compressed_ray_y[rayidx]; - // update shadow map - if (x_p + realx >= 0 && x_p + realx < GXM - && y_p + realy >= 0 && y_p + realy < GYM - && realx * realx + realy * realy <= los_radius_squared) - { - sh[sh_xo+realx][sh_yo+realy] = gr[x_p+realx][y_p+realy]; - } - } - ++rayidx; - if (rayidx == num_cellrays) - break; - } - } - } - - // [dshaligram] The player's current position is always visible. - sh[sh_xo][sh_yo] = gr[x_p][y_p]; - - *dead_rays = NULL; - *smoke_rays = NULL; - *los_blockrays = NULL; -} - // Determines if the given feature is present at (x, y) in _grid_ coordinates. // If you have map coords, add (1, 1) to get grid coords. @@ -4138,65 +2996,6 @@ bool mon_enemies_around(const monsters *monster) } } -bool see_grid( const env_show_grid &show, - const coord_def &c, - const coord_def &pos ) -{ - if (c == pos) - return (true); - - const coord_def ip = pos - c; - if (ip.rdist() < ENV_SHOW_OFFSET) - { - const coord_def sp(ip + coord_def(ENV_SHOW_OFFSET, ENV_SHOW_OFFSET)); - if (show(sp)) - return (true); - } - return (false); -} - -// Answers the question: "Is a grid within character's line of sight?" -bool see_grid( const coord_def &p ) -{ - return ((crawl_state.arena || crawl_state.arena_suspended) - && crawl_view.in_grid_los(p)) - || see_grid(env.show, you.pos(), p); -} - -// Answers the question: "Would a grid be within character's line of sight, -// even if all translucent/clear walls were made opaque?" -bool see_grid_no_trans( const coord_def &p ) -{ - return see_grid(env.no_trans_show, you.pos(), p); -} - -// Is the grid visible, but a translucent wall is in the way? -bool trans_wall_blocking( const coord_def &p ) -{ - return see_grid(p) && !see_grid_no_trans(p); -} - -// Usually calculates whether from one grid someone could see the other. -// Depending on the viewer's habitat, 'allowed' can be set to DNGN_FLOOR, -// DNGN_SHALLOW_WATER or DNGN_DEEP_WATER. -// Yes, this ignores lava-loving monsters. -// XXX: It turns out the beams are not symmetrical, i.e. switching -// pos1 and pos2 may result in small variations. -bool grid_see_grid(const coord_def& p1, const coord_def& p2, - dungeon_feature_type allowed) -{ - if (distance(p1, p2) > los_radius_squared) - return (false); - - dungeon_feature_type max_disallowed = DNGN_MAXOPAQUE; - if (allowed != DNGN_UNSEEN) - max_disallowed = static_cast<dungeon_feature_type>(allowed - 1); - - // XXX: Ignoring clouds for now. - return (!num_feats_between(p1, p2, DNGN_UNSEEN, max_disallowed, - true, true)); -} - // For order and meaning of symbols, see dungeon_char_type in enum.h. static const unsigned dchar_table[ NUM_CSET ][ NUM_DCHAR_TYPES ] = { @@ -5256,23 +4055,6 @@ static void _debug_pane_bounds() #endif } -void calc_show_los() -{ - if (!crawl_state.arena && !crawl_state.arena_suspended) - { - // Must be done first. - losight(env.show, grd, you.pos()); - - // What would be visible, if all of the translucent walls were - // made opaque. - losight(env.no_trans_show, grd, you.pos(), true); - } - else - { - losight(env.show, grd, crawl_view.glosc()); - } -} - //--------------------------------------------------------------- // // viewwindow -- now unified and rolled into a single pass @@ -5987,389 +4769,3 @@ void handle_terminal_resize(bool redraw) redraw_screen(); } -///////////////////////////////////////////////////////////////////////////// -// monster_los - -monster_los::monster_los() - : gridx(0), gridy(0), mons(), range(LOS_RADIUS), los_field() -{ -} - -monster_los::~monster_los() -{ -} - -void monster_los::set_monster(monsters *mon) -{ - mons = mon; - set_los_centre(mon->pos()); -} - -void monster_los::set_los_centre(int x, int y) -{ - if (!in_bounds(x, y)) - return; - - gridx = x; - gridy = y; -} - -void monster_los::set_los_range(int r) -{ - ASSERT (r >= 1 && r <= LOS_RADIUS); - range = r; -} - -coord_def monster_los::pos_to_index(coord_def &p) -{ - int ix = LOS_RADIUS + p.x - gridx; - int iy = LOS_RADIUS + p.y - gridy; - - ASSERT(ix >= 0 && ix < LSIZE); - ASSERT(iy >= 0 && iy < LSIZE); - - return (coord_def(ix, iy)); -} - -coord_def monster_los::index_to_pos(coord_def &i) -{ - int px = i.x + gridx - LOS_RADIUS; - int py = i.y + gridy - LOS_RADIUS; - - ASSERT(in_bounds(px, py)); - return (coord_def(px, py)); -} - -void monster_los::set_los_value(int x, int y, bool blocked, bool override) -{ - if (!override && !is_unknown(x,y)) - return; - - coord_def c(x,y); - coord_def lpos = pos_to_index(c); - - int value = (blocked ? L_BLOCKED : L_VISIBLE); - - if (value != los_field[lpos.x][lpos.y]) - los_field[lpos.x][lpos.y] = value; -} - -int monster_los::get_los_value(int x, int y) -{ - // Too far away -> definitely out of sight! - if (distance(x, y, gridx, gridy) > los_radius_squared) - return (L_BLOCKED); - - coord_def c(x,y); - coord_def lpos = pos_to_index(c); - return (los_field[lpos.x][lpos.y]); -} - -bool monster_los::in_sight(int x, int y) -{ - // Is the path to (x,y) clear? - return (get_los_value(x,y) == L_VISIBLE); -} - -bool monster_los::is_blocked(int x, int y) -{ - // Is the path to (x,y) blocked? - return (get_los_value(x, y) == L_BLOCKED); -} - -bool monster_los::is_unknown(int x, int y) -{ - return (get_los_value(x, y) == L_UNKNOWN); -} - -static bool _blocks_movement_sight(monsters *mon, dungeon_feature_type feat) -{ - if (feat < DNGN_MINMOVE) - return (true); - - if (!mon) // No monster defined? - return (false); - - if (!mon->can_pass_through_feat(feat)) - return (true); - - return (false); -} - -void monster_los::fill_los_field() -{ - int pos_x, pos_y; - for (int k = 1; k <= range; k++) - for (int i = -1; i <= 1; i++) - for (int j = -1; j <= 1; j++) - { - if (i == 0 && j == 0) // Ignore centre grid. - continue; - - pos_x = gridx + k*i; - pos_y = gridy + k*j; - - if (!in_bounds(pos_x, pos_y)) - continue; - - if (!_blocks_movement_sight(mons, grd[pos_x][pos_y])) - set_los_value(pos_x, pos_y, false); - else - { - set_los_value(pos_x, pos_y, true); - // Check all beam potentially going through a blocked grid. - check_los_beam(pos_x, pos_y); - } - } -} - -// (cx, cy) is the centre point -// (dx, dy) is the target we're aiming *through* -// target1 and target2 are targets we'll be aiming *at* to fire through (dx,dy) -static bool _set_beam_target(int cx, int cy, int dx, int dy, - int &target1_x, int &target1_y, - int &target2_x, int &target2_y, - int range) -{ - const int xdist = dx - cx; - const int ydist = dy - cy; - - if (xdist == 0 && ydist == 0) - return (false); // Nothing to be done. - - if (xdist <= -range || xdist >= range - || ydist <= -range || ydist >= range) - { - // Grids on the edge of a monster's LOS don't block sight any further. - return (false); - } - -/* - * The following code divides the field into eights of different directions. - * - * \ NW | NE / - * \ | / - * WN \ | / EN - * ---------------- - * WS / | \ ES - * / | \ - * / SW | SE \ - * - * target1_x and target1_y mark the base line target, so the base beam ends - * on the diagonal line closest to the target (or on one of the straight - * lines if cx == dx or dx == dy). - * - * target2_x and target2_y then mark the second target our beam finder should - * cycle through. It'll always be target2_x = dx or target2_y = dy, the other - * being on the edge of LOS, which one depending on the quadrant. - * - * The beam finder can then cycle from the nearest corner (target1) to the - * second edge target closest to (dx,dy). - */ - - if (xdist == 0) - { - target1_x = cx; - target1_y = (ydist > 0 ? cy + range - : cy - range); - - target2_x = target1_x; - target2_y = target1_y; - } - else if (ydist == 0) - { - target1_x = (xdist > 0 ? cx + range - : cx - range); - target1_y = cy; - - target2_x = target1_x; - target2_y = target1_y; - } - else if (xdist < 0 && ydist < 0 || xdist > 0 && ydist > 0) - { - if (xdist < 0) - { - target1_x = cx - range; - target1_y = cy - range; - } - else - { - target1_x = cx + range; - target1_y = cy + range; - } - - if (xdist == ydist) - { - target2_x = target1_x; - target2_y = target1_y; - } - else - { - if (xdist < 0) // both are negative (upper left corner) - { - if (dx > dy) - { - target2_x = dx; - target2_y = cy - range; - } - else - { - target2_x = cx - range; - target2_y = dy; - } - } - else // both are positive (lower right corner) - { - if (dx > dy) - { - target2_x = cx + range; - target2_y = dy; - } - else - { - target2_x = dx; - target2_y = cy + range; - } - } - } - } - else if (xdist < 0 && ydist > 0 || xdist > 0 && ydist < 0) - { - if (xdist < 0) // lower left corner - { - target1_x = cx - range; - target1_y = cy + range; - } - else // upper right corner - { - target1_x = cx + range; - target1_y = cy - range; - } - - if (xdist == -ydist) - { - target2_x = target1_x; - target2_y = target1_y; - } - else - { - if (xdist < 0) // ydist > 0 - { - if (-xdist > ydist) - { - target2_x = cx - range; - target2_y = dy; - } - else - { - target2_x = dx; - target2_y = cy + range; - } - } - else // xdist > 0, ydist < 0 - { - if (-xdist > ydist) - { - target2_x = dx; - target2_y = cy - range; - } - else - { - target2_x = cx + range; - target2_y = dy; - } - } - } - } - else - { - // Everything should have been handled above. - ASSERT(false); - } - - return (true); -} - -void monster_los::check_los_beam(int dx, int dy) -{ - ray_def ray; - - int target1_x = 0, target1_y = 0, target2_x = 0, target2_y = 0; - if (!_set_beam_target(gridx, gridy, dx, dy, target1_x, target1_y, - target2_x, target2_y, range)) - { - // Nothing to be done. - return; - } - - if (target1_x > target2_x || target1_y > target2_y) - { - // Swap the two targets so our loop will work correctly. - int help = target1_x; - target1_x = target2_x; - target2_x = help; - - help = target1_y; - target1_y = target2_y; - target2_y = help; - } - - const int max_dist = range; - int dist; - bool blocked = false; - for (int tx = target1_x; tx <= target2_x; tx++) - for (int ty = target1_y; ty <= target2_y; ty++) - { - // If (tx, ty) lies outside the level boundaries, there's nothing - // that shooting a ray into that direction could bring us, esp. - // as earlier grids in the ray will already have been handled, and - // out of bounds grids are simply skipped in any LoS check. - if (!map_bounds(tx, ty)) - continue; - - // Already calculated a beam to (tx, ty), don't do so again. - if (!is_unknown(tx, ty)) - continue; - - dist = 0; - ray.fullray_idx = -1; // to quiet valgrind - find_ray( coord_def(gridx, gridy), coord_def(tx, ty), - true, ray, 0, true, true ); - - if (ray.x() == gridx && ray.y() == gridy) - ray.advance(true); - - while (dist++ <= max_dist) - { - // The ray brings us out of bounds of the level map. - // Since we're always shooting outwards there's nothing more - // to look at in that direction, and we can break the loop. - if (!map_bounds(ray.x(), ray.y())) - break; - - if (blocked) - { - // Earlier grid blocks this beam, set to blocked if - // unknown, but don't overwrite visible grids. - set_los_value(ray.x(), ray.y(), true); - } - else if (_blocks_movement_sight(mons, grd[ray.x()][ray.y()])) - { - set_los_value(ray.x(), ray.y(), true); - // The rest of the beam will now be blocked. - blocked = true; - } - else - { - // Allow overriding in case another beam has marked this - // field as blocked, because we've found a solution where - // that isn't the case. - set_los_value(ray.x(), ray.y(), false, true); - } - if (ray.x() == tx && ray.y() == ty) - break; - - ray.advance(true); - } - } -} diff --git a/crawl-ref/source/view.h b/crawl-ref/source/view.h index b53cd82d4e..6f4dac75ff 100644 --- a/crawl-ref/source/view.h +++ b/crawl-ref/source/view.h @@ -69,12 +69,6 @@ bool mon_enemies_around(const monsters *monster); void find_features(const std::vector<coord_def>& features, unsigned char feature, std::vector<coord_def> *found); -void clear_rays_on_exit(); -void losight(env_show_grid &sh, feature_grid &gr, - const coord_def& center, bool clear_walls_block = false, - bool ignore_clouds = false); - - bool magic_mapping(int map_radius, int proportion, bool suppress_msg, bool force = false); @@ -179,31 +173,8 @@ void add_feature_override(const std::string &text); void clear_cset_overrides(); void add_cset_override(char_set_type set, const std::string &overrides); -bool see_grid( const env_show_grid &show, - const coord_def &c, - const coord_def &pos ); -bool see_grid(const coord_def &p); -bool see_grid_no_trans( const coord_def &p ); -bool trans_wall_blocking( const coord_def &p ); -bool grid_see_grid(const coord_def& p1, const coord_def& p2, - dungeon_feature_type allowed = DNGN_UNSEEN); unsigned grid_character_at(const coord_def &c); -inline bool see_grid( int grx, int gry ) -{ - return see_grid(coord_def(grx, gry)); -} - -inline bool see_grid_no_trans(int x, int y) -{ - return see_grid_no_trans(coord_def(x, y)); -} - -inline bool trans_wall_blocking(int x, int y) -{ - return trans_wall_blocking(coord_def(x, y)); -} - std::string screenshot(bool fullscreen = false); dungeon_char_type get_feature_dchar( dungeon_feature_type feat ); @@ -217,23 +188,11 @@ void view_update_at(const coord_def &pos); void flash_monster_colour(const monsters *mon, unsigned char fmc_colour, int fmc_delay); #endif -void calc_show_los(); void viewwindow(bool draw_it, bool do_updates); void update_monsters_in_view(); void handle_seen_interrupt(monsters* monster); void flush_comes_into_view(); -struct ray_def; -bool find_ray( const coord_def& source, const coord_def& target, - bool allow_fallback, ray_def& ray, int cycle_dir = 0, - bool find_shortest = false, bool ignore_solid = false ); - -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 = true, - bool just_check = false); - dungeon_char_type dchar_by_name(const std::string &name); void handle_terminal_resize(bool redraw = true); @@ -243,59 +202,4 @@ unsigned short dos_brand( unsigned short colour, unsigned brand = CHATTR_REVERSE); #endif -#define _monster_los_LSIZE (2 * LOS_RADIUS + 1) - -// This class can be used to fill the entire surroundings (los_range) -// of a monster or other position with seen/unseen values, so as to be able -// to compare several positions within this range. -class monster_los -{ -public: - monster_los(); - virtual ~monster_los(); - - // public methods - void set_monster(monsters *mon); - void set_los_centre(int x, int y); - void set_los_centre(const coord_def& p) { this->set_los_centre(p.x, p.y); } - void set_los_range(int r); - void fill_los_field(void); - bool in_sight(int x, int y); - bool in_sight(const coord_def& p) { return this->in_sight(p.x, p.y); } - -protected: - // protected methods - coord_def pos_to_index(coord_def &p); - coord_def index_to_pos(coord_def &i); - - void set_los_value(int x, int y, bool blocked, bool override = false); - int get_los_value(int x, int y); - bool is_blocked(int x, int y); - bool is_unknown(int x, int y); - - void check_los_beam(int dx, int dy); - - // The (fixed) size of the array. - static const int LSIZE; - - static const int L_VISIBLE; - static const int L_UNKNOWN; - static const int L_BLOCKED; - - // The centre of our los field. - int gridx, gridy; - - // Habitat checks etc. should be done for this monster. - // Usually the monster whose LOS we're trying to calculate - // (if mon->x == gridx, mon->y == gridy). - // Else, any monster trying to move around within this los field. - monsters *mons; - - // Range may never be greater than LOS_RADIUS! - int range; - - // The array to store the LOS values. - int los_field[_monster_los_LSIZE][_monster_los_LSIZE]; -}; - #endif diff --git a/crawl-ref/source/xom.cc b/crawl-ref/source/xom.cc index c3b3a26dcf..a49571aae8 100644 --- a/crawl-ref/source/xom.cc +++ b/crawl-ref/source/xom.cc @@ -18,6 +18,7 @@ REVISION("$Rev$"); #include "it_use2.h" #include "items.h" #include "kills.h" +#include "los.h" #include "makeitem.h" #include "message.h" #include "misc.h" |