Experimental "improved" explore algorithm which can be turned on by

adding "explore_improved=true" to crawlrc.  The intent is to reduce
backtracking and zig-zagging during auto-explore.  Currently only works
with non-greedy explore since I can't yet figure out how to intelligently
combine it with greediness.


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

7 files changed, 103 insertions, 4 deletions

diff --git a/crawl-ref/docs/crawl_options.txt b/crawl-ref/docs/crawl_options.txt
index e84aaf4eec..b25e607c2a 100644
--- a/crawl-ref/docs/crawl_options.txt
+++ b/crawl-ref/docs/crawl_options.txt
@@ -40,11 +40,11 @@ The contents of this text are:
                 scroll_margin
 4-g     Travel and Exploration. 
                 travel_delay, travel_avoid_terrain,
-                explore_greedy, explore_stop, tc_reachable,
+                explore_greedy, explore_stop, explore_improved, tc_reachable,
                 tc_dangerous, tc_excluded, tc_exclude_circle,
-                travel_stop_message, runrest_ignore_message,                    
+                travel_stop_message, runrest_ignore_message,
                 runrest_ignore_poison, runrest_ignore_monster,
-                trapwalk_safe_hp 
+                trapwalk_safe_hp
 4-h     Stashes.
                 stash_tracking, stash_filter
 4-i     Command Enhancements.
@@ -631,6 +631,11 @@ explore_stop = items,stairs,shops,altars,gates
         last explore_stop line will override all previous explore_stop 
         lines. 
 
+explore_improved = false
+        If set to true explore will used an expiremental improved algorithm
+        which is meant to reduce backtracking and zig-zagging.  Currently
+        only works with non-greedy explore.
+
 tc_reachable      = blue
 tc_dangerous      = cyan
 tc_disconnected   = darkgrey
diff --git a/crawl-ref/source/acr.cc b/crawl-ref/source/acr.cc
index 5297da5f0d..117f9bd7df 100644
--- a/crawl-ref/source/acr.cc
+++ b/crawl-ref/source/acr.cc
@@ -3661,6 +3661,7 @@ static void move_player(int move_x, int move_y)
         {
             move_x = random2(3) - 1;
             move_y = random2(3) - 1;
+            you.reset_prev_move();
         }
 
         const int new_targ_x = you.x_pos + move_x;
@@ -3755,6 +3756,9 @@ static void move_player(int move_x, int move_y)
         if (!move_player_to_grid(targ_x, targ_y, true, false, swap))
             return;
 
+        you.prev_move_x = move_x;
+        you.prev_move_y = move_y;
+
         move_x = 0;
         move_y = 0;
 
@@ -3766,7 +3770,11 @@ static void move_player(int move_x, int move_y)
 
     // BCR - Easy doors single move
     if (targ_grid == DNGN_CLOSED_DOOR && Options.easy_open && !attacking)
