Added NSUBST.

Should not highlight unvisited stairs in the Vestibule, since travel cache
doesn't track visited-ness of Vestibule stairs.

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

9 files changed, 256 insertions, 25 deletions

diff --git a/crawl-ref/docs/level-design.txt b/crawl-ref/docs/level-design.txt
index 1a173e5c6f..a2ab8655ca 100644
--- a/crawl-ref/docs/level-design.txt
+++ b/crawl-ref/docs/level-design.txt
@@ -475,6 +475,35 @@ SUBST:   ?=xc, !:bv, 1=2 1:100
          will be applied in order. Multiple substitutions can be performed
          on one line, using commas.
 
+NSUBST:  ? = 3:w / *:l
+
+         NSUBST is similar to SUBST, replacing placeholders with
+         replacements values. Unlike SUBST, however, it allows you to
+         replace different instances of the same placeholder with
+         completely different substitutions. For instance:
+
+         ? = 3:w / *:l
+
+         replaces three occurrences (randomly selected) of ? with w
+         and all others with l.
+         
+         You can use complex SUBST specifications:
+
+         ? = 3= w .:15 A / *: =+CF
+
+         This is equivalent to SUBST: ? = w .:15 A for three ? and
+         SUBST: ? : =+CF for all the others.
+
+         You use any number of NSUBST specifiers:
+
+         ? = wW / l / A / 1234
+
+         Each specifier is preceded by the number of symbols to apply
+         it to, followed by : or = (: to use one substitution for all
+         occurrences, = to randomly pick for each occurrence). If you
+         omit the initial N: or N=, then 1= is assumed, except for the
+         last spec where *= is assumed.
+
 KFEAT:   Z = C / needle trap / antique armour shop / altar of Zin
          The KFEAT: directive allows you to specify a placeholder symbol 
          that is replaced with another symbol, named feature, trap, or 
diff --git a/crawl-ref/source/dat/levdes.vim b/crawl-ref/source/dat/levdes.vim
index f466a49802..b643c9ee6b 100644
--- a/crawl-ref/source/dat/levdes.vim
+++ b/crawl-ref/source/dat/levdes.vim
@@ -41,12 +41,15 @@ syn region desPre start=/^\s*prelude\?\s*{{/ end=/}}\s*$/ contains=@desLuaGroup,
 setlocal iskeyword+=:
 setlocal iskeyword+=-
 
+syn keyword desSubstDec SUBST: contained
+syn keyword desNsubstDec NSUBST: contained
+syn keyword desShuffleDec SHUFFLE: contained
+
 syn region desSubst start=/^SUBST:\s*/ end=/$/ contains=desSubstDec,desSubstArg,desSubstSep,@desMapElements keepend
 
-syn region desShuffle start=/^SHUFFLE:\s*/ end=/$/ contains=desShuffleDec,desMapFrag keepend
+syn region desNsubst start=/^NSUBST:\s*/ end=/$/ contains=desNsubstDec,desSubstArg,desSubstSep,@desMapElements keepend
 
-syn keyword desSubstDec SUBST: contained
-syn keyword desShuffleDec SHUFFLE: contained
+syn region desShuffle start=/^SHUFFLE:\s*/ end=/$/ contains=desShuffleDec,desMapFrag keepend
 
 syn keyword desDeclarator NAME: ORIENT: DEPTH: PLACE: MONS: FLAGS: default-depth: TAGS: CHANCE: ITEM: KFEAT: KMONS: KITEM:
 syn keyword desOrientation encompass north south east west northeast northwest southeast southwest float no_hmirror no_vmirror no_rotate entry pan no_pool_fixup no_monster_gen generate_awake
@@ -88,6 +91,7 @@ syn region desMap start=/^\s*\<MAP\>\s*$/ end=/^\s*\<ENDMAP\>\s*$/ contains=@des
 
 hi link desDeclarator Statement
 hi link desSubstDec   Statement
+hi link desNsubstDec  Statement
 hi link desShuffleDec Statement
 hi link desMapBookend Statement
 hi link desLuaBlock   Statement
diff --git a/crawl-ref/source/luadgn.cc b/crawl-ref/source/luadgn.cc
index d76005102d..6507066111 100644
--- a/crawl-ref/source/luadgn.cc
+++ b/crawl-ref/source/luadgn.cc
@@ -456,19 +456,20 @@ static int dgn_shuffle_remove(lua_State *ls)
     return (0);
 }
 
