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.

1 files changed, 345 insertions, 0 deletions

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;
+    }
+}
+