Add a line on good gods disapproving of certain items to their

description (evil_item). Same for evil_eating.

In another step on the way to monster pathfinding, take the
shortest path and extract a vector of waypoints out of it.

When experimenting with ways to do this I noticed that grid_see_grid 
is not symmetrical (A may see B but not vice versa); I'm not sure 
what effects that could have. It won't directly affect the player as 
the checks for monster sees player and player sees monster both use 
the player LoS, but it could have an effect on friendly monsters 
fighting enemy ones, I guess.

Also, I don't think num_feats_between needs the shortest beam
available (called with false now). In fact, that seemed to hurt
visibility a bit, probably because of attempting to take vision
obstructing shortcuts. If this reasoning is wrong, please speak up
and/or correct it. (I sure hope not because the shortest beam 
calculation has some more overhead that can be avoided this way.)


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

9 files changed, 130 insertions, 58 deletions

diff --git a/crawl-ref/settings/food_colouring.txt b/crawl-ref/settings/food_colouring.txt
index f21ac57585..f483f5fb0c 100644
--- a/crawl-ref/settings/food_colouring.txt
+++ b/crawl-ref/settings/food_colouring.txt
@@ -8,8 +8,8 @@ inv := menu_colour
 msg = $inedible:.*inedible.*
 inv = $inedible:.*inedible.*
 
-inv = $evil:.*evil_item.*
 inv = $evil:.*evil_eating.*
+inv = $evil:.*evil_item.*
 
 msg = $preferred:.*preferred.*
 inv = $preferred:.*preferred.*
diff --git a/crawl-ref/source/debug.cc b/crawl-ref/source/debug.cc
index ddc3bd3017..cf5340e2b9 100644
--- a/crawl-ref/source/debug.cc
+++ b/crawl-ref/source/debug.cc
@@ -4101,8 +4101,21 @@ void debug_pathfind(int mid)
             snprintf(info, INFO_SIZE, "(%d, %d)  ", path[i].x, path[i].y);
             path_str += info;
         }
+        mpr(path_str.c_str());
+        mprf("-> path length: %d", path.size());
 
+        mpr(EOL);
+        path = mp.calc_waypoints();
+        path_str = "";
+        mpr(EOL);
+        mpr("And here are the needed waypoints: ");
+        for (unsigned int i = 0; i < path.size(); i++)
+        {
+            snprintf(info, INFO_SIZE, "(%d, %d)  ", path[i].x, path[i].y);
+            path_str += info;
+        }
         mpr(path_str.c_str());
+        mprf("-> #waypoints: %d", path.size());
     }
 }
 #endif
diff --git a/crawl-ref/source/describe.cc b/crawl-ref/source/describe.cc
index 4904d24b66..3b6d4969d8 100644
--- a/crawl-ref/source/describe.cc
+++ b/crawl-ref/source/describe.cc
@@ -1636,6 +1636,10 @@ std::string get_item_description( const item_def &item, bool verbose,
         description << "$";
         break;
 
+    case OBJ_CORPSES:
+        if (item.sub_type == CORPSE_SKELETON)
+            break;
+        // intentional fall-through
     case OBJ_FOOD:
         if (item.sub_type == FOOD_CHUNK)
         {
@@ -1685,6 +1689,13 @@ std::string get_item_description( const item_def &item, bool verbose,
             default:
                 break;
             }
+            if (is_good_god(you.religion) && is_player_same_species(item.plus)
+                || you.religion == GOD_ZIN
+                   && mons_intel(item.plus) >= I_NORMAL)
+            {
+                description << "$$" << god_name(you.religion) << " disapproves "
+                               "of eating such meat.";
+            }
             description << "$";
 
         }
@@ -1747,7 +1758,6 @@ std::string get_item_description( const item_def &item, bool verbose,
 
     case OBJ_SCROLLS:
     case OBJ_ORBS:
-    case OBJ_CORPSES:
     case OBJ_GOLD:
         // No extra processing needed for these item types.
         break;
@@ -1788,6 +1798,13 @@ std::string get_item_description( const item_def &item, bool verbose,
         }
     }
 
+    if (is_good_god(you.religion) && is_evil_item(item)
+        && item_type_known(item))
+    {
+        description << "$$" << god_name(you.religion) << " disapproves of the "
+                    << "use of such an item.";
+    }
+
     return description.str();
 }                               // end get_item_description()
 