-static int dgn_subst(lua_State *ls)
+static int dgn_map_add_transform(
+    lua_State *ls,
+    std::string (map_lines::*add)(const std::string &s),
+    void (map_lines::*erase)())
 {
     MAP(ls, 1, map);
-    if (lua_gettop(ls) == 1)
-        return dlua_stringtable(ls, map->get_subst_strings());
 
     for (int i = 2, size = lua_gettop(ls); i <= size; ++i)
     {
         if (lua_isnil(ls, i))
-            map->map.clear_substs();
+            (map->map.*erase)();
         else
         {
-            std::string err = map->map.add_subst(luaL_checkstring(ls, i));
+            std::string err = (map->map.*add)(luaL_checkstring(ls, i));
             if (!err.empty())
                 luaL_error(ls, err.c_str());
         }
@@ -477,6 +478,18 @@ static int dgn_subst(lua_State *ls)
     return (0);    
 }
 
+static int dgn_subst(lua_State *ls)
+{
+    return dgn_map_add_transform(ls, &map_lines::add_subst,
+                                 &map_lines::clear_substs);
+}
+
+static int dgn_nsubst(lua_State *ls)
+{
+    return dgn_map_add_transform(ls, &map_lines::add_nsubst,
+                                 &map_lines::clear_nsubsts);
+}
+
 static int dgn_subst_remove(lua_State *ls)
 {
     MAP(ls, 1, map);
@@ -858,6 +871,7 @@ static const struct luaL_reg dgn_lib[] =
     { "shuffle", dgn_shuffle },
     { "shuffle_remove", dgn_shuffle_remove },
     { "subst", dgn_subst },
+    { "nsubst", dgn_nsubst },
     { "subst_remove", dgn_subst_remove },
     { "map", dgn_map },
     { "mons", dgn_mons },
diff --git a/crawl-ref/source/mapdef.cc b/crawl-ref/source/mapdef.cc
index a4238facf4..0f8b161c2b 100644
--- a/crawl-ref/source/mapdef.cc
+++ b/crawl-ref/source/mapdef.cc
@@ -41,6 +41,19 @@ const char *map_section_name(int msect)
     return map_section_names[msect];
 }
 
+template <typename V>
+void scramble(V &v)
+{
+    V temp(v);
+    v.clear();
+    while (!temp.empty())
+    {
+        int i = random2(temp.size());
+        v.push_back(temp[i]);
+        temp.erase(temp.begin() + i);
+    }
+}
+
 // Returns true if s contains tag 'tag', and strips out tag from s.
 bool strip_tag(std::string &s, const std::string &tag)
 {
@@ -96,9 +109,10 @@ static int find_weight(std::string &s)
 }
 
 static std::string split_key_item(const std::string &s,
-                                  int *key,
+                                  std::string *key,
                                   int *separator,
-                                  std::string *arg)
+                                  std::string *arg,
+                                  int key_max_len = 1)
 {
     std::string::size_type
         norm = s.find("=", 1),
@@ -108,19 +122,18 @@ static std::string split_key_item(const std::string &s,
     if (sep == std::string::npos)
         return ("malformed declaration - must use = or :");
 
-    std::string what_to_subst = trimmed_string(s.substr(0, sep));
+    *key = trimmed_string(s.substr(0, sep));
     std::string substitute    = trimmed_string(s.substr(sep + 1));
 
-    if (what_to_subst.length() != 1)
+    if (key->empty() || (int) key->length() > key_max_len)
         return make_stringf(
             "selector '%s' must be exactly one character in '%s'",
-            what_to_subst.c_str(), s.c_str());
+            key->c_str(), s.c_str());
 
     if (substitute.empty())
         return make_stringf("no substitute defined in '%s'",
                             s.c_str());
 
-    *key = what_to_subst[0];
     *arg = substitute;
     *separator = s[sep];
     
@@ -410,8 +423,8 @@ void map_lines::add_marker(map_marker *marker)
 
 std::string map_lines::add_feature_marker(const std::string &s)
 {
-    std::string arg;
-    int key = 0, sep = 0;
+    std::string key, arg;
+    int sep = 0;
     std::string err = split_key_item(s, &key, &sep, &arg);
     if (!err.empty())
         return (err);
@@ -420,7 +433,7 @@ std::string map_lines::add_feature_marker(const std::string &s)
     if (feat == DNGN_UNSEEN)
         return make_stringf("unknown feature: %s", arg.c_str());
 
-    transforms.push_back(new map_feat_marker_spec(key, feat));    
+    transforms.push_back(new map_feat_marker_spec(key[0], feat));    
     return ("");
 }
 
@@ -521,7 +534,7 @@ std::string map_lines::add_subst(const std::string &sub)
         return ("");
     
     int sep = 0;
-    int key = 0;
+    std::string key;
     std::string substitute;
 
     std::string err = split_key_item(sub, &key, &sep, &substitute);
@@ -533,8 +546,64 @@ std::string map_lines::add_subst(const std::string &sub)
     if (!err.empty())
         return (err);
 
-    transforms.push_back( new subst_spec( key, sep == ':', repl ) );
+    transforms.push_back( new subst_spec( key[0], sep == ':', repl ) );
+
+    return ("");
+}
+
+std::string map_lines::parse_nsubst_spec(const std::string &s,
+                                         subst_spec &spec)
+{
+    std::string key, arg;
+    int sep;
+    std::string err = split_key_item(s, &key, &sep, &arg);
+    if (!err.empty())
+        return err;
+    const int keyval = key == "*"? -1 : atoi(key.c_str());
+    if (!keyval)
+        return make_stringf("Illegal spec: %s", s.c_str());
+    
+    glyph_replacements_t repl;
+    err = parse_glyph_replacements(arg, repl);
+    if (!err.empty())
+        return (err);
+
+    spec = subst_spec(keyval, sep == ':', repl);
+    return ("");
+}
+
+std::string map_lines::add_nsubst(const std::string &s)
+{
+    std::vector<subst_spec> substs;
+
+    int sep;
+    std::string key, arg;
+
+    std::string err = split_key_item(s, &key, &sep, &arg);
+    if (!err.empty())
+        return (err);
+    
+    std::vector<std::string> segs = split_string("/", arg);
+    for (int i = 0, size = segs.size(); i < size; ++i)
+    {
+        std::string &ns = segs[i];
+        if (ns.find('=') == std::string::npos
+            && ns.find(':') == std::string::npos)
+        {
+            if (i < size - 1)
+                ns = "1=" + ns;
+            else
+                ns = "*=" + ns;
+        }
+        subst_spec spec;
+        err = parse_nsubst_spec(ns, spec);
+        if (!err.empty())
+            return (make_stringf("Bad NSUBST spec: %s (%s)",
+                                 s.c_str(), err.c_str()));
+        substs.push_back(spec);
+    }
 
+    transforms.push_back( new nsubst_spec(key[0], substs) );
     return ("");
 }
 
