
--
-- Single village generation
--

village.villages = {}

-- Sidelength of the square of a village chunk, in nodes
local VILLAGE_CHUNK_SIZE = 12
-- Maximum height of village chunks (buildings)
local VILLAGE_CHUNK_HEIGHT = 20

-- Hill width and height
local HILL_W, HILL_H = 24, 6
-- Number of dirt nodes to extend below hill
local HILL_EXTEND_BELOW = 15

-- Chance values. Each chance is provided in a 1:x value,
-- e.g. a value of 8 means a chance of 1:8.
-- Only positive integers are allowed.

-- Chance that a ground node has a decor node on top (grass, etc.)
local DECOR_CHANCE = 8

-- Chance that a village is abandoned
local ABANDONED_CHANCE = 25

-- Chance a village chunk in an abandoned village spawns using
-- a 'ruins' variant (if one is available)
local ABANDONED_RUINS_CHANCE = 2

-- VoxelManip buffers for get_data() for more efficient memory usage
local vdata_main = {}
local vdata_spawn_chunk = {}

-- Savefile

local village_file = minetest.get_worldpath() .. "/villages.dat"

local modpath = minetest.get_modpath("rp_village")
local mod_locks = minetest.get_modpath("rp_locks") ~= nil
local mod_paint = minetest.get_modpath("rp_paint") ~= nil
local mapseed = minetest.get_mapgen_setting("seed")
local water_level = tonumber(minetest.get_mapgen_setting("water_level"))

local wood_materials = {
   wood = {
      "rp_default:planks",
      "rp_partialblocks:stair_wood",
      "rp_partialblocks:slab_wood",
      "rp_default:tree",
      "rp_default:fence",
      "rp_default:fence_gate_closed",
      "rp_door:door_wood_t_1",
      "rp_door:door_wood_b_1",
      "rp_door:door_wood_t_2",
      "rp_door:door_wood_b_2",
   },
   birch = {
      "rp_default:planks_birch",
      "rp_partialblocks:stair_birch",
      "rp_partialblocks:slab_birch",
      "rp_default:tree_birch",
      "rp_default:fence_birch",
      "rp_default:fence_gate_birch_closed",
      "rp_door:door_wood_birch_t_1",
      "rp_door:door_wood_birch_b_1",
      "rp_door:door_wood_birch_t_2",
      "rp_door:door_wood_birch_b_2",
   },
   oak = {
      "rp_default:planks_oak",
      "rp_partialblocks:stair_oak",
      "rp_partialblocks:slab_oak",
      "rp_default:tree_oak",
      "rp_default:fence_oak",
      "rp_default:fence_gate_oak_closed",
      "rp_door:door_wood_oak_t_1",
      "rp_door:door_wood_oak_b_1",
      "rp_door:door_wood_oak_t_2",
      "rp_door:door_wood_oak_b_2",
   },
   fir = {
      "rp_default:planks_fir",
      "rp_partialblocks:stair_fir",
      "rp_partialblocks:slab_fir",
      "rp_default:tree_fir",
      "rp_default:fence_fir",
      "rp_default:fence_gate_fir_closed",
      "rp_door:door_wood_fir_t_1",
      "rp_door:door_wood_fir_b_1",
      "rp_door:door_wood_fir_t_2",
      "rp_door:door_wood_fir_b_2",
   },
}

-- List of wood types used in the source schematic files
local SOURCE_STYLES = { "birch", "oak", "wood" }
--[[ List of village wood materials (schematic replacements)
One of these will be chosen at random per village. ]]
local village_wood_styles = {
   { "birch", "oak", "wood" },
   { "wood", "oak", "wood" },
   { "oak", "fir", "wood" },
   { "wood", "birch", "wood" },
   { "fir", "birch", "wood" },
   { "wood", "wood", "wood" },
   { "birch", "birch", "birch" },
   { "oak", "oak", "oak" }, -- must be synced with VILLAGE_REPLACE_OAK
   { "fir", "fir", "fir" },
}
-- Index of oak-only village wood style (must be synced with village_wood_styles
-- table)
local VILLAGE_REPLACE_OAK = 8

--[[ Generate list of replacable house blocks.
It will be a table indexed by the original node name (used in the schematic)
with the value being the new node name (to replace it with).
This allows houses to vary in wood styles ]]
local village_replaces = {}
for s=1, #village_wood_styles do
   local style = village_wood_styles[s]
   local replace = {}
   for t=1, #style do
      local materials = wood_materials[style[t]]
      local source_materials = wood_materials[SOURCE_STYLES[t]]
      for w=1, #materials do
         local mat1 = source_materials[w]
         local mat2 = materials[w]
         if mat1 ~= mat2 then
            replace[mat1] = mat2
         end
      end
   end
   table.insert(village_replaces, replace)
end

local schematic_cache = {}
-- Wrapper around minetest.read_schematic to
-- speed up loading time on subsequent reads.
-- returns a schematic specifier.
local function read_cached_chunk_schematic(subchunktype)
   if schematic_cache[subchunktype] then
      return schematic_cache[subchunktype], true
   end
   local schem_path = modpath .. "/schematics/village_" .. subchunktype .. ".mts"
   local schem_spec = minetest.read_schematic(schem_path, {})
   schematic_cache[subchunktype] = schem_spec
   return schem_spec, false
end

function village.get_id(name, pos)
   return name .. string.format("%d", minetest.hash_node_position(pos))
end

function village.save_villages()
   local f = io.open(village_file, "w")

   for name, def in pairs(village.villages) do
      f:write(name .. " " .. def.name .. " "
                 .. string.format("%d", minetest.hash_node_position(def.pos)) .. "\n")
   end

   io.close(f)
end

function village.load_villages()
   local f = io.open(village_file, "r")

   if f then
      repeat
	 local l = f:read("*l")
	 if l == nil then break end

	 for name, fname, pos in string.gmatch(l, "(.+) (%a+) (%d.+)") do
	    village.villages[name] = {
	       name = fname,
	       pos = minetest.get_position_from_hash(pos),
	    }
	    village.name.used[fname] = true
	 end
      until f:read(0) == nil

      io.close(f)
   else
      village.save_villages()
   end

   village.load_waypoints()
end

function village.load_waypoints()
   for name, def in pairs(village.villages) do
      nav.remove_waypoint("village_" .. name)
      nav.add_waypoint(
	 def.pos,
	 "village_" .. name,
	 def.name .. " village",
	 true,
	 "village"
      )
   end
end

function village.get_nearest_village(pos)
   local nearest = math.huge
   local npos = nil -- village pos
   local fname = nil -- human-readable village name
   local name = nil -- village ID

   for name, def in pairs(village.villages) do
      local dist = vector.distance(pos, def.pos)
      if dist < nearest then
	 nearest = dist
	 name = name
	 fname = def.name
	 npos = def.pos
      end
   end
   if not fname then
	   return nil
   end
   return {dist = nearest, pos = npos, name = name, fname = fname}
end

village.chunkdefs = {}