@@ -1823,7 +1840,7 @@ void describe_feature_wide(int x, int y)
         getch();
 }
 
-// Return true if spells can be shown to player
+// Returns true if spells can be shown to player.
 static bool show_item_description(const item_def &item)
 {
     clrscr();
diff --git a/crawl-ref/source/directn.cc b/crawl-ref/source/directn.cc
index 2933230868..c696cfea46 100644
--- a/crawl-ref/source/directn.cc
+++ b/crawl-ref/source/directn.cc
@@ -1015,10 +1015,10 @@ void direction(dist& moves, targeting_type restricts,
         }
 
 #ifdef USE_TILE
-        // tiles always need a beam redraw if show_beam is true (and if valid...)
-        if ( need_beam_redraw
-             || show_beam && find_ray(you.x_pos, you.y_pos, moves.tx, moves.ty,
-                                      true, ray, 0, true) )
+        // Tiles always need a beam redraw if show_beam is true (and valid...)
+        if (need_beam_redraw
+            || show_beam && find_ray(you.x_pos, you.y_pos, moves.tx, moves.ty,
+                                     true, ray, 0, true) )
         {
 #else
         if ( need_beam_redraw )
diff --git a/crawl-ref/source/enum.h b/crawl-ref/source/enum.h
index 1a906c9303..9a1ea32df8 100644
--- a/crawl-ref/source/enum.h
+++ b/crawl-ref/source/enum.h
@@ -863,21 +863,21 @@ enum dungeon_feature_type
     DNGN_CLEAR_STONE_WALL,             //   10 - Transparent
     DNGN_CLEAR_PERMAROCK_WALL,         //   11 - Transparent
 
-    // lowest/highest grid value which is a wall
+    // Lowest/highest grid value which is a wall.
     DNGN_MINWALL = DNGN_WAX_WALL,
     DNGN_MAXWALL = DNGN_CLEAR_PERMAROCK_WALL,
 
-    // Random wall types for big rooms
+    // Random wall types for big rooms.
     DNGN_RNDWALL_MIN = DNGN_METAL_WALL,
     DNGN_RNDWALL_MAX = DNGN_STONE_WALL,
 
-    // highest grid value which is opaque
+    // Highest grid value which is opaque.
     DNGN_MAXOPAQUE = DNGN_PERMAROCK_WALL,
 
-    // lowest grid value which can be seen through
+    // Lowest grid value which can be seen through.
     DNGN_MINSEE = DNGN_CLEAR_ROCK_WALL,
 
-    // highest grid value which can't be reached through
+    // Highest grid value which can't be reached through.
     DNGN_MAX_NONREACH = DNGN_CLEAR_PERMAROCK_WALL,
 
     // Can be seen through and reached past.
@@ -885,7 +885,7 @@ enum dungeon_feature_type
     DNGN_GRANITE_STATUE = 21,          //   21
     DNGN_STATUE_RESERVED,
 
-    // lowest grid value which can be passed by walking etc.
+    // Lowest grid value which can be passed by walking etc.
     DNGN_MINMOVE = 31,
 
     DNGN_LAVA = 61,                    //   61
diff --git a/crawl-ref/source/mon-util.cc b/crawl-ref/source/mon-util.cc
index 9d5f0a755f..4742f0a1fe 100644
--- a/crawl-ref/source/mon-util.cc
+++ b/crawl-ref/source/mon-util.cc
@@ -1269,7 +1269,7 @@ bool mons_amphibious(int mc)
     return mons_class_flag(mc, M_AMPHIBIOUS);
 }
 
-// this nice routine we keep in exactly the way it was
+// This nice routine we keep in exactly the way it was-
 int hit_points(int hit_dice, int min_hp, int rand_hp)
 {
     int hrolled = 0;
@@ -1281,11 +1281,11 @@ int hit_points(int hit_dice, int min_hp, int rand_hp)
     }
 
     return (hrolled);
-}                               // end hit_points()
+}
 
 // This function returns the standard number of hit dice for a type
 // of monster, not a pacticular monsters current hit dice. -- bwr
-// XXX: rename to mons_class_* to be like the rest
+// XXX: Rename to mons_class_* to be like the rest.
 int mons_type_hit_dice( int type )
 {
     struct monsterentry *mon_class = get_monster_data( type );
@@ -6079,8 +6079,8 @@ void monsters::react_to_damage(int damage)
             }
         }
 
