###############################################################################
# layout.des: Most large layout vaults go here. These are defined by having
#             both ORIENT: encompass and TAGS: layout. These are not true
#             vaults, in that the dungeon builder can add other vaults on
#             top of them. For the "loops" level layouts, see layout_loops.des.
#
###############################################################################

: crawl_require("dlua/vault.lua")
: crawl_require("dlua/layout/zonify.lua")
: crawl_require("dlua/layout/theme.lua")
: crawl_require("dlua/layout/minimum_map_area.lua")

{{
    -- Call func num times around a circle of radius centered at (x, y)
    function apply_circle(x, y, num, radius, scale_x, scale_y, func)
        radius = math.floor(radius)
        for n = 1, num do
            local rad = n * 2 * math.pi / num

            local rx = math.floor(math.cos(rad) * radius * scale_x + 0.5)
            local ry = math.floor(math.sin(rad) * radius * scale_y + 0.5)

            func(x + rx, y + ry)
        end
    end

    function spotty_stairs(mapgrd)
        local gxm, gym = dgn.max_bounds()

        local in_slime = you.in_branch("slime")
        local elevator = not in_slime

        -- We now only generate the three downstairs and build spotty
        -- caves around them (only three bubbles). This means connectivity
        -- is always guaranteed downstream to the branch end, which is always
        -- connected, so all bubbles can be traversed.
        local stairs = { '}', ')', ']' }

        local make_floor = function (x, y)
            mapgrd[x][y] = '.'
        end

        for i, glyph in ipairs(stairs) do
            local x, y
            repeat
                x = crawl.random_range(5, gxm - 5)
                y = crawl.random_range(5, gym - 5)
            until mapgrd[x][y] == 'x' and mapgrd[x + 1][y] == 'x'

            mapgrd[x][y] = glyph

            apply_circle(x, y, 4, 1, 1, 1, make_floor)

            if elevator and glyph == '}' then
                mapgrd[x + 1][y] = '{'
            end
        end
    end

}}

##############################################################
# layout_forbidden_doughnut
#
# This replaces dungeon.cc:_plan_1(). It usually creates a
# room with a large hole in the middle.
#
# This layout should only appear once, and thus does not have the
# "allow_dup" tag.
#
# TODO: Use "layout_type_open_caves" tag for cave version and
#       "layout_type_open" tag for non-cave version.
#
NAME:   layout_forbidden_donut
DEPTH:  Depths
WEIGHT: 5
ORIENT: encompass
TAGS:   overwritable layout no_primary_vault unrand layout_type_open
{{
    local gxm, gym = dgn.max_bounds()
    extend_map{width=gxm, height=gym, fill='x'}

    local width = (10 - crawl.random2(7))

    local floor = '.'
    local wall = 'x'

    -- construct donut
    fill_area{x1=10, y1=10, x2=gxm-10, y2=10+width, fill=floor}
    fill_area{x1=10, y1=60-width, x2=gxm-10, y2=gym-10, fill=floor}
    fill_area{x1=10, y1=10, x2=10+width, y2=gym-10, fill=floor}
    fill_area{x1=60-width, y1=10, x2=gxm-10, y2=gym-10, fill=floor}

    local spotty = crawl.coinflip()
    local smears = crawl.random2(300)

    -- sometimes add a hallway cross through center
    if crawl.coinflip() then
        local width2 = 1 + crawl.random2(5)

        fill_area{x1=10,           y1=gym/2-width2,
                  x2=gxm-10,       y2=gym/2+width2, fill=floor}
        fill_area{x1=gxm/2-width2, y1=10,
                  x2=gxm/2+width2, y2=gym-10,       fill=floor}

        -- sometimes add a small octagon room
        if crawl.coinflip() then
            local obl = 0
            if crawl.coinflip() then
                obl = 5 + crawl.random2(20)
            end

            local fill = util.random_choose_weighted({
                {'.', 10},
                {'w', 5},
                {'l', 1},
            })
            octa_room{x1=25, y1=25, x2=gxm-25, y2=gym-25,
                      oblique=obl, replace='x', inside=fill}

            -- decrease spotty chance
            spotty = crawl.one_chance_in(5)
        end
    end

    local spotty_boxy = crawl.coinflip()
    local smear_boxy = crawl.coinflip()

    if spotty then
        spotty_map{boxy=spotty_boxy}
    end
    if not spotty and crawl.one_chance_in(4) or spotty then
        smear_map{iterations=smears, smear='x', onto='.', boxy=smear_boxy}
    end

    if spotty then
      theme.D.caves(_G)
    else
      theme.level_material(_G)
    end
}}
MAP
ENDMAP

##############################################################
# layout_cross
#
# This replaces dungeon.cc:_plan_2(). It creates a large cross
# of varying width.
#
# Only one of this layout and layout_big_octagon should appear.
# Therefore both of these layouts have a "uniq_open_layout" tag.
#
# TODO: Use "layout_type_open_caves" tag for cave version and
#       "layout_type_open" tag for non-cave version.
#
NAME:   layout_cross
DEPTH:  D:9-, Depths, Pan
WEIGHT: 2
ORIENT: encompass
TAGS:   overwritable layout unrand uniq_open_layout layout_type_open
{{
    local gxm, gym = dgn.max_bounds()
    extend_map{width = gxm, height = gym, fill = 'L'}

    local floor = '.'
    local wall = 'x'
    local border = 'x'

    local width = 5 - crawl.random2(5)
    local height = 5 - crawl.random2(5)

    -- Include a small possibility of adding windows around the cross.
    -- This layout can get used with spotty_level, so don't make this
    -- chance too large as lava/water prevents that from happening.
    local window = not you.in_branch("Lair") and crawl.one_chance_in(20)

    if window then
        if crawl.coinflip() then
            wall = 'l'
            border = 'L'
            kfeat("L = endless_lava")
        else
            wall = 'w'
            border = 'L'
            kfeat("L = open_sea")
        end
    end

    fill_area{fill = border}
    fill_area{x1=1, y1=1, x2=gxm-2, y2=gym-2, fill = wall}

    -- don't spam water/lava monsters or clouds outside the cross
    kmask("wl = no_monster_gen")
    kprop("l = no_cloud_gen")

    -- create window
    if window then
        local clear = 'm'
        fill_area{x1=10, y1=gym/2-height-1, x2=gxm-10, y2=gym/2-height-1, fill=clear}
        fill_area{x1=10, y1=gym/2+height+1, x2=gxm-10, y2=gym/2+height+1, fill=clear}
        fill_area{x1=gxm/2-width-1, y1=10, x2=gxm/2-width-1, y2=gym-10, fill=clear}
        fill_area{x1=gxm/2+width+1, y1=10, x2=gxm/2+width+1, y2=gym-10, fill=clear}
    end

    -- create a cross
    fill_area{x1=10, y1=gym/2-height, x2=gxm-10, y2=gym/2+height, fill=floor}
    fill_area{x1=gxm/2-width, y1=10, x2=gxm/2+width, y2=gym-10, fill=floor}

    if not crawl.one_chance_in(4) then
        spotty_map{boxy = crawl.coinflip()}
    end

    theme.level_material(_G)
}}
MAP
ENDMAP

