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

5 files changed, 439 insertions, 20 deletions

diff --git a/crawl-ref/source/describe.cc b/crawl-ref/source/describe.cc
index b73cad38cc..9423d9bf8c 100644
--- a/crawl-ref/source/describe.cc
+++ b/crawl-ref/source/describe.cc
@@ -1886,7 +1886,7 @@ void describe_item( item_def &item, bool allow_inscribe )
             && !ainscrip.empty()
             && item.inscription.find(ainscrip) == std::string::npos;
 
-        if ( allow_autoinscribe )
+        if (allow_autoinscribe)
         {
             formatted_string::parse_string(
                 "<cyan>Do you wish to inscribe this item? "
@@ -1898,20 +1898,23 @@ void describe_item( item_def &item, bool allow_inscribe )
                 "<cyan>Do you wish to inscribe this item? ").display();
         }
 
-        if (Options.tutorial_left && wherey() <= get_number_of_lines() - 2)
+        if (Options.tutorial_left && wherey() <= get_number_of_lines() - 5)
         {
             tutorial_inscription_info(allow_autoinscribe);
 
-            if ( allow_autoinscribe )
+            if (wherey() <= get_number_of_lines() - 2)
             {
-                formatted_string::parse_string(
-                    "<cyan>So, do you wish to inscribe this item? "
-                    "('a' to autoinscribe) ").display();
-            }
-            else
-            {
-                formatted_string::parse_string(
-                    "<cyan>So, do you wish to inscribe this item? ").display();
+                if (allow_autoinscribe)
+                {
+                    formatted_string::parse_string(
+                        "<cyan>So, do you wish to inscribe this item? "
+                        "('a' to autoinscribe) ").display();
+                }
+                else
+                {
+                    formatted_string::parse_string(
+                        "<cyan>So, do you wish to inscribe this item? ").display();
+                }
             }
         }
 #ifdef USE_TILE
diff --git a/crawl-ref/source/monstuff.cc b/crawl-ref/source/monstuff.cc
index e06dd5573d..07c83a8bcc 100644
--- a/crawl-ref/source/monstuff.cc
+++ b/crawl-ref/source/monstuff.cc
@@ -2157,8 +2157,18 @@ static bool _choose_random_patrol_target_grid(monsters *mon)
 {
     int patrol_x = mon->patrol_point.x;
     int patrol_y = mon->patrol_point.y;
-    dungeon_feature_type habitat = habitat2grid(
-                                       mons_habitat_by_type(mon->type) );
+
+    monster_los lm;
+    lm.set_monster(mon);
+    lm.fill_los_field();
+    bool patrol_seen = lm.in_sight(patrol_x, patrol_y);
+
+    monster_los patrol;
+    // Set monster to make monster_los respect habitat restrictions.
+    patrol.set_monster(mon);
+    patrol.set_los_centre(patrol_x, patrol_y);
+    patrol.fill_los_field();
+
     int pos_x, pos_y;
     int count_grids = 0;
     for (int j = -LOS_RADIUS; j < LOS_RADIUS; j++)
@@ -2171,7 +2181,7 @@ static bool _choose_random_patrol_target_grid(monsters *mon)
                 continue;
 
             // Don't bother for the current position. If everything fails,
-            // we'll stay here anyways.
+            // we'll stay here anyway.
             if (pos_x == mon->x && pos_y == mon->y)
                 continue;
 
@@ -2186,7 +2196,7 @@ static bool _choose_random_patrol_target_grid(monsters *mon)
             if (mgrd[pos_x][pos_y] != NON_MONSTER)
                 continue;
 
-            if (grid_see_grid(mon->x, mon->y, patrol_x, patrol_y, habitat))
+            if (patrol_seen)
             {
                 // If the patrol point can be easily (within LOS) reached
                 // from the current position, it suffices if the target is
@@ -2197,8 +2207,8 @@ static bool _choose_random_patrol_target_grid(monsters *mon)
                 // patrol point is out of sight, too. Such a case will be
                 // handled below, though it might take a while until a monster
                 // gets out of a deadlock.
-                if (!grid_see_grid(patrol_x, patrol_y, pos_x, pos_y, habitat)
-                    && !grid_see_grid(mon->x, mon->y, pos_x, pos_y, habitat))
+                if (!patrol.in_sight(pos_x, pos_y)
+                    && !lm.in_sight(pos_x, pos_y))
                 {
                     continue;
                 }
@@ -2209,8 +2219,8 @@ static bool _choose_random_patrol_target_grid(monsters *mon)
                 // make sure the new target brings us into reach of it.
                 // This means that the target must be reachable BOTH from
                 // the patrol point AND the current position.
-                if (!grid_see_grid(patrol_x, patrol_y, pos_x, pos_y, habitat)
-                    || !grid_see_grid(mon->x, mon->y, pos_x, pos_y, habitat))
+                if (!patrol.in_sight(pos_x, pos_y)
+                    || !lm.in_sight(pos_x, pos_y))
                 {
                     continue;
                 }
diff --git a/crawl-ref/source/tutorial.cc b/crawl-ref/source/tutorial.cc
index 4aaae00e4f..d7cf5b96c8 100644
--- a/crawl-ref/source/tutorial.cc
+++ b/crawl-ref/source/tutorial.cc
@@ -1270,7 +1270,7 @@ static void _new_god_conduct()
 
     if (is_good_god(you.religion))
     {
-        // For the good gods, piety grows over them.
+        // For the good gods, piety grows over time.
         text << "From now on, " << new_god_name << " will watch over you and "
                 "judge your behaviour. Thus, your actions will greatly "
                 "influence your piety (divine favour). If your piety runs out ";
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);
+            }
+        }
+}
diff --git a/crawl-ref/source/view.h b/crawl-ref/source/view.h
index b0e6e0c2c4..9994707b12 100644
--- a/crawl-ref/source/view.h
+++ b/crawl-ref/source/view.h
@@ -244,4 +244,51 @@ unsigned short dos_brand( unsigned short colour,
                           unsigned brand = CHATTR_REVERSE);
 #endif
 
+// This class can be used to fill the entire surroundings (los_range)
+// of a monster or other position with seen/unseen values, so as to be able
+// to compare several positions within this range.
+class monster_los
+{
+public:
+    monster_los();
+    virtual ~monster_los();
+
+    // public methods
+    void set_monster(monsters *mon);
+    void set_los_centre(int x, int y);
+    void fill_los_field(void);
+    bool in_sight(int x, int y);
+
+protected:
+    // protected methods
+    coord_def pos_to_index(coord_def &p);
+    coord_def index_to_pos(coord_def &i);
+
+    void set_los_value(int x, int y, bool blocked, bool override = false);
+    int get_los_value(int x, int y);
+    bool is_blocked(int x, int y);
+    bool is_unknown(int x, int y);
+
+    void check_los_beam(int dx, int dy);
+
+    // The (fixed) size of the array.
+    static const int LSIZE = 2 * LOS_RADIUS + 1;
+
+    static const int L_VISIBLE =  1;
+    static const int L_UNKNOWN =  0;
+    static const int L_BLOCKED = -1;
+
+    // The centre of our los field.
+    int gridx, gridy;
+
+    // Habitat checks etc. should be done for this monster.
+    // Usually the monster whose LOS we're trying to calculate
+    // (if mon->x == gridx, mon->y == gridy).
+    // Else, any monster trying to move around within this los field.
+    monsters *mons;
+
+    // The array to store the LOS values.
+    int los_field[LSIZE][LSIZE];
+};
+
 #endif