Lua map improvements.

The previous dungeon layout.des functions all apply directly to the grid
and so are unsuitable for use in vaults.  This aims to correct that by
providing lua functions that can manipulate maps (of glyphs).

grd[x][y] in a .des file can now be used to get and set glyphs in the
current map.  This should allow for less cumbersome map variations
than what you can do with just SUBST and SHUFFLE.

To support that, map_def no longer batches up transforms--it applies
them all immediately.  This resulted in a good bit of refactoring.

FTILE/RTILE map commands now support setting the tile for multiple
features at once.

There are also a small number of new lua functions that apply to maps
(map_octa_room, map_smear, and map_extend).  Ideally, these will
eventually replace the existing builder funcs that work on grd.

10 files changed, 614 insertions, 418 deletions

diff --git a/crawl-ref/docs/develop/level_design.txt b/crawl-ref/docs/develop/level_design.txt
index f68a1b166f..0788a355f7 100644
--- a/crawl-ref/docs/develop/level_design.txt
+++ b/crawl-ref/docs/develop/level_design.txt
@@ -736,6 +736,9 @@ FTILE:    . = floor_grass:20 / floor_dirt / none
           destroyed, this floor tile will be used in place of the normal floor.
           Thus, it can be useful even for non-floor features.
 
+          For convenience, multiple glyphs can be specified together as a
+          group, e.g. ".[{( = floor_orc".
+
           Like COLOUR, this should be used sparingly.
 
 RTILE:    x = wall_hive:15 / wall_lair / none
@@ -1847,6 +1850,17 @@ mons_from_index, change_level_flags, change_branch_flags,
 set_random_mon_list
 
 
+Additionally, the dgn module provides a global "grd" variable that
+can access the current map glyphs.  The top left symbol in the map
+can be assigned like this:
+
+ grd[1][1] = 'x'
+
+The bottom right symbol can be assigned like this:
+
+ grd[width()][height()] = "."
+
+
 Lua API - global game state
 ---------------------------
 
diff --git a/crawl-ref/source/clua.cc b/crawl-ref/source/clua.cc
index 9743019e9d..44f4cd0393 100644
--- a/crawl-ref/source/clua.cc
+++ b/crawl-ref/source/clua.cc
@@ -597,6 +597,7 @@ void luaopen_crawl(lua_State *ls);
 void luaopen_file(lua_State *ls);
 void luaopen_options(lua_State *ls);
 void luaopen_monsters(lua_State *ls);
+void luaopen_grd(lua_State *ls);
 void luaopen_globals(lua_State *ls);
 
 void CLua::init_lua()
@@ -626,6 +627,7 @@ void CLua::init_lua()
     luaopen_file(_state);
     luaopen_options(_state);
     luaopen_monsters(_state);
+    luaopen_grd(_state);
 
     luaopen_globals(_state);
 
@@ -2788,6 +2790,109 @@ void luaopen_monsters(lua_State *ls)
     luaL_openlib(ls, "mons", mons_lib, 0);
 }
 
+/////////////////////////////////////////////////////////////////////
+// grd and grd_col handling (i.e. map_lines in a metatable)
+
+struct mapcolumn
+{
+    map_def* map;
+    int col;
+};
+
+static int grd_get(lua_State *ls)
+{
+    // Return a metatable for this column in the map grid.
+    map_def *map = *(map_def **) luaL_checkudata(ls, 1, GRD_METATABLE);
+
+    int column = luaL_checkint(ls, 2);
+
+    mapcolumn *mapref = clua_new_userdata<mapcolumn>(ls, GRD_COL_METATABLE);
+    mapref->map = map;
+    mapref->col = column;
+
+    return (1);
+}
+
+static int grd_set(lua_State *ls)
+{
+    return (luaL_error(ls, "%s", "Cannot assign to read-only table."));
+}
+
+static char* grd_glyph(lua_State *ls, int &col, int &row)
+{
+    mapcolumn *mapc = (mapcolumn *)luaL_checkudata(ls, 1, GRD_COL_METATABLE);
+    row = luaL_checkint(ls, 2);
+    col = mapc->col;
+
+    map_lines &lines = mapc->map->map;
+    if (row < 1 || col < 1 || col > lines.width() || row > lines.height())
+    {
+        return (NULL);
+    }
+
+    coord_def mc(col - 1, row - 1);
+    return (&lines(mc));
+}
+
+static int grd_col_get(lua_State *ls)
+{
+    int col, row;
+    char *gly = grd_glyph(ls, col, row);
+    if (!gly)
+        return (luaL_error(ls, "Invalid coords: %d, %d", col, row));
+
+    char buf[2];
+    buf[0] = *gly;
+    buf[1] = '\0';
+    
+    lua_pushstring(ls, buf); 
+
+    return (1);
+}
+
+static int grd_col_set(lua_State *ls)
+{
+    int col, row;
+    char *gly = grd_glyph(ls, col, row);
+    if (!gly)
+        return (luaL_error(ls, "Invalid coords: %d, %d", col, row));
+
+    const char *str = luaL_checkstring(ls, 3);
+    if (!str[0] || str[1])
+        return (luaL_error(ls, "%s", "grd must be set to a single char."));
+
+    (*gly) = str[0];
+
+    return (0);
+}
+
+void luaopen_grd(lua_State *ls)
+{
+    // grd table
+    luaL_newmetatable(ls, GRD_METATABLE);
+    lua_pushstring(ls, "__index");
+    lua_pushcfunction(ls, grd_get);
+    lua_settable(ls, -3);
+
+    lua_pushstring(ls, "__newindex");
+    lua_pushcfunction(ls, grd_set);
+    lua_settable(ls, -3);
+
+    lua_pop(ls, 1);
+
+    // grd col table    
+    luaL_newmetatable(ls, GRD_COL_METATABLE);
+    lua_pushstring(ls, "__index");
+    lua_pushcfunction(ls, grd_col_get);
+    lua_settable(ls, -3);
+
+    lua_pushstring(ls, "__newindex");
+    lua_pushcfunction(ls, grd_col_set);
+    lua_settable(ls, -3);
+
+    lua_pop(ls, 1);
+}
+
 //////////////////////////////////////////////////////////////////////
 // Miscellaneous globals
 
diff --git a/crawl-ref/source/clua.h b/crawl-ref/source/clua.h
index a6ed4ac413..f98e80076f 100644
--- a/crawl-ref/source/clua.h
+++ b/crawl-ref/source/clua.h
@@ -320,5 +320,7 @@ void print_clua_stack();
 #define MAP_METATABLE "dgn.mtmap"
 #define DEVENT_METATABLE "dgn.devent"
 #define MAPMARK_METATABLE "dgn.mapmark"
+#define GRD_METATABLE "dgn.grd"
+#define GRD_COL_METATABLE "dgn.grdcol"
 
 #endif
