Add explanatory comments to the pathfinding routines. I might have gone

overboard here :) - but I figured that it could be useful to occasionally 
explain *why* I implemented something a certain way.


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

7 files changed, 196 insertions, 84 deletions

diff --git a/crawl-ref/source/beam.cc b/crawl-ref/source/beam.cc
index bd7e702624..432b80175f 100644
--- a/crawl-ref/source/beam.cc
+++ b/crawl-ref/source/beam.cc
@@ -2664,11 +2664,20 @@ static void _beam_paralyses_monster(bolt &pbolt, monsters *monster)
     }
 }
 
+
+// Petrification works in two stages. First the monster is slowed down in
+// all of its actions and cannot move away (petrifying), and when that times
+// out it remains properly petrified (no movement or actions). The second
+// part is similar to paralysis, except that insubstantial monsters can't be
+// affected and that stabbing damage is drastically reduced.
 static void _beam_petrifies_monster(bolt &pbolt, monsters *monster)
 {
     int petrifying = monster->has_ench(ENCH_PETRIFYING);
     if (monster->has_ench(ENCH_PETRIFIED))
     {
+        // If the petrifying is not yet finished, we can force it to happen
+        // right away by casting again. Otherwise, the spell has no further
+        // effect.
         if (petrifying > 0)
         {
             monster->del_ench(ENCH_PETRIFYING, true);
@@ -2682,6 +2691,8 @@ static void _beam_petrifies_monster(bolt &pbolt, monsters *monster)
     else if (monster->add_ench(ENCH_PETRIFIED)
              && !monster->has_ench(ENCH_PARALYSIS))
     {
+        // Add both the petrifying and the petrified enchantment. The former
+        // will run out sooner and result in plain petrification behaviour.
         monster->add_ench(ENCH_PETRIFYING);
         if (simple_monster_message(monster, " is moving more slowly."))
             pbolt.obvious_effect = true;
@@ -2691,10 +2702,8 @@ static void _beam_petrifies_monster(bolt &pbolt, monsters *monster)
 }
 
 // Returns true if the curare killed the monster.
-bool curare_hits_monster( const bolt &beam,
-                          monsters *monster,
-                          kill_category who,
-                          int levels )
+bool curare_hits_monster( const bolt &beam,  monsters *monster,
+                          kill_category who, int levels )
 {
     const bool res_poison = mons_res_poison(monster) > 0;
     bool mondied = false;
@@ -3802,15 +3811,14 @@ static int _affect_player( bolt &beam, item_def *item )
                 mpr("This is polymorph other only!");
             }
             else
-            {
                 canned_msg( MSG_NOTHING_HAPPENS );
-            }
+
             break;
 
         case BEAM_SLOW:
             potion_effect( POT_SLOWING, beam.ench_power );
             beam.obvious_effect = true;
-            break;     // slow
+            break;
 
         case BEAM_HASTE:
             potion_effect( POT_SPEED, beam.ench_power );
@@ -3818,19 +3826,19 @@ static int _affect_player( bolt &beam, item_def *item )
             beam.obvious_effect = true;
             nasty = false;
             nice  = true;
-            break;     // haste
+            break;
 
         case BEAM_HEALING:
             potion_effect( POT_HEAL_WOUNDS, beam.ench_power );
             beam.obvious_effect = true;
             nasty = false;
             nice  = true;
-            break;     // heal (heal wounds potion eff)
+            break;
 
         case BEAM_PARALYSIS:
             potion_effect( POT_PARALYSIS, beam.ench_power );
             beam.obvious_effect = true;
-            break;     // paralysis
+            break;
 
         case BEAM_PETRIFY:
             you.petrify( beam.ench_power );
@@ -3840,7 +3848,7 @@ static int _affect_player( bolt &beam, item_def *item )
         case BEAM_CONFUSION:
             potion_effect( POT_CONFUSION, beam.ench_power );
             beam.obvious_effect = true;
-            break;     // confusion
+            break;
 
         case BEAM_INVISIBILITY:
             potion_effect( POT_INVISIBILITY, beam.ench_power );
@@ -3848,9 +3856,7 @@ static int _affect_player( bolt &beam, item_def *item )
             beam.obvious_effect = true;
             nasty = false;
             nice  = true;
-            break;     // invisibility
-
-            // 6 is used by digging
+            break;
 
         case BEAM_TELEPORT:
             you_teleport();
@@ -3887,12 +3893,12 @@ static int _affect_player( bolt &beam, item_def *item )
                 mpr("You feel trapped.");
                 break;
             }
-            you.banished = true;
-            you.banished_by = _beam_zapper(beam);
+            you.banished        = true;
+            you.banished_by     = _beam_zapper(beam);
             beam.obvious_effect = true;
-            break;     // banishment to the abyss
+            break;
 
-        case BEAM_PAIN:      // pain
+        case BEAM_PAIN:
             if (player_res_torment())
             {
                 mpr("You are unaffected.");
@@ -3945,10 +3951,10 @@ static int _affect_player( bolt &beam, item_def *item )
             break;
 
         default:
-            // _all_ enchantments should be enumerated here!
+            // _All_ enchantments should be enumerated here!
             mpr("Software bugs nibble your toes!");
             break;
-        }               // end of switch (beam.colour)
+        }
 
         if (nasty)
         {
@@ -3956,11 +3962,15 @@ static int _affect_player( bolt &beam, item_def *item )
             {
                 beam.fr_hurt++;
                 if (beam.beam_source == NON_MONSTER)
+                {
                     // Beam from player rebounded and hit player.
                     xom_is_stimulated(255);
+                }
                 else
+                {
                     // Beam from an ally or neutral.
                     xom_is_stimulated(128);
+                }
             }
             else
                 beam.foe_hurt++;
diff --git a/crawl-ref/source/monplace.cc b/crawl-ref/source/monplace.cc
index b4ff3b8767..43651ad435 100644
--- a/crawl-ref/source/monplace.cc
+++ b/crawl-ref/source/monplace.cc
@@ -2306,6 +2306,20 @@ monster_type summon_any_dragon(dragon_class_type dct)
 /////////////////////////////////////////////////////////////////////////////
 // monster_pathfind
 
+// The pathfinding is an implementation of the A* algorithm. Beginning at the
+// destination square we check all neighbours of a given grid, estimate the
+// distance needed for any shortest path including this grid and push the
+// result into a hash. We can then easily access all points with the shortest
+// distance estimates and then check _their_ neighbours and so on.
+// The algorithm terminates once we reach the monster position since - because
+// of the sorting of grids by shortest distance in the hash - there can be no
+// path between start and target that is shorter than the current one. There
+// could be other paths that have the same length but that has no real impact.
+// If the hash has been cleared and the start grid has not been encountered,
+// then there's no path that matches the requirements fed into monster_pathfind.
+// (These requirements are usually preference of habitat of a specific monster
+// or a limit of the distance between start and any grid on the path.)
+
 //#define DEBUG_PATHFIND
 monster_pathfind::monster_pathfind()
     : mons(), target(), range(0), min_length(0), max_length(0), dist(), prev()
@@ -2322,6 +2336,7 @@ void monster_pathfind::set_range(int r)
         range = r;
 }
 
+// The main method in the monster_pathfind class.
 // Returns true if a path was found, else false.
 bool monster_pathfind::start_pathfind(monsters *mon, coord_def dest, bool msg)
 {
@@ -2359,10 +2374,13 @@ bool monster_pathfind::start_pathfind(monsters *mon, coord_def dest, bool msg)
     bool success = false;
     do
     {
+        // Calculate the distance to all neighbours of the current position,
+        // and add them to the hash, if they haven't already been looked at.
         success = calc_path_to_neighbours();
         if (success)
             return (true);
 
+        // Pull the position with shortest distance estimate to our target grid.
         success = get_best_position();
 
         if (!success)
@@ -2387,8 +2405,14 @@ bool monster_pathfind::calc_path_to_neighbours()
     // For each point, we look at all neighbour points. Check the orthogonals
     // last, so that, should an orthogonal and a diagonal direction have the
     // same total travel cost, the orthogonal will be picked first, and thus
-    // zigzagging should be avoided. This means directions are looked at, in
-    // order: 1, 3, 5, 7, 0, 2, 4, 6. (dir = 0) is an intentional assignment.
+    // zigzagging can be significantly reduced.
+    //
+    //      1  0  2       This means directions are looked at, in order,
+    //       \ | /        1, 3, 5, 7 (diagonals) followed by 0, 2, 4, 6
+    //      7--.--3       (orthogonals). This is achieved by the assignment
+    //       / | \        of (dir = 0) once dir has passed 7.
+    //      6  5  4
+    //
     for (int dir = 1; dir < 8; (dir += 2) == 9 && (dir = 0))
     {
         npos = pos + Compass[dir];
@@ -2412,6 +2436,8 @@ bool monster_pathfind::calc_path_to_neighbours()
         mprf("old dist: %d, new dist: %d, infinite: %d", old_dist, distance,
              INFINITE_DISTANCE);
 #endif
+        // If the new distance is better than the old one (initialized with
+        // INFINITE), update the position.
         if (distance < old_dist)
         {
             // Calculate new total path length.
@@ -2422,7 +2448,6 @@ bool monster_pathfind::calc_path_to_neighbours()
                 mprf("Adding (%d,%d) to hash (total dist = %d)",
                      npos.x, npos.y, total);
 #endif
-
                 add_new_pos(npos, total);
                 if (total > max_length)
                     max_length = total;
@@ -2442,9 +2467,9 @@ bool monster_pathfind::calc_path_to_neighbours()
 
             // Set backtracking information.
             // Converts the Compass direction to their counterpart.
-            //      7  0  1
-            //      6  .  2
-            //      5  4  3
+            //      0  1  2         4  5  6
+            //      7  .  3   ==>   3  .  7       e.g. (3 + 4) % 8          = 7
+            //      6  5  4         2  1  0            (7 + 4) % 8 = 11 % 8 = 3
 
             prev[npos.x][npos.y] = (dir + 4) % 8;
 
@@ -2461,6 +2486,9 @@ bool monster_pathfind::calc_path_to_neighbours()
     return (false);
 }
 
+// Starting at known min_length (minimum total estimated path distance), check
+// the hash for existing vectors, then pick the last entry of the first vector
+// that matches. Update min_length, if necessary.
 bool monster_pathfind::get_best_position()
 {
     for (int i = min_length; i <= max_length; i++)
@@ -2469,9 +2497,13 @@ bool monster_pathfind::get_best_position()
         {
             if (i > min_length)
                 min_length = i;
+
             std::vector<coord_def> &vec = hash[i];
+            // Pick the last position pushed into the vector as it's most
+            // likely to be close to the target.
             pos = vec[vec.size()-1];
             vec.pop_back();
+
 #ifdef DEBUG_PATHFIND
             mprf("Returning (%d, %d) as best pos with total dist %d.",
                  pos.x, pos.y, min_length);
@@ -2488,6 +2520,8 @@ bool monster_pathfind::get_best_position()
     return (false);
 }
 
+// Using the prev vector backtrack from start to target to find all steps to
+// take along the shortest path.
 std::vector<coord_def> monster_pathfind::backtrack()
 {
 #ifdef DEBUG_PATHFIND
@@ -2522,7 +2556,13 @@ std::vector<coord_def> monster_pathfind::backtrack()
 }
 
 // Reduces the path coordinates to only a couple of key waypoints needed
-// to reach the target.
+// to reach the target. Waypoints are chosen such that from one waypoint you
+// can only just see the next one. Note that grid_see_grid() is probably
+// rather too conservative in these estimates.
+// This is done because Crawl's path finding once a target can be seen is
+// very robust and because it allows for more natural traversing if there are
+// other monsters in the way.
+
 std::vector<coord_def> monster_pathfind::calc_waypoints()
 {
     std::vector<coord_def> path = backtrack();
@@ -2558,14 +2598,16 @@ std::vector<coord_def> monster_pathfind::calc_waypoints()
     }
 
     // Add the actual target to the list of waypoints, so we can later check
-    // whether a tracked enemy has moved too much, and we have to update the
-    // path.
+    // whether a tracked enemy has moved too much, in case we have to update
+    // the path.
     if (pos != path[path.size() - 1])
         waypoints.push_back(pos);
 
     return waypoints;
 }
 
+// Checks whether a given monster can pass over a certain position, respecting
+// its preferred habit and capability of flight or opening doors.
 bool monster_pathfind::traversable(coord_def p)
 {
     const int montype = mons_is_zombified(mons) ? mons_zombie_base(mons)
@@ -2626,7 +2668,9 @@ int monster_pathfind::travel_cost(coord_def npos)
 
     // Travelling through water, entering or leaving water is more expensive
     // for non-amphibious monsters, so they'll avoid it where possible.
-    // Only tested for shallow water since they can't enter deep water anywa.
+    // (The resulting path might not be optimal but it will lead to a path
+    // a monster of such habits is likely to prefer.)
+    // Only tested for shallow water since they can't enter deep water anyway.
     if (!airborne && !mons_class_amphibious(montype)
         && (grd(pos) == DNGN_SHALLOW_WATER || grd(npos) == DNGN_SHALLOW_WATER))
     {
@@ -2634,7 +2678,6 @@ int monster_pathfind::travel_cost(coord_def npos)
     }
 
     // Try to avoid (known) traps.
-    //
     const int trap = trap_at_xy(npos.x, npos.y);
     if (trap >= 0)
     {
@@ -2652,6 +2695,7 @@ int monster_pathfind::travel_cost(coord_def npos)
         if (tt == TRAP_ALARM || tt == TRAP_ZOT)
         {
             // Your allies take extra precautions to avoid known alarm traps.
+            // Zot traps are considered intraversable.
             if (knows_trap && mons_friendly(mons))
                 return (3);
 
@@ -2663,13 +2707,12 @@ int monster_pathfind::travel_cost(coord_def npos)
         // tele traps are never traversable anyway.
         if (knows_trap && !airborne)
             return 2;
-
-        return 1;
     }
 
     return 1;
 }
 
+// The estimated cost to reach a grid is simply max(dx, dy).
 int monster_pathfind::estimated_cost(coord_def p)
 {
     return (grid_distance(p.x, p.y, target.x, target.y));
diff --git a/crawl-ref/source/monstuff.cc b/crawl-ref/source/monstuff.cc
index 1d046afcf8..627f0d68ef 100644
--- a/crawl-ref/source/monstuff.cc
+++ b/crawl-ref/source/monstuff.cc
@@ -2609,11 +2609,11 @@ static void _handle_behaviour(monsters *mon)
                 if (mon->foe == MHITYOU && travelling
                     && mon->travel_target == MTRAV_PLAYER)
                 {
+                    // We've got a target, so we'll continue on our way.
 #ifdef DEBUG_PATHFIND
                     mpr("Player out of LoS... start wandering.");
 #endif
                     new_beh = BEH_WANDER;
-                    // We've got a target, so we'll continue on our way.
                     break;
                 }
 
@@ -2699,8 +2699,29 @@ static void _handle_behaviour(monsters *mon)
 
             // Monster can see foe: continue 'tracking'
             // by updating target x,y.
-            if (mon->foe == MHITYOU && proxPlayer)
+            if (mon->foe == MHITYOU)
             {
+                // Just because we can *see* the player, that doesn't mean
+                // we can actually get there. To find about that, we first
+                // check for transparent walls. If there are transparent
+                // walls in the way we'll need pathfinding, no matter what.
+                // (Though monsters with a los attack don't need to get any
+                // closer to hurt the player.)
+                // If no walls are detected, there could still be a river
+                // or a pool of lava in the way. So we check whether there
+                // is water or lava in LoS (boolean) and if so, try to find
+                // a way around it. It's possible that the player can see
+                // lava but it actually has no influence on the monster's
+                // movement (because it's lying in the opposite direction)
+                // but if so, we'll find that out during path finding.
+                // In another attempt of optimization, don't bother with
+                // path finding if the monster in question has no trouble
+                // travelling through water or flying across lava.
+                // Also, if no path is found (too far away, perhaps) set a
+                // flag, so we don't directly calculate the whole thing again
+                // next turn, and even extend that flag to neighbouring
+                // monsters of similar movement restrictions.
+
                 bool potentially_blocking = trans_wall_block;
 
                 // Smart monsters that can fire through walls won't use
@@ -2760,17 +2781,11 @@ static void _handle_behaviour(monsters *mon)
                     // If we're already on our way, do nothing.
                     if (travelling && mon->travel_target == MTRAV_PLAYER)
                     {
-#ifdef DEBUG_PATHFIND
-                        mpr("Already travelling...");
-#endif
                         int len = mon->travel_path.size();
                         coord_def targ = mon->travel_path[len - 1];
                         if (grid_see_grid(targ.x, targ.y, you.x_pos, you.y_pos,
                                           can_move))
                         {
-#ifdef DEBUG_PATHFIND
-                            mpr("Target still valid?");
-#endif
                             // Current target still valid?
                             if (mon->x == mon->travel_path[0].x
                                 && mon->y == mon->travel_path[0].y)
@@ -2885,6 +2900,9 @@ static void _handle_behaviour(monsters *mon)
                         }
                     }
                 }
+                // Whew. If we arrived here, path finding didn't yield anything
+                // (or wasn't even attempted) and we need to set our target
+                // the traditional way.
 
                 // Sometimes, your friends will wander a bit.
                 if (isFriendly && one_chance_in(8))
@@ -2902,6 +2920,7 @@ static void _handle_behaviour(monsters *mon)
             }
             else
             {
+                // We have a foe but it's not the player.
                 mon->target_x = menv[mon->foe].x;
                 mon->target_y = menv[mon->foe].y;
             }
@@ -2984,6 +3003,9 @@ static void _handle_behaviour(monsters *mon)
                         // XXX: Note that this might still not be the best
                         // thing to do since another path might be even
                         // *closer* to our actual target now.
+                        // Not by much, though, since the original path was
+                        // optimal (A*) and the distance between the waypoints
+                        // is rather small.
 
                         int erase = -1;  // Erase how many waypoints?
                         for (unsigned int i = mon->travel_path.size() - 1;
@@ -3018,8 +3040,10 @@ static void _handle_behaviour(monsters *mon)
                         {
                             // We can't reach our old path from our current
                             // position, so calculate a new path instead.
-/*
+
                             monster_pathfind mp;
+                            // The last coordinate in the path vector is our
+                            // destination.
                             int len = mon->travel_path.size();
                             if (mp.start_pathfind(mon, mon->travel_path[len-1]))
                             {
@@ -3028,6 +3052,10 @@ static void _handle_behaviour(monsters *mon)
                                 {
                                     mon->target_x = mon->travel_path[0].x;
                                     mon->target_y = mon->travel_path[0].y;
+#ifdef DEBUG_PATHFIND
+                                mprf("Next waypoint: (%d, %d)",
+                                     mon->target_x, mon->target_y);
+#endif
                                 }
                                 else
                                 {
@@ -3037,22 +3065,20 @@ static void _handle_behaviour(monsters *mon)
                             }
                             else
                             {
-*/
                                 // Or just forget about the whole thing.
                                 mon->travel_path.clear();
                                 mon->travel_target = MTRAV_NONE;
                                 need_target = true;
-//                            }
+                            }
                         }
                     }
-                    else
-                    {
-#ifdef DEBUG_PATHFIND
-                        mpr("All clear. Continue travelling.");
-#endif
-                    }
+
+                    // Else, we can see the next waypoint and are making good
+                    // progress. Carry on, then!
                 }
 
+                // If we still need a target because we're not travelling
+                // (any more), check for patrol routes instead.
                 if (need_target && patrolling)
                 {
                     need_target = false;
@@ -3086,10 +3112,20 @@ static void _handle_behaviour(monsters *mon)
                         else
                         {
                             // It's time to head back!
-                            // Ideally, smart monsters should be able to use
-                            // pathfinding to find the way back, and animals
-                            // could decide to stop patrolling if the path
-                            // was too long.
+                            // Other than for tracking the player, there's
+                            // currently no distinction between smart and
+                            // stupid monsters when it comes to travelling
+                            // back to the patrol point. This is in part due
+                            // to the flavourness of bees finding their way
+                            // back to the Hive (patrolling should really be
+                            // restricted to cases like this), and for the
+                            // other part it's not that important because
+                            // we calculate the path once and then follow it
+                            // home, and the player won't ever see the
+                            // orderly fashion the bees will trudge along.
+                            // What he will see is them swarming back to the
+                            // Hive entrance after some time, and that is what
+                            // matters.
                             monster_pathfind mp;
                             if (mp.start_pathfind(mon, mon->patrol_point))
                             {
@@ -3102,6 +3138,9 @@ static void _handle_behaviour(monsters *mon)
                                 }
                                 else
                                 {
+                                    // We're so close we don't even need
+                                    // a path. (Shouldn't happen as that
+                                    // should have been found above.)
                                     mon->target_x = mon->patrol_point.x;
                                     mon->target_y = mon->patrol_point.y;
                                 }
@@ -3128,10 +3167,7 @@ static void _handle_behaviour(monsters *mon)
 
                 if (need_target)
                 {
-#ifdef DEBUG_PATHFIND
-                    if (!testbits( mon->flags, MF_BATTY ))
-                        mprf("Monster is wandering randomly.");
-#endif
+                    // The monster is travelling randomly.
                     mon->target_x = 10 + random2(GXM - 10);
                     mon->target_y = 10 + random2(GYM - 10);
                 }
diff --git a/crawl-ref/source/mstuff2.cc b/crawl-ref/source/mstuff2.cc
index b80db9bbba..75e48d46df 100644
--- a/crawl-ref/source/mstuff2.cc
+++ b/crawl-ref/source/mstuff2.cc
@@ -997,7 +997,8 @@ void monster_teleport(struct monsters *monster, bool instan, bool silent)
         return;
     }
 
-    bool was_seen = player_monster_visible(monster) && mons_near(monster);
+    bool was_seen = player_monster_visible(monster) && mons_near(monster)
+                    && monster->behaviour != BEH_LURK;
 
     if (!silent)
         simple_monster_message(monster, " disappears!");
diff --git a/crawl-ref/source/player.cc b/crawl-ref/source/player.cc
index 5434768742..f5214973fd 100644
--- a/crawl-ref/source/player.cc
+++ b/crawl-ref/source/player.cc
@@ -2571,7 +2571,7 @@ int player_see_invis(bool calc_unid)
 bool player_monster_visible( const monsters *mon )
 {
     if (mon->has_ench(ENCH_SUBMERGED)
-        || (mon->invisible() && !player_see_invis()))
+        || mon->invisible() && !player_see_invis())
     {
         return (false);
     }
@@ -2579,13 +2579,13 @@ bool player_monster_visible( const monsters *mon )
     return (true);
 }
 
-// returns true if player is beheld by a given monster
+// Returns true if player is beheld by a given monster.
 bool player_beheld_by( const monsters *mon )
 {
     if (!you.duration[DUR_BEHELD])
         return false;
 
-    // can this monster even behold you?
+    // Can this monster even behold you?
     if (mon->type != MONS_MERMAID)
         return false;
 
diff --git a/crawl-ref/source/religion.cc b/crawl-ref/source/religion.cc
index 5b46c34eb7..a74f75cbcd 100644
--- a/crawl-ref/source/religion.cc
+++ b/crawl-ref/source/religion.cc
@@ -495,7 +495,7 @@ void dec_penance(int val)
 bool beogh_water_walk()
 {
     return (you.religion == GOD_BEOGH && !player_under_penance()
-        && you.piety >= piety_breakpoint(4));
+            && you.piety >= piety_breakpoint(4));
 }
 
 static bool _need_water_walking()
@@ -743,11 +743,10 @@ static void _give_nemelex_gift()
         return;
 
     // Nemelex will give at least one gift early.
-    if ((you.num_gifts[GOD_NEMELEX_XOBEH] == 0
-         && random2(piety_breakpoint(1)) < you.piety) ||
-        (random2(MAX_PIETY) <= you.piety
-         && one_chance_in(3)
-         && !you.attribute[ATTR_CARD_COUNTDOWN]))
+    if (you.num_gifts[GOD_NEMELEX_XOBEH] == 0
+           && random2(piety_breakpoint(1)) < you.piety
+        || random2(MAX_PIETY) <= you.piety && one_chance_in(3)
+           && !you.attribute[ATTR_CARD_COUNTDOWN])
     {
         misc_item_type gift_type;
 
@@ -2580,17 +2579,19 @@ void gain_piety(int pgn)
         }
     }
 
-    // Apply hysteresis
+    // Apply hysteresis.
     {
         // piety_hysteresis is the amount of _loss_ stored up, so this
         // may look backwards.
         const int old_hysteresis = you.piety_hysteresis;
-        you.piety_hysteresis = (unsigned char)std::max<int>(
-            0, you.piety_hysteresis - pgn);
+        you.piety_hysteresis =
+            (unsigned char) std::max<int>( 0, you.piety_hysteresis - pgn );
         const int pgn_borrowed = (old_hysteresis - you.piety_hysteresis);
         pgn -= pgn_borrowed;
+
 #if DEBUG_PIETY
-mprf(MSGCH_DIAGNOSTICS, "Piety increasing by %d (and %d taken from hysteresis)", pgn, pgn_borrowed);
+        mprf(MSGCH_DIAGNOSTICS, "Piety increasing by %d (and %d taken from "
+                                "hysteresis)", pgn, pgn_borrowed);
 #endif
     }
 
@@ -2602,8 +2603,8 @@ mprf(MSGCH_DIAGNOSTICS, "Piety increasing by %d (and %d taken from hysteresis)",
 
     for ( int i = 0; i < MAX_GOD_ABILITIES; ++i )
     {
-        if ( you.piety >= piety_breakpoint(i) &&
-             old_piety < piety_breakpoint(i) )
+        if (you.piety >= piety_breakpoint(i)
+            && old_piety < piety_breakpoint(i))
         {
             take_note(Note(NOTE_GOD_POWER, you.religion, i));
             const char* pmsg = god_gain_power_messages[you.religion][i];
@@ -2971,8 +2972,8 @@ void lose_piety(int pgn)
 
         for ( int i = 0; i < MAX_GOD_ABILITIES; ++i )
         {
-            if ( you.piety < piety_breakpoint(i) &&
-                 old_piety >= piety_breakpoint(i) )
+            if (you.piety < piety_breakpoint(i)
+                && old_piety >= piety_breakpoint(i))
             {
                 const char* pmsg = god_lose_power_messages[you.religion][i];
                 const char first = pmsg[0];
@@ -5574,22 +5575,24 @@ int god_colour( god_type god ) //mv - added
     return(YELLOW);
 }
 
-int piety_rank( int piety )
+int piety_rank(int piety)
 {
     const int breakpoints[] = { 161, 120, 100, 75, 50, 30, 6 };
     const int numbreakpoints = sizeof(breakpoints) / sizeof(int);
-    if ( piety < 0 )
+    if (piety < 0)
         piety = you.piety;
-    for ( int i = 0; i < numbreakpoints; ++i )
-        if ( piety >= breakpoints[i] )
+
+    for (int i = 0; i < numbreakpoints; ++i)
+        if (piety >= breakpoints[i])
             return numbreakpoints - i;
+
     return 0;
 }
 
 int piety_breakpoint(int i)
 {
     int breakpoints[MAX_GOD_ABILITIES] = { 30, 50, 75, 100, 120 };
-    if ( i >= MAX_GOD_ABILITIES || i < 0 )
+    if (i >= MAX_GOD_ABILITIES || i < 0)
         return 255;
     else
         return breakpoints[i];
diff --git a/crawl-ref/source/travel.cc b/crawl-ref/source/travel.cc
index f54a28869a..08abb41ec7 100644
--- a/crawl-ref/source/travel.cc
+++ b/crawl-ref/source/travel.cc
@@ -1437,10 +1437,22 @@ coord_def travel_pathfind::pathfind(run_mode_type rmode)
 
     ignore_hostile = false;
 
-    // Set the seed point
+    // Set the seed point.
+    // For each round, circumference will store all points that were discovered
+    // in the previous round of a given distance. We use an array of size 2,
+    // so we can comfortably switch between the list of points to be
+    // investigated this round and the slowly growing list of points to be
+    // inspected next round. Once we've finished with the current round, i.e.
+    // there are no more points to be looked at in the current array, we switch
+    // circ_index over to !circ_index (between 0 and 1), so the "next round"
+    // becomes the current one, and the old points can be overwritten with
+    // newer ones. Since we count the number of points for next round in
+    // next_iter_points, we don't even need to reset the array.
     circumference[circ_index][0] = start;
 
     // Zap out previous distances array
+    // point_distance will hold the distance of all points from the starting
+    // point, i.e. the distance travelled to get there.
     memset(point_distance, 0, sizeof(travel_distance_grid_t));
 
     for ( ; points > 0; ++traveled_distance, circ_index = !circ_index,
@@ -1448,6 +1460,9 @@ coord_def travel_pathfind::pathfind(run_mode_type rmode)
     {
         for (int i = 0; i < points; ++i)
         {
+            // Look at all neighbours of the current grid.
+            // path_examine_point() returns true if the target is reached
+            // and marked as such.
             if (path_examine_point(circumference[circ_index][i]))
             {
                 return (runmode == RMODE_TRAVEL ? travel_move()
@@ -1455,6 +1470,8 @@ coord_def travel_pathfind::pathfind(run_mode_type rmode)
             }
         }
 
+        // If there are no more points to look at, we're done, but we did
+        // not find a path to our target.
         if (next_iter_points == 0)
         {
             // Don't reseed unless we've found no target for explore, OR
@@ -1671,8 +1688,7 @@ void travel_pathfind::good_square(const coord_def &c)
 {
     if (!point_distance[c.x][c.y])
     {
-        // This point is going to be on the agenda for the next
-        // iteration
+        // This point is going to be on the agenda for the next iteration.
         circumference[!circ_index][next_iter_points++] = c;
         point_distance[c.x][c.y] = traveled_distance;
     }
@@ -1691,6 +1707,9 @@ bool travel_pathfind::point_traverse_delay(const coord_def &c)
     return (false);
 }
 
+// Checks all neighbours of c, adds them to next round's list of points
+// - happens in path_flood() - and returns true if one of them turns out
+// to be the target; otherwise, false.
 bool travel_pathfind::path_examine_point(const coord_def &c)
 {
     if (point_traverse_delay(c))