Implement passive mapping

As you explore, a halo of mapping tracks you.  The halo includes a
percentage of tiles within a distance of every seen tile; optimal
play dictates seeing every tile, which just happens to be what
autoexplore does.  Added as random generation and to the demonspawn
tier-2 list.

Signed-off-by: Darshan Shaligram <dshaligram@users.sourceforge.net>

4 files changed, 116 insertions, 16 deletions

diff --git a/crawl-ref/source/enum.h b/crawl-ref/source/enum.h
index 634f8db364..91f4749898 100644
--- a/crawl-ref/source/enum.h
+++ b/crawl-ref/source/enum.h
@@ -2413,6 +2413,7 @@ enum mutation_type
     MUT_PATTERNED_SCALES,
 
     MUT_STOCHASTIC_TORMENT_RESISTANCE,
+    MUT_PASSIVE_MAPPING,
     NUM_MUTATIONS,
 
     RANDOM_MUTATION = 100,
diff --git a/crawl-ref/source/mutation.cc b/crawl-ref/source/mutation.cc
index 807e6e522d..f50a13c5c5 100644
--- a/crawl-ref/source/mutation.cc
+++ b/crawl-ref/source/mutation.cc
@@ -28,6 +28,7 @@
 #include "delay.h"
 #include "defines.h"
 #include "effects.h"
+#include "files.h"
 #include "format.h"
 #include "godabil.h"
 #include "itemprop.h"
@@ -41,6 +42,7 @@
 #include "stuff.h"
 #include "transfor.h"
 #include "tutorial.h"
+#include "view.h"
 #include "xom.h"
 
 static int _body_covered();
@@ -1194,6 +1196,21 @@ mutation_def mutation_defs[] = {
       {"","",""},
 
       "stochastic torment resistance"},
+    { MUT_PASSIVE_MAPPING,            3,  3, false, false,
+      {"You sense your immediate surroundings while exploring..",
+       "You sense your surroundings while exploring.",
+       "You sense a large area of your surroundings while exploring."},
+
+      {"You feel aware of your new surroundings.",
+       "You feel more aware of your new surroundings.",
+       "You feel even more aware of your new surroundings."},
+
+      {"You feel slightly disoriented.",
+       "You feel slightly disoriented.",
+       "You feel slightly disoriented."},
+
+      "passive mapping"
+    },
 };
 
 const mutation_def& get_mutation_def(mutation_type mut)
@@ -2068,6 +2085,12 @@ static bool _physiology_mutation_conflict(mutation_type mutat)
     return (false);
 }
 
+static bool _reautomap_callback()
+{
+    reautomap_level();
+    return true;
+}
+
 bool mutate(mutation_type which_mutation, bool failMsg,
             bool force_mutation, bool god_gift, bool stat_gain_potion,
             bool demonspawn, bool non_fatal)
@@ -2362,6 +2385,8 @@ bool mutate(mutation_type which_mutation, bool failMsg,
         calc_hp();
     if (mutat == MUT_LOW_MAGIC || mutat == MUT_HIGH_MAGIC)
         calc_mp();
+    if (mutat == MUT_PASSIVE_MAPPING)
+        apply_to_all_dungeons(_reautomap_callback);
 
     // Amusement value will be 16 * (11-rarity) * Xom's-sense-of-humor.
     xom_is_stimulated(_calc_mutation_amusement_value(mutat));
@@ -2690,7 +2715,8 @@ void roll_demonspawn_mutations()
         MUT_REPULSION_FIELD, MUT_MAGIC_RESISTANCE, MUT_BREATHE_FLAMES,
         MUT_NACREOUS_SCALES, MUT_GREY2_SCALES, MUT_BLACK2_SCALES,
         MUT_WHITE_SCALES, MUT_YELLOW_SCALES, MUT_BROWN_SCALES,
-        MUT_PURPLE_SCALES, MUT_INDIGO_SCALES, MUT_COLD_RESISTANCE
+        MUT_PURPLE_SCALES, MUT_INDIGO_SCALES, MUT_COLD_RESISTANCE,
+        MUT_PASSIVE_MAPPING
     };
 
     // "Good" mutations are rarely noticed; they improve your character
diff --git a/crawl-ref/source/view.cc b/crawl-ref/source/view.cc
index 1ff414295a..2f67488c36 100644
--- a/crawl-ref/source/view.cc
+++ b/crawl-ref/source/view.cc
@@ -269,17 +269,36 @@ void set_terrain_mapped( int x, int y )
 #endif
 }
 
