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, 47 insertions, 0 deletions

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