Greedy-explore tweaks: speedup by not double-floodfilling, and handle inability

to pick stuff up gracefully.

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

6 files changed, 161 insertions, 29 deletions

diff --git a/crawl-ref/source/externs.h b/crawl-ref/source/externs.h
index 01806f710d..f003ea590b 100644
--- a/crawl-ref/source/externs.h
+++ b/crawl-ref/source/externs.h
@@ -848,6 +848,9 @@ public:
                                    // item comes into view
 
     int         explore_stop_prompt;
+
+    // How much more eager greedy-explore is for items than to explore.
+    int         explore_item_greed;
     
     std::vector<sound_mapping> sound_mappings;
     std::vector<colour_mapping> menu_colour_mappings;
diff --git a/crawl-ref/source/initfile.cc b/crawl-ref/source/initfile.cc
index c87f7265be..529ab76e3a 100644
--- a/crawl-ref/source/initfile.cc
+++ b/crawl-ref/source/initfile.cc
@@ -629,6 +629,8 @@ void game_options::reset_options()
     // The prompt conditions will be combined into explore_stop after
     // reading options.
     explore_stop_prompt    = ES_NONE;
+
+    explore_item_greed     = 10;
     
     safe_zero_exp          = true;
     target_zero_exp        = false;
@@ -1944,6 +1946,14 @@ void game_options::read_option_line(const std::string &str, bool runscript)
         else
             explore_stop_prompt |= new_conditions;
     }
+    else if (key == "explore_item_greed")
+    {
+        explore_item_greed = atoi( field.c_str() );
+        if (explore_item_greed > 1000)
+            explore_item_greed = 1000;
+        else if (explore_item_greed < -1000)
+            explore_item_greed = -1000;
+    }
     else if (key == "stash_tracking")
     {
         stash_tracking =
diff --git a/crawl-ref/source/items.cc b/crawl-ref/source/items.cc
index c040288570..9a31ad7d79 100644
--- a/crawl-ref/source/items.cc
+++ b/crawl-ref/source/items.cc
@@ -2923,6 +2923,7 @@ static void autopickup(void)
     //David Loewenstern 6/99
     int result, o, next;
     bool did_pickup = false;
+    bool tried_pickup = false;
 
     if (!can_autopickup())
         return;
@@ -2945,11 +2946,13 @@ static void autopickup(void)
 
             if (result == 0)
             {
+                tried_pickup = true;
                 mpr("You can't carry any more.");
                 break;
             }
             else if (result == -1)
             {
+                tried_pickup = true;
                 mpr("Your pack is full.");
                 break;
             }
@@ -2968,6 +2971,10 @@ static void autopickup(void)
         you.turn_is_over = true;
         start_delay( DELAY_AUTOPICKUP, 1, unthrown );
     }
+    // Greedy explore has no good way to deal with an item that we can't
+    // pick up, so the only thing to do is to stop.
+    else if (tried_pickup && you.running == RMODE_EXPLORE_GREEDY)
+        stop_delay();
 }
 
 int inv_count(void)
@@ -2977,7 +2984,7 @@ int inv_count(void)
     for(int i=0; i< ENDOFPACK; i++)
     {
         if (is_valid_item( you.inv[i] ))
-            count += 1;
+            count++;
     }
 
     return count;
diff --git a/crawl-ref/source/makefile.unix b/crawl-ref/source/makefile.unix
index c656630acb..ac22286d29 100644
--- a/crawl-ref/source/makefile.unix
+++ b/crawl-ref/source/makefile.unix
@@ -34,7 +34,7 @@ INCLUDES := $(INCLUDES) -Iutil -I.
 CFWARN := -Wall -Wwrite-strings \
 	-Wshadow -pedantic
 
-CFOTHERS := -fsigned-char -g -D$(OS_TYPE) $(EXTRA_FLAGS)
+CFOTHERS := -fsigned-char -D$(OS_TYPE) $(EXTRA_FLAGS)
 
 ifneq ($(DATADIR),)
 CFOTHERS += '-DDATA_DIR_PATH="$(DATADIR)"'
@@ -42,7 +42,7 @@ endif
 
 CFLAGS  := $(INCLUDES) $(CFWARN) $(CFOTHERS)
 YCFLAGS := $(INCLUDES) $(CFOTHERS)
