Implement a much more efficient version of the LOS testing used for

monster patrolling. As before, ray casting is used to verify LOS
but ray casting now only happens if a blocked grid is encountered
when searching the surroundings in a growing spiral.
If a blocked grid is found, all beams that might possibly go through
this grid (heuristically tested, probably tests more than needed) are
checked right away and all grids behind the blocked one are marked as
well - this blocking can be reversed, if we later find another beam
that unblocks it. 
A beam that was already tried isn't tried a second time.

The values are stored in a (2*LOS_RANGE)^2 array and then directly
compared when deciding where to send a patrolling monster next.
In the worst case we still need to fire beams at each of the edge 
grids, but that probably can't be avoided entirely, though performance
could obviously still be improved.

The increase in speed is very much noticeable, i.e. for me Crawl runs
smoothly again. :)


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

1 files changed, 359 insertions, 0 deletions

diff --git a/crawl-ref/source/view.cc b/crawl-ref/source/view.cc
index 6afaa25843..7f62bf9057 100644
--- a/crawl-ref/source/view.cc
+++ b/crawl-ref/source/view.cc
@@ -5295,3 +5295,362 @@ void handle_terminal_resize(bool redraw)
     if (redraw)
         redraw_screen();
 }
+
+/////////////////////////////////////////////////////////////////////////////
+// monster_los
+
+monster_los::monster_los()
+    : gridx(0), gridy(0), mons(), los_field()
+{
+}
+
+monster_los::~monster_los()
+{
+}
+
+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 * LOS_RADIUS)
+        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::set_monster(monsters *mon)
+{
+    mons = mon;
+    if (gridx != mons->x)
+        gridx = mons->x;
+    if (gridy != mons->y)
+        gridy = mons->y;
+}
+
+void monster_los::set_los_centre(int x, int y)
+{
+    if (!in_bounds(x, y))
+        return;
+
+    gridx = x;
+    gridy = y;
+}
+
+void monster_los::fill_los_field()
+{
+    int pos_x, pos_y;
+    for (int k = 1; k <= LOS_RADIUS; 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)
+{
+    const int xdist = dx - cx;
+    const int ydist = dy - cy;
+
+    if (xdist == 0 && ydist == 0)
+        return (false); // Nothing to be done.
+
+    if (xdist <= -LOS_RADIUS || xdist >= LOS_RADIUS
+        || ydist <= -LOS_RADIUS || ydist >= LOS_RADIUS)
+    {
+        // 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 one of the straight line
+ *   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 0 or 2*LOS_RADIUS 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 + LOS_RADIUS
+                               : cy - LOS_RADIUS);
+
+        target2_x = target1_x;
+        target2_y = target1_y;
+    }
+    else if (ydist == 0)
+    {
+        target1_x = (xdist > 0 ? cx + LOS_RADIUS
+                               : cx - LOS_RADIUS);
+        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 - LOS_RADIUS;
+            target1_y = cy - LOS_RADIUS;
+        }
+        else
+        {
+            target1_x = cx + LOS_RADIUS;
+            target1_y = cy + LOS_RADIUS;
+        }
+
+        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 - LOS_RADIUS;
+                }
+                else
+                {
+                    target2_x = cx - LOS_RADIUS;
+                    target2_y = dy;
+                }
+            }
+            else // both are positive (lower right corner)
+            {
+                if (dx > dy)
+                {
+                    target2_x = cx + LOS_RADIUS;
+                    target2_y = dy;
+                }
+                else
+                {
+                    target2_x = dx;
+                    target2_y = cy + LOS_RADIUS;
+                }
+            }
+        }
+    }
+    else if (xdist < 0 && ydist > 0 || xdist > 0 && ydist < 0)
+    {
+        if (xdist < 0) // lower left corner
+        {
+            target1_x = cx - LOS_RADIUS;
+            target1_y = cy + LOS_RADIUS;
+        }
+        else // upper right corner
+        {
+            target1_x = cx + LOS_RADIUS;
+            target1_y = cy - LOS_RADIUS;
+        }
+
+        if (xdist == -ydist)
+        {
+            target2_x = target1_x;
+            target2_y = target1_y;
+        }
+        else
+        {
+            if (xdist < 0) // ydist > 0
+            {
+                if (-xdist > ydist)
+                {
+                    target2_x = cx - LOS_RADIUS;
+                    target2_y = dy;
+                }
+                else
+                {
+                    target2_x = dx;
+                    target2_y = cy + LOS_RADIUS;
+                }
+            }
+            else // xdist > 0, ydist < 0
+            {
+                if (-xdist > ydist)
+                {
+                    target2_x = dx;
+                    target2_y = cy - LOS_RADIUS;
+                }
+                else
+                {
+                    target2_x = cx + LOS_RADIUS;
+                    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))
+    {
+        // Nothing to be done.
+        return;
+    }
+
+    const int max_dist = LOS_RADIUS;
+    int dist;
+    bool blocked = false;
+    for (int tx = target1_x; tx <= target2_x; tx++)
+        for (int ty = target1_y; ty <= target2_y; ty++)
+        {
+            // 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( gridx, gridy, tx, ty, true, ray, 0, true, true );
+
+            ASSERT(in_bounds(ray.x(), ray.y()));
+            if (ray.x() == gridx && ray.y() == gridy)
+                ray.advance(true);
+
+            while (dist++ <= max_dist)
+            {
+                ASSERT(in_bounds(ray.x(), ray.y()));
+                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);
+            }
+        }
+}