Replace ray_def by a version using "diamond rays".

Think of the map tiled with squares (the cells).

Previously, a ray was blocked by any part of an opaque cell
except the very corners (to allow looking through diagonal
maps -- we can move through those after all).

In the new version, the rays are the same, but a dungeon feature
is only considered to occupy the the central "diamond": convex
hull of the mid points of the edges. The corners of the
diamond are considered part of the feature, so vertically or
horizontally adjacent walls still block.

This has some effect on LOS: It's a bit more permissive on
diagonals and around corners.

The main advantage is that most rays will now have a footprint
(the sequence of cells it passes through) that is like the
old anti-aliased rays, without requiring any ray munging.

TODO:
  * Make sure we don't hang because of stopping at a corner.
  * Implement proper bouncing.
  * Reenable setting/getting degrees for chaos beams.

2 files changed, 25 insertions, 212 deletions

diff --git a/crawl-ref/source/ray.cc b/crawl-ref/source/ray.cc
index 1094c5f0ae..e6952f2102 100644
--- a/crawl-ref/source/ray.cc
+++ b/crawl-ref/source/ray.cc
@@ -1,210 +1,47 @@
 /*
- *  File:       ray.cc
- *  Summary:    Ray definition
+ *  File:       .cc
+ *  Summary:
  */
 
 #include "AppHdr.h"
 
-#include "ray.h"
+#include <cmath>
 
-#include <math.h>
+#include "ray.h"
+#include "geom2d.h"
 
-#include "los.h"
-#include "terrain.h"
+static geom::grid diamonds(geom::lineseq(1, 1, 0.5, 1),
+                           geom::lineseq(1, -1, -0.5, 1));
 
 static int ifloor(double d)
 {
     return static_cast<int>(floor(d));
 }
 
-ray_def::ray_def(double ax, double ay, double s, int qx, int qy, int idx)
-    : accx(ax), accy(ay), slope(s), quadx(qx), quady(qy), cycle_idx(idx)
-{
-}
-
-int ray_def::x() const
-{
-    return ifloor(accx);
-}
-
-int ray_def::y() const
-{
-    return ifloor(accy);
-}
-
 coord_def ray_def::pos() const
 {
-    return coord_def(x(), y());
+    // TODO: Assert we're in a central diamond.
+    int x = ifloor(r.start.x);
+    int y = ifloor(r.start.y);
+    return (coord_def(x, y));
 }
 
-static double _reflect(double p, double c)
+bool ray_def::advance()
 {
-    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,
-                                bool blocked_x, bool blocked_y)
-{
-    if (blocked_x == blocked_y)
-    {
-        // What to do?
-        accx = oldx;
-        accy = oldy;
-        return;
-    }
-
-    if (blocked_x)
-    {
-        ASSERT(int(oldy) != int(accy));
-        accy = oldy;
-        accx = reflect(true, oldx, accx);
-    }
-    else
-    {
-        ASSERT(int(oldx) != int(accx));
-        accx = oldx;
-        accy = reflect(false, oldy, accy);
-    }
+    return (geom::nextcell(r, diamonds, true)
+            && geom::nextcell(r, diamonds, false));
 }
 
 void ray_def::advance_and_bounce()
 {
-    int oldx = x(), oldy = y();
-    const double oldaccx = accx, oldaccy = accy;
-    adv_type rc = advance();
-    int newx = x(), newy = y();
-    ASSERT(feat_is_solid(grd[newx][newy]));
-
-    const bool blocked_x = feat_is_solid(grd[oldx][newy]);
-    const bool blocked_y = feat_is_solid(grd[newx][oldy]);
-
-    if (double_is_zero(slope) || slope > 100.0)
-    {
-        quadx = -quadx;
-        quady = -quady;
-    }
-    else if (rc == ADV_X)
-        quadx = -quadx;
-    else if (rc == ADV_Y)
-        quady = -quady;
-    else // rc == ADV_XY
-    {
-        ASSERT((oldx != newx) && (oldy != newy));
-        if (blocked_x && blocked_y)
-        {
-            quadx = -quadx;
-            quady = -quady;
-        }
-        else if (blocked_x)
-            quady = -quady;
-        else
-            quadx = -quadx;
-    }
-
-    set_reflect_point(oldaccx, oldaccy, blocked_x, blocked_y);
+    // XXX
+    r.dir *= -1;
 }
 
 void ray_def::regress()
 {
-    quadx = -quadx; quady= -quady;
+    r.dir *= -1;
     advance();
-    quadx = -quadx; quady= -quady;
-}
-
-// Advance a ray in the positive quadrant.
-// 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
-adv_type ray_def::raw_advance_pos()
-{
-    // handle perpendiculars
-    if (double_is_zero(slope))
-    {
-        accx += 1.0;
-        return ADV_X;
-    }
-    if (slope > 100.0)
-    {
-        accy += 1.0;
-        return ADV_Y;
-    }
-
-    const double xtarget = ifloor(accx) + 1;
-    const double ytarget = ifloor(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 ADV_XY;
-    }
-
-    // move to the boundary
-    double traveldist;
-    adv_type rc;
-    if (distdiff > 0.0)
-    {
-        traveldist = ydistance / slope;
-        rc = ADV_Y;
-    }
-    else
-    {
-        traveldist = xdistance;
-        rc = ADV_X;
-    }
-
-    // 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;
+    r.dir *= -1;
 }
 
-/*
- * Mirror ray into positive quadrant or back.
- * this.quad{x,y} are not touched (used for the flip back).
- */
-void ray_def::flip()
-{
-    accx = 0.5 + quadx * (accx - 0.5);
-    accy = 0.5 + quady * (accy - 0.5);
-}
-
-adv_type ray_def::advance()
-{
-    adv_type rc;
-    flip();
-    rc = raw_advance_pos();
-    flip();
-    return rc;
-}
diff --git a/crawl-ref/source/ray.h b/crawl-ref/source/ray.h
index 5dd97dd0a9..477f8fcbf7 100644
--- a/crawl-ref/source/ray.h
+++ b/crawl-ref/source/ray.h
@@ -1,50 +1,26 @@
 /*
  *  File:       ray.h
  *  Summary:    Ray definition
- *  Written by: Linley Henzell
  */
 
 #ifndef RAY_H
 #define RAY_H
 
-// direction of advance:
-enum adv_type
-{
-    ADV_X  = 0, // changed x
-    ADV_Y  = 1, // changed y
-    ADV_XY = 2  // changed x and y (diagonal)
-};
+#include "geom2d.h"
 
 struct ray_def
 {
-public:
-    double accx;
-    double accy;
-    double slope;
-    // Quadrant by sign of x/y coordinate.
-    int quadx;
-    int quady;
-    // For cycling: where did we come from?
+    geom::ray r;
     int cycle_idx;
 
-public:
-    ray_def(double accx = 0.0, double accy = 0.0, double slope = 0.0,
-            int quadx = 1, int quady = 1, int fullray_idx = -1);
-    int x() const;
-    int y() const;
-    coord_def pos() const;
+    ray_def() {}
+    ray_def(const geom::ray& _r)
+        : r(_r), cycle_idx(0) {}
 
-    // returns the direction taken
-    adv_type advance();
+    coord_def pos() const;
+    bool advance();
     void advance_and_bounce();
     void regress();
-
-protected:
-    adv_type raw_advance_pos();
-    void flip();
-    double reflect(bool x, double oldc, double newc) const;
-    void set_reflect_point(const double oldx, const double oldy,
-                           bool blocked_x, bool blocked_y);
 };
 
 #endif