-            
+
 
 # If you have lex and yacc, set DOYACC to y (lowercase y).
 DOYACC := y
diff --git a/crawl-ref/source/travel.cc b/crawl-ref/source/travel.cc
index 84bc069b00..6e16d71834 100644
--- a/crawl-ref/source/travel.cc
+++ b/crawl-ref/source/travel.cc
@@ -704,7 +704,7 @@ bool prompt_stop_explore(int es_why)
 
 static bool es_say(const char *what)
 {
-    mprf("Spotted %s.", what);
+    mprf("Found %s.", what);
     return (true);
 }
 
@@ -722,16 +722,29 @@ static bool es_say(const char *what)
 /*
  * Given a square that has just become visible during explore, returns true
  * if the player might consider the square worth stopping explore for.
+ * 
+ * NOTE: These are env.map coords, add +1 to get grid coords.
  */
 static bool is_interesting_square(int x, int y)
 {
-    if (ES_item && igrd[x + 1][y + 1] != NON_ITEM
-        && you.running != RMODE_EXPLORE_GREEDY)
+    if (ES_item && igrd[x + 1][y + 1] != NON_ITEM)
     {
-        mprf("Spotted %s.",
-             item_name( mitm[ igrd[x + 1][y + 1] ], DESC_NOCAP_A ));
-        if (prompt_stop_explore(ES_ITEM))
-            return (true);
+        bool valid_stop = true;
+        if (you.running == RMODE_EXPLORE_GREEDY)
+        {
+            // The things we need to do...
+            const LevelStashes *lev = stashes.find_current_level();
+            if (lev && lev->needs_visit(x + 1, y + 1))
+                valid_stop = false;
+        }
+
+        if (valid_stop)
+        {
+            mprf("Found %s.",
+                 item_name( mitm[ igrd[x + 1][y + 1] ], DESC_NOCAP_A ));
+            if (prompt_stop_explore(ES_ITEM))
+                return (true);
+        }
     }
 
     unsigned char grid = grd[x + 1][y + 1];
@@ -780,6 +793,33 @@ void stop_running(void)
     you.running.stop();
 }
 
