This is an experimental attempt at selecting more intuitive beams for

targeting (see 1725723):
- The default beam selected for targeting is the shortest available beam
  that is closest to the Bresenham line between src->targ.
- Targeting beams convert aliased perpendiculars into diagonals, which
  look better. This requires an immortal fudge to make sure the diagonal
  conversion doesn't happen at the wrong places (when the conversion
  would cause the beam to miss the target square).
- Tweaked beam bounce behaviour to look more natural.

Comments and suggestions welcome.

git-svn-id: https://crawl-ref.svn.sourceforge.net/svnroot/crawl-ref/trunk@1511 c06c8d41-db1a-0410-9941-cceddc491573

5 files changed, 262 insertions, 40 deletions

diff --git a/crawl-ref/source/beam.cc b/crawl-ref/source/beam.cc
index ef80105aab..8305758b35 100644
--- a/crawl-ref/source/beam.cc
+++ b/crawl-ref/source/beam.cc
@@ -1262,11 +1262,12 @@ static void zappy( zap_type z_type, int power, struct bolt &pbolt )
  */
 
 
-void fire_beam( struct bolt &pbolt, item_def *item )
+void fire_beam( bolt &pbolt, item_def *item )
 {
     bool beamTerminate;     // has beam been 'stopped' by something?
     int tx = 0, ty = 0;     // test(new) x,y - integer
     int rangeRemaining;
+    bool did_bounce = false;
     cursor_control coff(false);
 
     beam_message_cache.clear();
@@ -1302,11 +1303,12 @@ void fire_beam( struct bolt &pbolt, item_def *item )
     {
         ray.fullray_idx = -1;   // to quiet valgrind
         find_ray( pbolt.source_x, pbolt.source_y,
-                  pbolt.target_x, pbolt.target_y, true, ray);
+                  pbolt.target_x, pbolt.target_y, true, ray,
+                  0, true );
     }
 
     if ( !pbolt.aimed_at_feet )
-        ray.advance();
+        ray.advance_through(pbolt.target());
 
     // give chance for beam to affect one cell even if aimed_at_feet.
     beamTerminate = false;
@@ -1351,16 +1353,19 @@ void fire_beam( struct bolt &pbolt, item_def *item )
             else
             {
                 // BEGIN bounce case
-                if (!isBouncy(pbolt, grd[tx][ty])) {
-                    ray.regress();
+                if (!isBouncy(pbolt, grd[tx][ty]))
+                {
+                    ray.regress(pbolt.target());
                     tx = ray.x();
                     ty = ray.y();
                     break;          // breaks from line tracing
                 }
 
+                did_bounce = true;
+
                 // bounce
                 do {
-                    ray.regress();
+                    ray.regress(pbolt.target());
                     ray.advance_and_bounce();
                     --rangeRemaining;
                 } while ( rangeRemaining > 0 &&
@@ -1458,7 +1463,11 @@ void fire_beam( struct bolt &pbolt, item_def *item )
             }
 
         }
-        ray.advance();
+
+        if (!did_bounce)
+            ray.advance_through(pbolt.target());
+        else
+            ray.advance(true);
     } // end- while !beamTerminate
 
     // the beam has finished, and terminated at tx, ty
diff --git a/crawl-ref/source/direct.cc b/crawl-ref/source/direct.cc
index 77d3a80d16..0b746910d5 100644
--- a/crawl-ref/source/direct.cc
+++ b/crawl-ref/source/direct.cc
@@ -291,7 +291,7 @@ static const char *target_mode_help_text(int mode)
 //           dx,dy          direction delta for DIR_DIR
 //
 //---------------------------------------------------------------
