From 3ed1aedeb73e82e7339e06690524b22c2c79fc78 Mon Sep 17 00:00:00 2001
From: Tung Nguyen <tungtn3@gmail.com>
Date: Fri, 11 Mar 2016 00:24:40 +1100
Subject: [PATCH] Fix travel moving player back and forth infinitely
This fixes a bug where hundreds of turns are wasted by the travel system
moving the player back and forth when the player targets an unreachable
space and sight-blocking obstacles occur in certain formations
in-between. The player will only be stopped if they're interrupted
externally, e.g. growing hungry or being hit by a monster. See the
comment in the code for full details.
Based on DynaHack commit 02da53e (Fix travel moving player back and
forth repeatedly) by me.
---
src/hack.c | 37 ++++++++++++++++++++++++++++++++++++-
1 file changed, 36 insertions(+), 1 deletion(-)
diff --git a/src/hack.c b/src/hack.c
index 6ce28907a..0669978cb 100644
--- a/src/hack.c
+++ b/src/hack.c
@@ -929,7 +929,42 @@ boolean guess;
int nx = x + xdir[ordered[dir]];
int ny = y + ydir[ordered[dir]];
- if (!isok(nx, ny))
+ /*
+ * When guessing and trying to travel as close as possible
+ * to an unreachable target space, don't include spaces
+ * that would never be picked as a guessed target in the
+ * travel matrix describing player-reachable spaces.
+ * This stops travel from getting confused and moving the
+ * player back and forth in certain degenerate configurations
+ * of sight-blocking obstacles, e.g.
+ *
+ * T 1. Dig this out and carry enough to not be
+ * #### able to squeeze through diagonal gaps.
+ * #--.--- Stand at @ and target travel at space T.
+ * @.....
+ * |.....
+ *
+ * T 2. couldsee() marks spaces marked a and x as
+ * #### eligible guess spaces to move the player
+ * a--.--- towards. Space a is closest to T, so it gets
+ * @xxxxx chosen. Travel system moves @ right to travel
+ * |xxxxx to space a.
+ *
+ * T 3. couldsee() marks spaces marked b, c and x
+ * #### as eligible guess spaces to move the player
+ * a--c--- towards. Since findtravelpath() is called
+ * b@xxxx repeatedly during travel, it doesn't remember
+ * |xxxxx that it wanted to go to space a, so in
+ * comparing spaces b and c, b is chosen, since
+ * it seems like the closest eligible space to T.
+ * Travel system moves @ left to go to space b.
+ *
+ * 4. Go to 2.
+ *
+ * By limiting the travel matrix here, space a in the example
+ * above is never included in it, preventing the cycle.
+ */
+ if (!isok(nx, ny) || (guess && !couldsee(nx, ny)))
continue;
if ((!Passes_walls && !can_ooze(&youmonst)
&& closed_door(x, y)) || sobj_at(BOULDER, x, y)
--
2.40.0