+static void _automap_from( int x, int y, int mutated )
+{
+    if (mutated)
+        magic_mapping(8 * mutated, 5 * mutated, true, false,
+                      true, coord_def(x,y));
+}
+
+void reautomap_level( )
+{
+    int passive = player_mutation_level(MUT_PASSIVE_MAPPING);
+
+    for (int x = X_BOUND_1; x <= X_BOUND_2; ++x)
+        for (int y = Y_BOUND_1; y <= Y_BOUND_2; ++y)
+            if (env.map[x][y].flags & MAP_SEEN_FLAG)
+                _automap_from(x, y, passive);
+}
+
 void set_terrain_seen( int x, int y )
 {
     const dungeon_feature_type feat = grd[x][y];
 
     // First time we've seen a notable feature.
-    if (!(env.map[x][y].flags & MAP_SEEN_FLAG) && is_notable_terrain(feat))
+    if (!(env.map[x][y].flags & MAP_SEEN_FLAG))
     {
-        const bool boring =
+        _automap_from(x, y, player_mutation_level(MUT_PASSIVE_MAPPING));
+
+        const bool boring = !is_notable_terrain(feat)
             // A portal deeper into the Zigguart is boring.
-            (feat == DNGN_ENTER_PORTAL_VAULT
-             && you.level_type == LEVEL_PORTAL_VAULT)
+            || (feat == DNGN_ENTER_PORTAL_VAULT
+                && you.level_type == LEVEL_PORTAL_VAULT)
             // Altars in the temple are boring.
             || (feat_is_altar(feat)
                 && player_in_branch(BRANCH_ECUMENICAL_TEMPLE))
@@ -295,7 +314,7 @@ void set_terrain_seen( int x, int y )
         if (!boring)
         {
             coord_def pos(x, y);
-            std::string desc = 
+            std::string desc =
                 feature_description(pos, false, DESC_NOCAP_A);
 
             take_note(Note(NOTE_SEEN_FEAT, 0, 0, desc.c_str()));
@@ -2851,10 +2870,57 @@ void show_map( coord_def &spec_place, bool travel_mode )
     }
 }
 
+// We logically associate a difficulty parameter with each tile on each level,
+// to make deterministic magic mapping work.  This function returns the
+// difficulty parameters for each tile on the current level, whose difficulty
+// is less than a certain amount.
+//
+// Random difficulties are used in the few cases where we want repeated maps
+// to give different results; scrolls and cards, since they are a finite
+// resource.
+static const FixedArray<char, GXM, GYM>& _tile_difficulties(bool random)
+{
+    // We will often be called with the same level parameter and cutoff, so
+    // cache this (DS with passive mapping autoexploring could be 5000 calls
+    // in a second or so).
+    static FixedArray<char, GXM, GYM> cache;
+    static int cache_seed = -1;
+
+    int seed = random ? -1 :
+        (static_cast<int>(you.where_are_you) << 8) + you.your_level - 1731813538;
+
+    if (seed == cache_seed && !random)
+    {
+        return cache;
+    }
+
+    if (!random)
+    {
+        push_rng_state();
+        seed_rng(cache_seed);
+    }
+
+    cache_seed = seed;
+
+    for (int y = Y_BOUND_1; y <= Y_BOUND_2; ++y)
+        for (int x = X_BOUND_1; x <= X_BOUND_2; ++x)
+            cache[x][y] = random2(100);
+
+    if (!random)
+    {
+        pop_rng_state();
+    }
+
+    return cache;
+}
+
 // Returns true if it succeeded.
 bool magic_mapping(int map_radius, int proportion, bool suppress_msg,
-                   bool force)
+                   bool force, bool deterministic, coord_def pos)
 {
+    if (!in_bounds(pos))
+        pos = you.pos();
+
     if (!force
         && (testbits(env.level_flags, LFLAG_NO_MAGIC_MAP)
             || testbits(get_branch_flags(), BFLAG_NO_MAGIC_MAP)))
@@ -2882,19 +2948,24 @@ bool magic_mapping(int map_radius, int proportion, bool suppress_msg,
     bool did_map = false;
     int  num_altars        = 0;
     int  num_shops_portals = 0;
-    for (radius_iterator ri(you.pos(), map_radius, true, false); ri; ++ri)
-    {
-        if (proportion < 100 && random2(100) >= proportion)
-            continue;       // note that proportion can be over 100
 
+    const FixedArray<char, GXM, GYM>& difficulty =
+        _tile_difficulties(!deterministic);
+
+    for (radius_iterator ri(pos, map_radius, true, false); ri; ++ri)
+    {
         if (!wizard_map)
         {
+            int threshold = proportion;
+
             const int dist = grid_distance( you.pos(), *ri );
 
-            if (dist > pfar && one_chance_in(3))
-                continue;
+            if (dist > very_far)
+                threshold = threshold / 3;
+            else if (dist > pfar)
+                threshold = threshold * 2 / 3;
 
-            if (dist > very_far && coinflip())
+            if (difficulty(*ri) > threshold)
                 continue;
         }
 
@@ -4808,4 +4879,3 @@ void handle_terminal_resize(bool redraw)
     if (redraw)
         redraw_screen();
 }
-
diff --git a/crawl-ref/source/view.h b/crawl-ref/source/view.h
index 44cd06863b..d760e8726b 100644
--- a/crawl-ref/source/view.h
+++ b/crawl-ref/source/view.h
@@ -10,6 +10,7 @@
 
 
 #include "externs.h"
+#include "player.h"
 
 // various elemental colour schemes... used for abstracting random
 // short lists. When adding colours, please also add their names in
@@ -70,7 +71,9 @@ void find_features(const std::vector<coord_def>& features,
         unsigned char feature, std::vector<coord_def> *found);
 
 bool magic_mapping(int map_radius, int proportion, bool suppress_msg,
-                   bool force = false);
+                   bool force = false, bool deterministic = false,
+                   coord_def origin = coord_def(-1, -1));
+void reautomap_level();
 
 bool noisy(int loudness, const coord_def& where, int who,
            bool mermaid = false);