--[[
Village chunks are the square sections of a village. This includes buildings,
farms, roads, and the like.

village chunk definition:
{
   -- every field is optional
   can_cache = <bool>, -- if true, schematic can be cached by Luanti
                       -- use this if no random node replacements (like wood)
                      -- are required (default: false)
   variants = { "variant_1", ..., "variant_n" },
   -- list of chunktype variants. One random variatn will be picked at random
   -- on placement. Each name must correspond to a file
   -- in `schematics/village_<variant_name>.mts`. By default, a chunktype has
   -- 1 variant with the name equal to the chunktype identifier
   groundclass_variants = {
      [ "groundclass_1"] = { "variant_1", ... "variant_n" },
      ...,
      [ "groundclass_n"] = { "another_variant_1", ... "another_variant_n" },
   },
   -- An alternative way to specify variants. Instead of a single list of
   -- variants, this specifies multiple lists of variants, each assigned
   -- a groundclass. In this case, the chunktype can only be placed if
   -- the village has this given groundclass. If it has that groundclass,
   -- a random variant in that groundclass is selected.

   -- Note: either variants, groundclass_variants or neither can be specified,
   -- but not both.

   ruins = { "ruins_1", ..., "ruins_n" },
   -- Like variants, but for a ruined version of this chunktype. In abandoned
   -- villages, one random ruined variant MAY be chosen from the list, or the
   -- 'intact' schematic is placed (but "generic" ruinations like broken glass
   -- still apply).
   -- If unused, the 'intact' schematic will be placed.

   groundclass_ruins = {
      [ "groundclass_1"] = { "ruins_1", ... "ruins_n" },
      ...,
      [ "groundclass_n"] = { "another_ruins_1", ... "another_ruins_n" },
   },
   -- Like groundclass_variants, but for ruins.

   entities = {
      [entity_1] = <number>,
      ...
      [entity_n] = <number>,
   },
   -- list of entities that can spawn (needs entity spawner node in schematic).
   -- For villagers, the key must be of the form '__villager_<profession>',
   -- e.g. '__villager_farmer'.
   -- For all other entities, use the entitystring, e.g. 'rp_mobs_mobs:sheep'.

   entity_chance = <number>,
   -- Chance for an entity to spawn by an entity spawner. Chance is 1/<number>
}
]]

village.chunkdefs["livestock_pen"] = {
   groundclass_variants = {
      ["grassland"] = {"livestock_pen", "livestock_pen_mirrored"},
   },
   entities = {
      ["rp_mobs_mobs:sheep"] = 3,
      ["rp_mobs_mobs:boar"] = 1,
   },
}
village.chunkdefs["lamppost"] = { -- not road because of road height limit of 1 nodes
   groundclass_variants = {
      ["grassland"] = {"lamppost"},
      ["dry"] = {"lamppost"},
      ["savanna"] = {"lamppost"},
      ["swamp"] = {"swamp_lamppost"},
   },
   groundclass_ruins = {
      ["grassland"] = {"lamppost_ruins"},
      ["dry"] = {"lamppost_ruins"},
      ["savanna"] = {"lamppost_ruins"},
      ["swamp"] = {"swamp_lamppost_ruins", "swamp_lamppost_ruins_2"},
   },
   can_cache = true,
   entity_chance = 2,
   entities = {
      ["__villager_carpenter"] = 1,
   },
}
village.chunkdefs["well"] = {
   ruins = {"well_ruins"},
   entities = {
      ["__villager_farmer"] = 1,
      ["__villager_tavernkeeper"] = 1,
   },
}
village.chunkdefs["house"] = {
   groundclass_variants = {
      ["grassland"] = {"house", "house_2", "house_3", "house_4", "house_5", "house_6", "house_7", "house_8", "house_9"},
      ["dry"] = {"house", "house_2", "house_3", "house_4", "house_5", "house_6", "house_7", "house_8", "house_9"},
      ["savanna"] = {"house", "house_2", "house_3", "house_4", "house_5", "house_6", "house_7", "house_8", "house_9"},
   },
   ruins = {"house_ruins", "house_ruins_2"},
   entity_chance = 2,
   entities = {
      ["__villager_carpenter"] = 1,
   },
}
village.chunkdefs["hut_s"] = {
   groundclass_variants = {
      ["swamp"] = {"reed_hut_s_1","reed_hut_s_2","reed_hut_s_3","reed_hut_s_4","reed_hut_s_5","reed_hut_s_6","reed_hut_s_7"},
   },
   ruins = {"reed_hut_s_ruins", "reed_hut_s_ruins_2"},
   entitity_chance = 2,
   entities = {
      ["__villager_farmer"] = 1,
   },
}
village.chunkdefs["hut_m"] = {
   groundclass_variants = {
      ["swamp"] = {"reed_hut_m_1","reed_hut_m_2","reed_hut_m_3","reed_hut_m_4","reed_hut_m_5","reed_hut_m_6","reed_hut_m_7"},
   },
   ruins = {"reed_hut_m_ruins", "reed_hut_m_ruins_2"},
   entitity_chance = 2,
   entities = {
      ["__villager_farmer"] = 1,
   },
}

village.chunkdefs["workshop"] = {
   groundclass_variants = {
      grassland = {"workshop"},
      dry = {"workshop"},
      savanna = {"workshop"},
      swamp = {"reed_workshop"},
   },
   groundclass_ruins = {
      grassland = {"workshop_ruins", "rubble"},
      dry = {"workshop_ruins", "rubble"},
      savanna = {"workshop_ruins", "rubble"},
      swamp = {"reed_workshop_ruins"},
   },
   entity_chance = 2,
   entities = {
      ["__villager_carpenter"] = 1,
   },
}
village.chunkdefs["townhall"] = {
   groundclass_variants = {
      grassland = {"townhall"},
      dry = {"townhall"},
      savanna = {"townhall"},
      swamp = {"reed_townhall"},
   },
   groundclass_ruins = {
      grassland = {"townhall_ruins", "rubble"},
      dry = {"townhall_ruins", "rubble"},
      savanna = {"townhall_ruins", "rubble"},
      swamp = {"reed_townhall_ruins"},
   },
   entity_chance = 1,
   entities = {
      ["__villager_tavernkeeper"] = 1,
      ["__villager_farmer"] = 1,
      ["__villager_blacksmith"] = 1,
      ["__villager_carpenter"] = 1,
   },
}


village.chunkdefs["tavern"] = {
   groundclass_variants = {
      grassland = {"tavern"},
      dry = {"tavern"},
      savanna = {"tavern"},
      swamp = {"reed_tavern_1"},
   },
   groundclass_ruins = {
      grassland = {"tavern_ruins"},
      dry = {"tavern_ruins"},
      savanna = {"tavern_ruins"},
      swamp = {"reed_tavern_ruins_1", "reed_tavern_ruins_2"},
   },
   entity_chance = 2,
   entities = {
      ["__villager_tavernkeeper"] = 1,
   },
}

village.chunkdefs["inn"] = {
   groundclass_variants = {
      grassland = {"inn"},
      dry = {"inn"},
      savanna = {"inn"},
   },
   groundclass_ruins = {
      grassland = {"tavern_ruins"},
      dry = {"tavern_ruins"},
      savanna = {"tavern_ruins"},
   },
   entity_chance = 2,
   entities = {
      ["__villager_tavernkeeper"] = 1,
   },
}

village.chunkdefs["library"] = {
   groundclass_variants = {
      grassland = {"library"},
      dry = {"library"},
      savanna = {"library"},
      swamp = {"reed_library"},
   },
   groundclass_ruins = {
      grassland = {"library_ruins"},
      dry = {"library_ruins"},
      savanna = {"library_ruins"},
      swamp = {"reed_library_ruins"},
   },
   entity_chance = 3,
   entities = {
      ["__villager_carpenter"] = 1,
   },
}
village.chunkdefs["reading_club"] = {
   groundclass_variants = {
      grassland = {"reading_club"},
      dry = {"reading_club"},
      savanna = {"reading_club"},
   },
   ruins = {"house_ruins", "house_ruins_2"},
   entity_chance = 3,
   entities = {
      ["__villager_farmer"] = 1,
      ["__villager_blacksmith"] = 1,
   },
}

village.chunkdefs["bakery"] = {
   groundclass_variants = {
      grassland = {"bakery"},
      dry = {"bakery"},
      savanna = {"bakery"},
   },
   ruins = {"bakery_ruins"},
   entity_chance = 2,
   entities = {
      ["__villager_farmer"] = 1,
   },
}