+static bool is_valid_explore_target(int x, int y)
+{
+    // If an adjacent square is unmapped, it's valid.
+    for (int yi = -1; yi <= 1; ++yi)
+    {
+        for (int xi = -1; xi <= 1; ++xi)
+        {
+            if (!xi && !yi)
+                continue;
+
+            const int ax = x + xi, ay = y + yi;
+            if (!in_bounds(ax, ay))
+                continue;
+            if (!is_player_mapped( get_envmap_char(ax, ay) ))
+                return (true);
+        }
+    }
+
+    if (you.running == RMODE_EXPLORE_GREEDY)
+    {
+        LevelStashes *lev = stashes.find_current_level();
+        return (lev && lev->needs_visit(x, y));
+    }
+
+    return (false);
+}
+
 /*
  * Top-level travel control (called from input() in acr.cc).
  *
@@ -837,16 +877,23 @@ command_type travel()
             LevelStashes *lev = stashes.find_current_level();
             if (lev && lev->shop_needs_visit(you.x_pos, you.y_pos))
             {
-                stop_running();
+                you.running = 0;
                 return (CMD_GO_UPSTAIRS);
             }
         }
-        
-        you.running.x = 0;
-        find_travel_pos(you.x_pos, you.y_pos, NULL, NULL);
-        // No place to go?
-        if (!you.running.x)
-            stop_running();
+
+        // Speed up explore by not doing a double-floodfill if we have
+        // a valid target.
+        if (!you.running.x
+            || (you.running.x == you.x_pos && you.running.y == you.y_pos)
+            || !is_valid_explore_target(you.running.x, you.running.y))
+        {
+            you.running.x = 0;
+            find_travel_pos(you.x_pos, you.y_pos, NULL, NULL);
+            // No place to go?
+            if (!you.running.x)
+                stop_running();
+        }
     }
 
     if (you.running == RMODE_INTERLEVEL && !you.running.x)
@@ -1004,6 +1051,13 @@ void find_travel_pos(int youx, int youy,
     unsigned char feature;
     LevelStashes *lev = stashes.find_current_level();
 
+    // For greedy explore, keep track of the closest unexplored
+    // territory and the closest greedy square.
+    int e_x = 0, e_y = 0;
+    int i_x = 0, i_y = 0;
+    // Use these weird defaults to handle negative item greeds.
+    int ex_dist = -10000, ix_dist = -10000;
+
     // Normally we start from the destination and floodfill outwards, looking
     // for the character's current position. If we're merely trying to populate
     // the point_distance array (or exploring), we'll want to start from the 
@@ -1110,24 +1164,68 @@ void find_travel_pos(int youx, int youy,
 
                 unsigned char envf = env.map[dx - 1][dy - 1];
 
-                if (floodout && you.running.is_explore()
-                    && (!is_player_mapped(envf)
-                        || (you.running == RMODE_EXPLORE_GREEDY
-                            && is_greed_inducing_square(lev, dx, dy))))
+                if (floodout && you.running.is_explore())
                 {
-                    // Setting running.x and running.y here is evil - this
-                    // function should ideally not modify game state in any way.
                     if (!is_player_mapped(envf))
                     {
-                        you.running.x = x;
-                        you.running.y = y;
+                        if (you.running != RMODE_EXPLORE_GREEDY)
+                        {
+                            you.running.x = x;
+                            you.running.y = y;
+                            return;
+                        }
+
+                        if (ex_dist == -10000)
+                        {
+                            e_x = x;
+                            e_y = y;
+                            ex_dist = 
+                                traveled_distance + Options.explore_item_greed;
+                        }
+                    }
+                    else if (you.running == RMODE_EXPLORE_GREEDY
+                             && ix_dist == -10000
+                             && is_greed_inducing_square(lev, dx, dy))
+                    {
+                        i_x = dx;
+                        i_y = dy;
+                        ix_dist = traveled_distance + 1;
+                    }
+
+                    // Short-circuit if we can.
+                    if (you.running == RMODE_EXPLORE_GREEDY)
+                    {
+                        const int refdist =
+                            Options.explore_item_greed > 0? ex_dist: ix_dist;
+                    
+                        if (refdist != -10000
+                            && traveled_distance > refdist)
+                        {
+                            if (Options.explore_item_greed > 0)
+                                ix_dist = 10000;
+                            else
+                                ex_dist = 10000;
+                        }
                     }
-                    else
+                    
+                    // ex_dist/ix_dist are only ever set in
+                    // greedy-explore so this check implies
+                    // greedy-explore.
+                    if (ex_dist != -10000 && ix_dist != -10000)
                     {
-                        you.running.x = dx;
-                        you.running.y = dy;
+                        if (ex_dist < ix_dist)
+                        {
+                            you.running.x = e_x;
+                            you.running.y = e_y;
+                        }
+                        else
+                        {
+                            you.running.x = i_x;
+                            you.running.y = i_y;
+                        }
+                        return;
                     }
-                    return;
+                    
                 }
 
                 if ((dx != dest_x || dy != dest_y) 
@@ -1236,6 +1334,19 @@ void find_travel_pos(int youx, int youy,
             fill_exclude_radius(exc);
         }
     }
+
+    if (you.running == RMODE_EXPLORE_GREEDY
+        && (ex_dist != -10000 || ix_dist != -10000))
+    {
+        if (ix_dist != -10000)
+        {
+            e_x = i_x;
+            e_y = i_y;
+        }
+
+        you.running.x = e_x;
+        you.running.y = e_y;
+    }
 }
 
 // Mappings of which branches spring from which other branches, essential to
diff --git a/crawl-ref/source/view.h b/crawl-ref/source/view.h
index bbf07baf9a..857cb2c1e7 100644
--- a/crawl-ref/source/view.h
+++ b/crawl-ref/source/view.h
@@ -114,6 +114,7 @@ void clear_map();
 bool is_feature(int feature, int x, int y);
 
 void set_envmap_char( int x, int y, unsigned char chr );
+unsigned get_envmap_char(int x, int y);
 void set_envmap_detected_item(int x, int y, bool detected = true);
 void set_envmap_detected_mons(int x, int y, bool detected = true);
 void set_envmap_col( int x, int y, int colour, int flags );