-        const bool needs_message =
-            spawned && mons_near(this) && player_monster_visible(this);
+        const bool needs_message = spawned && mons_near(this)
+                                   && player_monster_visible(this);
 
         if (needs_message)
         {
@@ -6089,6 +6089,7 @@ void monsters::react_to_damage(int damage)
                  spawned >= 5 ? " alarmingly" :
                  spawned >= 3 ? " violently" :
                  spawned > 1 ? " vigorously" : "");
+
             if (spawned == 1)
                 mprf("%s spits out another jelly.", monnam.c_str());
             else
diff --git a/crawl-ref/source/monplace.cc b/crawl-ref/source/monplace.cc
index 141920fb15..5780548926 100644
--- a/crawl-ref/source/monplace.cc
+++ b/crawl-ref/source/monplace.cc
@@ -2329,8 +2329,8 @@ bool monster_pathfind::calc_path_to_neighbours()
             total = distance + estimated_cost(npos);
             if (old_dist == INFINITE_DISTANCE)
             {
-                mprf("Adding (%d,%d) to hash (total dist = %d)",
-                     npos.x, npos.y, total);
+//                mprf("Adding (%d,%d) to hash (total dist = %d)",
+//                     npos.x, npos.y, total);
 
                 add_new_pos(npos, total);
                 if (total > max_length)
@@ -2338,8 +2338,8 @@ bool monster_pathfind::calc_path_to_neighbours()
             }
             else
             {
-                mprf("Improving (%d,%d) to total dist %d",
-                     npos.x, npos.y, total);
+//                mprf("Improving (%d,%d) to total dist %d",
+//                     npos.x, npos.y, total);
 
                 update_pos(npos, total);
             }
@@ -2368,7 +2368,6 @@ bool monster_pathfind::calc_path_to_neighbours()
 
 bool monster_pathfind::get_best_position()
 {
-//    mprf("minlength: %d, maxlength: %d", min_length, max_length);
     for (int i = min_length; i <= max_length; i++)
     {
         if (!hash[i].empty())
@@ -2378,8 +2377,8 @@ bool monster_pathfind::get_best_position()
             std::vector<coord_def> &vec = hash[i];
             pos = vec[vec.size()-1];
             vec.pop_back();
-            mprf("Returning (%d, %d) as best pos with total dist %d.",
-                 pos.x, pos.y, min_length);
+//            mprf("Returning (%d, %d) as best pos with total dist %d.",
+//                 pos.x, pos.y, min_length);
 
             return (true);
         }
@@ -2406,8 +2405,8 @@ std::vector<coord_def> monster_pathfind::backtrack()
         dir = prev[pos.x][pos.y];
         pos = pos + Compass[dir];
         ASSERT(in_bounds(pos));
-        mprf("prev: (%d, %d), pos: (%d, %d)", Compass[dir].x, Compass[dir].y,
-                                              pos.x, pos.y);
+//        mprf("prev: (%d, %d), pos: (%d, %d)", Compass[dir].x, Compass[dir].y,
+//                                              pos.x, pos.y);
         path.push_back(pos);
 
         if (pos.x == 0 && pos.y == 0)
@@ -2419,6 +2418,41 @@ std::vector<coord_def> monster_pathfind::backtrack()
     return path;
 }
 