-void direction(struct dist& moves, targeting_type restricts,
+void direction(dist& moves, targeting_type restricts,
                int mode, bool just_looking, const char *prompt)
 {
     // NOTE: Even if just_looking is set, moves is still interesting,
@@ -466,8 +466,17 @@ void direction(struct dist& moves, targeting_type restricts,
             break;
             
         case CMD_TARGET_HIDE_BEAM:
-            show_beam = false;
-            need_beam_redraw = true;
+            if (show_beam)
+            {
+                show_beam = false;
+                need_beam_redraw = true;
+            }
+            else
+            {
+                show_beam = find_ray(you.x_pos, you.y_pos, moves.tx, moves.ty,
+                                     true, ray, 0, true);
+                need_beam_redraw = show_beam;
+            }
             break;
             
         case CMD_TARGET_FIND_YOU:
@@ -696,7 +705,8 @@ void direction(struct dist& moves, targeting_type restricts,
         {
             have_moved = true;
             show_beam = show_beam &&
-                find_ray(you.x_pos, you.y_pos, moves.tx, moves.ty, true, ray);
+                find_ray(you.x_pos, you.y_pos, moves.tx, moves.ty, true, ray,
+                         0, true);
         }
 
         if ( force_redraw )
@@ -738,7 +748,7 @@ void direction(struct dist& moves, targeting_type restricts,
                                 grid2viewY(raycopy.y()));
                         cprintf("*");
                     }
-                    raycopy.advance();
+                    raycopy.advance_through(moves.target());
                 }
                 textcolor(LIGHTGREY);
             }
@@ -762,7 +772,7 @@ static void extend_move_to_edge(dist &moves)
     int mx = 0, my = 0;
 
     if (moves.dx > 0)
-        mx = (GXM  - 1) - you.x_pos;
+        mx = (GXM - 1) - you.x_pos;
     if (moves.dx < 0)
         mx = you.x_pos;
 
diff --git a/crawl-ref/source/externs.h b/crawl-ref/source/externs.h
index c845e382f5..1608e76b51 100644
--- a/crawl-ref/source/externs.h
+++ b/crawl-ref/source/externs.h
@@ -248,41 +248,53 @@ struct coord_def
 
     int distance_from(const coord_def &b) const;
     
-    bool operator == (const coord_def &other) const {
+    bool operator == (const coord_def &other) const
+    {
         return x == other.x && y == other.y;
     }
 
-    bool operator != (const coord_def &other) const {
+    bool operator != (const coord_def &other) const
+    {
         return !operator == (other);
     }
 
-    bool operator <  (const coord_def &other) const {
+    bool operator <  (const coord_def &other) const
+    {
         return (x < other.x) || (x == other.x && y < other.y);
     }
 
-    const coord_def &operator += (const coord_def &other) {
+    const coord_def &operator += (const coord_def &other)
+    {
         x += other.x;
         y += other.y;
         return (*this);
     }
     
-    const coord_def &operator -= (const coord_def &other) {
+    const coord_def &operator -= (const coord_def &other)
+    {
         x -= other.x;
         y -= other.y;
         return (*this);
     }
     
-    coord_def operator + (const coord_def &other) const {
+    coord_def operator + (const coord_def &other) const
+    {
         coord_def copy = *this;
         copy += other;
         return (copy);
     }
 
-    coord_def operator - (const coord_def &other) const {
+    coord_def operator - (const coord_def &other) const
+    {
         coord_def copy = *this;
         copy -= other;
         return (copy);
     }
+
+    int abs() const
+    {
+        return (x * x + y * y);
+    }
 };
 
 struct dice_def
@@ -295,6 +307,7 @@ struct dice_def
 
 struct ray_def
 {
+public:
     double accx;
     double accy;
     double slope;
@@ -304,12 +317,25 @@ struct ray_def
     // Quadrant 4: up-right
     int quadrant;
     int fullray_idx;            // for cycling: where did we come from?
-    
+
+public:
     int x() const { return static_cast<int>(accx); }
     int y() const { return static_cast<int>(accy); }
-    int advance();              // returns the direction taken (0,1,2)
+    coord_def pos() const { return coord_def(accx, accy); }
+    
+    // returns the direction taken (0,1,2)
+    int advance(bool shorten = false, const coord_def *p = NULL);
+    int advance_through(const coord_def &point);
     void advance_and_bounce();
-    void regress();
+    void regress(const coord_def &point);
+
+private:
+    int raw_advance();
+    double reflect(bool x, double oldc, double newc) const;
+    double reflect(double x, double c) const;
+    void set_reflect_point(const double oldx, const double oldy,
+                           double *newx, double *newy,
+                           bool blocked_x, bool blocked_y);
 };
 
 // output from direction() function:
@@ -328,6 +354,12 @@ struct dist
 
     // internal use - ignore
     int  prev_target;   // previous target
+
+    // target - source (source == you.pos())
+    coord_def target() const
+    {
+        return coord_def(tx, ty);
+    }
 };
 
 struct bolt
@@ -384,6 +416,11 @@ public:
 
     // Returns YOU_KILL or MON_KILL, depending on the source of the beam.
     int  killer() const;
+
+    coord_def target() const
+    {
+        return (coord_def(target_x, target_y));
+    }
 };
 
 struct run_check_dir
diff --git a/crawl-ref/source/view.cc b/crawl-ref/source/view.cc
index 20ca4468ea..3858f89aba 100644
--- a/crawl-ref/source/view.cc
+++ b/crawl-ref/source/view.cc
@@ -27,6 +27,7 @@
 #include "view.h"
 
 #include <string.h>
+#include <cmath>
 
 #ifdef DOS
 #include <conio.h>
@@ -1144,6 +1145,50 @@ static int find_next_intercept(double* accx, double* accy, const double slope)
     return rc;
 }
 
+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? abs(slope) > 1.0 : abs(slope) < 1.0)
+        return (reflect(oldx, floor(oldx) + 0.5));
+
+    const int flnew = newx;
+    const int flold = 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
@@ -1152,9 +1197,14 @@ void ray_def::advance_and_bounce()
         { 1, 3, 2 }, { 0, 2, 3 }, { 3, 1, 0 }, { 2, 0, 1 }
     };
     int oldx = x(), oldy = y();
-    int rc = advance();
+    const double oldaccx = accx, oldaccy = accy;
+    int rc = advance(true);
     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 )
@@ -1162,8 +1212,6 @@ void ray_def::advance_and_bounce()
     else
     {
         ASSERT( (oldx != newx) && (oldy != newy) );
-        bool blocked_x = grid_is_solid(grd[oldx][newy]);
-        bool blocked_y = grid_is_solid(grd[newx][oldy]);
         if ( blocked_x && blocked_y )
             quadrant = bouncequad[quadrant][rc];
         else if ( blocked_x )
@@ -1171,18 +1219,54 @@ void ray_def::advance_and_bounce()
         else
             quadrant = bouncequad[quadrant][0];
     }
-    advance();
+
+    set_reflect_point(oldaccx, oldaccy, &accx, &accy, blocked_x, blocked_y);
 }
 