@@ -617,6 +686,11 @@ void map_lines::clear_shuffles()
     clear_transforms(map_transformer::TT_SHUFFLE);
 }
 
+void map_lines::clear_nsubsts()
+{
+    clear_transforms(map_transformer::TT_NSUBST);
+}
+
 void map_lines::clear_substs()
 {
     clear_transforms(map_transformer::TT_SUBST);    
@@ -709,6 +783,44 @@ void map_lines::subst(subst_spec &spec)
         subst(lines[y], spec);
 }
 
+void map_lines::nsubst(nsubst_spec &spec)
+{
+    std::vector<coord_def> positions;
+    for (int y = 0, ysize = lines.size(); y < ysize; ++y)
+    {
+        std::string::size_type pos = 0;
+        while ((pos = lines[y].find(spec.key, pos)) != std::string::npos)
+            positions.push_back(coord_def(pos++, y));
+    }
+    scramble(positions);
+
+    int pcount = 0;
+    const int psize = positions.size();
+    for (int i = 0, size = spec.specs.size(); i < size && pcount < psize; ++i)
+    {
+        const int nsubsts = spec.specs[i].key();
+        pcount += apply_nsubst(positions, pcount, nsubsts, spec.specs[i]);
+    }
+}
+
+int map_lines::apply_nsubst(std::vector<coord_def> &pos,
+                             int start, int nsub,
+                             subst_spec &spec)
+{
+    if (nsub == -1)
+        nsub = pos.size();
+    const int end = std::min(start + nsub, (int) pos.size());
+    int substituted = 0;
+    for (int i = start; i < end; ++i)
+    {
+        const int val = spec.value();
+        const coord_def &c = pos[i];
+        lines[c.y][c.x] = val;
+        ++substituted;
+    }
+    return (substituted);
+}
+
 std::string map_lines::block_shuffle(const std::string &s)
 {
     std::vector<std::string> segs = split_string("/", s);
@@ -1525,16 +1637,15 @@ std::string map_def::add_key_field(
     const std::string &s,
     std::string (keyed_mapspec::*set_field)(const std::string &s, bool fixed))
 {
-    int key = 0;
     int separator = 0;
-    std::string arg;
+    std::string key, arg;
 
     std::string err = split_key_item(s, &key, &separator, &arg);
     if (!err.empty())
         return (err);
 
-    keyed_mapspec &km = keyspecs[key];
-    km.key_glyph = key;
+    keyed_mapspec &km = keyspecs[key[0]];
+    km.key_glyph = key[0];
     return ((km.*set_field)(arg, separator == ':'));
 }
 
@@ -2159,6 +2270,30 @@ bool subst_spec::operator == (const subst_spec &other) const
 }
 
 //////////////////////////////////////////////////////////////////////////