#############################################################
# layout_big_octagon
#
# This replaces dungeon.cc:_plan_6(). It has an octagonal
# room with some number of pillars in the middle. The stairs
# are generally all grouped together.
#
# Only one of this layout and layout_cross should appear.
# Therefore both of these layouts have a "uniq_open_layout" tag.
#
# TODO: Use "layout_type_open_caves" tag for cave version and
#       "layout_type_open" tag for non-cave version.
#
# TODO: A better way of preventing small maps
#
NAME:   layout_big_octagon
DEPTH:  D:9-, Depths, Pan
WEIGHT: 3
ORIENT: encompass
TAGS:   overwritable layout unrand no_primary_vault layout_type_open
TAGS:   uniq_open_layout
{{
    function smear()
        local gxm, gym = dgn.max_bounds()
        local iterations = 100 + crawl.random2(800)
        smear_map{iterations = iterations, boxy = false}

        --Fill in disconnected zones now, prior to adding the stairs.
        --Temporarily set a (passable) unique symbol in the middle of the map,
        --to guarantee everything is connected to it after smearing.
        mapgrd[gxm/2][gym/2] = '@'
        fill_disconnected{wanted = '@'}
        mapgrd[gxm/2][gym/2] = '.'
    end
    -- Step 1: Big octagon.

    local gxm, gym = dgn.max_bounds()
    extend_map{width = gxm, height = gym, fill = 'x'}

    local oblique = 10 + crawl.random2(20)
    octa_room{
        x1 = 10,
        y1 = 10,
        x2 = gxm-10,
        y2 = gym-10,
        oblique = oblique,
        replace = 'x',
        inside = '.'}

    -- 50% chance of smearing at all; 50% chance of including pillars in
    -- smearing when smearing.
    local do_smear = crawl.coinflip()
    local smear_before = crawl.coinflip()
    if do_smear and smear_before then
        smear()
    end

    -- Step 2: Add pillars

    -- pillar types and relative weights
    local pillar_fill = {
        {'x', 15},
        {'b', 5},
        {'v', 4},
        {'m', 3},
        {'w', 2},
        {'l', 1}
    }
    if (you.in_branch("lair")) then
        pillar_fill[#pillar_fill + 1] = {'t', 15}
    end

    -- Potential pillar drawing routines
    local pillar_func = {
        make_circle,
        make_diamond,
        make_square,
        make_rounded_square
    }

    -- Sometimes generate more than one pillar ring for variety.
    local ring_count = 1 + crawl.random2(4)
    local circle_radius = 2 + crawl.random2(ring_count == 1 and 6 or 3)

    for i = 1, ring_count do
        -- Pillar size params
        -- NOTE: Be careful about tweaking the ranges here. Pillars that are
        -- too large, close, or large in number can entirely surround the center.
        local pfunc = pillar_func[crawl.random2(#pillar_func) + 1]
        local num = 3 + 2*i crawl.random2(9 - 2*i)
        local pillar_radius =
            1 + crawl.random2((pfunc == make_diamond) and 3 or 2)
        circle_radius = circle_radius + pillar_radius * 2 + num / 2
        if circle_radius >= (gym-oblique)/2 then break end
        local fill = util.random_choose_weighted(pillar_fill)

        -- Finally, make the pillars
        local make_pillar = function(x, y)
            return pfunc({
                x = x,
                y = y,
                radius = pillar_radius,
                fill = fill})
        end
        apply_circle(gxm/2, gym/2, num, circle_radius, 1, 1, make_pillar)
    end

    if do_smear and not smear_before then
        smear()
    end

    -- Step 3: Create stairs

    -- Potential stair locations
    -- 0) random
    -- 1) inside
    -- 2) up
    -- 3) right
    -- 4) down
    -- 5) left

    local full_stair_set = {[0] = {}, [1] = {}, [2] = {},
                            [3] = {}, [4] = {}, [5] = {} }

    if crawl.coinflip() then
        -- Sets of stairs all in the same place, as with the original layout.
        local up_loc = crawl.random2(6)
        local down_loc = crawl.random2(6)
        while up_loc == down_loc do
            down_loc = crawl.random2(6)
        end

        local up_stairs = {"{", "(", "["}
        local down_stairs = {"}", ")", "]"}
        full_stair_set = {[up_loc] = up_stairs, [down_loc] = down_stairs}
    else
        -- Each stair goes to a unique location.
        local stairs = {"{", "}", "(", ")", "[", "]"}
        local locs = {0, 1, 2, 3, 4, 5}
        for i = 1, #stairs do
            local which = crawl.random2(#locs) + 1
            local loc = locs[which]
            table.remove(locs, which)
            full_stair_set[loc] = { stairs[i] }
        end
    end

    for loc, stair_list in pairs (full_stair_set) do
        for i = 1, #stair_list do
            local st = stair_list[i]

            if loc == 0 then
                replace_random({find = ".", replace = st})
            elseif loc == 1 then
                mapgrd[gxm/2 + i - 2][gym/2 + 1 - math.abs(i - 2)] = st
            elseif loc == 2 then
                replace_first({
                    x = gxm/2 + i - 2,
                    y = 0,
                    xdir = 0,
                    ydir = 1,
                    find = ".",
                    replace = st})
            elseif loc == 3 then
                replace_first({
                    x = gxm - 1,
                    y = gym/2 + i - 2,
                    xdir = -1,
                    ydir = 0,
                    find = ".",
                    replace = st})
            elseif loc == 4 then
                replace_first({
                    x = gxm/2 + i - 2,
                    y = gym - 1,
                    xdir = 0,
                    ydir = -1,
                    find = ".",
                    replace = st})
            elseif loc == 5 then
                replace_first({
                    x = 0,
                    y = gym/2 + i - 2,
                    xdir = 1,
                    ydir = 0,
                    find = ".",
                    replace = st})
            end
        end
    end

    -- Do we still want this special case here?
    if you.where() == "Pan" and crawl.coinflip() then
        mapgrd[40][36] = 'O'
        mapgrd[41][36] = 'O'
        nsubst('O = 1:O / *:.')
        kfeat('O = exit_through_abyss')
    end

    theme.level_material(_G)
}}
# Enforce minimum floor size - otherwise we get very tiny floors sometimes
validate {{
    return minimum_map_area.is_map_big_enough(_G, minimum_map_area.OPEN)
}}
MAP
ENDMAP

