I think my previous "fix" was actually a misinterpretation of the code.

Accordingly, I'm now limiting total path length to 2x the range, in
addition to preventing any point on that path from being more than
range cells away from the target (as the code did originally).

1 files changed, 16 insertions, 2 deletions

diff --git a/crawl-ref/source/mon-pathfind.cc b/crawl-ref/source/mon-pathfind.cc
index 61f0e1145c..b3c7ac6250 100644
--- a/crawl-ref/source/mon-pathfind.cc
+++ b/crawl-ref/source/mon-pathfind.cc
@@ -211,11 +211,25 @@ bool monster_pathfind::calc_path_to_neighbours()
         if (!traversable(npos) && npos != target)
             continue;
 
+        // Ignore this grid if it takes us above the allowed distance
+        // away from the target.
+        if (range && estimated_cost(npos) > range)
+            continue;
+
         distance = dist[pos.x][pos.y] + travel_cost(npos);
         old_dist = dist[npos.x][npos.y];
 
-        // Ignore this grid if it takes us above the allowed distance.
-        if (range && distance > range)
+        // Also bail out if this would make the path longer than twice the
+        // allowed distance from the target. (This factor may need tuning.)
+        //
+        // This is actually motivated by performance, as pathfinding
+        // in mazes with see-through walls (e.g. plants) can otherwise
+        // soak up a lot of CPU cycles.
+        //
+        // FIXME: This will still happen for monsters with >I_NORMAL
+        // intelligence, since they have range=0 and are therefore
+        // exempt. Should we cap total path length for them, too?
+        if (range && distance > range * 2)
             continue;
 
 #ifdef DEBUG_PATHFIND