+// nsubst_spec
+
+nsubst_spec::nsubst_spec(int _key, const std::vector<subst_spec> &_specs)
+    : key(_key), specs(_specs)
+{
+}
+
+std::string nsubst_spec::apply_transform(map_lines &map)
+{
+    map.nsubst(*this);
+    return ("");
+}
+
+map_transformer *nsubst_spec::clone() const
+{
+    return new nsubst_spec(key, specs);
+}
+
+std::string nsubst_spec::describe() const
+{
+    return ("");
+}
+
+//////////////////////////////////////////////////////////////////////////
 // shuffle_spec
 
 std::string shuffle_spec::apply_transform(map_lines &map)
diff --git a/crawl-ref/source/mapdef.h b/crawl-ref/source/mapdef.h
index d761668f3d..4cc77e0af9 100644
--- a/crawl-ref/source/mapdef.h
+++ b/crawl-ref/source/mapdef.h
@@ -79,6 +79,7 @@ public:
     {
         TT_SHUFFLE,
         TT_SUBST,
+        TT_NSUBST,
         TT_MARKER
     };
     
@@ -94,6 +95,7 @@ class subst_spec : public map_transformer
 {
 public:
     subst_spec(int torepl, bool fix, const glyph_replacements_t &repls);
+    subst_spec() : foo(0), fix(false), frozen_value(0), repl() { }
 
     int key() const
     {
@@ -117,6 +119,21 @@ private:
     glyph_replacements_t repl;
 };
 
+class nsubst_spec : public map_transformer
+{
+public:
+    nsubst_spec(int key, const std::vector<subst_spec> &specs);
+    std::string apply_transform(map_lines &map);
+    map_transformer *clone() const;
+    transform_type type() const { return TT_NSUBST; }
+    std::string describe() const;
+    
+public:
+    int key;
+    std::vector<subst_spec> specs;
+};
+
+
 struct shuffle_spec : public map_transformer
 {
     std::string shuffle;
@@ -159,12 +176,14 @@ public:
     map_lines &operator = (const map_lines &);
 
     void add_line(const std::string &s);
+    std::string add_nsubst(const std::string &st);
     std::string add_subst(const std::string &st);
     std::string add_shuffle(const std::string &s);
     void remove_shuffle(const std::string &s);
     void remove_subst(const std::string &s);
     void clear_shuffles();
     void clear_substs();
+    void clear_nsubsts();
     void clear_markers();
 
     std::vector<coord_def> find_glyph(int glyph) const;
@@ -218,6 +237,7 @@ private:
     void resolve_shuffle(const std::string &shuffle);
     void subst(std::string &s, subst_spec &spec);
     void subst(subst_spec &);
+    void nsubst(nsubst_spec &);
     void check_borders();
     void clear_transforms(map_transformer::transform_type);
     std::string shuffle(std::string s);
@@ -225,10 +245,16 @@ private:
     std::string check_shuffle(std::string &s);
     std::string check_block_shuffle(const std::string &s);
     std::string clean_shuffle(std::string s);
+    std::string parse_nsubst_spec(const std::string &s,
+                                  subst_spec &spec);
+    int apply_nsubst(std::vector<coord_def> &pos,
+                     int start, int nsub,
+                     subst_spec &spec);
     std::string parse_glyph_replacements(std::string s,
                                          glyph_replacements_t &gly);
 
     friend class subst_spec;
+    friend class nsubst_spec;
     friend class shuffle_spec;
     
 private:
diff --git a/crawl-ref/source/mtransit.cc b/crawl-ref/source/mtransit.cc
index 01a57917dd..3cab171bc8 100644
--- a/crawl-ref/source/mtransit.cc
+++ b/crawl-ref/source/mtransit.cc
@@ -86,6 +86,10 @@ void place_followers()
 
 static bool place_lost_monster(follower &f)
 {
+#ifdef DEBUG_DIAGNOSTICS
+    mprf(MSGCH_DIAGNOSTICS, "Placing lost one: %s",
+         f.mons.name(DESC_PLAIN).c_str());
+#endif    
     return (f.place(false));
 }
 
diff --git a/crawl-ref/source/util/levcomp.lpp b/crawl-ref/source/util/levcomp.lpp
index 49a7456ecc..b4010596c5 100644
--- a/crawl-ref/source/util/levcomp.lpp
+++ b/crawl-ref/source/util/levcomp.lpp
@@ -175,6 +175,7 @@ WEIGHT:             return CHANCE;
 FLAGS:              { BEGIN(KEYWORDS); return TAGS; }
 TAGS:               { BEGIN(KEYWORDS); return TAGS; }
 SUBST:              { BEGIN(ITEM_LIST); return SUBST; }
+NSUBST:             { BEGIN(ITEM_LIST); return NSUBST; }
 MONS:               { BEGIN(MNAME); return MONS; }
 ITEM:               { BEGIN(ITEM_LIST); return ITEM; }
 MARKER:             { BEGIN(ITEM_LIST); return MARKER; }
diff --git a/crawl-ref/source/util/levcomp.ypp b/crawl-ref/source/util/levcomp.ypp
index 136b03673c..d3470e7baf 100644
--- a/crawl-ref/source/util/levcomp.ypp
+++ b/crawl-ref/source/util/levcomp.ypp
@@ -67,7 +67,7 @@ level_range set_range(const char *s, int start, int end)
 
 %token <i>      DEFAULT_DEPTH SHUFFLE SUBST TAGS KFEAT KITEM KMONS
 %token <i>      NAME DEPTH ORIENT PLACE CHANCE MONS ITEM MARKER
-%token <i>      PRELUDE MAIN VALIDATE VETO
+%token <i>      PRELUDE MAIN VALIDATE VETO NSUBST
 
 %token <i>      COMMA INTEGER CHARACTER
 
@@ -167,6 +167,7 @@ metaline        : place
                 | items
                 | marker
                 | subst
+                | nsubst
                 | shuffle
                 | tags
                 | kfeat
@@ -308,6 +309,22 @@ marker_spec     : ITEM_INFO
                 }
                 ;
 
+nsubst          : NSUBST nsubst_specifiers { }
+                ;
+
+nsubst_specifiers : nsubst_spec
+                  | nsubst_specifiers COMMA nsubst_spec
+                  ;
+
+nsubst_spec     : ITEM_INFO
+                {
+                    lc_map.main.add(
+                        yylineno, 
+                        make_stringf("nsubst(\"%s\")", 
+                            quote_lua_string($1).c_str()));
+                }
+                ;
+                
 subst           : SUBST subst_specifiers { }
                 ;
 
diff --git a/crawl-ref/source/view.cc b/crawl-ref/source/view.cc
index 4ea107e343..8df3cb2ca4 100644
--- a/crawl-ref/source/view.cc
+++ b/crawl-ref/source/view.cc
@@ -308,7 +308,8 @@ static int view_emphasised_colour(int x, int y, dungeon_feature_type feat,
 {
     if (is_travelable_stair(feat) && !travel_cache.know_stair(coord_def(x, y)))
     {
-        if (you.your_level || stair_direction(feat) == CMD_GO_DOWNSTAIRS)
+        if ((you.your_level || stair_direction(feat) == CMD_GO_DOWNSTAIRS)
+            && you.where_are_you != BRANCH_VESTIBULE_OF_HELL)
             return (newcolour);
     }
     return (oldcolour);