+// Reduces the path coordinates to only a couple of key waypoints needed
+// to reach the target.
+std::vector<coord_def> monster_pathfind::calc_waypoints()
+{
+    std::vector<coord_def> path = backtrack();
+    // If no path found, nothing to be done.
+    if (path.empty())
+        return path;
+
+    dungeon_feature_type can_move;
+    if (mons_amphibious(mons_is_zombified(mons) ? mons->base_monster
+                                                : mons->type))
+    {
+        can_move = DNGN_DEEP_WATER;
+    }
+    else
+        can_move = DNGN_SHALLOW_WATER;
+
+    std::vector<coord_def> waypoints;
+    pos = path[0];
+
+    for (unsigned int i = 1; i < path.size(); i++)
+    {
+        if (grid_see_grid(pos.x, pos.y, path[i].x, path[i].y, can_move))
+            continue;
+        else
+        {
+            pos = path[i-1];
+            waypoints.push_back(pos);
+        }
+    }
+
+    return waypoints;
+}
+
 bool monster_pathfind::traversable(coord_def p)
 {
     const int montype = mons_is_zombified(mons) ? mons_zombie_base(mons)
diff --git a/crawl-ref/source/monplace.h b/crawl-ref/source/monplace.h
index cfa3f9ca4d..9d877a86ab 100644
--- a/crawl-ref/source/monplace.h
+++ b/crawl-ref/source/monplace.h
@@ -303,6 +303,7 @@ public:
     // public methods
     bool start_pathfind(monsters *mon, coord_def dest, bool msg = false);
     std::vector<coord_def> backtrack(void);
+    std::vector<coord_def> calc_waypoints(void);
 
 protected:
     // protected methods
diff --git a/crawl-ref/source/view.cc b/crawl-ref/source/view.cc
index 234b371c21..1c41232987 100644
--- a/crawl-ref/source/view.cc
+++ b/crawl-ref/source/view.cc
@@ -1100,17 +1100,17 @@ inline static bool _update_monster_grid(const monsters *monster)
             && env.cgrid(monster->pos()) == EMPTY_CLOUD)
         {
             _set_show_backup(ex, ey);
-            env.show[ex][ey] = DNGN_INVIS_EXPOSED;
+            env.show[ex][ey]     = DNGN_INVIS_EXPOSED;
             env.show_col[ex][ey] = BLUE;
         }
         return (false);
     }
 
-    // mimics are always left on map
+    // Mimics are always left on map.
     if (!mons_is_mimic( monster->type ))
         _set_show_backup(ex, ey);
 
-    env.show[ex][ey] = monster->type + DNGN_START_OF_MONSTERS;
+    env.show[ex][ey]     = monster->type + DNGN_START_OF_MONSTERS;
     env.show_col[ex][ey] = get_mons_colour( monster );
 
     return (true);
@@ -1456,7 +1456,7 @@ inline static void _update_cloud_grid(int cloudno)
     }
 
     _set_show_backup(ex, ey);
-    env.show[ex][ey] = DNGN_CLOUD;
+    env.show[ex][ey]     = DNGN_CLOUD;
     env.show_col[ex][ey] = which_colour;
 
 #ifdef USE_TILE