##############################################################
# layout_rooms
#
# This replaces dungeon.cc:_plan_3().
#
# TODO: Differentiate Elf version more
#       Improve room generation
#       Make random_room_point work correctly for new room types
#
NAME:   layout_rooms
DEPTH:  D, Elf, Snake, Crypt, Pan
WEIGHT: 15 (D), 10 (Elf), 15 (Snake), 10 (Crypt), 10 (Pan)
ORIENT: encompass
TAGS:   overwritable layout allow_dup unrand layout_type_rooms
{{
    local is_elf_branch = you.in_branch("Elf")

    function draw_room(room)
        local room_type = 0
        if is_elf_branch then
           room_type = 1
        else
           if crawl.coinflip() then
             room_type = 0
           else
             room_type = 2
           end
        end
        if room_type == 0 then
            -- rectangular
            replace_area({
                x1 = room.x1,
                y1 = room.y1,
                x2 = room.x2,
                y2 = room.y2,
                find = "x",
                replace = "."})
        elseif room_type == 1 then
            -- octagonal-ish
            local corner_size =
                1 + crawl.random2(math.min(room.x2 - room.x1 - 1,
                                           room.y2 - room.y1 - 1))
            for i = 0, corner_size do
                local j = corner_size - i
                replace_area({
                    x1 = room.x1 + i,
                    y1 = room.y1 + j,
                    x2 = room.x2 - i,
                    y2 = room.y2 - j,
                    find = "x",
                    replace = "."})
            end
        else
            -- circular-ish
            local xdelta = room.x2 - room.x1
            local ydelta = room.y2 - room.y1
            local radius = math.max(xdelta, ydelta) / 2
            local steps = math.abs(ydelta - xdelta) - radius
            if ydelta > xdelta then
                for i = 1, steps do
                    make_circle ({ x = room.x1 + radius,
                                   y = room.y1 + radius + i,
                                   radius = radius, fill = '.'})
                    make_circle ({ x = room.x2 - radius,
                                   y = room.y1 + radius + i,
                                   radius = radius, fill = '.'})
                end
            else
                for i = 1, steps do
                    make_circle ({ x = room.x1 + radius + i,
                                   y = room.y1 + radius,
                                   radius = radius, fill = '.'})
                    make_circle ({ x = room.x1 + radius + i,
                                   y = room.y2 - radius,
                                   radius = radius, fill = '.'})
                end
            end
        end
    end

    function random_room_point(room)
        -- TODO: make this properly random for the new room types
        return dgn.point((room.x1 + room.x2) / 2,
                         (room.y1 + room.y2) / 2)
    end

    function join_the_dots_p(start, finish)
        return join_the_dots({
            x1 = start.x,
            y1 = start.y,
            x2 = finish.x,
            y2 = finish.y,
            force_straight = is_elf_branch,
            allow_diagonals = is_elf_branch})
    end

    local gxm, gym = dgn.max_bounds()
    extend_map{width = gxm, height = gym, fill = 'x'}

    local num_rooms = 30 + crawl.random2(90)
    local exclusive = not crawl.one_chance_in(10)
    local exclusive2 = crawl.coinflip()

    local rooms = {}

    for i = 0, num_rooms do
        local new_room = {
            x1 = 10 + crawl.random2(50),
            y1 = 10 + crawl.random2(40)
        }
        new_room.x2 = new_room.x1 + 2 + crawl.random2(8)
        new_room.y2 = new_room.y1 + 2 + crawl.random2(8)

        local not_walls = count_antifeature_in_box({
            x1 = new_room.x1,
            y1 = new_room.y1,
            x2 = new_room.x2,
            y2 = new_room.y2,
            feat = "x"})

        if (not exclusive or not_walls == 0) then
            draw_room(new_room)

            if #rooms > 0 and not exclusive2 then
                join_the_dots_p(random_room_point(new_room),
                                random_room_point(rooms[#rooms]))
            end

            table.insert(rooms, new_room)
            if #rooms >= 30 then
                break
            end
        end
    end

    if exclusive2 then
        for i = 2, #rooms do
          join_the_dots_p(random_room_point(rooms[i]),
                          random_room_point(rooms[i - 1]))
        end
    end

    theme.level_material(_G)
}}
MAP
ENDMAP

##############################################################
# layout_regular_city
#
# This replaces dungeon.cc:_city_level().
# Previously named "layout_city".
#
NAME:   layout_regular_city
DEPTH:  Lair, Crypt, !Crypt:$, Dis, !Dis:$
WEIGHT: 10, 15 (Lair)
ORIENT: encompass
TAGS:   overwritable layout allow_dup unrand layout_type_city
TAGS:   no_rotate no_vmirror no_hmirror
{{
    local rooms = {}
    local i, j

    local wall_type = util.random_choose_weighted(
        { {'x', 3}, {'c', 3}, {'v', 2} } )
    local percent_thickness_2 =   crawl.random_range(0, 8)
                                * crawl.random_range(0, 8)
    local percent_thickness_3 =   crawl.random_range(0, 7)
                                * crawl.random_range(0, 7)
    local percent_thickness_4 = 0
    local percent_inner_new_wall = crawl.random_range(0, 100)
    local percent_inner_box   = crawl.random_range(0, 25)
    local percent_inner_split = crawl.random_range(0, 25)
    local percent_room_gone = 14 -- was 1/7 chance
    local max_wall_in = 5

    if you.in_branch("Lair") then
        wall_type = 'x'
        percent_thickness_2 = 50 + you.depth_fraction() * 150 -- 100% at Lair:2
        percent_thickness_3 = 20 + you.depth_fraction() * 80  -- 100% at Lair:$
        percent_thickness_4 = 10 + you.depth_fraction() * 40
        percent_inner_new_wall = 0
        percent_inner_box   = 0
        percent_inner_split = 0
        percent_room_gone = 0
        max_wall_in = you.at_branch_bottom() and 3 or 4
    elseif you.in_branch("Dis") then
        wall_type = 'x'
        percent_thickness_2 = 0
        percent_thickness_3 = 0
        percent_inner_new_wall = 0
        percent_inner_box   = percent_inner_box * 1.5
        percent_inner_split = percent_inner_split * 2
    end

    local gxm, gym = dgn.builder_bounds()
    extend_map{width = gxm, height = gym, fill = 'x'} --wall_type}
    fill_area { x1=8, y1=8, x2=gxm-9, y2=gym-9, fill="." }

    for i = 0, 4 do
        for j = 0, 3 do
            local xs = 8 + (i * 13)
            local ys = 8 + (j * 14)
            local a1 = xs +      crawl.random2avg(max_wall_in, 2)
            local a2 = ys +      crawl.random2avg(max_wall_in, 2)
            local b1 = xs + 11 - crawl.random2avg(max_wall_in, 2)
            local b2 = ys + 11 - crawl.random2avg(max_wall_in, 2)

            -- move walls in if they would hit the edge of the open area
            --  -> otherwise edge rooms sometimes don't appear
            a1 = (a1 >= 9)      and a1 or 9
            a2 = (a2 >= 9)      and a2 or 9
            b1 = (b1 <= gxm-10) and b1 or gxm-10
            b2 = (b2 <= gym-10) and b2 or gym-10

            if not crawl.x_chance_in_y(percent_room_gone, 100)
                and is_valid_coord {x=a1, y=a2}
                and is_valid_coord {x=b1, y=b2}
                and not find_in_area {x1 = a1 - 1, y1 = a2 - 1,
                                      x2 = b1 + 1, y2 = b2 + 1,
                                      find = "xcvb+", find_vault = true } then

                local wall_type_room = theme.room_material(wall_type)

                local size_x = b1 - a1
                local size_y = b2 - a2
                local thickness = 1
                if size_x > 8 and size_y > 8
                   and crawl.x_chance_in_y(percent_thickness_4, 100) then
                    thickness = 4
                elseif size_x > 6 and size_y > 6
                       and crawl.x_chance_in_y(percent_thickness_3, 100) then
                    thickness = 3
                elseif size_x > 4 and size_y > 4
                       and crawl.x_chance_in_y(percent_thickness_2, 100) then
                    thickness = 2
                end

                table.insert(rooms, {a1, a2, b1, b2, thickness})
                make_box { x1=a1, y1=a2, x2=b1, y2=b2,
                           wall=wall_type_room, thickness=thickness }

                local size_x_inner = size_x - thickness * 2
                local size_y_inner = size_y - thickness * 2
                if size_x_inner > 3 and size_y_inner > 3 then

                    if crawl.x_chance_in_y(percent_inner_box, 100) then
                        local A1 = a1 + thickness + 1
                        local A2 = a2 + thickness + 1
                        local B1 = b1 - thickness - 1
                        local B2 = b2 - thickness - 1
                        local door_number = 1 +
                                            crawl.random2(2) * crawl.random2(2)

                        local wall_type_inner = wall_type_room
                        if crawl.x_chance_in_y(percent_inner_new_wall, 100) then
                            wall_type_inner = theme.room_material(wall_type)
                        end

                        make_box { x1=A1, y1=A2, x2=B1, y2=B2,
                                   wall=wall_type_inner }
                        make_box_doors { x1=A1, y1=A2, x2=B1, y2=B2,
                                         number=door_number }

                    elseif crawl.x_chance_in_y(percent_inner_split, 100) then
                        local door_x = a1 + thickness + 1
                                       + crawl.random2(size_x_inner - 2)
                        local door_y = a2 + thickness + 1
                                       + crawl.random2(size_y_inner - 2)

                        if crawl.coinflip() then
                            for x = a1 + thickness, b1 - thickness do
                                mapgrd[x][door_y] = wall_type_room
                            end
                        else
                            for y = a2 + thickness, b2 - thickness do
                                mapgrd[door_x][y] = wall_type_room
                            end
                        end
                        mapgrd[door_x][door_y] = '+'
                    end

                end
            end
        end
    end

    for _, room in ipairs(rooms) do
        local doors = 1 + crawl.random2(5) - crawl.random2(3)
        if doors < 1 then
            doors = 1
        end

        if doors > 3 and crawl.one_chance_in(3) then
            doors = 2
        end

        local thickness = room[5]
        local outer_door = '+'
        local inner_door = '+'
        if thickness == 2 then
            outer_door = util.random_choose_weighted { {'+', 1}, {'.', 2} }
            inner_door = util.random_choose_weighted { {'+', 1}, {'.', 3} }
        elseif thickness == 3 then
            outer_door = util.random_choose_weighted { {'+', 2}, {'.', 1} }
            inner_door = util.random_choose_weighted { {'+', 1}, {'.', 2} }
        elseif thickness == 4 then
            outer_door = util.random_choose_weighted { {'+', 4}, {'.', 1} }
            inner_door = util.random_choose_weighted { {'+', 1}, {'.', 1} }
        end

        if outer_door == '.' and crawl.coinflip() then
            doors = doors + 1
        end
        if inner_door == '.' and crawl.coinflip() then
            doors = doors + 1
        end

        make_box_doors {x1=room[1], y1=room[2], x2=room[3], y2=room[4],
                        number=doors, thickness=thickness,
                        door=outer_door, inner_door=inner_door,
                        veto_gates=true }
    end

    -- remove doors in Lair, increasingly with depth
    if you.in_branch("Lair") then
        local keep_weight   = dgn.br_depth(you.branch())
        local remove_weight = you.depth() * 2
        subst("+ = .:" .. remove_weight .. " +:" .. keep_weight)
    end
}}
MAP
ENDMAP

##############################################################
# layout_misc_corridors
#
# This replaces dungeon.cc:_plan_5().
# Previously named "layout_misc".
#
NAME:   layout_misc_corridors
DEPTH:  Lair, Snake, Crypt, Zot
WEIGHT: 20, 5 (Lair)
ORIENT: encompass
TAGS:   overwritable layout allow_dup unrand layout_type_corridors
TAGS:   no_rotate no_vmirror no_hmirror
{{
    function random_coord(max_x, max_y)
        local x = crawl.random2(max_x - 16) + 8
        local y = crawl.random2(max_y - 16) + 8
        local sanity = 0
        while (dgn.in_vault(x, y) and sanity < 10) do
            x = crawl.random2(max_x - 16) + 8
            y = crawl.random2(max_y - 16) + 8
            sanity = sanity + 1
        end
        return x, y
    end

    local gxm, gym = dgn.max_bounds()

    local corridors = crawl.random_range(15, 25)
    local force_straight = false
    local allow_diagonals = false
    local max_thickness = 1
    if you.in_branch("Crypt") then
        force_straight = true
    elseif you.in_branch("Zot") then
        corridors = crawl.random_range(10, 16)
        force_straight = true
        allow_diagonals = crawl.coinflip()
        max_thickness = 3
    end
    if you.at_branch_bottom() then
        corridors = math.floor(corridors * (1.2 + crawl.random_real() * 0.3))
    end

    local area_fraction = 1;
    local x_min, x_max, y_min, y_max = primary_vault_dimensions()
    if x_min ~= nil then
        local vault_area = (x_max - x_min + 1) * (y_max - y_min + 1)
        local total_area = (gxm - 2) * (gym - 2)
        area_fraction = 1 - (vault_area / total_area)
        corridors = math.ceil(corridors * area_fraction)
    end

    extend_map { width = gxm, height = gym, fill = 'x' }

    local x, y = random_coord(gxm, gym)
    local new_x, new_y

    while corridors > 0 do
        new_x, new_y = random_coord(gxm, gym)

        local thickness = crawl.random_range(1, max_thickness)
        join_the_dots { x1 = x, y1 = y, x2 = new_x, y2 = new_y,
                        force_straight = force_straight,
                        allow_diagonals = allow_diagonals,
                        thickness = thickness }

        x, y = new_x, new_y
        corridors = corridors - 1
    end

    local iterations = math.floor(crawl.random_range(75, 125) * area_fraction)
    if you.in_branch("Lair") then
        spotty_map { boxy = crawl.coinflip(), iterations = iterations }
    else
        spotty_map { boxy = true, iterations = iterations }
    end

    theme.level_material(_G)
}}
MAP
ENDMAP

##############################################################
# layout_caves
#
# One (sometimes more) large open caverns with irregular
# walls.
#
# TODO: Take out special case for non-Orc non-Slime.
#
NAME:   layout_caves
DEPTH:  Orc, Slime
WEIGHT: 10
ORIENT: encompass
TAGS:   overwritable layout allow_dup unrand layout_type_open_caves
{{
    local gxm, gym = dgn.max_bounds()

    extend_map { width = gxm, height = gym, fill = 'x' }

    spotty_stairs(mapgrd)

    local iterations
    local boxy = false
    local connected = false
    if dgn.is_descent() then
        connected = true
    end
    if you.in_branch("orc") or you.in_branch("slime") then
        if you.at_branch_bottom() then
            iterations = 600 + crawl.random2(600)
            connected = true
        elseif you.in_branch("slime") then
            iterations = 350 + crawl.random2(250)
            connected = true
        else
            iterations = 100 + crawl.random2(500)
        end
    else
        -- Normal branches
        boxy = crawl.coinflip()
        iterations = 300 + crawl.random2(boxy and 750 or 1500)
    end

    spotty_map { boxy = boxy, iterations = iterations }

    -- For Orc branch end, fill in all but the largest zone
    if connected then
      zonify.map_fill_zones(_G, 1, 'x')
    end

    theme.D.caves(_G)
}}
# Enforce minimum floor size - otherwise we get very tiny floors sometimes
validate {{
    return minimum_map_area.is_map_big_enough(_G, minimum_map_area.OPEN_CAVES)
}}
MAP
ENDMAP

##############################################################
# This replaces dungeon.cc:_roguey_level.
#
NAME:   layout_roguey
DEPTH:  D:9-, Lair, Depths
WEIGHT: 25 (D), 10 (Lair), 10 (Depths)
ORIENT: encompass
TAGS:   overwritable layout no_primary_vault allow_dup unrand layout_type_rooms
{{
    function make_inner_room(room, feat)
        local inner_room = {
            x1 = room.x1 + 1, y1 = room.y1 + 1,
            x2 = room.x2 - 1, y2 = room.y2 - 1,
            wall = feat, number = 1
        }

        make_box(inner_room)
        make_box_doors(inner_room)
    end

    local maze_startx = 0
    local maze_starty = 0
    local maze_endx = 0
    local maze_endy = 0

    function dig_maze(x, y)
        local delta = { {x =  2, y =  0},
                        {x = -2, y =  0},
                        {x =  0, y =  2},
                        {x =  0, y = -2} }
        local count = 0
        local i = 0
        local newx = 0
        local newy = 0
        local nextx = 0
        local nexty = 0
        while true do
            count = 0
            for i = 1, 4 do
                newx = x + delta[i].x
                newy = y + delta[i].y
                if newx >= maze_startx
                    and newx <= maze_endx
                    and newy >= maze_starty
                    and newy <= maze_endy then
                    if mapgrd[newx][newy] ~= '.' then
                       count = count + 1
                       if crawl.random2(count) == 0 then
                           nextx = newx
                           nexty = newy
                       end
                    end
                end
            end
            if count == 0 then
                return
            end
            if nexty == y then
                newy = y
                if nextx - x < 0 then
                    newx = nextx + 1
                else
                    newx = nextx - 1
                end
            else
                newx = x
                if nexty - y < 0 then
                    newy = nexty + 1
                else
                    newy = nexty - 1
                end
            end
            mapgrd[newx][newy] = '.'
            mapgrd[nextx][nexty] = '.'
            dig_maze(nextx, nexty)
        end
    end

    function make_roguey_maze(room)
        maze_startx = room.x1
        maze_starty = room.y1
        maze_endx = room.x2
        maze_endy = room.y2
        local startx = 2*crawl.random2((maze_endx - maze_startx) / 2)
                     + maze_startx
        local starty = 2*crawl.random2((maze_endy - maze_starty) / 2)
                     + maze_starty
        dig_maze(startx, starty)
    end

    function sign(a)
        return a > 0 and 1 or a < 0 and -1 or 0
    end

    function link_rooms(r1, r2, sideways)
        if not r1.present or not r2.present then
            return
        end
        local x1, y1, x2, y2
        local tries = 100
        if sideways then
            x1 = r1.x2 + 1
            y1 = crawl.random_range(r1.y1 + 1, r1.y2 - 1)
            while (r1.maze and mapgrd[r1.x2][y1] ~= '.') do
                y1 = crawl.random_range(r1.y1 + 1, r1.y2 - 1)
            end
            x2 = r2.x1 - 1
            y2 = crawl.random_range(r2.y1 + 1, r2.y2 - 1)
            while (r2.maze and mapgrd[r2.x1][y2] ~= '.') or
                  (y1 == y2 and not crawl.one_chance_in(3)) do
                y2 = crawl.random_range(r2.y1 + 1, r2.y2 - 1)
            end

            if x2 - x1 >= 2 then
                mapgrd[x1][y1] = r1.door
                mapgrd[x2][y2] = r2.door
                x1 = x1 + 1
                x2 = x2 - 1
            end
        else
            x1 = crawl.random_range(r1.x1 + 1, r1.x2 - 1)
            while (r1.maze and mapgrd[x1][r1.y2] ~= '.') do
                x1 = crawl.random_range(r1.x1 + 1, r1.x2 - 1)
            end
            y1 = r1.y2 + 1
            x2 = crawl.random_range(r2.x1 + 1, r2.x2 - 1)
            while (r2.maze and mapgrd[x2][r2.y1] ~= '.')
                  or (x1 == x2 and not crawl.one_chance_in(3)) do
                x2 = crawl.random_range(r2.x1 + 1, r2.x2 - 1)
            end
            y2 = r2.y1 - 1

            if y2 - y1 >= 2 then
                mapgrd[x1][y1] = r1.door
                mapgrd[x2][y2] = r2.door
                y1 = y1 + 1
                y2 = y2 - 1
            end
        end

        mapgrd[x1][y1] = '.'

        while x1 ~= x2 or y1 ~= y2 do
            if x1 ~= x2
               and crawl.x_chance_in_y(math.abs(x2 - x1),
                                       math.abs(x2 - x1) + math.abs(y2 - y1))
               then
                x1 = x1 + sign(x2 - x1)
            else
                y1 = y1 + sign(y2 - y1)
            end

            mapgrd[x1][y1] = '.'
        end
    end

    function room_is_placeable(x1, y1, x2, y2)
        if is_validating() then return true end
        for point in iter.rect_iterator(dgn.point(x1, y1),
                                        dgn.point(x2, y2)) do
            if dgn.in_vault(point.x, point.y) then
                return false
            end
        end
        return true
    end

    local gxm, gym = dgn.max_bounds()

    extend_map { width = gxm, height = gym, fill = 'x' }

    local rows = util.random_choose_weighted({ {5, 10}, {4, 5}, {3, 1} })
    local cols = util.random_choose_weighted({ {5, 10}, {4, 5}, {3, 1} })
    local xspace = 13 + 2*(5-cols)
    local yspace = 11 + 2*(5-rows)
    local xsize  = 6 + 2*(5-cols)
    local ysize  = 6 + 2*(5-rows)
    local special = -1

    if crawl.one_chance_in(10) and dgn.map_by_tag('special_room', true) then
        special = crawl.random_range(1, rows * cols)
    end

    local rooms = {}

    for y = 0, rows - 1 do
        for x = 0, cols - 1 do
            local base_x, base_y = x * xspace + 8, y * yspace + 8
            local x1, x2, y1, y2
            local tries = 50
            local placeable = true
            while tries > 0 do
                x1 = base_x + crawl.random2(4)
                y1 = base_y + crawl.random2(4)
                x2 = base_x + xsize + crawl.random2(5)
                y2 = base_y + ysize + crawl.random2(3)
                if room_is_placeable(x1, y1, x2, y2) then break end
                tries = tries - 1
            end

            if tries == 0 then placeable = false end

            local room = {
                x1 = base_x + crawl.random2(4),
                y1 = base_y + crawl.random2(4),
                x2 = base_x + xsize + crawl.random2(5),
                y2 = base_y + ysize + crawl.random2(3),
                -- Rogue has 0-3 rooms per 3x3 level missing;
                -- this averages to 1.5 in 9, or 1 in 6.
                present = placeable and not crawl.one_chance_in(6),
                maze = (crawl.random2(10) < you.absdepth() - 1 and
                        crawl.one_chance_in(15)),
                fill = '.',
                door = crawl.one_chance_in(3) and '.' or '+',
            }

            if room.maze then
                if ((room.x2 - room.x1) % 2) ~= 0 then
                    room.x2 = room.x2 + 1
                end
                if ((room.y2 - room.y1) % 2) ~= 0 then
                    room.y2 = room.y2 + 1
                end
            end

            table.insert(rooms, room)
        end
    end

    for i, room in ipairs(rooms) do
        if i == special then
            if room.present then
                room.fill = 'O'
                room.door = '+'
            else
                special = -1
            end
        end

        if room.present then
            if room.maze then
                make_roguey_maze(room)
            else
                fill_area(room)
            end

            if not room.maze
               and room.fill == '.'
               and (room.x2 - room.x1 > 5)
               and (room.y2 - room.y1 > 5)
               and (you.in_branch("D") or you.in_branch("Lair"))
               and crawl.x_chance_in_y(you.absdepth() - 9, 450)
            then
                local feat = util.random_choose_weighted({ {'v', 2},
                                                           {'c', 3},
                                                           {'x', 3} })
                make_inner_room(room, feat)
            end
        end
    end

    for i, room in ipairs(rooms) do
        if room.present then
            -- If there is a neighbour on the right, connect to it.
            if i % cols ~= 0 then
                local j = i + 1
                local done = false
                while j % cols ~= 1 and not done do
                    if rooms[j].present then
                        link_rooms(room, rooms[j], true)
                        done = true
                    else
                        j = j + 1
                    end
                end
            end

            -- If there is a neighbour below, connect to it.
            if i + cols <= #rooms then
                local j = i + cols
                local done = false
                while j <= #rooms and not done do
                    if rooms[j].present then
                        link_rooms(room, rooms[j], false)
                        done = true
                    else
                        j = j + cols
                    end
                end
            end
        end
    end

    -- Prevent staircases from being placed in special or inner rooms.
    nsubst('. = { / ( / [ / < / } / ) / ] / > / .')
    -- Prevent treasure rooms being overwritten by vaults
    kmask('* = vault')

    if special ~= -1 then
        subvault('O : special_room')
    end
}}
MAP
ENDMAP

##############################################################
# layout_subdivisions, by rwbarton
#
# Previously named "layout_dis".
#
# TODO: place around primary vault, then allow on Dis:$.
#
NAME:   layout_subdivisions
DEPTH:  Dis:1-6
WEIGHT: 15
ORIENT: encompass
TAGS:   overwritable layout allow_dup unrand layout_type_divisions
TAGS:   no_rotate no_vmirror no_hmirror
{{
    local gxm, gym = dgn.builder_bounds()
    extend_map{width = gxm, height = gym, fill = 'x'}

    local subdivide_threshold = 9 + gym / 35

    -- Create the alternate version?
    local alt = crawl.x_chance_in_y(2,3)

    function room(x1, y1, x2, y2)
        if x1 < x2 and y1 < y2 then
           local floor_type = '.'
           make_box { x1=x1, y1=y1, x2=x2, y2=y2, wall='x', floor=floor_type }

           if x1+2 <= x2-2 and y1+2 <= y2-2 and crawl.one_chance_in(10) then
              -- decorative statues
              local x3 = crawl.random_range(x1+2, x2-2)
              local y3 = crawl.random_range(y1+2, y2-2)
              local x4 = x1+x2-x3
              local y4 = y1+y2-y3

              if math.abs(x3 - x4) ~= 1 and math.abs(y3 - y4) ~= 1 then
                  mapgrd[x3][y3] = 'G'
                  mapgrd[x4][y3] = 'G'
                  mapgrd[x3][y4] = 'G'
                  mapgrd[x4][y4] = 'G'
               end
           end

           if (x1+x2) % 2 == 0 and (y1+y2) % 2 == 0
              and crawl.one_chance_in(10) then
              -- dry fountain
              mapgrd[(x1+x2)/2][(y1+y2)/2] = 'V'
           end
        end
    end

    function fill(x1, y1, x2, y2, orient)
        if orient == 0 then
            if x2 - x1 < subdivide_threshold then
               if y2 - y1 >= subdivide_threshold then
                  fill(x1, y1, x2, y2, 1)
               else
                  room(x1, y1, x2, y2)
               end
            else
               local x3 = x1 + 4 + crawl.random2(x2 - x1 - 7)
               fill(x1, y1, x3, y2, 1)
               fill(x3, y1, x2, y2, 1)
               if not alt then
                   replace_random { x1=x3, y1=y1+1, x2=x3, y2=y2-1,
                                    find='x', replace='+' }
               end
           end
        else
            if y2 - y1 < subdivide_threshold then
               if x2 - x1 >= subdivide_threshold then
                  fill(x1, y1, x2, y2, 0)
               else
                   room(x1, y1, x2, y2)
               end
            else
               local y3 = y1 + 4 + crawl.random2(y2 - y1 - 7)
               fill(x1, y1, x2, y3, 0)
               fill(x1, y3, x2, y2, 0)
               if not alt then
                   replace_random { x1=x1+1, y1=y3, x2=x2-1, y2=y3,
                                    find='x', replace='+' }
               end
            end
        end
    end

    fill_area { fill = 'x' }
    fill_area { x1=8, y1=8, x2=gxm-9, y2=gym-9, fill="." }

    fill(7, 7, gxm-8, gym-8, 0)

    -- Alternate version, connect rooms at the end.
    if alt then
        local thresh = 150 + (50 * gym) / 35
        connect_adjacent_rooms { max = crawl.random_range(2 * thresh, 3 * thresh),
                                 min = thresh, replace = '+' }
        zonify.map_fill_zones(_G, 1, 'x')
    end
}}
# Enforce minimum floor size - this is important with the alt version
validate {{
    return minimum_map_area.is_map_big_enough(_G, minimum_map_area.DIVISIONS)
}}
: vault_metal_statue_setup(_G, "G", "iron statue")
MAP
ENDMAP

##############################################################
# layout_jigsaw
#
# A grid of irregular rooms with walls between them.  The
#  effect of this is that it is not always obvious whether you
#  are inside a room or outside.
#
# This is a Dis-specific variant of layout_honeycomb.
#
NAME:   layout_jigsaw
DEPTH:  Dis:1-6
WEIGHT: 10
ORIENT: encompass
TAGS:   overwritable layout allow_dup unrand layout_type_divisions
TAGS:   no_rotate no_vmirror no_hmirror
{{
    local gxm, gym = dgn.builder_bounds()
    local ROOMS_ACROSS = 2 * (gym / 35)
    local ROOM_SIZE = 1 + 5 * (gym / 35)
    local ROOM_SEPARATION = 2
    local EDGE_IN = 5
    local ROOM_IN = 4

    local ROOM_SPACING = ROOM_SIZE + ROOM_SEPARATION
    local MAP_SIZE = ROOM_SPACING * ROOMS_ACROSS + ROOM_SEPARATION
                     + EDGE_IN * 2
    local FIRST_ROOM = EDGE_IN + ROOM_SEPARATION
    local DOOR_OFFSET_MIN = FIRST_ROOM + ROOM_IN - 1
    local DOOR_OFFSET_MAX = FIRST_ROOM + ROOM_SIZE - ROOM_IN

    extend_map{width = gxm, height = gym, fill = 'x'}

    assert(MAP_SIZE < gxm, "Map size is too large")
    assert(MAP_SIZE < gym, "Map size is too large")
    make_irregular_box { x1    = 0,            y1    = 0,
                         x2    = MAP_SIZE - 1, y2    = MAP_SIZE - 1,
                         div_x = MAP_SIZE / 4, div_y = MAP_SIZE / 4,
                         in_x  = EDGE_IN,      in_y  = EDGE_IN;
                         door_count = 0 }

    -- add rooms in a grid
    for i = 0, ROOMS_ACROSS - 1 do
        for j = 0, ROOMS_ACROSS - 1 do
            local x = FIRST_ROOM + i * ROOM_SPACING
            local y = FIRST_ROOM + j * ROOM_SPACING

            make_irregular_box { x1 = x, x2 = x + ROOM_SIZE - 1,
                                 y1 = y, y2 = y + ROOM_SIZE - 1,
                                 div_x = 3, div_y = 3,
                                 in_x = ROOM_IN, in_y = ROOM_IN,
                                 door_count = crawl.random_range(1, 3) }
        end
    end

    -- add horizontal walls
    for i = 0, ROOMS_ACROSS do
        for j = 0, ROOMS_ACROSS - 1 do
            local x = EDGE_IN + i * ROOM_SPACING
                      + crawl.random_range(0, ROOM_SEPARATION - 1)
            local y = crawl.random_range(DOOR_OFFSET_MIN, DOOR_OFFSET_MAX)
                      + j * ROOM_SPACING

            -- add door
            mapgrd[x][y] = '+'

            -- build wall to left
            local x1 = x
            while x1 > 0 and mapgrd[x1][y + 1] ~= 'x'
                  and mapgrd[x1][y - 1] ~= 'x' and mapgrd[x1 - 1][y] ~= 'x' do
                x1 = x1 - 1
                mapgrd[x1][y] = 'x'
            end

            -- build wall to right
            local x1 = x
            while x1 < MAP_SIZE - 2 and mapgrd[x1][y + 1] ~= 'x'
                  and mapgrd[x1][y - 1] ~= 'x' and mapgrd[x1 + 1][y] ~= 'x' do
                x1 = x1 + 1
                mapgrd[x1][y] = 'x'
            end
        end
    end

    -- add vertical walls
    for i = 0, ROOMS_ACROSS - 1 do
        for j = 0, ROOMS_ACROSS do
            local x = crawl.random_range(DOOR_OFFSET_MIN, DOOR_OFFSET_MAX)
                      + i * ROOM_SPACING
            local y = EDGE_IN + j * ROOM_SPACING
                      + crawl.random_range(0, ROOM_SEPARATION - 1)

            -- add door
            mapgrd[x][y] = '+'

            -- build wall to top
            local y1 = y
            while y1 > 0 and mapgrd[x + 1][y1] ~= 'x'
                  and mapgrd[x - 1][y1] ~= 'x' and mapgrd[x][y1 - 1] ~= 'x' do
                y1 = y1 - 1
                mapgrd[x][y1] = 'x'
            end

            -- build wall to bottom
            local y1 = y
            while y1 < MAP_SIZE - 2 and mapgrd[x + 1][y1] ~= 'x'
                  and mapgrd[x - 1][y1] ~= 'x' and mapgrd[x][y1 + 1] ~= 'x' do
                y1 = y1 + 1
                mapgrd[x][y1] = 'x'
            end
        end
    end

    --
    -- We do need this: the walls we add can seal off areas
    --
    -- e.g.
    -- ..xxxxx..
    -- .xx...x..    x is existing room
    -- .x..xxx..
    -- xx..x*vvv    v is new wall (really made of 'x's)
    -- x...xxx..
    -- xxx...x..    * is isolated location
    -- ..xxxxx..
    --
    -- Also, we might block all the doors to a room
    --

    zonify.map_fill_zones(_G, 1, 'x')
}}
MAP
ENDMAP

##############################################################
# layout_diamond_mine
#
# A cave-like mine based off diamond shapes.
#
# Places around primary vaults.
#
# There is a grid of potential rooms across the map.  We
#  repeatedly select one at random (weighted towards the center)
#  and add it.  This gives much better control over map size
#  than just giving each room a chance of appearing.
#
NAME:   layout_diamond_mine
DEPTH:  Orc
WEIGHT: 5
ORIENT: encompass
TAGS:   overwritable layout allow_dup unrand layout_type_narrow_caves
TAGS:   no_rotate no_hmirror no_vmirror
{{
  -- information for rooms of different sizes

  local GLYPH_BY_RADIUS =
    { [4] = { [0] = "c", "-", ".", ".", ":" },
      [5] = { [0] = "c", "-", ".", ".", ":", ":" },
      [6] = { [0] = "c", "c", "-", ".", ".", ":", ":" },
      [7] = { [0] = "c", "c", "-", "-", ".", ".", ":", ":" },
      [8] = { [0] = "c", "c", "-", "-", ".", ".", ":", ":", ":" },
      [9] = { [0] = "c", "c", "-", "-", ".", ".", ".", ":", ":", ":" },
     [10] = { [0] = "c", "c", "-", "-", "-", ".", ".", ".", ":", ":", ":" },
     [11] = { [0] = "c", "c", "-", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":" },
     [12] = { [0] = "c", "c", "c", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":", ":" },
     [13] = { [0] = "c", "c", "c", "-", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":", ":" },
     [14] = { [0] = "c", "c", "c", "-", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":", ":", ":" },
     [15] = { [0] = "c", "c", "c", "c", "-", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":", ":", ":" } }

  -- these are based on where the last "." glyph is in the array above
  local SPACING_BY_RADIUS =
    { [4] =  6,
      [5] =  6,
      [6] =  8,
      [7] =  8,
      [8] = 10,
      [9] = 12,
     [10] = 12,
     [11] = 14,
     [12] = 16,
     [13] = 16,
     [14] = 16,
     [15] = 18 }

  -- these are based on how many rooms fit
  local ROOMS_ACROSS_BY_RADIUS =
    { [4] = 10,
      [5] = 10,
      [6] =  7,
      [7] =  7,
      [8] =  5,
      [9] =  5,
     [10] =  4,
     [11] =  4,
     [12] =  3,
     [13] =  3,
     [14] =  3,
     [15] =  3 }

  -- which glyphs replace which when placing rooms
  local GLYPH_PRIORITY =
   { ["c"] = 0, ["-"] = 1, ["."] = 2, [":"] = 3, ["x"] = 4 }

  -- this function draws a diamond shape with the appropriate
  --  glyphs at different distances from the center
  function draw_diamond (center_x, center_y, radius)
    for dx = -radius, radius do
      for dy = -radius, radius do
        local x = center_x + dx
        local y = center_y + dy
        local abs_sum = math.abs(dx) + math.abs(dy)
        if (abs_sum <= radius) then
          local new_glyph = GLYPH_BY_RADIUS[radius][abs_sum]
          if (GLYPH_PRIORITY[new_glyph] <
              GLYPH_PRIORITY[mapgrd[x][y]]) then
            mapgrd[x][y] = new_glyph
          end
        end
      end
    end
  end

  -- choose parameters for layout

  -- valid room sizes 4 - 15, but middle ones look better
  local room_radius = math.floor(8.5 + you.depth_fraction() * 3
                                     + crawl.random_real() * 4
                                     - crawl.random_real() * 4)
  local ROOM_SPACING = SPACING_BY_RADIUS[room_radius]
  local ROOMS_ACROSS = ROOMS_ACROSS_BY_RADIUS[room_radius]

  local gxm, gym = dgn.max_bounds()
  extend_map{width = gxm, height = gym, fill = 'x'}

  local CENTER_X = gxm/2
  local CENTER_Y = gym/2
  local ROOMS_FROM_CENTER = (ROOMS_ACROSS - 1) / 2

  local MIN_ZONE_SIZE = 20  -- for connectivity

  -- room frequency and distribution
  local room_chance_center = 0.8
  local room_chance_at_1   = 0.5
  local room_chance_decrease = room_chance_center - room_chance_at_1
  local rooms_placed_fraction = 0.3 + crawl.random_real() * 0.1
  if you.at_branch_bottom() then
    rooms_placed_fraction = 0.4 + crawl.random_real() * 0.2
  end

  -- Variables for keeping track of how many rooms we have
  --  already added and which ones.
  --  -> We also keep track of the number of attempts so that we
  --     don't get an infinite loop if there is no room to place
  --     the rooms around the primary vault.
  local ROOM_COUNT_MAX = ROOMS_ACROSS * ROOMS_ACROSS
  local rooms_to_place = math.floor(ROOM_COUNT_MAX * rooms_placed_fraction)
  local rooms_placed_so_far = 0
  local sanity = 0
  local sanity_max = ROOM_COUNT_MAX * 10
  local room_already_placed = {}
  for x = 0, ROOMS_ACROSS - 1 do
    room_already_placed[x] = {}
    for y = 0, ROOMS_ACROSS - 1 do
      room_already_placed[x][y] = false
    end
  end

  -- place the rooms
  while (rooms_placed_so_far < rooms_to_place and sanity < sanity_max) do
    x = crawl.random_range(0, ROOMS_ACROSS - 1)
    y = crawl.random_range(0, ROOMS_ACROSS - 1)
    sanity = sanity + 1

    if (not room_already_placed[x][y]) then
      -- We are using a distribution with equal probability
      --  lines that form a superellipse (n=4).  This should
      --  yield a large map than a simple circle, but not look
      --  as regular as a square distribution.
      local x2 = x / ROOMS_FROM_CENTER - 1
      local y2 = y / ROOMS_FROM_CENTER - 1
      local distance_fraction = math.sqrt(x2*x2*x2*x2 + y2*y2*y2*y2)

      -- Probabilities of room placement fall of quadratically
      local falloff_factor = distance_fraction * distance_fraction
      local probability = room_chance_center -
                          room_chance_decrease * falloff_factor
      if (crawl.random_real() < probability) then
        -- the position will have a .5 if the number of rooms is even
        local room_x = CENTER_X +
                       math.floor((x - ROOMS_FROM_CENTER) * ROOM_SPACING)
        local room_y = CENTER_Y +
                       math.floor((y - ROOMS_FROM_CENTER) * ROOM_SPACING)
        if (not find_in_area {x1 = room_x - room_radius,
                              y1 = room_y - room_radius,
                              x2 = room_x + room_radius,
                              y2 = room_y + room_radius,
                              find = "", find_vault = true } ) then
          draw_diamond(room_x, room_y, room_radius)
          rooms_placed_so_far = rooms_placed_so_far + 1
          room_already_placed[x][y] = true
        end
      end
    end
  end

  -- crazy substitutions and effects to produce randomness
  subst("c=x")
  subst("-=:")
  smear_map { onto = ":", smear = "x", boxy = true,
              iterations = crawl.random_range(300, 500) }
  subst(":=.")
  if (crawl.coinflip()) then
    spotty_map { replace = "x", fill = ".", boxy = false,
                 iterations = crawl.random_range(50, 100) }
  end

  -- clean up the map
  --  -> the branch bottom must have only one open bubble
  --  -> remove disconnected areas
  --  -> ensure each bubble has a down stairs
  --  -> largest bubble should have the branch exit

  if you.at_branch_bottom() then
    zonify.map_fill_zones(_G, 1, 'x')
  else
    zonify.map_fill_zones(_G, 3, 'x', MIN_ZONE_SIZE)
    zonify.map_fill_zones(_G, 2, 'v', MIN_ZONE_SIZE)
    zonify.map_fill_zones(_G, 1, 'b', MIN_ZONE_SIZE)
    nsubst(". = 1:} / *:.")
    if you.depth() == 0 then
      nsubst(". = 1:{ / *:.")
    end
    nsubst("b = 1:) / *:.")
    nsubst("v = 1:] / *:.")
    shuffle("})]")
  end
}}
# Enforce minimum floor size - this is important
validate {{
  return minimum_map_area.is_map_big_enough(_G, minimum_map_area.NARROW_CAVES)
}}
MAP
ENDMAP