diff --git a/crawl-ref/source/dat/clua/dungeon.lua b/crawl-ref/source/dat/clua/dungeon.lua
index 5d178b891d..b1cc8de795 100644
--- a/crawl-ref/source/dat/clua/dungeon.lua
+++ b/crawl-ref/source/dat/clua/dungeon.lua
@@ -75,6 +75,10 @@ function dgn_map_meta_wrap(map, tab)
                     return crawl.err_trace(val, map, ...)
                  end
    end
+
+   -- Convenience global variable, e.g. grd[x][y] = 'x'
+   meta['grd'] = dgn.grd_table(map)
+
    meta['_G'] = meta
    meta.wrapped_instance = map
    return meta
@@ -89,19 +93,21 @@ function dgn_set_map(map)
    g_dgn_curr_map = map
 end
 
-function dgn_run_map(prelude, main)
-   if prelude or main then
+function dgn_run_map(prelude, map, main)
+   if prelude or map or main then
       local env = dgn_map_meta_wrap(g_dgn_curr_map, dgn)
+      local ret
       if prelude then
-         local fn = setfenv(prelude, env)
-         if not main then
-            return fn()
-         end
-         fn()
+         ret = setfenv(prelude, env)()
+      end
+      if map then
+         ret = setfenv(map, env)()
+         dgn.normalise(g_dgn_curr_map)
       end
       if main then
-         return setfenv(main, env)()
+         ret = setfenv(main, env)()
       end
+      return ret
    end
 end
 
@@ -387,4 +393,4 @@ dgn.good_scrolls = [[
     w:5   scroll of vorpalise weapon /
     w:5   scroll of immolation / 
     w:5   scroll of vulnerability
-    ]]
\ No newline at end of file
+    ]]
diff --git a/crawl-ref/source/dat/entry.des b/crawl-ref/source/dat/entry.des
index a1c3d59a0e..591e284510 100644
--- a/crawl-ref/source/dat/entry.des
+++ b/crawl-ref/source/dat/entry.des
@@ -2484,7 +2484,7 @@ ORIENT:  float
 MONS:    plant
 SHUFFLE: 1x
 SUBST:   x = '
-FTILE:   ' = floor_grass, 1 = floor_grass, { = floor_grass
+FTILE:   '1{ = floor_grass
 FTILE:   . = floor_grass / floor_normal
 COLOUR:  ' = green
 COLOUR:  . = green / none
@@ -3495,9 +3495,7 @@ MONS:    w:30 nothing / ooze / w:2 jelly / giant cockroach / w:2 worm / \
 # There is a very slight chance that a jelly or an intelligent monster
 # (hobgoblin) might spawn inside near the door. This is okay; added an exit.
 ORIENT:  float
-FTILE:   1=floor_dirt, 2=floor_dirt, 3=floor_dirt, 4=floor_dirt, +=floor_dirt
-FTILE:   A=floor_dirt, B=floor_dirt, C=floor_dirt, D=floor_dirt, E=floor_dirt
-FTILE:   a=floor_dirt, b=floor_dirt, c=floor_dirt, d=floor_dirt, e=floor_dirt
+FTILE:   1234+ABCDEabcde = floor_dirt
 SHUFFLE: abcde / fghij
 SUBST:   f=A, g=B, h=C, i=D, j=E
 SUBST:   a=mx, b=mx, c=mx, d=mx, e=mx
@@ -4822,7 +4820,7 @@ ENDMAP
 NAME:   misc_entry_001
 TAGS:   entry no_monster_gen
 RTILE:  x = wall_hall