+    {
         open_door(move_x, move_y, false);
+        you.prev_move_x = move_x;
+        you.prev_move_y = move_y;
+    }
     else if (!targ_pass && !attacking)
     {
         stop_running();
diff --git a/crawl-ref/source/externs.h b/crawl-ref/source/externs.h
index e97594c863..14707eeeb2 100644
--- a/crawl-ref/source/externs.h
+++ b/crawl-ref/source/externs.h
@@ -552,6 +552,9 @@ public:
   int x_pos;
   int y_pos;
 
+  int prev_move_x;
+  int prev_move_y;
+
   int hunger;
   FixedVector<char, NUM_EQUIP> equip;
 
@@ -740,6 +743,9 @@ public:
     // changing x_pos and y_pos directly.
     void moveto(int x, int y);
     void moveto(const coord_def &c);
+
+    coord_def prev_move() const;
+    void reset_prev_move();
     
     bool in_water() const;
     bool can_swim() const;
@@ -1643,6 +1649,9 @@ public:
 
     // How much more eager greedy-explore is for items than to explore.
     int         explore_item_greed;
+
+    // Some experimental improvments to explore
+    bool        explore_improved;
     
     std::vector<sound_mapping> sound_mappings;
     std::vector<colour_mapping> menu_colour_mappings;
diff --git a/crawl-ref/source/files.cc b/crawl-ref/source/files.cc
index 1cd9febc60..049f410a39 100644
--- a/crawl-ref/source/files.cc
+++ b/crawl-ref/source/files.cc
@@ -909,6 +909,10 @@ bool load( dungeon_feature_type stair_taken, load_mode_type load_mode,
         you.transit_stair, stair_taken, DNGN_UNSEEN);
     unwind_bool ylev(you.entering_level, true, false);
 
+    // Going up/down stairs, going through a portal, or being banished
+    // means the previous x/y movement direction is no longer valid.
+    you.reset_prev_move();
+
     const bool make_changes =
         (load_mode != LOAD_RESTART_GAME && load_mode != LOAD_VISITOR);
     
diff --git a/crawl-ref/source/initfile.cc b/crawl-ref/source/initfile.cc
index 5e66290cc5..9a8242cef9 100644
--- a/crawl-ref/source/initfile.cc
+++ b/crawl-ref/source/initfile.cc
@@ -684,6 +684,8 @@ void game_options::reset_options()
 
     explore_item_greed     = 10;
     explore_greedy         = false;
+
+    explore_improved       = false;
     
     target_zero_exp        = false;
     target_wrap            = true;
@@ -2412,6 +2414,10 @@ void game_options::read_option_line(const std::string &str, bool runscript)
     {
         explore_greedy = read_bool(field, explore_greedy);
     }
+    else if (key == "explore_improved")
+    {
+        explore_improved = read_bool(field, explore_improved);
+    }
     else if (key == "stash_tracking")
     {
         stash_tracking =
diff --git a/crawl-ref/source/player.cc b/crawl-ref/source/player.cc
index 2cfa244719..bc36fa055c 100644
--- a/crawl-ref/source/player.cc
+++ b/crawl-ref/source/player.cc
@@ -5271,6 +5271,9 @@ void player::init()
     x_pos = 0;
     y_pos = 0;
 
+    prev_move_x = 0;
+    prev_move_y = 0;
+
     running.clear();
     travel_x = 0;
     travel_y = 0;
@@ -6227,7 +6230,21 @@ void player::moveto(const coord_def &c)
     crawl_view.set_player_at(c);
 
     if (real_move)
+    {
+        you.reset_prev_move();
         dungeon_events.fire_position_event(DET_PLAYER_MOVED, c);
+    }
+}
+
+coord_def player::prev_move() const
+{
+    return coord_def(prev_move_x, prev_move_y);
+}
+
+void player::reset_prev_move()
+{
+    prev_move_x = 0;
+    prev_move_y = 0;
 }
 
 bool player::asleep() const
diff --git a/crawl-ref/source/travel.cc b/crawl-ref/source/travel.cc
index 750201af37..83c9cd1268 100644
--- a/crawl-ref/source/travel.cc
+++ b/crawl-ref/source/travel.cc
@@ -850,7 +850,57 @@ static int find_explore_status(const travel_pathfind &tp)
 static void explore_find_target_square()
 {
     travel_pathfind tp;
-    tp.set_floodseed(coord_def(you.x_pos, you.y_pos), true);
+    coord_def       seed = you.pos();
+
+    // "Improved" explore: keep moving in a line along the same
+    // direction as the previous move, stop if we hit a barrier or
+    // something that would slow us down, and use *that* as the
+    // floodout seed.  This is meant to:
+    //
+    // 1) Prevent explore from sticking its head in a room and then
+    //    backing out even though the room has unexplored corners
+    //    because there are unexplored squares closer than the corners.
+    //
+    // 2) Similarly, prevent the bevahior of going a little bit down
+    //    a long, straight corridor only to back out of it because
+    //    the nearest unexplored square in that corridor is
+    //    LOS_RADIUS + 1 squares away, which is further away than
+    //    another unexplored square which is in the opposite direction.
+    // 
+    // 3) Prevent the annoying zig-zag when exploring open spaces.
+    //
+    // We stop at squres that would slow us down so that we won't slog
+    // across a bunch of shallow water just for the sake of going in
+    // a straight line.
+    //
+    // Not yet used with greedy explore because I can't figure out
+    // how to combined it with greediness in a way that won't display
+    // weird or uninuitive behavior.
+    if (you.running != RMODE_EXPLORE_GREEDY && Options.explore_improved
+        && (you.prev_move_x || you.prev_move_y))
+    {
+        coord_def prev_move_delta = you.prev_move();
+
+        dungeon_feature_type feature;
+        do {
+            seed += prev_move_delta;
+            feature = grd(seed);
+        } while (is_travelsafe_square(seed.x, seed.y)
+                 && is_traversable(feature)
+                 && feature_traverse_cost(feature) == 1);
+
+        seed -= prev_move_delta;
+
+        // Has moving along the straight line found an unexplored
+        // square?  If so, just use that square as the target.
+        if (!is_terrain_seen(seed + prev_move_delta) && seed != you.pos())
+        {
+            you.running.x = seed.x;
+            you.running.y = seed.y;
+            return;
+        }
+    }
+    tp.set_floodseed(seed, true);
 
     coord_def whereto =
         tp.pathfind( static_cast<run_mode_type>(you.running.runmode) );