village.chunkdefs["forge"] = {
   groundclass_variants = {
      grassland = {"forge"},
      dry = {"forge"},
      savanna = {"forge"},
      swamp = {"reed_forge"},
   },
   groundclass_ruins = {
      grassland = {"forge_ruins", "rubble"},
      dry = {"forge_ruins", "rubble"},
      savanna = {"forge_ruins", "rubble"},
      swamp = {"reed_forge_ruins"},
   },
   entity_chance = 2,
   entities = {
      ["__villager_blacksmith"] = 1,
   },
}
village.chunkdefs["orchard"] = {
   groundclass_variants = {
      ["grassland"] = {"orchard"},
   },
   ruins = {"orchard_ragged"},
   can_cache = true,
   entity_chance = 2,
   entities = {
      ["__villager_farmer"] = 1,
   },
}
village.chunkdefs["road"] = {
   can_cache = true,
}

-- Farm chunktypes.
--
-- Farm chunktype naming scheme:
--
--    farm_<water><lines>_<plants>
--
-- * <water>: water position:
--    * "v": vertical lines
--    * "h": horizontal lines
--    * "c": center
--    * "o": outwards
-- * <lines>:
--    * for v/h: list of numbers at where the water will be
--    * for c/o: how much water in total
-- * <plants>: List of plants (from left to right)

village.chunkdefs["farm_small_plants"] = {
   groundclass_variants = {
      ["grassland"] = {
         "farm_v24_potato",
         "farm_v24_potato_wheat",
         "farm_v24_wheat",
         "farm_v24_wheat_cotton",
         "farm_v24_cotton",
         "farm_h246_potato",
         "farm_h246_wheat",
         "farm_h246_cotton",
      },
      ["swamp"] = {
         "farm_swamp_v24_asparagus",
         "farm_swamp_h246_asparagus",
      },
      ["savanna"] = {
         "farm_dry_v24_cotton",
         "farm_dry_h246_cotton",
      },
      ["dry"] = {
         "farm_dryd_v24_carrot",
         "farm_dryd_h246_carrot",
      },
   },
   entity_chance = 2,
   entities = {
      ["__villager_farmer"] = 1,
   }
}

village.chunkdefs["farm_papyrus"] = {
   groundclass_variants = {
      ["grassland"] = {
         "farm_c4_papyrus",
         "farm_o4_papyrus",
      },
      ["swamp"] = {
         "farm_swamp_c4_papyrus",
         "farm_swamp_o4_papyrus",
      },
   },
   entity_chance = 2,
   entities = {
      ["__villager_farmer"] = 1,
   }
}

-- List of chunk types. Chunk types are structurs and buildings
-- that are not the well and are placed next to roads.
-- The number is their absolute frequency. The higher the number,
-- the more likely it will occur.
-- The well is not listed here because it acts as the start point.
village.chunktypes = {
   -- { chunktype, absolute frequency }

   -- houses
   { "house", 210 },
   { "hut_s", 105 },
   { "hut_m", 105 },
   -- meeting rooms
   { "tavern", 120 },
   { "townhall", 60 },
   { "library", 20 },
   { "reading_club", 30 },
   { "inn", 20 },
   -- workplaces
   { "forge", 100 },
   { "workshop", 100 },
   { "bakery", 60 },
   -- farming
   { "farm_small_plants", 120 },
   { "farm_papyrus", 120 },
   { "orchard", 60 },
   { "livestock_pen", 60 },
}

-- List of chunktypes to be used as fallback for the starting
-- village chunk if the village failed to place any buildings
-- outside the starting point.
-- In this case, the "starter well" will be a house
-- instead. This will create nice "lonely huts".
village.chunktypes_start_fallback = {
   -- chunktype, absolute frequency
   { "house", 14 },
   { "tavern", 7 },
   { "forge", 3 },
}

-- Calculate cumulated absolute frequency of a chunktypes
-- table and put it in index 3 of each entry. Puts the sum
-- of all absolute frequencies in `chunksum`.
local write_absolute_frequencies = function(chunktypes)
   local chunksum = 0
   for i=1, #chunktypes do
      chunksum = chunksum + chunktypes[i][2]
      chunktypes[i][3] = chunksum
   end
   chunktypes.chunksum = chunksum
end
write_absolute_frequencies(village.chunktypes)
write_absolute_frequencies(village.chunktypes_start_fallback)

-- Select a random chunk. The probability of a chunk being selected is
-- <absolute frequency> / <sum of all absolute frequencies>.
-- * `pr`: PseudoRandom object
-- * `chunktypes`: A table of chunktypes (see above) (default: `village.chunktypes`)
-- * `groundclass`: Restrict chunktypes to this ground class
local function random_chunktype(pr, chunktypes, groundclass)
   if not chunktypes then
      chunktypes = village.chunktypes
   end
   local check_chunktypes = table.copy(chunktypes)
   while #check_chunktypes > 0 do
      local rnd = pr:next(1, check_chunktypes.chunksum)
      for i=1, #check_chunktypes do
         if rnd <= check_chunktypes[i][3] then
            local chunktype = check_chunktypes[i][1]
            if groundclass and village.chunkdefs[chunktype].groundclass_variants and village.chunkdefs[chunktype].groundclass_variants[groundclass] == nil then
               table.remove(check_chunktypes, i)
               break
            else
               return chunktype
            end
         end
      end
   end
   minetest.log("error", "[rp_village] random_chunktype: Failed to find a chunktype, using a fallback")
   return "house" -- fallback
end