-FTILE:  . = floor_hall, ( = floor_hall, [ = floor_hall, { = floor_hall
+FTILE:  .([{ = floor_hall
 ORIENT: float
 
 MAP
@@ -4885,9 +4883,7 @@ NAME:   exit_the_forest
 TAGS:   entry no_rotate no_pool_fixup
 ORIENT: northwest
 MONS:   plant
-FTILE:  . = floor_lair
-FTILE:  t = floor_lair
-FTILE:  1 = floor_lair
+FTILE:  .t1 = floor_lair
 MAP
 ttttttttttttttttttttttttttttttttttttttttttt
 tttttttttttt1ttttttwwtttttttttttttttttttttt
@@ -4916,3 +4912,41 @@ tt....
 t..
 t.
 ENDMAP
+
+###########################################################
+# Basic island, with variations
+#
+NAME:   enne_octagon_isle
+ORIENT: float
+TAGS:   entry
+FTILE:  '[({ = floor_sand_stone
+SUBST:  ' = .
+{{
+    map_octa_room({
+        oblique = crawl.random_range(3,7),
+        replace = '.',
+        outside = 'W',
+        inside  = '.'
+    })
+    if crawl.coinflip() then
+        map_smear({iterations=20, smear='x', onto='.W', boxy = true})
+    end
+}}
+SUBST: W:xw
+MAP
+ xxxxxxxxxxxxx 
+x.............x
+x.............x
+x.............x
+x.............x
+......www......
+.....w[''w.....
+@....w'{'w....@
+.....w''(w.....
+......www......
+x.............x
+x.............x
+x.............x
+x.............x
+ xxxxxxxxxxxxx 
+ENDMAP
diff --git a/crawl-ref/source/luadgn.cc b/crawl-ref/source/luadgn.cc
index 226138780f..5e7a366039 100644
--- a/crawl-ref/source/luadgn.cc
+++ b/crawl-ref/source/luadgn.cc
@@ -832,46 +832,20 @@ static int dgn_orient(lua_State *ls)
     PLUARET(string, map_section_name(map->orient));
 }
 
-static int dgn_shuffle(lua_State *ls)
+static int dgn_map_add_transform(
+    lua_State *ls,
+    std::string (map_lines::*add)(const std::string &s))
 {
     MAP(ls, 1, map);
     if (lua_gettop(ls) == 1)
-        return dlua_stringtable(ls, map->get_shuffle_strings());
+        luaL_error(ls, "Expected args, got none.");
 
     for (int i = 2, size = lua_gettop(ls); i <= size; ++i)
     {
         if (lua_isnil(ls, i))
-            map->map.clear_shuffles();
-        else
         {
-            std::string err = map->map.add_shuffle(luaL_checkstring(ls, i));
-            if (!err.empty())
-                luaL_error(ls, err.c_str());
+            luaL_error(ls, "Unexpected nil.");
         }
-    }
-
-    return (0);
-}
-
-static int dgn_shuffle_remove(lua_State *ls)
-{
-    MAP(ls, 1, map);
-    for (int i = 2, size = lua_gettop(ls); i <= size; ++i)
-        map->map.remove_shuffle(luaL_checkstring(ls, i));
-    return (0);
-}
-
-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);
-
-    for (int i = 2, size = lua_gettop(ls); i <= size; ++i)
-    {
-        if (lua_isnil(ls, i))
-            (map->map.*erase)();
         else
         {
             std::string err = (map->map.*add)(luaL_checkstring(ls, i));
@@ -883,30 +857,30 @@ static int dgn_map_add_transform(
     return (0);
 }
 
+static int dgn_shuffle(lua_State *ls)
+{
+    return dgn_map_add_transform(ls, &map_lines::add_shuffle);
+}
+
 static int dgn_subst(lua_State *ls)
 {
-    return dgn_map_add_transform(ls, &map_lines::add_subst,
-                                 &map_lines::clear_substs);
+    return dgn_map_add_transform(ls, &map_lines::add_subst);
 }
 
 static int dgn_nsubst(lua_State *ls)
 {
-    return dgn_map_add_transform(ls, &map_lines::add_nsubst,
-                                 &map_lines::clear_nsubsts);
+    return dgn_map_add_transform(ls, &map_lines::add_nsubst);
 }
 
 static int dgn_colour(lua_State *ls)
 {
-    return dgn_map_add_transform(ls,
-                                 &map_lines::add_colour,
-                                 &map_lines::clear_colours);
+    return dgn_map_add_transform(ls, &map_lines::add_colour);
 }
 
-static int dgn_subst_remove(lua_State *ls)
+static int dgn_normalise(lua_State *ls)
 {
     MAP(ls, 1, map);
-    for (int i = 2, size = lua_gettop(ls); i <= size; ++i)
-        map->map.remove_subst(luaL_checkstring(ls, i));
+    map->map.normalise();
     return (0);
 }
 
@@ -2082,6 +2056,33 @@ static void _clamp_to_bounds(int &x, int &y, bool edge_ok = false)
     y = std::min(std::max(y, Y_BOUND_1 + edge_offset), Y_BOUND_2 - edge_offset);
 }
 
+// Return a metatable for a point on the map_lines grid.
+static int dgn_grd_table(lua_State *ls)
+{
+    MAP(ls, 1, map);
+
+    map_def **mapref = clua_new_userdata<map_def *>(ls, GRD_METATABLE);
+    *mapref = map;
+
+    return (1);
+}
+
+static int dgn_width(lua_State *ls)
+{
+    MAP(ls, 1, map);
+    
+    lua_pushnumber(ls, map->map.width());
+    return (1);
+}
+
+static int dgn_height(lua_State *ls)
+{
+    MAP(ls, 1, map);
+    
+    lua_pushnumber(ls, map->map.height());
+    return (1);
+}
+
 static int dgn_fill_area(lua_State *ls)
 {
     int x1 = luaL_checkint(ls, 1);
@@ -2950,9 +2951,7 @@ LUAFN(dgn_change_floor_tile)
 LUAFN(dgn_ftile)
 {
 #ifdef USE_TILE
-    return dgn_map_add_transform(ls,
-                                 &map_lines::add_floortile,
-                                 &map_lines::clear_floortiles);
+    return dgn_map_add_transform(ls, &map_lines::add_floortile);
 #else
     return 0;
 #endif
@@ -2961,9 +2960,7 @@ LUAFN(dgn_ftile)
 LUAFN(dgn_rtile)
 {
 #ifdef USE_TILE
-    return dgn_map_add_transform(ls,
-                                 &map_lines::add_rocktile,
-                                 &map_lines::clear_rocktiles);
+    return dgn_map_add_transform(ls, &map_lines::add_rocktile);
 #else
     return 0;
 #endif
@@ -3025,13 +3022,12 @@ static const struct luaL_reg dgn_lib[] =
     { "welcome", dgn_welcome },
     { "orient", dgn_orient },
     { "shuffle", dgn_shuffle },
-    { "shuffle_remove", dgn_shuffle_remove },
     { "subst", dgn_subst },
     { "nsubst", dgn_nsubst },
     { "colour", dgn_colour },
     { "lfloorcol", dgn_lfloorcol},
     { "lrockcol", dgn_lrockcol},
-    { "subst_remove", dgn_subst_remove },
+    { "normalise", dgn_normalise },
     { "map", dgn_map },
     { "mons", dgn_mons },
     { "item", dgn_item },
@@ -3085,6 +3081,9 @@ static const struct luaL_reg dgn_lib[] =
     { "apply_area_cloud", dgn_apply_area_cloud },
 
     // building routines
+    { "grd_table", dgn_grd_table },
+    { "width", dgn_width },
+    { "height", dgn_height },
     { "fill_area", dgn_fill_area },
     { "replace_area", dgn_replace_area },
     { "octa_room", dgn_octa_room },
@@ -3540,6 +3539,221 @@ static void luaopen_mapmarker(lua_State *ls)
     luaopen_setmeta(ls, "mapmarker", mapmarker_lib, MAPMARK_METATABLE);
 }
 
+
+// Return the integer stored in the table (on the stack) with the key name.
+// If the key doesn't exist or the value is the wrong type, return defval.
+static int _table_int(lua_State *ls, int idx, const char *name, int defval)
+{
+    lua_pushstring(ls, name);
+    lua_gettable(ls, idx < 0 ? idx - 1 : idx);
+    bool nil = lua_isnil(ls, idx);
+    bool valid = lua_isnumber(ls, idx);
+    if (!nil && !valid)
+        luaL_error(ls, "'%s' in table, but not an int.", name);
+    int ret = (!nil && valid ? lua_tonumber(ls, idx) : defval);
+    lua_pop(ls, 1);
+    return (ret);
+}
+
+// Return the character stored in the table (on the stack) with the key name.
+// If the key doesn't exist or the value is the wrong type, return defval.
+static char _table_char(lua_State *ls, int idx, const char *name, char defval)
+{
+    lua_pushstring(ls, name);
+    lua_gettable(ls, idx < 0 ? idx - 1 : idx);
+    bool nil = lua_isnil(ls, idx);
+    bool valid = lua_isstring(ls, idx);
+    if (!nil && !valid)
+        luaL_error(ls, "'%s' in table, but not a string.", name);
+
+    char ret = defval;
+    if (!nil && valid)
+    {
+        const char *str = lua_tostring(ls, idx);
+        if (str[0] && !str[1])
+            ret = str[0];
+        else
+            luaL_error(ls, "'%s' has more than one character.", name);
+    }
+    lua_pop(ls, 1);
+    return (ret);
+}
+
+// Return the string stored in the table (on the stack) with the key name.
+// If the key doesn't exist or the value is the wrong type, return defval.
+static const char* _table_str(lua_State *ls, int idx, const char *name, const char *defval)
+{
+    lua_pushstring(ls, name);
+    lua_gettable(ls, idx < 0 ? idx - 1 : idx);
+    bool nil = lua_isnil(ls, idx);
+    bool valid = lua_isstring(ls, idx);
+    if (!nil && !valid)
+        luaL_error(ls, "'%s' in table, but not a string.", name);
+    const char *ret = (!nil && valid ? lua_tostring(ls, idx) : defval);
+    lua_pop(ls, 1);
+    return (ret);
+}
+
+// Return the boolean stored in the table (on the stack) with the key name.
+// If the key doesn't exist or the value is the wrong type, return defval.
+static bool _table_bool(lua_State *ls, int idx, const char *name, bool defval)
+{
+    lua_pushstring(ls, name);
+    lua_gettable(ls, idx < 0 ? idx - 1 : idx);
+    bool nil = lua_isnil(ls, idx);
+    bool valid = lua_isboolean(ls, idx);
+    if (!nil && !valid)
+        luaL_error(ls, "'%s' in table, but not a bool.", name);
+    bool ret = (!nil && valid ? lua_toboolean(ls, idx) : defval);
+    lua_pop(ls, 1);
+    return (ret);
+}
+
+#define BF_INT(ls, val, def) int val = _table_int(ls, -1, #val, def);
+#define BF_CHAR(ls, val, def) char val = _table_char(ls, -1, #val, def);
+#define BF_STR(ls, val, def) const char *val = _table_str(ls, -1, #val, def);
+#define BF_BOOL(ls, val, def) bool val = _table_bool(ls, -1, #val, def);
+
+static void bf_octa_room(lua_State *ls, map_lines &lines)
+{
+    int default_oblique = std::min(lines.width(), lines.height()) / 2 - 1;
+    BF_INT(ls, oblique, default_oblique);
+    BF_CHAR(ls, outside, 'x');
+    BF_CHAR(ls, inside, '.');
+    BF_STR(ls, replace, ".");
+
+    coord_def tl, br;
+    if (!lines.find_bounds(replace, tl, br))
+        return;
+
+    for (rectangle_iterator ri(tl, br); ri; ++ri)
+    {
+        const coord_def mc = *ri;
+        char glyph = lines(mc);
+        if (replace[0] && !strchr(replace, glyph))
+            continue;
+
+        int ob = 0;
+        ob += std::max(oblique + tl.x - mc.x, 0);
+        ob += std::max(oblique + mc.x - br.x, 0);
+
+        bool is_inside = (mc.y >= tl.y + ob && mc.y <= br.y - ob);
+        lines(mc) = is_inside ? inside : outside;
+    }
+}
+
+static void bf_smear(lua_State *ls, map_lines &lines)
+{
+    BF_INT(ls, iterations, 1);
+    BF_CHAR(ls, smear, 'x');
+    BF_STR(ls, onto, ".");
+    BF_BOOL(ls, boxy, false);
+
+    const int max_test_per_iteration = 10;
+    int sanity = 0;
+    int max_sanity = iterations * max_test_per_iteration;
+
+    for (int i = 0; i < iterations; i++)
+    {
+        bool diagonals, straights;
+        coord_def mc;
+
+        do
+        {
+            do
+            {
+                sanity++;
+                mc.x = random_range(1, lines.width() - 2);
+                mc.y = random_range(1, lines.height() - 2);
+            }
+            while (onto[0] && !strchr(onto, lines(mc)));
+  
+            // Prevent too many iterations. 
+            if (sanity > max_sanity)
+                return;
+        
+            // Is there a "smear" feature along the diagonal from mc?    
+            diagonals = lines(coord_def(mc.x+1, mc.y+1)) == smear ||
+                        lines(coord_def(mc.x-1, mc.y+1)) == smear ||
+                        lines(coord_def(mc.x-1, mc.y-1)) == smear ||
+                        lines(coord_def(mc.x+1, mc.y-1)) == smear;
+
+            // Is there a "smear" feature up, down, left, or right from mc?
+            straights = lines(coord_def(mc.x+1, mc.y)) == smear ||
+                        lines(coord_def(mc.x-1, mc.y)) == smear ||
+                        lines(coord_def(mc.x, mc.y+1)) == smear ||
+                        lines(coord_def(mc.x, mc.y-1)) == smear;
+        }
+        while (!straights && (boxy || !diagonals));
+     
+        lines(mc) = smear; 
+    }
+}
+
+static void bf_extend(lua_State *ls, map_lines &lines)
+{
+    BF_INT(ls, height, 1);
+    BF_INT(ls, width, 1);
+    BF_CHAR(ls, fill, 'x');
+
+    lines.extend(width, height, fill);
+}
+
+typedef void (*bf_func)(lua_State *ls, map_lines &lines);
+struct bf_entry
+{
+    const char* name;
+    bf_func func;
+};
+
+// Create a separate list of builder funcs so that we can automatically
+// generate a list of closures for them, rather than individually
+// and explicitly exposing them to the dgn namespace.
+static struct bf_entry bf_map[] =
+{
+    { "map_octa_room", &bf_octa_room },
+    { "map_smear", &bf_smear },
+    { "map_extend", &bf_extend }
+};
+
+static int dgn_call_builder_func(lua_State *ls)
+{
+    // This function gets called for all the builder functions that
+    // operate on map_lines.
+
+    MAP(ls, 1, map);
+    if (!lua_istable(ls, 2) && !lua_isfunction(ls, 2))
+        return luaL_argerror(ls, 2, "Expected table");
+
+    bf_func *func = (bf_func *)lua_topointer(ls, lua_upvalueindex(1));
+    if (!func)
+        return luaL_error(ls, "Expected C function in closure upval");
+ 
+    // Put the table on top.
+    lua_settop(ls, 2);
+
+    // Call the builder func itself.
+    (*func)(ls, map->map);
+
+    return (0);
+}
+
+static void _register_builder_funcs(lua_State *ls)
+{
+    lua_getglobal(ls, "dgn");
+   
+    const size_t num_entries = sizeof(bf_map) / sizeof(bf_entry); 
+    for (size_t i = 0; i < num_entries; i++)
+    {
+        // Push a closure with the C function into the dgn table.
+        lua_pushlightuserdata(ls, &bf_map[i].func);
+        lua_pushcclosure(ls, &dgn_call_builder_func, 1);
+        lua_setfield(ls, -2, bf_map[i].name);
+    }
+
+    lua_pop(ls, 1);
+}
+
 void init_dungeon_lua()
 {
     lua_stack_cleaner clean(dlua);
@@ -3562,6 +3776,8 @@ void init_dungeon_lua()
     luaopen_mapmarker(dlua);
     luaopen_ray(dlua);
 
+    _register_builder_funcs(dlua);
+
     _register_mapdef_tables(dlua);
 }
 
diff --git a/crawl-ref/source/mapdef.cc b/crawl-ref/source/mapdef.cc
index 20c5ceaf3e..0d2b5f6864 100644
--- a/crawl-ref/source/mapdef.cc
+++ b/crawl-ref/source/mapdef.cc
@@ -335,17 +335,10 @@ int level_range::span() const
 }
 
 ////////////////////////////////////////////////////////////////////////
-// map_transformer
-
-map_transformer::~map_transformer()
-{
-}
-
-////////////////////////////////////////////////////////////////////////
 // map_lines
 
 map_lines::map_lines()
-    : transforms(), markers(), lines(), overlay(),
+    : markers(), lines(), overlay(),
       map_width(0), solid_north(false), solid_east(false),
       solid_south(false), solid_west(false), solid_checked(false)
 {
@@ -356,7 +349,22 @@ map_lines::map_lines(const map_lines &map)
     init_from(map);
 }
 
-int map_lines::operator () (const coord_def &c) const
+rectangle_iterator map_lines::get_iter() const
+{
+    ASSERT(width() > 0);
+    ASSERT(height() > 0);
+
+    coord_def tl(0, 0);
+    coord_def br(width() - 1, height() - 1);
+    return rectangle_iterator(tl, br);
+}
+
+char map_lines::operator () (const coord_def &c) const
+{
+    return lines[c.y][c.x];
+}
+
+char& map_lines::operator () (const coord_def &c)
 {
     return lines[c.y][c.x];
 }
@@ -375,14 +383,12 @@ map_lines &map_lines::operator = (const map_lines &map)
 
 map_lines::~map_lines()
 {
-    clear_transforms();
     clear_markers();
 }
 
 void map_lines::init_from(const map_lines &map)
 {
-    // Transforms and markers have to be regenerated, they will not be copied.
-    clear_transforms();
+    // Markers have to be regenerated, they will not be copied.
     clear_markers();
     overlay.reset(NULL);
     lines         = map.lines;
@@ -402,11 +408,6 @@ void map_lines::clear_vector(V &vect)
     vect.clear();
 }
 
-void map_lines::clear_transforms()
-{
-    clear_vector(transforms);
-}
-
 void map_lines::clear_markers()
 {
     clear_vector(markers);
@@ -425,14 +426,17 @@ std::string map_lines::add_feature_marker(const std::string &s)
     if (!err.empty())
         return (err);
 
-    transforms.push_back(new map_marker_spec(key[0], arg));
+    map_marker_spec spec(key[0], arg);
+    spec.apply_transform(*this);
+
     return ("");
 }
 
 std::string map_lines::add_lua_marker(const std::string &key,
                                       const lua_datum &function)
 {
-    transforms.push_back(new map_marker_spec(key[0], function));
+    map_marker_spec spec(key[0], function);
+    spec.apply_transform(*this);
     return ("");
 }
 
@@ -452,6 +456,7 @@ void map_lines::apply_grid_overlay(const coord_def &c)
 {
     if (!overlay.get())
         return;
+
     for (int y = height() - 1; y >= 0; --y)
         for (int x = width() - 1; x >= 0; --x)
         {
@@ -624,7 +629,9 @@ std::string map_lines::add_colour(const std::string &sub)
     if (!err.empty())
         return (err);
 
-    transforms.push_back( new colour_spec( key[0], sep == ':', colours ) );
+    colour_spec spec(key[0], sep == ':', colours);
+    overlay_colours(spec);
+
     return ("");
 }
 
@@ -648,7 +655,8 @@ std::string map_lines::add_subst(const std::string &sub)
     if (!err.empty())
         return (err);
 
-    transforms.push_back( new subst_spec( key[0], sep == ':', repl ) );
+    subst_spec spec(key[0], sep == ':', repl); 
+    subst(spec);
 
     return ("");
 }
@@ -705,7 +713,9 @@ std::string map_lines::add_nsubst(const std::string &s)
         substs.push_back(spec);
     }
 
-    transforms.push_back( new nsubst_spec(key[0], substs) );
+    nsubst_spec spec(key[0], substs);
+    nsubst(spec);
+
     return ("");
 }
 
@@ -715,114 +725,61 @@ std::string map_lines::add_shuffle(const std::string &raws)
     const std::string err = check_shuffle(s);
 
     if (err.empty())
-        transforms.push_back( new shuffle_spec(s) );
+        resolve_shuffle(s);
 
     return (err);
 }
 
-void map_lines::remove_shuffle(const std::string &raw)
+int map_lines::width() const
 {
-    std::string s = raw;
-    const std::string err = check_shuffle(s);
-    if (err.empty())
-    {
-        const shuffle_spec ss(s);
-        for (int i = 0, vsize = transforms.size(); i < vsize; ++i)
-        {
-            if (transforms[i]->type() == map_transformer::TT_SHUFFLE)
-            {
-                const shuffle_spec *other =
-                    dynamic_cast<shuffle_spec*>(transforms[i]);
-                if (ss == *other)
-                {
-                    delete transforms[i];
-                    transforms.erase( transforms.begin() + i );
-                    return;
-                }
-            }
-        }
-    }
+    return map_width;
 }
 
-void map_lines::remove_subst(const std::string &raw)
+int map_lines::height() const
 {
-    // Parsing subst specs is a pain, so we just let add_subst do the
-    // work, then pop the subst off the end of the vector.
-    if (add_subst(raw).empty())
-    {
-        map_transformer *sub = *transforms.rbegin();
-        subst_spec spec = *dynamic_cast<subst_spec*>(sub);
-        delete sub;
-        transforms.pop_back();
-
-        for (int i = 0, vsize = transforms.size(); i < vsize; ++i)
-        {
-            if (transforms[i]->type() == map_transformer::TT_SUBST)
-            {
-                subst_spec *cand = dynamic_cast<subst_spec*>(transforms[i]);
-                if (spec == *cand)
-                {
-                    delete cand;
-                    transforms.erase( transforms.begin() + i );
-                    return;
-                }
-            }
-        }
-    }
+    return lines.size();
 }
 
-void map_lines::clear_transforms(map_transformer::transform_type tt)
+void map_lines::extend(int min_width, int min_height, char fill)
 {
-    if (transforms.empty())
-        return;
-    for (int i = transforms.size() - 1; i >= 0; --i)
-        if (transforms[i]->type() == tt)
-        {
-            delete transforms[i];
-            transforms.erase( transforms.begin() + i );
-        }
-}
+    min_width = std::max(1, min_width);
+    min_height = std::max(1, min_height);
 
-void map_lines::clear_colours()
-{
-    clear_transforms(map_transformer::TT_COLOUR);
-}
+    bool dirty = false;
+    int old_width = width();
+    int old_height = height();
 
-#ifdef USE_TILE
-void map_lines::clear_rocktiles()
-{
-    clear_transforms(map_transformer::TT_ROCKTILE);
-}
+    if (static_cast<int>(lines.size()) < min_height)
+    {
+        dirty = true;
+        while (static_cast<int>(lines.size()) < min_height)
+            add_line(std::string(min_width, fill));
+    }
 
-void map_lines::clear_floortiles()
-{
-    clear_transforms(map_transformer::TT_FLOORTILE);
-}
-#endif
+    if (width() < min_width)
+    {
+        dirty = true;
+        lines[0] += std::string(min_width - width(), fill);
+        map_width = std::max(map_width, min_width);
+    }
 
-void map_lines::clear_shuffles()
-{
-    clear_transforms(map_transformer::TT_SHUFFLE);
-}
+    if (!dirty)
+        return;
 
-void map_lines::clear_nsubsts()
-{
-    clear_transforms(map_transformer::TT_NSUBST);
-}
+    normalise(fill);
 
-void map_lines::clear_substs()
-{
-    clear_transforms(map_transformer::TT_SUBST);
-}
+    // Extend overlay matrix as well.
+    if (overlay.get())
+    {
+        std::auto_ptr<overlay_matrix> new_overlay(
+            new overlay_matrix(width(), height()));
 
-int map_lines::width() const
-{
-    return map_width;
-}
+        for (int y = 0; y < old_height; ++y)
+            for (int x = 0; x < old_width; ++x)
+                (*new_overlay)(x, y) = (*overlay)(x, y);
 
-int map_lines::height() const
-{
-    return lines.size();
+        overlay = new_overlay;
+    }
 }
 
 coord_def map_lines::size() const
@@ -892,7 +849,6 @@ bool map_lines::solid_borders(map_section_type border)
 
 void map_lines::clear()
 {
-    clear_transforms();
     clear_markers();
     lines.clear();
     overlay.reset(NULL);
@@ -938,7 +894,7 @@ void map_lines::overlay_tiles(tile_spec &spec)
     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)
+        while ((pos = lines[y].find_first_of(spec.key, pos)) != std::string::npos)
         {
             if (spec.floor)
                 (*overlay)(pos, y).floortile = spec.get_tile();
@@ -1036,21 +992,6 @@ void map_lines::resolve_shuffle(const std::string &shufflage)
     }
 }
 
-std::string map_lines::apply_transforms()
-{
-    std::string error;
-    for (int i = 0, vsize = transforms.size(); i < vsize; ++i)
-    {
-        error = transforms[i]->apply_transform(*this);
-        if (!error.empty())
-            return (error);
-    }
-
-    // Release the transforms so we don't try them again.
-    clear_transforms();
-    return ("");
-}
-
 void map_lines::normalise(char fillch)
 {
     for (int i = 0, vsize = lines.size(); i < vsize; ++i)
@@ -1196,24 +1137,6 @@ void map_lines::hmirror()
     solid_checked = false;
 }
 
-std::vector<std::string> map_lines::get_shuffle_strings() const
-{
-    std::vector<std::string> shuffles;
-    for (int i = 0, vsize = transforms.size(); i < vsize; ++i)
-        if (transforms[i]->type() == map_transformer::TT_SHUFFLE)
-            shuffles.push_back( transforms[i]->describe() );
-    return (shuffles);
-}
-
-std::vector<std::string> map_lines::get_subst_strings() const
-{
-    std::vector<std::string> substs;
-    for (int i = 0, vsize = transforms.size(); i < vsize; ++i)
-        if (transforms[i]->type() == map_transformer::TT_SUBST)
-            substs.push_back( transforms[i]->describe() );
-    return (substs);
-}
-
 std::vector<coord_def> map_lines::find_glyph(int gly) const
 {
     std::vector<coord_def> points;
@@ -1252,6 +1175,58 @@ coord_def map_lines::find_first_glyph(const std::string &glyphs) const
     return coord_def(-1, -1);
 }
 
+bool map_lines::find_bounds(int gly, coord_def &tl, coord_def &br) const
+{
+    tl = coord_def(width(), height());
+    br = coord_def(-1, -1);
+
+    if (width() == 0 || height() == 0)
+        return false;
+
+    for (rectangle_iterator ri(get_iter()); ri; ++ri)
+    {
+        const coord_def mc = *ri;
+        if ((*this)(mc) != gly)
+            continue;
+
+        tl.x = std::min(tl.x, mc.x);
+        tl.y = std::min(tl.y, mc.y);
+        br.x = std::max(br.x, mc.x);
+        br.y = std::max(br.y, mc.y);
+    }
+
+    return (br.x >= 0);
+}
+
+bool map_lines::find_bounds(const char *str, coord_def &tl, coord_def &br) const
+{
+    tl = coord_def(width(), height());
+    br = coord_def(-1, -1);
+
+    if (width() == 0 || height() == 0)
+        return false;
+
+    for (rectangle_iterator ri(get_iter()); ri; ++ri)
+    {
+        ASSERT(ri);
+        const coord_def &mc = *ri;
+        const size_t len = strlen(str);
+        for (size_t i = 0; i < len; ++i)
+        {
+            if ((*this)(mc) == str[i])
+            {
+                tl.x = std::min(tl.x, mc.x);
+                tl.y = std::min(tl.y, mc.y);
+                br.x = std::max(br.x, mc.x);
+                br.y = std::max(br.y, mc.y);
+                break;
+            }
+        }
+    }
+
+    return (br.x >= 0);
+}
+
 #ifdef USE_TILE
 bool map_tile_list::parse(const std::string &s, int weight)
 {
@@ -1274,7 +1249,7 @@ std::string map_lines::add_tile(const std::string &sub, bool is_floor)
     std::string key;
     std::string substitute;
 
-    std::string err = mapdef_split_key_item(sub, &key, &sep, &substitute);
+    std::string err = mapdef_split_key_item(sub, &key, &sep, &substitute, -1);
     if (!err.empty())
         return (err);
 
@@ -1283,7 +1258,9 @@ std::string map_lines::add_tile(const std::string &sub, bool is_floor)
     if (!err.empty())
         return (err);
 
-    transforms.push_back(new tile_spec(key[0], sep == ':', is_floor, list));
+    tile_spec spec(key, sep == ':', is_floor, list);
+    overlay_tiles(spec);
+
     return ("");
 }
 
@@ -1300,17 +1277,6 @@ std::string map_lines::add_floortile(const std::string &sub)
 //////////////////////////////////////////////////////////////////////////
 // tile_spec
 
-std::string tile_spec::apply_transform(map_lines &map)
-{
-    map.overlay_tiles(*this);
-    return ("");
-}
-
-std::string tile_spec::describe() const
-{
-    return ("");
-}
-
 int tile_spec::get_tile()
 {
     if (chose_fixed)
@@ -1353,7 +1319,8 @@ map_def::map_def()
     : name(), tags(), place(), depths(), orient(), chance(), weight(),
       weight_depth_mult(), weight_depth_div(), welcome_messages(), map(),
       mons(), items(), random_mons(), keyspecs(), prelude("dlprelude"),
-      main("dlmain"), validate("dlvalidate"), veto("dlveto"),
+      mapchunk("dlmapchunk"), main("dlmain"),
+      validate("dlvalidate"), veto("dlveto"),
       rock_colour(BLACK), floor_colour(BLACK), rock_tile(0), floor_tile(0),
       index_only(false), cache_offset(0L)
 {
@@ -1368,6 +1335,7 @@ void map_def::init()
     place.clear();
     depths.clear();
     prelude.clear();
+    mapchunk.clear();
     main.clear();
     validate.clear();
     veto.clear();
@@ -1436,6 +1404,7 @@ void map_def::write_full(writer& outf)
     marshallShort(outf, MAP_CACHE_VERSION);   // Level indicator.
     marshallString4(outf, name);
     prelude.write(outf);
+    mapchunk.write(outf);
     main.write(outf);
     validate.write(outf);
     veto.write(outf);
@@ -1463,6 +1432,7 @@ void map_def::read_full(reader& inf)
     }
 
     prelude.read(inf);
+    mapchunk.read(inf);
     main.read(inf);
     validate.read(inf);
     veto.read(inf);
@@ -1558,6 +1528,7 @@ void map_def::read_depth_ranges(reader& inf)
 void map_def::set_file(const std::string &s)
 {
     prelude.set_file(s);
+    mapchunk.set_file(s);
     main.set_file(s);
     validate.set_file(s);
     veto.set_file(s);
@@ -1575,9 +1546,18 @@ std::string map_def::run_lua(bool run_main)
         return (prelude.orig_error());
 
     if (!run_main)
+    {
         lua_pushnil(dlua);
+        lua_pushnil(dlua);
+    }
     else
     {
+        err = mapchunk.load(dlua);
+        if (err == -1000)
+            lua_pushnil(dlua);
+        else if (err)
+            return (mapchunk.orig_error());
+
         err = main.load(dlua);
         if (err == -1000)
             lua_pushnil(dlua);
@@ -1585,7 +1565,7 @@ std::string map_def::run_lua(bool run_main)
             return (main.orig_error());
     }
 
-    if (!dlua.callfn("dgn_run_map", 2, 0))
+    if (!dlua.callfn("dgn_run_map", 3, 0))
         return rewrite_chunk_errors(dlua.error);
 
     return (dlua.error);
@@ -1636,6 +1616,8 @@ std::string map_def::rewrite_chunk_errors(const std::string &s) const
     std::string res = s;
     if (prelude.rewrite_chunk_errors(res))
         return (res);
+    if (mapchunk.rewrite_chunk_errors(res))
+        return (res);
     if (main.rewrite_chunk_errors(res))
         return (res);
     if (validate.rewrite_chunk_errors(res))
@@ -1704,7 +1686,7 @@ std::string map_def::validate_map_def()
     }
 
     dlua_set_map dl(this);
-    return (map.apply_transforms());
+    return ("");
 }
 
 bool map_def::is_usable_in(const level_id &lid) const
@@ -1993,7 +1975,7 @@ void map_def::normalise()
 std::string map_def::resolve()
 {
     dlua_set_map dl(this);
-    return map.apply_transforms();
+    return ("");
 }
 
 void map_def::fixup()
@@ -2079,16 +2061,6 @@ std::string map_def::add_key_mask(const std::string &s)
     return add_key_field(s, &keyed_mapspec::set_mask);
 }
 
-std::vector<std::string> map_def::get_shuffle_strings() const
-{
-    return map.get_shuffle_strings();
-}
-
-std::vector<std::string> map_def::get_subst_strings() const
-{
-    return map.get_subst_strings();
-}
-
 ///////////////////////////////////////////////////////////////////
 // mons_list
 //
@@ -3147,48 +3119,6 @@ int subst_spec::value()
     return (chosen);
 }
 
-std::string subst_spec::apply_transform(map_lines &map)
-{
-    map.subst(*this);
-    return ("");
-}
-
-map_transformer::transform_type subst_spec::type() const
-{
-    return (TT_SUBST);
-}
-
-std::string subst_spec::describe() const
-{
-    std::string subst(1, foo);
-    subst += std::string(" ") + (fix? ':' : '=');
-    for (int i = 0, size = repl.size(); i < size; ++i)
-    {
-        const glyph_weighted_replacement_t &gly = repl[i];
-        subst += " ";
-        subst += static_cast<char>(gly.first);
-        if (gly.second != 10)
-            subst += make_stringf(":%d", gly.second);
-    }
-    return (subst);
-}
-
-bool subst_spec::operator == (const subst_spec &other) const
-{
-    if (foo != other.foo || fix != other.fix)
-        return (false);
-
-    if (repl.size() != other.repl.size())
-        return (false);
-
-    for (int i = 0, size = repl.size(); i < size; ++i)
-    {
-        if (repl[i] != other.repl[i])
-            return (false);
-    }
-    return (true);
-}
-
 //////////////////////////////////////////////////////////////////////////
 // nsubst_spec
 
@@ -3197,31 +3127,9 @@ nsubst_spec::nsubst_spec(int _key, const std::vector<subst_spec> &_specs)
 {
 }
 
-std::string nsubst_spec::apply_transform(map_lines &map)
-{
-    map.nsubst(*this);
-    return ("");
-}
-
-std::string nsubst_spec::describe() const
-{
-    return ("");
-}
-
 //////////////////////////////////////////////////////////////////////////
 // colour_spec
 
-std::string colour_spec::apply_transform(map_lines &map)
-{
-    map.overlay_colours(*this);
-    return ("");
-}
-
-std::string colour_spec::describe() const
-{
-    return ("");
-}
-
 int colour_spec::get_colour()
 {
     if (fixed_colour != BLACK)
@@ -3238,25 +3146,6 @@ int colour_spec::get_colour()
 }
 
 //////////////////////////////////////////////////////////////////////////
-// shuffle_spec
-
-std::string shuffle_spec::apply_transform(map_lines &map)
-{
-    map.resolve_shuffle(shuffle);
-    return ("");
-}
-
-map_transformer::transform_type shuffle_spec::type() const
-{
-    return (TT_SHUFFLE);
-}
-
-std::string shuffle_spec::describe() const
-{
-    return (shuffle);
-}
-
-//////////////////////////////////////////////////////////////////////////
 // map_marker_spec
 
 std::string map_marker_spec::apply_transform(map_lines &map)
@@ -3293,16 +3182,6 @@ map_marker *map_marker_spec::create_marker()
         : map_marker::parse_marker(marker);
 }
 
-map_transformer::transform_type map_marker_spec::type() const
-{
-    return (TT_MARKER);
-}
-
-std::string map_marker_spec::describe() const
-{
-    return ("unimplemented");
-}
-
 //////////////////////////////////////////////////////////////////////////
 // map_flags
 map_flags::map_flags()
diff --git a/crawl-ref/source/mapdef.h b/crawl-ref/source/mapdef.h
index 33452a712e..a7b9bc4d9b 100644
--- a/crawl-ref/source/mapdef.h
+++ b/crawl-ref/source/mapdef.h
@@ -15,12 +15,13 @@
 #include <cstdio>
 #include <memory>
 
-#include "luadgn.h"
 #include "enum.h"
 #include "externs.h"
+#include "fixary.h"
+#include "luadgn.h"
 #include "makeitem.h"
+#include "stuff.h"
 #include "travel.h"
-#include "fixary.h"
 
 // [dshaligram] Maps can be mirrored; for every orientation, there must be
 // a suitable mirror.
@@ -100,28 +101,8 @@ typedef std::pair<int,int> glyph_weighted_replacement_t;
 typedef std::vector<glyph_weighted_replacement_t> glyph_replacements_t;
 
 class map_lines;
-class map_transformer
-{
-public:
-    enum transform_type
-    {
-        TT_SHUFFLE,
-        TT_SUBST,
-        TT_NSUBST,
-        TT_MARKER,
-        TT_COLOUR,
-        TT_ROCKTILE,
-        TT_FLOORTILE
-    };
-
-public:
-    virtual ~map_transformer() = 0;
-    virtual std::string apply_transform(map_lines &map) = 0;
-    virtual transform_type type() const = 0;
-    virtual std::string describe() const = 0;
-};
 
-class subst_spec : public map_transformer
+class subst_spec
 {
 public:
     subst_spec(int torepl, bool fix, const glyph_replacements_t &repls);
@@ -134,12 +115,6 @@ public:
 
     int value();
 
-    std::string apply_transform(map_lines &map);
-    transform_type type() const;
-    std::string describe() const;
-
-    bool operator == (const subst_spec &other) const;
-
 private:
     int foo;        // The thing to replace.
     bool fix;       // If true, the first replacement fixes the value.
@@ -148,14 +123,10 @@ private:
     glyph_replacements_t repl;
 };
 
-class nsubst_spec : public map_transformer
+class nsubst_spec
 {
 public:
     nsubst_spec(int key, const std::vector<subst_spec> &specs);
-    std::string apply_transform(map_lines &map);
-    transform_type type() const { return TT_NSUBST; }
-    std::string describe() const;
-
 public:
     int key;
     std::vector<subst_spec> specs;
@@ -167,16 +138,13 @@ class map_colour_list : public std::vector<map_weighted_colour>
 public:
     bool parse(const std::string &s, int weight);
 };
-class colour_spec : public map_transformer
+class colour_spec
 {
 public:
     colour_spec(int _key, bool _fix, const map_colour_list &clist)
         : key(_key), fix(_fix), fixed_colour(BLACK), colours(clist)
     {
     }
-    std::string apply_transform(map_lines &map);
-    transform_type type() const { return TT_COLOUR; }
-    std::string describe() const;
 
     int get_colour();
 
@@ -194,23 +162,20 @@ class map_tile_list : public std::vector<map_weighted_colour>
 public:
     bool parse(const std::string &s, int weight);
 };
-class tile_spec : public map_transformer
+
+class tile_spec
 {
 public:
-    tile_spec(int _key, bool _fix, bool _floor, const map_tile_list &_tiles)
+    tile_spec(const std::string &_key, bool _fix, bool _floor, const map_tile_list &_tiles)
         : key(_key), fix(_fix), chose_fixed(false), floor(_floor),
           fixed_tile(0), tiles(_tiles)
     {
     }
 
-    std::string apply_transform(map_lines &map);
-    transform_type type() const { return (floor ? TT_FLOORTILE : TT_ROCKTILE); }
-    std::string describe() const;
-
     int get_tile();
 
 public:
-    int key;
+    std::string key;
     bool fix;
     bool chose_fixed;
     bool floor;
@@ -219,26 +184,7 @@ public:
 };
 #endif
 
-class shuffle_spec : public map_transformer
-{
- public:
-    std::string shuffle;
-
-    shuffle_spec(const std::string &spec)
-        : shuffle(spec)
-    {
-    }
-
-    std::string apply_transform(map_lines &map);
-    transform_type type() const;
-    std::string describe() const;
-    bool operator == (const shuffle_spec &other) const
-    {
-        return (shuffle == other.shuffle);
-    }
-};
-
-class map_marker_spec : public map_transformer
+class map_marker_spec
 {
 public:
     int key;
@@ -254,8 +200,6 @@ public:
         : key(_key), marker(), lua_fn(new lua_datum(fn)) { }
 
     std::string apply_transform(map_lines &map);
-    transform_type type() const;
-    std::string describe() const;
 
 private:
     map_marker *create_marker();
@@ -278,25 +222,23 @@ public:
     std::string add_subst(const std::string &st);
     std::string add_shuffle(const std::string &s);
     std::string add_colour(const std::string &col);
-    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();
-    void clear_colours();
 
 #ifdef USE_TILE
     std::string add_floortile(const std::string &s);
     std::string add_rocktile(const std::string &s);
-    void clear_rocktiles();
-    void clear_floortiles();
 #endif
 
     std::vector<coord_def> find_glyph(int glyph) const;
     coord_def find_first_glyph(int glyph) const;
     coord_def find_first_glyph(const std::string &glyphs) const;
 
+    // Find rectangular bounds (inclusive) for uses of the glyph in the map.
+    // Returns false if glyph could not be found.
+    bool find_bounds(int glyph, coord_def &tl, coord_def &br) const;
+    // Same as above, but for any of the glyphs in glyph_str.
+    bool find_bounds(const char *glyph_str, coord_def &tl, coord_def &br) const;
+
     void set_orientation(const std::string &s);
 
     int width() const;
@@ -309,8 +251,6 @@ public:
 
     bool solid_borders(map_section_type border);
 
-    std::string apply_transforms();
-
     // Make all lines the same length.
     void normalise(char fillc = ' ');
 
@@ -332,14 +272,16 @@ public:
 
     const std::vector<std::string> &get_lines() const;
     std::vector<std::string> &get_lines();
-    std::vector<std::string> get_shuffle_strings() const;
-    std::vector<std::string> get_subst_strings() const;
 
-    int operator () (const coord_def &c) const;
+    rectangle_iterator get_iter() const;
+    char operator () (const coord_def &c) const;
+    char& operator () (const coord_def &c);
+
+    // Extend map dimensions with glyph 'fill' to minimum width and height.
+    void extend(int min_width, int min_height, char fill);
 
 private:
     void init_from(const map_lines &map);
-    void clear_transforms();
     template <typename V> void clear_vector(V &vect);
     void vmirror_markers();
     void hmirror_markers();
@@ -359,7 +301,6 @@ private:
     void overlay_tiles(tile_spec &);
 #endif
     void check_borders();
-    void clear_transforms(map_transformer::transform_type);
     std::string shuffle(std::string s);
     std::string block_shuffle(const std::string &s);
     std::string check_shuffle(std::string &s);
@@ -386,7 +327,6 @@ private:
     friend class tile_spec;
 
 private:
-    std::vector<map_transformer *> transforms;
     std::vector<map_marker *> markers;
     std::vector<std::string> lines;
     struct overlay_def
@@ -713,7 +653,7 @@ public:
 
     keyed_specs     keyspecs;
 
-    dlua_chunk      prelude, main, validate, veto;
+    dlua_chunk      prelude, mapchunk, main, validate, veto;
 
     map_file_place  place_loaded_from;
 
diff --git a/crawl-ref/source/maps.h b/crawl-ref/source/maps.h
index 3d0994dd02..484e3a0f01 100644
--- a/crawl-ref/source/maps.h
+++ b/crawl-ref/source/maps.h
@@ -62,7 +62,7 @@ typedef std::vector<coord_def> point_vector;
 extern map_place_check_t map_place_valid;
 extern point_vector      map_anchor_points;
 
-const int              MAP_CACHE_VERSION = 1010;
+const int              MAP_CACHE_VERSION = 1011;
 
 
 #ifdef DEBUG_DIAGNOSTICS
diff --git a/crawl-ref/source/util/levcomp.ypp b/crawl-ref/source/util/levcomp.ypp
index 3567083a4a..1aa82e25b1 100644
--- a/crawl-ref/source/util/levcomp.ypp
+++ b/crawl-ref/source/util/levcomp.ypp
@@ -589,7 +589,7 @@ map_lines       : map_lines map_line
 
 map_line        : MAP_LINE
                 {
-                    lc_map.main.add(
+                    lc_map.mapchunk.add(
                         yylineno,
                         make_stringf("map(\"%s\")",
                                      quote_lua_string($1).c_str()));