@@ -2330,15 +2330,15 @@ bool find_ray( int sourcex, int sourcey, int targetx, int targety,
     {
         const int fullray = _cyclic_offset( fray, cycle_dir, ray.fullray_idx,
                                             fullrays.size() );
-        // yeah, yeah, this is O(n^2). I know.
+        // Yeah, yeah, this is O(n^2). I know.
         cur_offset = 0;
-        for ( int i = 0; i < fullray; ++i )
+        for (int i = 0; i < fullray; ++i)
             cur_offset += raylengths[i];
 
-        for ( cellray = 0; cellray < raylengths[fullray]; ++cellray )
+        for (cellray = 0; cellray < raylengths[fullray]; ++cellray)
         {
-            if ( ray_coord_x[cellray + cur_offset] == absx &&
-                 ray_coord_y[cellray + cur_offset] == absy )
+            if (ray_coord_x[cellray + cur_offset] == absx
+                && ray_coord_y[cellray + cur_offset] == absy)
             {
                 if (find_shortest)
                 {
@@ -2346,11 +2346,11 @@ bool find_ray( int sourcex, int sourcey, int targetx, int targety,
                     unaliased_ray.push_back(coord_def(0, 0));
                 }
 
-                // check if we're blocked so far
+                // Check if we're blocked so far.
                 bool blocked = false;
                 coord_def c1, c3;
                 int real_length = 0;
-                for ( inray = 0; inray <= cellray; ++inray )
+                for (inray = 0; inray <= cellray; ++inray)
                 {
                     const int xi = signx * ray_coord_x[inray + cur_offset];
                     const int yi = signy * ray_coord_y[inray + cur_offset];
@@ -2419,13 +2419,13 @@ bool find_ray( int sourcex, int sourcey, int targetx, int targety,
                 const double ray_slope_diff = find_shortest ?
                     fabs(_slope_factor(fullrays[fullray]) - want_slope) : 0.0;
 
-                if ( !blocked
-                     &&  (!find_shortest
-                          || _superior_ray(shortest, imbalance,
-                                           real_length, cimbalance,
-                                           slope_diff, ray_slope_diff)))
+                if (!blocked
+                    &&  (!find_shortest
+                         || _superior_ray(shortest, imbalance,
+                                          real_length, cimbalance,
+                                          slope_diff, ray_slope_diff)))
                 {
-                    // success!
+                    // Success!
                     ray        = fullrays[fullray];
                     ray.fullray_idx = fullray;
 
@@ -2437,11 +2437,13 @@ bool find_ray( int sourcex, int sourcey, int targetx, int targety,
                         ray.accx = 1.0 - ray.accx;
                     if ( sourcey > targety )
                         ray.accy = 1.0 - ray.accy;
+
                     ray.accx += sourcex;
                     ray.accy += sourcey;
+
                     _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety);
                     if (!find_shortest)
-                        return true;
+                        return (true);
                 }
             }
         }
@@ -2450,24 +2452,24 @@ bool find_ray( int sourcex, int sourcey, int targetx, int targety,
     if (find_shortest && shortest != INFINITE_DISTANCE)
         return (true);
 
-    if ( allow_fallback )
+    if (allow_fallback)
     {
         ray.accx = sourcex + 0.5;
         ray.accy = sourcey + 0.5;
-        if ( targetx == sourcex )
+        if (targetx == sourcex)
             ray.slope = VERTICAL_SLOPE;
         else
         {
-            ray.slope = targety - sourcey;
+            ray.slope  = targety - sourcey;
             ray.slope /= targetx - sourcex;
-            if ( ray.slope < 0 )
+            if (ray.slope < 0)
                 ray.slope = -ray.slope;
         }
         _set_ray_quadrant(ray, sourcex, sourcey, targetx, targety);
         ray.fullray_idx = -1;
-        return true;
+        return (true);
     }
-    return false;
+    return (false);
 }
 
 // Count the number of matching features between two points along
@@ -2485,7 +2487,9 @@ int num_feats_between(int sourcex, int sourcey, int targetx, int targety,
     int     max_dist = grid_distance(sourcex, sourcey, targetx, targety);
 
     ray.fullray_idx = -1; // to quiet valgrind
-    find_ray( sourcex, sourcey, targetx, targety, true, ray, 0, true, true );
+
+    // We don't need to find the shortest beam, any beam will suffice.
+    find_ray( sourcex, sourcey, targetx, targety, true, ray, 0, false, true );
 
     if (exclude_endpoints && ray.x() == sourcex && ray.y() == sourcey)
     {
@@ -3497,7 +3501,7 @@ void show_map( coord_def &spec_place, bool travel_mode )
 }                               // end show_map()
 
 
-// Returns true if succeeded
+// Returns true if succeeded.
 bool magic_mapping(int map_radius, int proportion, bool suppress_msg,
                    bool force)
 {
@@ -3610,11 +3614,11 @@ bool magic_mapping(int map_radius, int proportion, bool suppress_msg,
     return true;
 }                               // end magic_mapping()
 
-// realize that this is simply a repackaged version of
+// Realize that this is simply a repackaged version of
 // stuff::see_grid() -- make certain they correlate {dlb}:
 bool mons_near(const monsters *monster, unsigned short foe)
 {
-    // early out -- no foe!
+    // Early out -- no foe!
     if (foe == MHITNOT)
         return (false);
 
@@ -3629,7 +3633,7 @@ bool mons_near(const monsters *monster, unsigned short foe)
         return (false);
     }
 
-    // must be a monster
+    // Must be a monster.
     const monsters *myFoe = &menv[foe];
     if (myFoe->type >= 0)
     {
@@ -3641,7 +3645,7 @@ bool mons_near(const monsters *monster, unsigned short foe)
     }
 
     return (false);
-}                               // end mons_near()
+}
 
 bool mon_enemies_around(const monsters *monster)
 {
@@ -3679,7 +3683,7 @@ bool see_grid( const env_show_grid &show,
     return (false);
 }
 
-// answers the question: "Is a grid within character's line of sight?"
+// Answers the question: "Is a grid within character's line of sight?"
 bool see_grid( const coord_def &p )
 {
     return see_grid(env.show, you.pos(), p);
@@ -3702,6 +3706,8 @@ bool trans_wall_blocking( const coord_def &p )
 // Depending on the viewer's habitat, 'allowed' can be set to DNGN_FLOOR,
 // DNGN_SHALLOW_WATER or DNGN_DEEP_WATER.
 // Yes, this ignores lava-loving monsters.
+// XXX: It turns out the beams are not symmetrical, i.e. switching
+// pos1 and pos2 may result in small variations.
 bool grid_see_grid(int posx_1, int posy_1, int posx_2, int posy_2,
                    dungeon_feature_type allowed)
 {