local function get_chunktype_variant(pr, chunktype, groundclass)
   local ctd = village.chunkdefs[chunktype]
   if not ctd then
      return chunktype
   end
   if ctd.variants then
      return ctd.variants[pr:next(1, #ctd.variants)]
   elseif groundclass and ctd.groundclass_variants and ctd.groundclass_variants[groundclass] then
      return ctd.groundclass_variants[groundclass][pr:next(1, #ctd.groundclass_variants[groundclass])]
   else
      return chunktype
   end
end

-- Given a chunktype, returns a random 'ruins' version
-- for that chunktype if one is available. Otherwise,
-- returns `chunktype`.
-- * `pr`: PseudoRandom object
-- * `chunktype`: Chunktype identifier
-- * `groundclass`: Restrict chunktypes to this ground class
local function get_ruined_chunktype(pr, chunktype, groundclass)
   local ctd = village.chunkdefs[chunktype]
   if not ctd then
      return chunktype
   end
   if ctd.ruins then
      return ctd.ruins[pr:next(1, #ctd.ruins)]
   elseif groundclass and ctd.groundclass_ruins and ctd.groundclass_ruins[groundclass] then
      return ctd.groundclass_ruins[groundclass][pr:next(1, #ctd.groundclass_ruins[groundclass])]
   else
      return get_chunktype_variant(pr, chunktype, groundclass)
   end
end

local function check_column_end(nn)
   local nd = minetest.registered_nodes[nn]
   return (not nd) or nn == "ignore" or (not (nn == "air" or (not nd.walkable) or ((minetest.get_item_group(nn, "dirt") > 0) and minetest.get_item_group(nn, "grass_cover") > 0)))
end

function village.get_column_nodes(vmanip, pos, scanheight, dirtnodes)
   local nn = vmanip:get_node_at({x=pos.x,y=pos.y+1,z=pos.z}).name
   if check_column_end(nn) then
       return
   end

   for y = pos.y, pos.y - scanheight, -1 do
      local p = {x = pos.x, y = y, z = pos.z}

      nn = vmanip:get_node_at(p).name
      if check_column_end(nn) then
         break
      else
         table.insert(dirtnodes, p)
      end
   end
end

-- Generate a hill.
--
-- * vmanip: VoxelMapnip object
-- * vdata: VoxelManip data table
-- * pos: Hill position
-- * ground: Ground nodename (below surface)
-- * ground_top: Ground nodename (surface)
-- * top_decors: Optional table of possible decorations to place on top of ground_top
-- * decors_to_place: Table in which positions of decor nodes will be stored (call-by-reference)
--                    Must be provided if `top_decors` is set
function village.generate_hill(vmanip, vdata, pos, ground, ground_top, top_decors, decors_to_place)
   local c_ground = minetest.get_content_id(ground)
   local c_ground_top = minetest.get_content_id(ground_top)
   local c_decors = {}
   local seed = 13 + minetest.hash_node_position(pos) + mapseed
   local decor_pr = PcgRandom(seed)
   if top_decors then
      for d=1, #top_decors do
         c_decors[d] = minetest.get_content_id(top_decors[d])
      end
   end
   local dirts = {}
   local dirts_with_grass = {}
   local vmin, vmax = vmanip:get_emerged_area()
   local varea = VoxelArea:new({MinEdge = vmin, MaxEdge = vmax})
   for y=HILL_H-1, 0, -1 do
   -- Count number of nodes that were actually changed on this layer
   local nodes_set = 0
   for z=y,HILL_W-1-y do
   for x=y,HILL_W-1-y do
      local p = {x=pos.x+x, y=pos.y+y, z=pos.z+z}
      local vindex = varea:index(p.x,p.y,p.z)
      local vindex_above = varea:index(p.x,p.y+1,p.z)
      local n_content = vdata[vindex]
      if n_content then
         local nname = minetest.get_name_from_content_id(n_content)
         local def = minetest.registered_nodes[nname]
         local is_any_dirt = minetest.get_item_group(nname, "dirt") == 1
         local is_dirt = nname == "rp_default:dirt" or nname == "rp_default:swamp_dirt"
         local is_dry_dirt = nname == "rp_default:dry_dirt"
         if (not is_dry_dirt) and (is_dirt or (not is_any_dirt)) and (nname == "air" or nname == "ignore" or (def and (def.liquidtype ~= "none" or (def.is_ground_content)))) then
            local prev_was_ground = n_content == c_ground or n_content == c_ground_top
            if (y == HILL_H-1 or z == y or x == y or z == HILL_W-1-y or x == HILL_W-1-y) and (p.y >= water_level) then
               -- set surface node (e.g. dirt-with-grass)
               vdata[vindex] = c_ground_top
            else
               -- set 'below ground' node (e.g. dirt)
               vdata[vindex] = c_ground
            end
            if not prev_was_ground then
               nodes_set = nodes_set + 1
            end
         end
         -- chance to spawn a decor node (like grass) above ground_top
         local vindex_above = varea:index(p.x,p.y+1,p.z)
         if top_decors and #c_decors > 0 and vdata[vindex] == c_ground_top and vdata[vindex_above] == minetest.CONTENT_AIR and decor_pr:next(1,DECOR_CHANCE) == 1 then
            local decor = c_decors[decor_pr:next(1, #c_decors)]
            -- Don't place the decor immediately, instead remember this position and decor nodename
            -- and place all decorations at the end. This makes it easier to avoid conflicts
            -- with the rest of the generation algorithm.
            table.insert(decors_to_place, {
               -- VManip data index of decor position
               index_decor = vindex_above,
               -- content ID of decor node
               content_decor = c_decors[decor_pr:next(1, #c_decors)],
               -- VManip data index of floor position (on which decor will be placed)
               index_floor = vindex,
               -- content ID of floor node
               content_floor = vdata[vindex],
            })
            -- decors_to_place is call-by-reference, the caller can use this table afterwards
         end
      end
   end
   end
   -- Stop hill generation if no nodes were changed in this layer,
   -- because the building already has a foundation.
   if nodes_set == 0 then
      -- Partial / no hill generated (because not neccessary)
      return false
   end
   end
   -- Full hill generated
   return true
end

local function check_empty(pos)
   local min = { x = pos.x, y = pos.y + 1, z = pos.z }
   local max = { x = pos.x+12, y = pos.y+12, z = pos.z+12 }
   local ignores = minetest.find_nodes_in_area(min, max, "ignore")
   -- Treat an area of ignore nodes as non-empty (we err on the side of caution)
   if #ignores > 0 then
       minetest.log("action", "[rp_village] check_empty: Ignore found! pos="..minetest.pos_to_string(pos, 0).."; number of ignores="..(#ignores))
       return false
   end
   local stones = minetest.find_nodes_in_area(min, max, "group:stone")
   if #stones > 15 then
      return false
   end
   local leaves = minetest.find_nodes_in_area(min, max, "group:leaves")
   if #leaves > 2 then
      return false
   end
   local trees = minetest.find_nodes_in_area(min, max, "group:tree")
   if #trees > 0 then
      return false
   end
   return true
end

-- Map ground nodes with appropiate decor nodes to place on top
-- (e.g. grass)
-- Decors for normal villages
local decors_from_ground = {
   ["rp_default:dirt_with_grass"] = { "rp_default:grass" },
   ["rp_default:dirt_with_dry_grass"] = { "rp_default:dry_grass" },
   ["rp_default:dirt_with_swamp_grass"] = { "rp_default:swamp_grass" },
}
-- Decors for abandoned villages
local decors_from_ground_abandoned = table.copy(decors_from_ground)
-- Same as normal villages, except there's also tall grass
decors_from_ground_abandoned["rp_default:dirt_with_grass"] =
   {"rp_default:grass", "rp_default:grass", "rp_default:grass", "rp_default:tall_grass"}

-- Spawns a village chunk. This is a section of a village.
-- By default, this checks for empty space first (fails if no space),
-- then it generates a foundation of ground nodes, then it deletes
-- nodes above, then places the building as specified in chunktype.
--
-- Parameters:
-- * vmanip: VoxelManip object
-- * pos: pos to spawn chunk in
-- * state: table for internal state (call-by-reference)
-- * orient: orientation (for minetest.place_schematic)
-- * replace: one of these:
--    * node replacements table (for minetest.place_schematic)
--    * number of village replacements ID (from village_replacements table)
-- * pr: PseudoRandom object for random stuff
-- * chunktype: village chunk type ID
-- * noclear: If true, won't delete nodes before spawning
-- * nofill: If true, won't build a dirt foundation
-- * dont_check_empty: If true, don't fail if there is no empty space
-- * ground: ground node below surface
-- * ground_top: ground node on surface
--
-- returns true if chunk was placed, false otherwise.
function village.spawn_chunk(vmanip, pos, state, orient, replace, pr, chunktype, noclear, nofill, dont_check_empty, ground, ground_top)
   if not dont_check_empty and not check_empty(pos) then
      minetest.log("verbose", "[rp_village] Chunk not generated (too many stone/leaves/trees in the way) at "..minetest.pos_to_string(pos))
      return false
   end

   if noclear ~= true then
       local ok = minetest.place_schematic_on_vmanip(
         vmanip,
         pos,
         modpath .. "/schematics/village_empty.mts",
         "0",
         {},
         true
      )
      if not ok then
         minetest.log("warning", "[rp_village] Could not fully place empty schematic in village at "..minetest.pos_to_string(pos, 0))
      end
   end

   if nofill ~= true then
      vmanip:get_data(vdata_spawn_chunk)
      -- Make a hill for the buildings to stand on
      local decors
      if state.is_abandoned then
         decors = decors_from_ground_abandoned[ground_top] or {}
      else
         decors = decors_from_ground[ground_top] or {}
      end
      if not state.decors_to_place then
         state.decors_to_place = {}
      end
      local full_hill = village.generate_hill(vmanip, vdata_spawn_chunk, {x=pos.x-6, y=pos.y-5, z=pos.z-6}, ground, ground_top, decors, state.decors_to_place)

      if full_hill then
         -- Extend the dirt below the hill, in case the hill is floating
         -- in mid-air
         local py = pos.y-6
         local dirtnodes = {}
         local vmin, vmax = vmanip:get_emerged_area()
         local varea = VoxelArea:new({MinEdge=vmin, MaxEdge=vmax})
         local c_ground = minetest.get_content_id(ground)
         for z=pos.z-6, pos.z+17 do
         for x=pos.x-6, pos.x+17 do
            village.get_column_nodes(vmanip, {x=x, y=py, z=z}, HILL_EXTEND_BELOW, dirtnodes)
            for d=1, #dirtnodes do
               local vindex = varea:index(dirtnodes[d].x, dirtnodes[d].y, dirtnodes[d].z)
               vdata_spawn_chunk[vindex] = c_ground
            end
         end
         end
      end
      vmanip:set_data(vdata_spawn_chunk)
   end

   if type(replace) == "number" then
      replace = village_replaces[replace]
   end
   local sreplace = table.copy(replace)
   if chunktype == "orchard" or chunktype == "orchard_ragged" then
      sreplace["rp_default:tree"] = nil
   end

   -- Select random variant (ruins or normal) for schematic name
   local schem_segment = chunktype
   if state.is_abandoned and pr:next(1, ABANDONED_RUINS_CHANCE) == 1 then
      schem_segment = get_ruined_chunktype(pr, chunktype, state.groundclass)
   else
      schem_segment = get_chunktype_variant(pr, chunktype, state.groundclass)
   end

   local schem_spec
   if village.chunkdefs[chunktype] and village.chunkdefs[chunktype].can_cache then
      -- Luanti's caching is allowed for this chunktype, so we call the schematic place function
      -- in the normal way (schematics are cached by Luanti if the schematic path is
      -- specified in the place function)
      schem_spec = modpath .. "/schematics/village_" .. schem_segment .. ".mts"
   else
      -- load schematic from table definition (read_schematic). This will force Luanti
      -- to skip its schematic cache and guarantee that node replacements are
      -- applied every time.
      -- However, this mod still caches the result of read_schematic itself to save
      -- a bit of time.
      local cached
      schem_spec, cached = read_cached_chunk_schematic(schem_segment)
   end
   local ok = minetest.place_schematic_on_vmanip(
      vmanip,
      pos,
      schem_spec,
      orient,
      sreplace,
      true
   )
   if not ok then
      minetest.log("warning", "[rp_village] Could not fully place village chunk in village at "..minetest.pos_to_string(pos, 0))
   end

   if not state.nodeupdates then
      state.nodeupdates = {}
   end
   table.insert(state.nodeupdates, {pos=pos, chunktype=chunktype})

   minetest.log("verbose", "[rp_village] Chunk generated at "..minetest.pos_to_string(pos))
   return true
end

function village.spawn_road(vmanip, pos, state, houses, built, roads, depth, pr, replace, dont_check_empty, dist_from_start, ground, ground_top)
   if not dont_check_empty and not check_empty(pos) then
      minetest.log("verbose", "[rp_village] Road not generated (too many stone/leaves/trees in the way) at "..minetest.pos_to_string(pos))
      return false
   end

   for i=1,4 do
      local nextpos = {x = pos.x, y = pos.y, z = pos.z}
      local orient = "random"

      local new_dist_from_start = vector.new(dist_from_start.x, dist_from_start.y, dist_from_start.z)
      if i == 1 then
	 orient = "0"
	 new_dist_from_start.z = new_dist_from_start.z - 1
	 nextpos.z = nextpos.z - 12
      elseif i == 2 then
	 orient = "90"
	 new_dist_from_start.x = new_dist_from_start.x - 1
	 nextpos.x = nextpos.x - 12
      elseif i == 3 then
	 orient = "180"
	 new_dist_from_start.z = new_dist_from_start.z + 1
	 nextpos.z = nextpos.z + 12
      else
	 orient = "270"
	 new_dist_from_start.x = new_dist_from_start.x + 1
	 nextpos.x = nextpos.x + 12
      end

      local hnp = minetest.hash_node_position(nextpos)

      local chunk_ok
      if built[hnp] == nil then
	 built[hnp] = true

         -- True is the next position is at or beyond the maximum village boundaries.
         -- This will ensure the village does not spread too far from the starting
         -- point.
         local is_at_village_border = math.abs(new_dist_from_start.x) >= village.max_village_spread or math.abs(new_dist_from_start.z) >= village.max_village_spread
         if is_at_village_border then
            minetest.log("verbose", "[rp_village] Border hit at "..minetest.pos_to_string(nextpos).." "..minetest.pos_to_string(new_dist_from_start))
         end

	 if depth <= 0 or is_at_village_border or pr:next(1, 8) < 6 then
	    houses[hnp] = {pos = nextpos, front = pos}

	    local structure = random_chunktype(pr, nil, state.groundclass)
	    chunk_ok = village.spawn_chunk(vmanip, nextpos, state, orient, replace, pr, structure, nil, nil, nil, ground, ground_top)
            if not chunk_ok then
               houses[hnp] = false
            end
	 else
	    roads[hnp] = {pos = nextpos}
	    chunk_ok = village.spawn_road(vmanip, nextpos, state, houses, built, roads, depth - 1, pr, replace, false, new_dist_from_start, ground, ground_top)
            if not chunk_ok then
               roads[hnp] = false
            end
	 end
      end
   end
   return true
end

-- Village modifiy functions: These are called after the VManip has placed
-- the village for further changes like setting metadata or tweak
-- nodes.
--
-- Parameters for all village_modify_* functions:
-- * upos, upos2: Lower and upper bounds of the village
-- * pr: PseudoRandom object used for randomness
-- * extras: Table with extra infos (function-specific, not always used)

-- Village modifier: Abandoned village. A complex modifier that
-- makes a village look like it was abandoned. It does these things:
-- * Turns all torches into dead torches
-- * Removes music players
-- * Makes grass overgrow on floor
-- * Randomly destroys farming plants, fences, glass, doors
-- * Generates seagrass and algae in water
--
-- The `extras` parameter must specify:
-- {
--    path = <itemname of path node>,
--    path_slab = <itemname of path node slab>,
--    ground_top = <itemname of top surface node outdoors (e.g. rp_default:dirt_with_grass>>,
-- }
local function village_modify_abandoned_village(upos, upos2, pr, extras)
      -- Replace all torches with dead torches
      util.nodefunc(
         upos, upos2,
	 {"rp_default:torch", "rp_default:torch_weak"},
         function(pos)
           local node = minetest.get_node(pos)
           minetest.set_node(pos, {name="rp_default:torch_dead", param2=node.param2})
         end, true)
      util.nodefunc(
         upos, upos2,
	 {"rp_default:torch_wall", "rp_default:torch_weak_wall"},
         function(pos)
           local node = minetest.get_node(pos)
           minetest.set_node(pos, {name="rp_default:torch_dead_wall", param2=node.param2})
         end, true)

      -- Remove all music players
      util.nodefunc(
         upos, upos2,
         "rp_music:player",
         function(pos)
           minetest.remove_node(pos)
         end, true)

      -- Remove 95% of farming plants
      util.nodefunc(
         upos, upos2,
	 "group:farming_plant",
         function(pos)
           if pr:next(1,100) <= 95 then
              -- 30% chance to replace with a decor (grass), if the ground type allows it
              if pr:next(1,10) <= 3 then
                 local below = vector.add(pos, vector.new(0,-1,0))
                 local belownode = minetest.get_node(below)
                 local decors = decors_from_ground_abandoned[belownode.name]
                 if decors then
                    local plant = decors[pr:next(1, #decors)]
                    minetest.set_node(pos, {name=plant})
                 else
                    minetest.remove_node(pos)
                 end
              else
                 minetest.remove_node(pos)
              end
           end
         end, true)

      -- Remove 80% of glass
      util.nodefunc(
         upos, upos2,
	 "group:glass",
         function(pos)
           if pr:next(1,5) >= 4 then
              minetest.remove_node(pos)
           end
         end, true)

      -- Replace 25% of path nodes
      util.nodefunc(
         upos, upos2,
	 {extras.path},
         function(pos)
           if pr:next(1,4) == 1 then
              minetest.set_node(pos, {name=extras.ground_top})
              local above = {x=pos.x,y=pos.y+1,z=pos.z}
              local abovenode = minetest.get_node(above)
              if abovenode.name == "air" and pr:next(1,DECOR_CHANCE) == 1 then
                 local decors = decors_from_ground_abandoned[extras.ground_top]
		 if decors then
		    local decor = decors[pr:next(1, #decors)]
                    minetest.set_node(above, {name=decor})
                 end
              end
           end
         end, true)
      -- Remove 25% of path slab nodes
      util.nodefunc(
         upos, upos2,
	 {extras.path_slab},
         function(pos)
           if pr:next(1,4) == 1 then
              minetest.remove_node(pos)
	      local below = vector.add(pos, vector.new(0,-1,0))
	      if minetest.get_node(below).name == "rp_default:dirt" then
                 if pr:next(1,3) == 1 then
                    minetest.set_node(below, {name=extras.path})
                 else
                    minetest.set_node(below, {name=extras.ground_top})
                 end
              end
           end
         end, true)

      -- Replace 25% of brick/cobble floor with ground
      util.nodefunc(
         upos, upos2,
	 {"rp_default:cobble", "rp_default:brick"},
         function(pos)
           if pr:next(1,4) == 1 then
	      local below = vector.add(pos, vector.new(0,-1,0))
	      local above = vector.add(pos, vector.new(0,1,0))
	      local nbelow = minetest.get_node(below)
	      local nabove = minetest.get_node(above)
	      if nabove.name == "air" and (nbelow.name == "rp_default:dirt" or nbelow.name == "rp_default:stone") then
                 minetest.set_node(pos, {name=extras.ground_top})
                 local plant = pr:next(1,5)
                 if plant == 1 then
                    minetest.set_node(above, {name="rp_default:grass"})
                 end
              end
           end
         end, true)

      -- Remove 50% of doors
      util.nodefunc(
         upos, upos2,
	 "group:door",
         function(pos)
           if pr:next(1,2) == 1 then
              local posup = vector.add(pos, vector.new(0,1,0))
              local posdn = vector.add(pos, vector.new(0,-1,0))

              local nup = minetest.get_node(posup)
              local ndn = minetest.get_node(posdn)
              if minetest.get_item_group(ndn.name, "door") == 1 then
                 return
              end
              minetest.remove_node(pos)
              if minetest.get_item_group(nup.name, "door") == 1 then
                 minetest.remove_node(posup)
              end
           end
         end, true)

      -- Remove 10% of fences
      util.nodefunc(
         upos, upos2,
	 "group:fence",
         function(pos)
            if pr:next(1,10) == 1 then
               local posup = vector.add(pos, vector.new(0,1,0))
               local posdn = vector.add(pos, vector.new(0,-1,0))
	       local nup = minetest.get_node(posup)
	       local ndn = minetest.get_node(posdn)
               -- make sure only fences on floor and below air are removed so we don't
               -- leave floating fences behind
	       if nup.name == "air" and minetest.get_item_group(ndn.name, "group:fence") == 0 then
                  minetest.remove_node(pos)
               end
            end
         end, true)

      -- Place seagrass or alga underwater
      util.nodefunc(
         upos, upos2,
         {"rp_default:water_source", "rp_default:swamp_water_source"},
         function(pos)
            if pr:next(1,2) == 1 then
               local posdn = vector.add(pos, vector.new(0,-1,0))
               local posup = vector.add(pos, vector.new(0,1,0))
               local ndn = minetest.get_node(posdn)
               local nup = minetest.get_node(posup)
               -- Alga may replaces seagrass if water is at least 2 nodes deep and if we're VERY lucky
               local alga = pr:next(1,100) == 1 and minetest.get_item_group(nup.name, "water") ~= 0
               local plant, p2
               if alga then
                  plant = "alga"
                  p2 = 16
               else
                  plant = "seagrass"
                  p2 = 0
               end
               if ndn.name == "rp_default:dirt" or ndn.name == "rp_default:dirt_with_grass" or ndn.name == "rp_default:dirt_with_dry_grass" then
                  minetest.set_node(posdn, {name="rp_default:"..plant.."_on_dirt", param2=p2})
               elseif ndn.name == "rp_default:swamp_dirt" or ndn.name == "rp_default:dirt_with_swamp_grass" then
                  minetest.set_node(posdn, {name="rp_default:"..plant.."_on_swamp_dirt", param2=p2})
               end
            end
      end, true)
end

-- Village modifier: Fills containers with goodies
local function village_modify_populate_containers(upos, upos2, pr, extras)
      -- Populate chests
      -- TODO: Damaged tools in abandoned villages
      util.nodefunc(
         upos, upos2,
         {"rp_default:chest", "rp_locks:chest"},
         function(pos)
            goodies.fill(pos, extras.chunktype, pr, "main", 3)
         end, true)

      -- Populate bookshelves
      util.nodefunc(
         upos, upos2,
         {"rp_default:bookshelf"},
         function(pos)
            goodies.fill(pos, "BOOKSHELF", pr, "main", 1)
         end, true)

      -- Populate furnaces
      if extras.chunktype == "forge" or extras.chunktype == "bakery" then
         local g_src, g_fuel, g_dst
         if extras.chunktype == "bakery" then
            g_src = "FURNACE_SRC_bakery"
            g_fuel = "FURNACE_FUEL_bakery"
            g_dst = "FURNACE_DST_bakery"
         else
            g_src = "FURNACE_SRC_general"
            g_fuel = "FURNACE_FUEL_general"
            g_dst = "FURNACE_DST_general"
         end
         util.nodefunc(
            upos, upos2,
            "rp_default:furnace",
            function(pos)
               goodies.fill(pos, g_src, pr, "src", 1)
               goodies.fill(pos, g_fuel, pr, "fuel", 1)
               goodies.fill(pos, g_dst, pr, "dst", 1)
               -- If both the src and fuel slots have an item,
               -- simulate the cooking process.
               -- We convert the src item into its cooked version,,,,
               -- put it into dst and reduce the fuel itemstack by 1.
               -- This prevents the furnace from going into
               -- active state when the village generates.
               local inv = minetest.get_meta(pos):get_inventory()
               local src = inv:get_stack("src", 1)
               local fuel = inv:get_stack("fuel", 1)
               if not src:is_empty() and not fuel:is_empty() then
                  local output = minetest.get_craft_result({method="cooking", items={src:get_name()}, width=1})
                  if output and not output.item:is_empty() then
                     local cooked = output.item
                     cooked:set_count(src:get_count()*cooked:get_count())
                     if cooked:get_count() > cooked:get_stack_max() then
                        cooked:set_count(cooked:set_stack_max())
                     end
                     inv:set_stack("src", 1, "")
                     inv:add_item("dst", cooked)
                     fuel:set_count(fuel:get_count()-1)
                     inv:set_stack("fuel", 1, fuel)
                  end
               end
            end, true)
      end
end

-- Village modifier: Limit number of music players in village to 1.
-- Also set random color for the remaning music player.
local function village_modify_limit_music_players(upos, upos2, pr)
      -- Maximum of 1 music player per village; remove excess music players
      local music_players = 0
      util.nodefunc(
         upos, upos2,
         "rp_music:player",
         function(pos)
           if music_players >= 1 or pr:next(1,8) > 1 then
              minetest.remove_node(pos)
           else
              music_players = music_players + 1

              -- Also initialize music box with random color
              local color = math.random(1, rp_paint.COLOR_COUNT)
              minetest.swap_node(pos, {name="rp_music:player", param2 = color-1})
              local meta = minetest.get_meta(pos)
              meta:set_int("music_player_legacy_color", 1)
           end
         end, true)
end

-- Village modifier: Random bed color
local function village_modify_bed_colors(upos, upos2, pr)
      if not mod_paint then
         return
      end
      util.nodefunc(
         upos, upos2,
         "rp_bed:bed_foot",
         function(pos)
             local node = minetest.get_node(pos)
             local dir = minetest.fourdir_to_dir(node.param2)
             local param2 = node.param2 % 4 + math.random(0, rp_paint.COLOR_COUNT-1)*4
             node.param2 = param2
             minetest.swap_node(pos, node)

             local pos2 = vector.add(pos, dir)
             local node2 = minetest.get_node(pos2)
             node2.param2 = param2
             if node2.name == "rp_bed:bed_head" then
                 minetest.swap_node(pos2, node2)
             end
         end, true)
end

-- Village modifier: Randomly turn some chests into locked chests
local function village_modify_lock_chests(upos, upos2, pr)
      -- Replace 25% of chests with locked chests
      if mod_locks then
         util.nodefunc(
            upos, upos2,
            "rp_default:chest",
            function(pos)
               if pr:next(1,4) == 1 then
                  local node = minetest.get_node(pos)
                  node.name = "rp_locks:chest"
                  minetest.swap_node(pos, node)
               end
            end, true)
      end
end

-- Village modifier: Inizialize doors
local function village_modify_init_doors(upos, upos2, pr)
     util.nodefunc(
          upos, upos2,
          "group:door",
          function(pos)
             -- The `is_open` parameter is false because we assume all
             -- doors in the village chunks are closed
             door.init_segment(pos, false)
          end, true)
end

local function after_village_area_emerged(blockpos, action, calls_remaining, params)
   local done = action == minetest.EMERGE_GENERATED or action == minetest.EMERGE_FROM_DISK or action == minetest.EMERGE_FROM_MEMORY
   if not done or calls_remaining > 0 then
      return
   end
   local vmanip = VoxelManip(params.emin, params.emax)
   local vmin, vmax = vmanip:get_emerged_area()
   local varea = VoxelArea:new({MinEdge=vmin, MaxEdge=vmax})
   local pos = params.pos
   local poshash = minetest.hash_node_position(pos)
   local pr = params.pr
   local ground = params.ground
   local ground_top = params.ground_top
   local force_place_starter = params.force_place_starter
   local is_abandoned = params.is_abandoned == true
   local village_name = params.village_name

   minetest.log("info", "[rp_village] Village area emerged at startpos = "..minetest.pos_to_string(pos))

   local depth = pr:next(village.min_size, village.max_size)

   local houses = {}
   local built = {}
   local roads = {}
   local state = {}

   state.is_abandoned = is_abandoned
   state.groundclass = "grassland"
   if ground_top == "rp_default:dirt_with_swamp_grass" or ground_top == "rp_default:swamp_dirt" then
      state.groundclass = "swamp"
   elseif ground_top == "rp_default:dirt_with_dry_grass" then
      state.groundclass = "savanna"
   elseif ground_top == "rp_default:dry_dirt" then
      state.groundclass = "dry"
   end

   local spawnpos = pos

   -- Get village wood type for this village
   local vpr = PcgRandom(mapseed + poshash)
   local village_replace_id
   if state.groundclass == "swamp" then
      -- swamp village: always oak wood
      village_replace_id = VILLAGE_REPLACE_OAK
   else
      -- other villages: random
      village_replace_id = vpr:next(1,#village_replaces)
   end
   minetest.log("verbose", "[rp_village] village_replace_id="..village_replace_id)
   local replace = village_replaces[village_replace_id]
   local dirt_path = "rp_default:dirt_path"
   local dirt_path_slab = "rp_default:path_slab"

   -- For measuring the generation time
   local t1 = os.clock()

   built[poshash] = true

   -- Generate a road below the starting position. The road tries to grow in 4 directions
   -- growing either recursively more roads or buildings (where the road
   -- terminates)
   village.spawn_road(vmanip, pos, state, houses, built, roads, depth, pr, replace, true, vector.zero(), ground, ground_top)

   local function connects(pos, nextpos)
      local hnp = minetest.hash_node_position(nextpos)

      if houses[hnp] ~= nil and houses[hnp] ~= false then
	 if vector.equals(houses[hnp].front, pos) then
	    return true
	 end
      end

      if roads[hnp] ~= nil and roads[hnp] ~= false then
	 return true
      end

      if vector.equals(pos, nextpos) or vector.equals(nextpos, spawnpos) then
	 return true
      end
   end

   -- Add position of starter chunk to roads list to connect it properly with
   -- the road network.
   roads[poshash] = { pos = pos, is_starter = true }

   -- Connect dirt paths with other village tiles.
   -- The road schematic uses planks and cobble for each of the 4 cardinal
   -- directions and it will be replaced either with a dirt path or
   -- the ground.

   local c_path = minetest.get_content_id(dirt_path)
   local c_ground_top = minetest.get_content_id(ground_top)

   -- Generate road center tiles
   for _,road in pairs(roads) do
      -- No road center tile for starter chunk since we expect it to occupy the center
      if road ~= false and not road.is_starter then
         -- This only places the center of the road, the connections will be manually placed
         village.spawn_chunk(vmanip, road.pos, state, "0", {}, pr, "road", false, false, true, ground, ground_top)
      end
   end

   -- Iterate through the road tiles and determine where to place dirt path nodes and lamps

   -- Lamp positions
   local lamps = {}
   -- Store positions of nodes to replace, they will be set after the last village chunk
   -- was generated
   local road_bulk_set = {}

   for _,road in pairs(roads) do
   if road ~= false then
      local amt_connections = 0
      local all_nodes = {}
      for i = 1, 4 do
	 local nextpos = {x = road.pos.x, y = road.pos.y, z = road.pos.z}

	 if i == 1 then -- North (planks)
	    nextpos.z = nextpos.z + 12
	    if connects(road.pos, nextpos) then
               amt_connections = amt_connections + 1
               table.insert(road_bulk_set, {vector.add(road.pos, {x=4, y=0, z=8}), vector.add(road.pos, {x=7,y=0,z=11}), c_path})
	    end
	 elseif i == 2 then -- East (cobble)
	    nextpos.x = nextpos.x + 12
	    if connects(road.pos, nextpos) then
               amt_connections = amt_connections + 1
               table.insert(road_bulk_set, {vector.add(road.pos, {x=8, y=0, z=4}), vector.add(road.pos, {x=11, y=0, z=7}), c_path})
	    end
	 elseif i == 3 then -- South (oak planks)
	    nextpos.z = nextpos.z - 12
	    if connects(road.pos, nextpos) then
               amt_connections = amt_connections + 1
               table.insert(road_bulk_set, {vector.add(road.pos, {x=4, y=0, z=0}), vector.add(road.pos, {x=7, y=0, z=3}), c_path})
	    end
	 else
	    nextpos.x = nextpos.x - 12 -- West (birch planks)
	    if connects(road.pos, nextpos) then
               amt_connections = amt_connections + 1
               table.insert(road_bulk_set, {vector.add(road.pos, {x=0, y=0, z=4}), vector.add(road.pos, {x=3, y=0, z=7}), c_path})
	    end
	 end
      end


      if amt_connections >= 2 and not road.is_starter then
         table.insert(lamps, {x=road.pos.x, y=road.pos.y, z=road.pos.z})
      end
   end
   end

   -- Place lamp posts
   for l=1, #lamps do
      village.spawn_chunk(
         vmanip,
         lamps[l],
         state,
         "0",
         {},
         pr,
         "lamppost",
         true,
         true,
         true,
         ground,
         ground_top
         )
   end

   -- <<< FINAL VILLAGE CHUNK! >>>

   -- Check if this village has created any houses so far
   local has_house = false
   for k,v in pairs(houses) do
      if v ~= false then
         has_house = true
         break
      end
   end
   -- Place a building at the start position as the final step.
   -- Normally, this is the well.
   local chunk_ok
   if has_house then
      chunk_ok = village.spawn_chunk(vmanip, pos, state, "0", replace, pr, "well", true, nil, true, ground, ground_top)
   else
      -- Place a fallback building instead of the well if the village does not have any buildings yet.
      -- A nice side-effect of this is that this will create 'lonely huts'.
      local structure = random_chunktype(pr, village.chunktypes_start_fallback, state.groundclass)
      chunk_ok = village.spawn_chunk(vmanip, pos, state, "random", replace, pr, structure, true, nil, true, ground, ground_top)
      minetest.log("info", "[rp_village] Village generated with fallback building instead of well")
   end
   if not chunk_ok then
      minetest.log("warning", string.format("[rp_village] Failed to generated starter chunk at %s", minetest.pos_to_string(pos)))
   end

   -- <<< END OF VILLAGE CHUNK GENERATION >>>

   -- All village chunks have been generated!
   -- Now we apply changes to the VoxelManip data
   vmanip:get_data(vdata_main)

   local vdata_bulk_set_node = function(vdata, varea, minpos, maxpos, content_id)
      for z=minpos.z, maxpos.z do
      for y=minpos.y, maxpos.y do
      for x=minpos.x, maxpos.x do
         local vindex = varea:index(x, y, z)
         vdata[vindex] = content_id
      end
      end
      end
   end

   -- Apply the road node replacements that were calculated above
   for r=1, #road_bulk_set do
      local rdata = road_bulk_set[r]
      vdata_bulk_set_node(vdata_main, varea, rdata[1], rdata[2], rdata[3])
   end

   -- Generate ground decorations (like grass)
   for d=1, #state.decors_to_place do
      -- We just iterate through the positions we have collected earlier
      local decor_info = state.decors_to_place[d]
      -- Check if this position is still valid for the decor. Prevents placing decorations
      -- in non-air nodes and if the floor node has changed (e.g. dirt path).
      if vdata_main[decor_info.index_decor] == minetest.CONTENT_AIR and vdata_main[decor_info.index_floor] == decor_info.content_floor then
          vdata_main[decor_info.index_decor] = decor_info.content_decor
      end
   end

   vmanip:set_data(vdata_main)

   -- The main village generation is complete here
   vmanip:write_to_map()
   vmanip:update_liquids()

   -- <<< END OF VOXELMANIP CHANGES >>>

   -- Final step: set node metadata (stuff that cannot be done in VManip)
   -- and perform other manipulations
   if state.nodeupdates then
   for u=1, #state.nodeupdates do
      local chunktype = state.nodeupdates[u].chunktype
      local upos = state.nodeupdates[u].pos
      local upos2 = vector.add(upos, vector.new(VILLAGE_CHUNK_SIZE, VILLAGE_CHUNK_SIZE, VILLAGE_CHUNK_SIZE))

      -- Replace random chests with locked chests
      village_modify_lock_chests(upos, upos2, pr)

      -- Maximum of 1 music player per village
      village_modify_limit_music_players(upos, upos2, pr)

      -- Village modifier: Abandoned village
      if state.is_abandoned then
         village_modify_abandoned_village(upos, upos2, pr, {path=dirt_path, path_slab=dirt_path_slab, ground_top=ground_top})
      end

      -- Colorize beds
      village_modify_bed_colors(upos, upos2, pr)

      -- Force on_construct to be called on all nodes
      util.reconstruct(upos, upos2, pr)

      -- Initialize doors (required by rp_doors mod)
      village_modify_init_doors(upos, upos2, pr)

      -- Fill containers with goodies
      village_modify_populate_containers(upos, upos2, pr, {chunktype=chunktype})

      -- Handle entity spawner nodes.
      -- In abandoned villages, remove all spawners and don't spawn anything.
      -- Otherwise, randomly spawn an entity at each
      -- spawner (chance of 1:chunkdef.entity_chance), then
      -- remove the spawner nodes.
      local chunkdef = village.chunkdefs[chunktype]
      if chunkdef ~= nil then
         if chunkdef.entities ~= nil then
	    if state.is_abandoned or (chunkdef.entity_chance ~= nil and pr:next(1, chunkdef.entity_chance) == 1) then
               -- Remove entity spawners
	       util.nodefunc(
	          upos, upos2,
	          "rp_village:entity_spawner",
	          function(pos)
		     minetest.remove_node(pos)
                  end)
            else
               local ent_spawns = {}

               -- Collect entitiy spawners
               util.nodefunc(
                  upos, upos2,
                  "rp_village:entity_spawner",
                  function(pos)
                     table.insert(ent_spawns, pos)
                  end, true)

               -- Initialize entity spawners
	       if #ent_spawns > 0 then
	          for ent, amt in pairs(chunkdef.entities) do
                     local profession
                     if string.sub(ent, 1, 11) == "__villager_" then
                        profession = string.sub(ent, 12, -1)
                        ent = "rp_mobs_mobs:villager"
                     end
                     for j = 1, pr:next(1, amt) do
                        if #ent_spawns == 0 then
                           break
                        end
                        local spawn, index = util.choice_element(ent_spawns, pr)
                        if spawn ~= nil then
                           local meta = minetest.get_meta(spawn)
                           meta:set_string("entity", ent)
                           if profession then
                              meta:set_string("villager_profession", profession)
                           end
                           minetest.get_node_timer(spawn):start(1)
                           -- Prevent spawning on same tile
                           table.remove(ent_spawns, index)
                        end
                     end
                  end
               end
               -- Remove unused entity spawners
               for e=1, #ent_spawns do
                  minetest.remove_node(ent_spawns[e])
               end
            end
          end
       end
   end
   end

   minetest.log("action", string.format("[rp_village] Generated village '%s' at %s in %.2fms", village_name, minetest.pos_to_string(pos), (os.clock() - t1) * 1000))
   return true
end

function village.spawn_village(pos, pr, force_place_starter, ground, ground_top)
   if not ground then
      ground = "rp_default:dirt"
   end
   if not ground_top then
      ground_top = "rp_default:dirt_with_grass"
   end

   -- Before we begin, make sure there is enough space for the first chunk
   -- (unless force_place_starter is true)
   local empty = force_place_starter or check_empty(pos)
   if not empty then
      -- Oops! Not enough space. Village generation fails.
      minetest.log("action", "[rp_village] Village generation not done at "..minetest.pos_to_string(pos)..". Not enough space for the first village chunk")
      return false
   end

   -- Village generation can start!
   -- Set village init stuff
   local village_name = village.name.generate(pr, village.name.used)
   village.villages[village.get_id(village_name, pos)] = {
      name = village_name,
      pos = pos,
   }
   village.save_villages()
   village.load_waypoints()

   local spread = VILLAGE_CHUNK_SIZE * village.max_village_spread
   local vspread = vector.new(spread, spread, spread)
   local emerge_min = vector.add(pos, vector.new(-spread, -(HILL_H + HILL_EXTEND_BELOW + 1), -spread))
   local emerge_max = vector.add(pos, vector.new(spread, VILLAGE_CHUNK_HEIGHT, spread))
   -- chance for village to be abandoned
   local is_abandoned = pr:next(1,ABANDONED_CHANCE) == 1
   minetest.emerge_area(emerge_min, emerge_max, after_village_area_emerged, {
      pos=pos,
      pr=pr,
      force_place_starter=force_place_starter,
      ground=ground,ground_top=ground_top,
      village_name=village_name,
      emin=emerge_min,
      emax=emerge_max,
      is_abandoned=is_abandoned})
   return true
end

minetest.register_on_mods_loaded(village.load_villages)
