From 5fc4ef91a5a82981c3becf54509a2ae64b2b4ec1 Mon Sep 17 00:00:00 2001 From: Robert Vollmert Date: Thu, 8 Oct 2009 14:24:43 +0200 Subject: Split LOS code from view.cc. los.cc: basic raycasting algorithm; losight(), see_grid() etc. ray.cc: ray_def implementation. mon-los.cc: monster_los This includes adding a bunch of #includes; there's probably some obsolete includes of view.h now. --- crawl-ref/source/ray.cc | 345 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 345 insertions(+) create mode 100644 crawl-ref/source/ray.cc (limited to 'crawl-ref/source/ray.cc') 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 + +#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(*accx) + 1); + const double ytarget = (static_cast(*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(accx); + cury = static_cast(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(accx), static_cast(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(accx), static_cast(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; + } +} + -- cgit v1.2.3-54-g00ecf