local np_distort_x = mapgen_rivers.noise_params.distort_x
local np_distort_z = mapgen_rivers.noise_params.distort_z
local np_distort_amplitude = mapgen_rivers.noise_params.distort_amplitude

local nobj_distort_x, nobj_distort_z, nobj_distort_amplitude

local sea_level = mapgen_rivers.settings.sea_level
local distort = mapgen_rivers.settings.distort

-- Linear interpolation
local function interp(v00, v01, v11, v10, xf, zf)
	local v0 = v01*xf + v00*(1-xf)
	local v1 = v11*xf + v10*(1-xf)
	return v1*zf + v0*(1-zf)
end

local function estimate_spawn_level(pos, use_distort)
	local x, z = pos.x, pos.z
	if distort and use_distort then
		nobj_distort_x = nobj_distort_x or minetest.get_perlin(np_distort_x)
		nobj_distort_z = nobj_distort_z or minetest.get_perlin(np_distort_z)
		nobj_distort_amplitude = nobj_distort_amplitude or minetest.get_perlin(np_distort_amplitude)

		local amplitude = nobj_distort_amplitude:get_2d({x=pos.x, y=pos.z})
		x = x + nobj_distort_x:get_3d(pos)*amplitude
		z = z + nobj_distort_z:get_3d(pos)*amplitude
	end

	local terrain, lakes = mapgen_rivers.make_heightmaps(
		{x=math.floor(x),   z=math.floor(z)  },
		{x=math.floor(x)+1, z=math.floor(z)+1}
	)

	local ex, ez = x % 1, z % 1
	--local h = terrain[1]*(1-ex)*(1-ez) + terrain[2]*ex*(1-ez) + terrain[3]*(1-ex)*ez + terrain[4]*ex*ez
	local h = interp(terrain[1], terrain[2], terrain[4], terrain[3], ex, ez)
	local lake = math.min(lakes[1], lakes[2], lakes[3], lakes[4])

	if h < lake or h <= sea_level then
		return false, h
	end

	return true, h
end

local function get_spawn_level(x, z)
	local pos = {x=x, z=z}
	local suitable, y = estimate_spawn_level(pos, false)
	if not suitable then
		return
	end

	if not distort then
		return math.floor(y) + 1
	end

	local low_bound = -math.huge
	local high_bound = math.huge
	local suitable_high = false

	repeat
		pos.y = math.max(math.min(math.floor(y+0.5), high_bound-1), low_bound+1)
		suitable, y = estimate_spawn_level(pos, true)
		if y > pos.y then
			low_bound = pos.y
		else
			high_bound = pos.y
			suitable_high = suitable
		end
	until high_bound - low_bound <= 1

	if not suitable_high then
		return
	end

	return high_bound + 1
end
minetest.get_spawn_level = get_spawn_level

local rmax = 2000
local function find_spawn_point(seed)
	local level = get_spawn_level(0, 0)
	if level then
		return {x=0, y=level, z=0}
	end

	local pr = PcgRandom(seed or os.time())
	local incr = 16
	local r0 = 0

	while r0 < rmax do
		local r1 = r0 + incr
		local r = pr:next(r0*r0+1, r1*r1) ^ 0.5
		local a = pr:next() / 2147483648 * math.pi

		local x = math.floor(math.cos(a) * r + 0.5)
		local z = math.floor(math.sin(a) * r + 0.5)

		level = get_spawn_level(x, z)
		if level then
			return {x=x, y=level, z=z}
		end
		r0 = r1
	end
end

local function spawn_player(player)
	if minetest.settings:get("static_spawnpoint") then
		return
	end

	local spawn_point = find_spawn_point()
	if spawn_point then
		player:set_pos(spawn_point)
	end
end

minetest.register_on_newplayer(spawn_player)
minetest.register_on_respawnplayer(spawn_player)