-void ray_def::regress()
+void ray_def::regress(const coord_def &point)
 {
     int opp_quadrant[4] = { 2, 3, 0, 1 };
     quadrant = opp_quadrant[quadrant];
-    advance();
+    advance(true, &point);
     quadrant = opp_quadrant[quadrant];
 }
 
-int ray_def::advance()
+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 minimize the number of moves on the ray, look one
+    // step ahead and see if we can get a diagonal.
+    
+    const coord_def old(accx, 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(accx, 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 )
@@ -1566,9 +1650,12 @@ static int cyclic_offset( unsigned int ui, int cycle_dir, int startpoint,
 // 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( int sourcex, int sourcey, int targetx, int targety,
-               bool allow_fallback, ray_def& ray, int cycle_dir )
+               bool allow_fallback, ray_def& ray, int cycle_dir,
+               bool find_shortest )
 {
     
     int cellray, inray;
@@ -1577,6 +1664,10 @@ bool find_ray( int sourcex, int sourcey, int targetx, int targety,
     const int absx = signx * (targetx - sourcex);
     const int absy = signy * (targety - sourcey);
     int cur_offset = 0;
+    int shortest = INFINITE_DISTANCE;
+    int imbalance = INFINITE_DISTANCE;
+    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,
@@ -1591,25 +1682,94 @@ bool find_ray( int sourcex, int sourcey, int targetx, int targety,
             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 )
                 {
-                    if (grid_is_solid(
-                            grd[sourcex
-                                + signx * ray_coord_x[inray + cur_offset]]
-                               [sourcey
-                                + signy * ray_coord_y[inray + cur_offset]]))
+                    const int xi = signx * ray_coord_x[inray + cur_offset];
+                    const int yi = signy * ray_coord_y[inray + cur_offset];
+                    if (grid_is_solid(grd[sourcex + xi][sourcey + yi]))
                     {
-                        blocked = true;                   
+                        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];
+                    }
+                }
+
+                if (find_shortest)
+                    unaliased_ray.push_back(
+                        coord_def(signx * absx, signy * absy));
+
+                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;
+                        }
+                    }
                 }
 
-                if ( !blocked )
+                if ( !blocked
+                     && (!find_shortest
+                         || shortest > real_length
+                         || (shortest == real_length
+                             && imbalance > cimbalance)) )
                 {
                     // success!
+                    shortest  = real_length;
+                    imbalance = cimbalance;
                     ray = fullrays[fullray];
                     ray.fullray_idx = fullray;
                     if ( sourcex > targetx )
@@ -1619,11 +1779,16 @@ bool find_ray( int sourcex, int sourcey, int targetx, int targety,
                     ray.accx += sourcex;
                     ray.accy += sourcey;
                     set_ray_quadrant(ray, sourcex, sourcey, targetx, targety);
-                    return true;
+                    if (!find_shortest)
+                        return true;
                 }
             }
         }
     }
+
+    if (find_shortest && shortest != INFINITE_DISTANCE)
+        return (true);
+    
     if ( allow_fallback )
     {
         ray.accx = sourcex + 0.5;
diff --git a/crawl-ref/source/view.h b/crawl-ref/source/view.h
index 099f39e48e..841e33c3ab 100644
--- a/crawl-ref/source/view.h
+++ b/crawl-ref/source/view.h
@@ -156,7 +156,8 @@ void viewwindow(bool draw_it, bool do_updates);
 void fire_monster_alerts();
 
 bool find_ray( int sourcex, int sourcey, int targetx, int targety,
-               bool allow_fallback, ray_def& ray, int cycle_dir = 0 );
+               bool allow_fallback, ray_def& ray, int cycle_dir = 0,
+               bool find_shortest = false );
 
 dungeon_char_type dchar_by_name(const std::string &name);