-- Squaresville mapgen.lua
-- Copyright Duane Robertson (duane@duanerobertson.com), 2017
-- Distributed under the LGPLv2.1 (https://www.gnu.org/licenses/old-licenses/lgpl-2.1.en.html)


local DEBUG
local abyssal_pivot = -20
local big_trees_mod = minetest.get_modpath('big_trees')
--local biomemap = {}
local biomes = squaresville.biomes
local booty_mod = minetest.get_modpath('booty')
local breaker = squaresville.breaker
local checking_schem_matches
local civ_base = squaresville.civ_base
local cloudcity_mod  -- = minetest.get_modpath('cloudcity')
local dangerous = squaresville.dangerous_terrain
local data = {}  -- This is not thread-safe.
local defmap = {}
local desolation = squaresville.desolation
local fun_caves_mod = minetest.get_modpath('fun_caves')
local geomoria_mod = minetest.get_modpath('geomoria')
local get_decoration = squaresville.get_decoration
--local heightmap = {}
local heightmap_p
local lake_depth = squaresville.lake_depth / 200
local math_abs = math.abs
local math_floor = math.floor
local math_max = math.max
local math_min = math.min
local max_height = 31000
local no_buildings = squaresville.no_buildings
local node = squaresville.node
local noore_mod = minetest.get_modpath('noore')
local os_clock = os.clock
local overgen = 0
local p2data = {}  -- vm rotation data buffer
local passages_mod = minetest.get_modpath('passages')
local river_base = squaresville.river_base
local river_cutoff = squaresville.river_cutoff
local schem_arrays = {}
local string_match = string.match
local terrain_scale_2 = squaresville.terrain_scale_2
local terrain_scale = squaresville.terrain_scale
local water_base = squaresville.water_level_base_mod
local zigg_mod = minetest.get_modpath('zigg')

-- These seem to help the y loop some (but not much).
local node_air = node['air']
local node_concrete = node['squaresville:concrete']
local node_road = node['squaresville:road']
local node_road_yellow_line = node['squaresville:road_yellow_line']
local node_sidewalk = node['squaresville:sidewalk']
local node_streetlight = node['squaresville:streetlight']
local node_stone = node['default:stone']


squaresville.fix_lighting = false
squaresville.chunks = 0


-- This will FAIL if run on multiple threads.
if squaresville.single_node or squaresville.single_node_ruin then
  squaresville.real_get_mapgen_object = minetest.get_mapgen_object
  minetest.get_mapgen_object = function(object)
    if object == 'heightmap' then
      return table.copy(heightmap_p)
    else
      return squaresville.real_get_mapgen_object(object)
    end
  end
end


-- Return information on proximity to roads and cities.
local function _get_zone(pos, dist_z, def)
  if not def then
    def = {}
  end

  def.attenuation = 1
  def.biome = nil
  def.biome_height = nil
  def.city = true
  def.civ = false
  def.danger = math_floor(math_max(math_abs(pos.x) / 6000, math_abs(pos.z) / 6000))
  def.ground_1 = nil
  def.ground_2 = nil
  def.heat = nil
  def.heat_1 = nil
  def.heat_2 = nil
  def.height = nil
  def.humidity = nil
  def.humidity_1 = nil
  def.humidity_2 = nil
  def.inter_city_road = false
  def.pre_river_height = nil
  def.river = nil
  def.road_center_here = false
  def.road_center_orient = 0
  def.road_here = false
  def.sewer = false
  def.sewer_wall = false
  def.sidewalk_here = false
  def.streetlight_here = false
  def.suburb = true
  def.water_height = water_base

  if not dist_z then
    local center_z = math_floor((pos.z + squaresville.center_add) / squaresville.wild_limits) * squaresville.wild_limits
    dist_z = math_abs(center_z - (pos.z + squaresville.max_height))
  end

  local center_x = math_floor((pos.x + squaresville.center_add) / squaresville.wild_limits) * squaresville.wild_limits
  local dist_x = math_abs(center_x - (pos.x + squaresville.max_height))
  local dist1 = math_max(dist_x, dist_z)

  if dist1 >= squaresville.suburb_limits + squaresville.half_road_size + 1 then
    -- in the wild
    def.city = false
    def.suburb = false
  elseif dist1 < squaresville.city_limits - squaresville.half_road_size then
    -- in the city
    def.suburb = false
    def.civ = true
  else
    -- in the suburbs
    def.city = false
    def.civ = true
  end

  local road_x = (dist_x + squaresville.half_road_size) % squaresville.block_plus_road_size
  local road_z = (dist_z + squaresville.half_road_size) % squaresville.block_plus_road_size

  if def.civ and not no_buildings then
    if road_x < squaresville.road_size or road_z < squaresville.road_size then
      def.road_here = true

      if not (road_x < squaresville.road_size and road_z < squaresville.road_size) and not (road_x ~= squaresville.half_road_size and road_z ~= squaresville.half_road_size) then
        def.road_center_here = true

        if road_z == squaresville.half_road_size then
          def.road_center_orient = 1
        end
      end

      if road_x >= squaresville.half_road_size - 1 and road_x <= squaresville.half_road_size + 1 and road_z >= squaresville.half_road_size - 1 and road_z <= squaresville.half_road_size + 1 then
        if road_x == squaresville.half_road_size and road_z == squaresville.half_road_size then
          def.sewer = true
        else
          def.sewer_wall = true
        end
      end
    end
  end

  local side_size_x = (dist_x + squaresville.half_road_size + 2) % squaresville.block_plus_road_size
  local side_size_z = (dist_z + squaresville.half_road_size + 2) % squaresville.block_plus_road_size
  if def.civ and (not def.road_here) and (side_size_x < squaresville.road_size + 4 or side_size_z < squaresville.road_size + 4) then
    def.sidewalk_here = true

    local light_x = (pos.x + squaresville.max_height + squaresville.half_road_size + 2) % squaresville.block_plus_road_size
    local light_z = (pos.z + squaresville.max_height + squaresville.half_road_size + 2) % squaresville.block_plus_road_size
    if light_x == squaresville.road_size + 2 and light_z % 20 == 5 then
      def.streetlight_here = 1
    elseif light_z == squaresville.road_size + 2 and light_x % 20 == 15 then
      def.streetlight_here = 0
    elseif light_x == 1 and light_z % 20 == 15 then
      def.streetlight_here = 3
    elseif light_z == 1 and light_x % 20 == 5 then
      def.streetlight_here = 2
    end
  end

  local road_dist = math_min(dist_x - squaresville.half_road_size, dist_z - squaresville.half_road_size)
  if road_dist == - squaresville.half_road_size then
    def.road_center_here = true
    if dist_z - squaresville.half_road_size < dist_x - squaresville.half_road_size then
      def.road_center_orient = 1
    end
  end
  road_dist = math_max(0, road_dist)

  if road_dist == 0 and not no_buildings then
    def.road_here = true
    def.inter_city_road = true
  end

  -- Attenuation is used to slope the terrain near towns.
  dist1 = dist1 - squaresville.suburb_limits - squaresville.half_road_size - 1
  if dist1 < squaresville.attenuation then
    def.attenuation = dist1 / squaresville.attenuation
  end

  if road_dist < squaresville.attenuation then
    def.attenuation = math_min(def.attenuation, road_dist / squaresville.attenuation)
  end

  return def
end


function squaresville.get_zone(pos)
  return _get_zone(pos)
end


-- Altitude has to be calculated for spawns (for a single point)
--  as well as for terrain (from tables of values), and doing it
--  in two locations is error-prone, so it all stays here.
local function _get_altitude_from_def(def)
  def.height = def.ground_1
  def.river = def.river - def.ground_2 / terrain_scale_2
  local g2 = def.ground_2

  if def.civ then
    def.height = civ_base
    if not (def.road_here or def.sidewalk_here) then
      -- Slightly alter flat terrain.
      if def.ground_1 > squaresville.half_terrain_scale then
        def.height = def.height + 1
      elseif def.ground_1 < squaresville.half_terrain_scale_neg then
        def.height = def.height - 1
      end
    end
  elseif def.road_here then
    def.height = civ_base
  else
    if math_abs(def.height) < 10 then
      g2 = g2 * math_abs(def.height) * 0.1
    end

    -- Add mountains and islands.
    if def.height > 0 then
      if g2 < 0 then
        g2 = -g2 * g2 * lake_depth
      end
    else
      if g2 < abyssal_pivot then
        g2 = 2 * (abyssal_pivot - g2) + abyssal_pivot
      end
    end
    def.height = def.height + g2 + water_base

    -- Slope the terrain at the edges of town to let it blend better.
    def.height = math_floor((def.height - civ_base) * def.attenuation + civ_base)
  end

  return def
end

local function _rivers_from_def(def)
  -- Lower the rivers in dry regions.
  if def.humidity_1 < 50 then
    def.river = def.river - (def.humidity_1 / 10) + 5
  end

  def.pre_river_height = def.height
  local t_base = river_base
  if def.civ then
    t_base = civ_base
  elseif def.attenuation < 1 then
    t_base = math_floor(river_base * def.attenuation + civ_base * (1 - def.attenuation))
  end

  if def.height > abyssal_pivot and def.river < river_cutoff then
    if def.civ then
      def.height = civ_base
    end
    def.water_height = math_min(t_base, def.height) - 3
    local bottom = math_min(t_base, def.height) + math_floor((def.river - river_cutoff) * 2) - water_base + river_base
    def.height = bottom
  elseif def.civ then
    -- No river valley effect necessary, since urban areas are flat.
  elseif def.height > t_base and def.river < squaresville.river_zone then
    def.height = math_max(t_base, math_floor((def.height - t_base) * math_max(0, def.river - river_cutoff) / squaresville.river_scale_less_one) + t_base)
  end

  -- River biomes use the height of the surrounding terrain.
  def.biome_height = def.height

  return def
end


function squaresville.get_altitude(pos)
  local noise = squaresville.noise
  local pos_2d = {x=pos.x, y=pos.z}

  local def = squaresville.get_zone(pos)
  def.ground_1 = minetest.get_perlin(noise['ground_1'].def):get2d(pos_2d)
  def.ground_2 = minetest.get_perlin(noise['ground_2'].def):get2d(pos_2d)
  def.river = math_abs(minetest.get_perlin(noise['river'].def):get2d(pos_2d))
  def.heat_1 = minetest.get_perlin(noise['heat_1'].def):get2d(pos_2d)
  def.heat_2 = minetest.get_perlin(noise['heat_2'].def):get2d(pos_2d)
  def.humidity_1 = minetest.get_perlin(noise['humidity_1'].def):get2d(pos_2d)
  def.humidity_2 = minetest.get_perlin(noise['humidity_2'].def):get2d(pos_2d)

  def = _get_altitude_from_def(def)
  return _rivers_from_def(def)
end


local function get_biome_from_def(def)
  if not def then
    return
  end

  -- Adjust height for standard biomes.
  def.biome_height = def.biome_height - water_base + 1
  if def.biome_height >= water_base and def.pre_river_height > def.biome_height then
    def.biome_height = math_max(def.biome_height, 8)
  end

  local height_factor = 0
  if def.biome_height > 20 then
    local h2 = def.biome_height - 20
    height_factor = - h2 * h2 / (terrain_scale + terrain_scale_2)
  end

  def.heat, def.humidity = def.heat_1, def.humidity_1

  if dangerous and def.danger < 1 then
    def.heat = math_min(math_max(def.heat, 40), 80)
    def.humidity = math_min(math_max(def.humidity, 40), 80)
  end

  if def.civ and desolation == 0 then
    def.humidity = squaresville.suburb_humidity
  end

  def.heat = def.heat + def.heat_2 + height_factor
  def.humidity = def.humidity + def.humidity_2

  local biome_name, biome_diff
  for name, biome in pairs(biomes) do
    if not dangerous or def.danger >= (biome.danger or 0) then
      if (biome.y_min or -31000) <= def.biome_height and (biome.y_max or 31000) >= def.biome_height then
        local heat_d = biome.heat_point - def.heat
        local humidity_d = biome.humidity_point - def.humidity
        local danger_d = 0
        if dangerous then
          danger_d = (biome.danger or 0) - def.danger
        end
        local diff = heat_d * heat_d + humidity_d * humidity_d + danger_d * danger_d

        if (not biome_diff) or diff < biome_diff then
          biome_name, biome_diff = name, diff
        end
      end
    end
  end

  if def.civ and biomes[biome_name].civ then
    def.biome = biomes[biome_name].civ
  else
    def.biome = biome_name
  end

  return def
end
squaresville.get_biome_from_def = get_biome_from_def


function squaresville.get_terrain(pos)
  local def = squaresville.get_altitude(pos)
  return get_biome_from_def(def)
end


-- This is a simple, breadth-first search, for checking whether
-- a depression in the ground is enclosed (for placing ponds).
-- It is cpu-intensive, but also easy to code.
local function heightmap_search(heightmap, csize, ri)
  if not heightmap[ri] then
    return
  end

  local s = {}
  local q = {}
  local tho = -squaresville.max_height

  for th = heightmap[ri], heightmap[ri] + 6 do
    for k, v in pairs(s) do
      s[k] = nil
    end
    for k, v in pairs(q) do
      q[k] = nil
    end
    s[ri] = true
    q[#q+1] = ri

    while #q > 0 do
      local ci = q[#q]
      local cx = (ci - 1) % csize.x
      local cz = math_floor((ci - 1) / csize.x)
      if ((cx <= 1 or cx >= csize.x - 2) or (cz <= 1 or cz >= csize.z - 2)) then
        break
      end
      q[#q] = nil
      for zo = -1, 1 do
        for xo = -1, 1 do
          if zo ~= xo then
            local ni = ci + (zo * csize.x) + xo
            if not s[ni] and heightmap[ni] <= th then
              s[ni] = true
              q[#q+1] = ni
            end
          end
        end
      end
    end

    if #q > 1 then
      tho = th - 1
      break
    end
  end

  if tho >= heightmap[ri] then
    return tho
  end
end


local Mapgen = {}
Mapgen.__index = Mapgen

function Mapgen.new(minp, maxp, seed)
  local self = setmetatable({
    area = nil,
    csize = nil,
    baseline = squaresville.baseline,
    biomemap = {}, -- use global?
    data = data,
    extent_bottom = squaresville.extent_bottom,
    extent_top = squaresville.extent_top,
    heightmap = {}, -- use global?
    meta_data = {},
    minp = minp,
    maxp = maxp,
    p2data = p2data,
    noise = {},
    schem = {},
    seed = seed,
    terrain_point_def = {},
    vm = nil,
  }, Mapgen)

  if maxp.y >= squaresville.baseline_ruin + squaresville.extent_bottom_ruin and minp.y <= squaresville.baseline_ruin + squaresville.extent_top_ruin then
    self.baseline = squaresville.baseline_ruin
    self.extent_bottom = squaresville.extent_bottom_ruin
    self.extent_top = squaresville.extent_top_ruin
  elseif maxp.y < self.baseline + self.extent_bottom or minp.y > self.baseline + self.extent_top then
    return nil
  end

  self.csize = vector.add(vector.subtract(maxp, minp), 1)

  local vm, emin, emax = minetest.get_mapgen_object("voxelmanip")
  if not (vm and emin and emax) then
    return
  end
  self.vm = vm

  self.data = vm:get_data(self.data)
  self.p2data = vm:get_param2_data(self.p2data)
  self.area = VoxelArea:new({MinEdge = emin, MaxEdge = emax})
  self.csize = vector.add(vector.subtract(maxp, minp), 1)

  return self
end


function Mapgen:generate(timed)
  -- For faux get_mapgen_object method above.
  heightmap_p = self.heightmap

  self:make_noise()

  local t_terrain = os_clock()
  self:terrain()
  squaresville.time_terrain = squaresville.time_terrain + os_clock() - t_terrain

  local occupied

  self:generate_caves(timed)
  self:generate_buildings(timed)

  if squaresville.single_node then
    for non_loop = 1, 1 do
      -- and (not squaresville.in_town or (geomoria_mod and geomoria and geomoria.geomoria_depth and self.maxp.y < geomoria.geomoria_depth * 80))
      if self:generate_big_trees(timed) then
        break
      end

      if self:generate_cloud_city(timed) then
        break
      end

      if self:generate_moria(timed) then
        break
      end

      -- Past here, call things that would cover roads.
      if squaresville.inter_city_road then
        break
      end

      if self:generate_zigg(timed) then
        break
      end
    end
  end

  self:check_repeatability()

  self:save_map(timed)

  -- Clear any tables that won't be reused.
  squaresville.chunks = squaresville.chunks + 1
end


function Mapgen:get_zone(pos, dist_z)
  return _get_zone(pos, dist_z, {})
end


function Mapgen:get_altitude(index, dist_z, check)
  local pos = {
    x = (index - 1) % self.csize.x + self.minp.x,
    z = math_floor((index - 1) / self.csize.x) + self.minp.z
  }

  if check and (pos.x ~= check.x or pos.z ~= check.z) then
    print(index..': '..(pos.x-self.minp.x+1)..','..(pos.z-self.minp.z+1)..' ~= '..(check.x-self.minp.x+1)..','..(check.z-self.minp.z+1))
  end

  local def = self:get_zone(pos, dist_z)
  def.ground_1 = self.noise['ground_1'].map[index]
  def.ground_2 = self.noise['ground_2'].map[index]
  def.heat_1 = self.noise['heat_1'].map[index]
  def.heat_2 = self.noise['heat_2'].map[index]
  def.humidity_1 = self.noise['humidity_1'].map[index]
  def.humidity_2 = self.noise['humidity_2'].map[index]
  def.river = math_abs(self.noise['river'].map[index])
  self.terrain_point_def = def

  return _get_altitude_from_def(def)
end


function Mapgen:terrain()
  local area = self.area
  local baseline = self.baseline
  local biomemap = self.biomemap
  local biome_survey = {}
  local civ_base_adj = self.baseline + civ_base
  local csize = self.csize
  local data = self.data
  local extent_bottom = self.extent_bottom
  local heightmap = self.heightmap
  local inter_city_road
  local maxp = self.maxp
  local minp = self.minp
  local p2data = self.p2data
  local schem = self.schem
  local seed = self.seed
  local water_level_base = self.baseline + water_base
  local water_level_town = self.baseline - 10

  squaresville.in_town = nil
  squaresville.suburbs = nil

  -- Empty the heightmap.
  for k, v in pairs(heightmap) do
    heightmap[k] = nil
  end
  for k, v in pairs(biomemap) do
    biomemap[k] = nil
  end
  for k, v in pairs(defmap) do
    defmap[k] = nil
  end

  local index = 1
  for z = minp.z, maxp.z do
    local center_z = math_floor((z + squaresville.center_add) / squaresville.wild_limits) * squaresville.wild_limits
    local dist_z = math_abs(center_z - (z + squaresville.max_height))

    for x = minp.x, maxp.x do
      local def = self:get_altitude(index, dist_z)
      defmap[index] = def
      index = index + 1
    end
  end

  -- This doesn't work so well...
  --index = 1
  --for z = minp.z, maxp.z, 8 do
  --  for x = minp.x, maxp.x, 8 do
  --    local low = squaresville.max_height
  --    local high = -squaresville.max_height
  --    local ip = 0
  --    for zp = 0, 7 do
  --      for xp = 0, 7 do
  --        if defmap[index + ip].height < low then
  --          low = defmap[index + ip].height
  --        end
  --        if defmap[index + ip].height > high then
  --          high = defmap[index + ip].height
  --        end
  --        ip = ip + 1
  --      end
  --      ip = ip + csize.x - 8
  --    end

  --    if high - low > 5 then
  --      ip = 0
  --      for zp = 0, 7 do
  --        for xp = 0, 7 do
  --          local d1, d2 = math_floor(low + (high - low) * 0.3), math_floor(low + (high - low) * 0.6)
  --          if defmap[index + ip].height <= d1 then
  --            defmap[index + ip].height = low
  --          elseif defmap[index + ip].height <= d2 then
  --            defmap[index + ip].height = low + 1
  --          end

  --          ip = ip + 1
  --        end
  --        ip = ip + csize.x - 8
  --      end
  --    end

  --    index = index + 8
  --  end
  --  index = index + csize.x * 7
  --end

  index = 1
  for z = minp.z, maxp.z do
    --local center_z = math_floor((z + squaresville.center_add) / squaresville.wild_limits) * squaresville.wild_limits
    --local dist_z = math_abs(center_z - (z + squaresville.max_height))

    for x = minp.x, maxp.x do
      local water_level = water_level_base

      local def = defmap[index]
      def = _rivers_from_def(def)
      get_biome_from_def(def)

      if not inter_city_road and def.inter_city_road then
        inter_city_road = true
      end

      local civ = def.civ
      desolation = squaresville.get_desolation(baseline, def.danger)
      local height = def.height
      local road_center_here = def.road_center_here
      local road_center_orient = def.road_center_orient
      local road_here = def.road_here
      local sewer = def.sewer
      local sewer_wall = def.sewer_wall
      local sidewalk_here = def.sidewalk_here
      local streetlight_here = def.streetlight_here

      if civ and not squaresville.in_town then
        squaresville.in_town = true
      end

      local biome_name = def.biome
      biome_survey[biome_name] = (biome_survey[biome_name] or 0) + 1
      biomemap[index] = biomes[biome_name]
      height = height + baseline
      heightmap[index] = height
      local biome_filler = node[biomes[biome_name].node_filler or 'default:stone']
      local biome_riverbed = node[biomes[biome_name].node_riverbed or 'default:sand']
      local biome_river_water = node[biomes[biome_name].node_river_water or 'default:water_source']
      local biome_stone = node[biomes[biome_name].node_stone] or node_stone
      local biome_top = node[biomes[biome_name].node_top or 'default:stone']
      local biome_water = node[biomes[biome_name].node_water or 'default:water_source']

      local fill_1 = height - (biomes[biome_name].depth_top or 0)
      local fill_2 = fill_1 - (biomes[biome_name].depth_filler or 0)
      local water_fill_1 = water_level - (biomes[biome_name].depth_water_top or 0)
      local deco

      local ivm = area:index(x, minp.y - overgen, z)
      local sewer_top = civ_base_adj - 12
      local sewer_bottom = civ_base_adj - 19
      for y = minp.y-overgen, maxp.y+overgen do
        for y_non_loop = 1, 1 do
          if data[ivm] ~= node_air then
            break
          end

          if y < height and y < -100 then
            data[ivm] = node_stone
          elseif y < height then
            data[ivm] = biome_stone
          end

          if civ and not no_buildings then
            if sewer_wall and y < civ_base_adj and y >= sewer_top then
              data[ivm] = breaker(node_concrete, y - baseline, def.humidity_1, desolation)
              break
            elseif sewer and y == civ_base_adj + 1 then
              data[ivm] = breaker(node['doors:trapdoor_steel'], y - baseline, def.humidity_1, desolation)
              p2data[ivm] = 0
              break
            elseif sewer and y <= civ_base_adj and y > sewer_bottom then
              data[ivm] = breaker(node['default:ladder_steel'], y - baseline, def.humidity_1, desolation)
              p2data[ivm] = 4
              break
            elseif road_here and y > sewer_bottom and y < sewer_top then
              data[ivm] = node_air
              break
            elseif sidewalk_here and y > sewer_bottom and y < sewer_top then
              data[ivm] = breaker(node_concrete, y - baseline, def.humidity_1, desolation)
              break
            elseif road_here and (y == sewer_bottom or y == sewer_top) then
              data[ivm] = breaker(node_concrete, y - baseline, def.humidity_1, desolation)
              break
            end
          end

          if road_here and y == civ_base_adj then
            if road_center_here then
              data[ivm] = breaker(node_road_yellow_line, y - baseline, def.humidity_1, desolation)
              p2data[ivm] = road_center_orient
            else
              data[ivm] = breaker(node_road, y - baseline, def.humidity_1, desolation)
            end
          elseif sidewalk_here and y == civ_base_adj then
            data[ivm] = breaker(node_sidewalk, y - baseline, def.humidity_1, desolation)
          elseif streetlight_here and y == civ_base_adj + 1 then
            data[ivm] = breaker(node_streetlight, y - baseline, def.humidity_1, desolation)
            p2data[ivm] = streetlight_here
          elseif def.river < river_cutoff and y < def.water_height and y <= height and y > height - (biomes[biome_name].depth_riverbed or 0) then
            data[ivm] = biome_riverbed
            if y > def.water_height - 2 then
              deco = y
            end
          elseif y <= height and y > fill_1 and not road_here and not sidewalk_here then
            data[ivm] = biome_top
            deco = y
          elseif y <= height and y > fill_2 then
            data[ivm] = biome_filler
          elseif def.river < river_cutoff and y >= height and y <= def.water_height then
            data[ivm] = biome_river_water
          elseif y >= height and y <= water_level and y > water_fill_1 then
            data[ivm] = node[biomes[biome_name].node_water_top or 'default:water_source']
          elseif y >= height and y <= water_level then
            data[ivm] = biome_water
          end

          if y <= baseline + extent_bottom then
            if y == baseline + extent_bottom then
              data[ivm] = node['squaresville:bedrock']
            else
              data[ivm] = node_air
            end
          end
        end

        -- Interesting caves...
        --local h2 = noise['ground_2'].map[index]
        --if y < height - h2 and y > height - h2 - 10 then
        --  data[ivm] = node_air
        --end

        ivm = ivm + area.ystride
      end

      index = index + 1
    end
  end

  squaresville.place_all_decorations(self)

  -- Determine the most common biome.
  do
    local bc = 0
    for b, c in pairs(biome_survey) do
      if c > bc then
        bc = c
        squaresville.main_biome = b
      end
    end
  end

  self:generate_ponds(squaresville.main_biome)

  squaresville.inter_city_road = inter_city_road
end


function Mapgen:generate_ponds(biome)
  if squaresville.lake_depth < 1 then
    return
  end

  local area = self.area
  local biome_filler = squaresville.node[squaresville.biomes[biome].node_filler or 'default:stone']
  local biome_water = squaresville.node[squaresville.biomes[biome].node_water or 'default:water_source']
  local checked = {}
  local csize = self.csize
  local data = self.data
  local heightmap = self.heightmap
  local lilies
  local maxp = self.maxp
  local minp = self.minp
  local pond_min = self.baseline + 20
  local ps = PcgRandom(self.seed + 93)
  local schem = self.schem

  if biome == 'deciduous_forest' or biome == 'savanna' or biome == 'rainforest' then
    lilies = true
  end

  -- Check for depressions every eight meters.
  for z = 5, csize.z - 4, 8 do
    for x = 5, csize.x - 4, 8 do
      local p = {x=x+minp.x-1, z=z+minp.z-1}
      local index = (z - 1) * csize.x + x
      local height = heightmap[index] + 1
      if height > pond_min and height >= minp.y - 1 and height <= maxp.y + 1 then
        local search = {}
        local h2 = heightmap_search(heightmap, csize, index)
        -- If a depression is there, look at all the adjacent squares.
        if h2 then
          for zo = -8, 8 do
            for xo = -8, 8 do
              local subindex = index + zo * csize.x + xo
              if not checked[subindex] then
                h2 = heightmap_search(heightmap, csize, subindex)
                -- Mark this as already searched.
                checked[subindex] = true
                if h2 then
                  -- Store depressed positions.
                  search[#search+1] = {x=x+xo, z=z+zo, h1=heightmap[subindex], h2=h2}
                end
              end
            end
          end

          for _, p2 in ipairs(search) do
            p2.x = p2.x + minp.x - 1
            p2.z = p2.z + minp.z - 1

            -- Take out any trees.
            local rem
            for i, sch in ipairs(schem) do
              if sch.pos.x == p2.x and sch.pos.z == p2.z then
                rem = i
                break
              end
            end
            if rem then
              table.remove(schem, rem)
            end

            -- Place water and lilies.
            local ivm = area:index(p2.x, p2.h1-1, p2.z)
            data[ivm] = biome_filler
            for h = p2.h1, p2.h2 do
              ivm = ivm + area.ystride
              data[ivm] = biome_water
            end
            ivm = ivm + area.ystride
            if lilies and ps:next(1, 10) == 1 then
              data[ivm] = node['flowers:waterlily']
            else
              data[ivm] = node_air
            end
          end
        end
      end
    end
  end
end


function Mapgen:save_map(timed)
  local t_over
  if timed then
    t_over = os_clock()
  end

  self.vm:set_data(self.data)
  self.vm:set_param2_data(self.p2data)

  -- Place all schematics after saving map data.
  for _, s in ipairs(self.schem) do
    squaresville.place_schematic(s.def, s.pos, self.vm, nil)
  end

  minetest.generate_ores(self.vm, self.minp, self.maxp)

  if booty_mod then
    booty.placer(self.minp, self.maxp, self.data, self.area)
  end

  if DEBUG then
    self.vm:set_lighting({day = 10, night = 10})
  else
    self.vm:set_lighting({day = 0, night = 0}, self.minp, self.maxp)
    self.vm:calc_lighting()
  end

  self.vm:update_liquids()
  self.vm:write_to_map()

  -- Sometimes calc_lighting doesn't work without this.
  if squaresville.fix_lighting then
    minetest.after(10, function(minp, maxp)
      local vm = minetest.get_voxel_manip(minp, maxp)
      if not vm then
        return
      end

      vm:calc_lighting(minp, maxp)
      vm:update_liquids()
      vm:write_to_map()
      vm:update_map()
    end, emin, emax)
  end

  -- Save all meta data for chests, cabinets, etc.
  for _, t in ipairs(self.meta_data) do
    local meta = minetest.get_meta({x=t.x, y=t.y, z=t.z})
    meta:from_table()
    meta:from_table(t.meta)
  end

  -- Call on_construct methods for nodes that request it.
  -- This is mainly useful for starting timers.
  for i, n in ipairs(self.data) do
    if squaresville.construct_nodes[n] then
      local pos = self.area:position(i)
      local node_name = minetest.get_name_from_content_id(n)
      if minetest.registered_nodes[node_name] and minetest.registered_nodes[node_name].on_construct then
        minetest.registered_nodes[node_name].on_construct(pos)
      end
    end
  end

  if timed then
    squaresville.time_overhead = squaresville.time_overhead + os_clock() - t_over
  end
end


function Mapgen:generate_moria(timed)
  if not geomoria_mod or not geomoria.in_range(self.minp, self.maxp) then
    return
  end

  local t_moria
  if timed then
    t_moria = os.clock()
  end

  local write, wetness = geomoria.geomorph(self.minp, self.maxp, self.data, self.p2data, self.area, node, self.heightmap, self.seed)
  local write = write or geomoria.exit_stair(self.minp, self.maxp)

  if timed then
    squaresville.time_moria = squaresville.time_moria + os_clock() - t_moria
  end

  return write
end


function Mapgen:generate_zigg(timed)
  if (not zigg_mod) or squaresville.in_town or self.minp.y > 100 or self.minp.y < -50 or (not zigg.ziggurat_biomes[squaresville.main_biome]) then
    return
  end

  local t_zigg
  if timed then
    t_zigg = os_clock()
  end

  local write, _ = zigg.ziggurat(self.minp, self.maxp, self.data, self.area, nil, nil, self.heightmap, self.schem)

  if timed then
    squaresville.time_zigg = squaresville.time_zigg + os_clock() - t_zigg
  end

  return write
end


function Mapgen:generate_cloud_city(timed)
  if not cloudcity_mod or self.minp.y > 129 or self.maxp.y < 47 then
    return
  end

  squaresville.cloudcity(self.minp, self.maxp, self.data, self.p2data, self.area, node, self.heightmap, self.seed)
end


function Mapgen:generate_big_trees(timed)
  if not big_trees_mod or tonumber(big_trees.version) and tonumber(big_trees.version) < 1.1 or self.minp.y > big_trees.tree_top or self.maxp.y < big_trees.tree_bottom then
    return
  end

  local t_tree, write
  if timed then
    t_tree = os.clock()
  end

  -- Try to determine if a tree will collide with a city.
  local h_width = math.floor(big_trees.tree_width / 2)
  local ex = (self.minp.x + 32) / big_trees.tree_width
  local ez = (self.minp.z + 32) / big_trees.tree_width
  ex = (ex == math.floor(ex))
  ez = (ez == math.floor(ez))
  local cz = (ez and self.minp.z + h_width or self.minp.z)
  local cx = (ex and self.minp.x + h_width or self.minp.x)
  local center_z = math.floor((self.minp.z + squaresville.center_add) / squaresville.wild_limits) * squaresville.wild_limits
  local dist_z = math.abs(center_z - (cz + squaresville.max_height))
  local center_x = math.floor(((ez and self.minp.x or self.minp.x + h_width) + squaresville.center_add) / squaresville.wild_limits) * squaresville.wild_limits
  local dist_x = math.abs(center_x - (cx + squaresville.max_height))
  local dist = math.max(dist_x, dist_z)
  if dist >= squaresville.suburb_limits + squaresville.half_road_size + h_width + 1 then
    write = big_trees.treegen(self.minp, self.maxp, self.data, self.area)
  end

  if timed then
    squaresville.time_trees = squaresville.time_trees + os_clock() - t_tree
  end

  return write
end


function Mapgen:generate_buildings(timed)
  if no_buildings or self.minp.y > self.baseline + 800 or self.maxp.y < self.baseline - 25 then
    return
  end

  local t_build
  if timed then
    t_build = os_clock()
  end

  squaresville.build(self)

  if timed then
    squaresville.time_buildings = squaresville.time_buildings + os_clock() - t_build
  end
end


function Mapgen:generate_caves(timed)
  local t_caves
  if timed then
    t_caves = os_clock()
  end

  if fun_caves_mod and squaresville.single_node then
    fun_caves.cavegen(self.minp, self.maxp, self.data, self.area, self.heightmap, self.schem)
  end

  if passages_mod and squaresville.single_node then
    passages.passages(self.minp, self.maxp, self.data, self.p2data, self.area, self.seed)
  end

  if fun_caves_mod and squaresville.single_node then
    fun_caves.decogen(self.minp, self.maxp, self.data, self.area, self.heightmap)
  end

  if noore_mod and noore.ore_in_caves > 0 and squaresville.single_node then
    noore.cavegen(self.minp, self.maxp, self.data, self.area)
  end

  if timed then
    squaresville.time_caves = squaresville.time_caves + os_clock() - t_caves
  end
end


function Mapgen:make_noise()
  -- Generate all squaresville noises.
  for n, _ in pairs(squaresville.noise) do
    if not squaresville.noise[n].noise then
      if squaresville.noise[n].is3d then
        squaresville.noise[n].noise = minetest.get_perlin_map(squaresville.noise[n].def, self.csize)
      else
        squaresville.noise[n].noise = minetest.get_perlin_map(squaresville.noise[n].def, {x=self.csize.x, y=self.csize.z})
      end

      if not squaresville.noise[n].noise then
        return
      end
    end

    if not self.noise[n] then
      -- Keep pointers to global noise info
      self.noise[n] = {
        def = squaresville.noise[n].def,
        map = nil,
        noise = squaresville.noise[n].noise,
      }
    end

    -- This stays with the mapgen object.
    if squaresville.noise[n].is3d then
      self.noise[n].map = squaresville.noise[n].noise:get3dMap_flat(self.minp, self.noise[n].map)
    else
      self.noise[n].map = squaresville.noise[n].noise:get2dMap_flat({x=self.minp.x, y=self.minp.z}, self.noise[n].map)
    end
  end
end


function Mapgen:check_repeatability()
  -- This is debug code to check that everything is 100% repeatable.
  if not checking_schem_matches then
    return
  end

  table.sort(self.schem, function(c,d)
    if c.pos.x < d.pos.x then
      return true
    elseif c.pos.x == d.pos.x and c.pos.z < d.pos.z then
      return true
    elseif c.pos.x == d.pos.x and c.pos.z == d.pos.z and c.pos.y < d.pos.y then
      return true
    else
      return false
    end
  end)
  if not schem_arrays[self.seed] then
    schem_arrays[self.seed] = self.schem
  else
    local wrong
    for i, d in pairs(self.schem) do
      if self.schem[i].pos then
        if self.schem[i].pos.x ~= schem_arrays[self.seed][i].pos.x or self.schem[i].pos.z ~= schem_arrays[self.seed][i].pos.z then
          wrong = i
          break
        end
      else
        print(i, dump(self.schem[i]))
      end
    end
    if wrong then
      print(self.seed, #self.schem, #schem_arrays[self.seed], wrong)
    elseif #self.schem > 0 then
      print(self.seed, 'Match!', #self.schem)
    end
  end
end


local function generate(minp, maxp, seed)
  if not (minp and maxp and seed) then
    return
  end

  if not squaresville.csize then
    squaresville.csize = vector.add(vector.subtract(maxp, minp), 1)

    if not squaresville.csize then
      return
    end
  end

  local mg = Mapgen.new(minp, maxp, seed)
  if not mg then
    return
  end

  mg:generate(true)
end


if squaresville.path then
  dofile(squaresville.path .. "/buildings.lua")
  --dofile(squaresville.path .. "/caves.lua")
  --dofile(squaresville.path .. "/cloudcity.lua")
end


local function pgenerate(...)
  local status, err = pcall(generate, ...)
  --local status, err = true
  --generate(...)
  if not status then
    print('Squaresville: Could not generate terrain:')
    print(dump(err))
    collectgarbage("collect")
  end
end


if squaresville.single_node and minetest.registered_on_generateds then
  -- This is unsupported. I haven't been able to think of an alternative.
  table.insert(minetest.registered_on_generateds, 1, pgenerate)
else
  minetest.register_on_generated(pgenerate)
end


function squaresville.spawnplayer(player)
  if minetest.get_modpath('beds') and beds and beds.spawn then
    local name = player:get_player_name()
    if beds.spawn[name] then
      return
    end
  end

  for i = 1, 200 do
    local x, z = math.random(4000) - 2000, math.random(4000) - 2000
    --x, z = 350, -900
    local pos = {x=x, z=z}
    pos.y = squaresville.get_altitude(pos).height
    if pos.y > squaresville.water_level_base_mod then
      pos.y = pos.y + 2
      --pos = {x=1100, y=squaresville.baseline + 25, z=1000}
      player:setpos(pos)
      return true
    end
  end
end