init_105_LIB_FSTile.lua

local ft = {}
ft.__index = ft

function FSTile(w, h)
	local self = {}
	setmetatable(self, ft)
	-- init stuff here
	self.containers = {}
	self.width = w
	self.height = h
	return self
end

-- cb_func(w, h, fs) -> fits? true/false
function ft:add_container(x, y, w, h, cb_func, data)
	-- Change to min/max table
	w = type(w) == "table" and w or { w, w }
	h = type(h) == "table" and h or { h, h }
	assert(w[1] >= 1 and w[2] >= 1)
	assert(w[1] <= w[2])
	assert(h[1] >= 1 and h[2] >= 1)
	assert(h[1] <= h[2])
	assert(type(cb_func) == "string" or type(cb_func) == "function")
	data = data or {}

	-- Append
	self.containers[#self.containers + 1] = {
		pos_x = x, pos_y = y, -- Desired position
		lim_x = w, lim_y = h, -- Width/height limits
		callback = cb_func,
		data = data,
		hidden = true -- Yet no intersections
	}
end

function ft:_render_preprocess()
	for i, c in ipairs(self.containers) do
		-- Start with minimal size
		c.dim_x = c.lim_x[1]
		c.dim_y = c.lim_y[1]

		-- Keep in bounds
		c.pos_x = math.min(c.pos_x, self.width - c.dim_x)
		c.pos_y = math.min(c.pos_y, self.width - c.dim_y)
		c.pos_x = math.max(c.pos_x, 0)
		c.pos_y = math.max(c.pos_y, 0)
	end

	-- Start from top left
	local function get_distance_sq(c)
		local x = c.pos_x + c.dim_x / 2
		local y = c.pos_y + c.dim_y / 2
		return (x * x + y * y) - c.dim_x * c.dim_y
	end

	table.sort(self.containers, function(a, b)
		return get_distance_sq(a) < get_distance_sq(b)
	end)
end

local function logme(what, c)
	print(what .. "\t " .. c.data[1] .. ": " .. c.pos_x .. ", " .. c.pos_y ..
		"; " .. c.dim_x .. ", " .. c.dim_y)
end

function ft:_render_make_formspec()
	-- Container for formspec elements
	local fs = {}

	for _, c in ipairs(self.containers) do
		local start_i = #fs + 1
		fs[start_i] = ("container[%.1f,%.1f]"):format(c.pos_x, c.pos_y)

		local fits = true
		logme("plot", c)

		if type(c.callback) == "function" then
			fits = c.callback(c.dim_x, c.dim_y, fs, c.data)
		else
			-- String for fixed-size containers
			fs[#fs + 1] = c.callback
		end
		if c.hidden then
			-- For debugging
			fs[#fs + 1] = "label[0,0;H]"
		end

		if fits then
			fs[#fs + 1] = "container_end[]"
		else
			local scrollbar_name = "scrollbar_TODO"
			fs[start_i] = ("scroll_container[%f,%f;%f,%f;%s;vertical]"):format(
				c.pos_x, c.pos_y, c.dim_x, c.dim_y, scrollbar_name)
			fs[#fs + 1] = "scroll_container_end[]"
			fs[#fs + 1] = ("scrollbar[%f,%f;%f,%f;vertical;%s;]"):format(
				c.pos_x + c.dim_x, c.pos_y, 0.1, c.dim_y, scrollbar_name)
		end
	end

	return table.concat(fs, '\n')
end

-- Intersection box calculation
function ft:_get_intersection(a, b)
	if a == b or a.hidden or b.hidden then
		return
	end

	if		a.pos_x < b.pos_x + b.dim_x and
			a.pos_y < b.pos_y + b.dim_y and
			a.pos_x + a.dim_x > b.pos_x and
			a.pos_y + a.dim_y > b.pos_y then
		-- Intersection!
			
		return { -- X-Coordinates (min, max)
			math.max(a.pos_x, b.pos_x),
			math.min(a.pos_x + a.dim_x, b.pos_x + b.dim_x)
		}, { -- Y-Coordinates (min, max)
			math.max(a.pos_y, b.pos_y),
			math.min(a.pos_y + a.dim_y, b.pos_y + b.dim_y)
		}
	end
end

function ft:_get_intersection_info(c)
	local x, y = 0, 0
	
	if c.pos_x < 0 then x = -1 end
	if c.pos_y < 0 then y = -1 end
	if c.pos_x + c.dim_x > self.width  then x = self.width  + 1 end
	if c.pos_y + c.dim_y > self.height then y = self.height + 1 end
	if x ~= 0 or y ~= 0 then
		-- Outer boundary collision, use some high value
		logme("outer collision", c)
		return x, y, 1000
	end

	local x, y, area = 0, 0, 0
	local cbox_x, cbox_y = {self.width, 0}, {self.height, 0}
	for _, c2 in ipairs(self.containers) do
		local ix, iy = self:_get_intersection(c, c2)
		if ix then

			local i_area = (ix[2] - ix[1]) * (iy[2] - iy[1])
			x = x + (ix[1] + ix[2]) / 2 * i_area
			y = y + (iy[1] + iy[2]) / 2 * i_area

			-- Sum up the total collision box area
			area = area + i_area

			-- Biggest bounding collision box
			cbox_x[1] = math.min(cbox_x[1], ix[1])
			cbox_x[2] = math.max(cbox_x[2], ix[2])
			cbox_y[1] = math.min(cbox_y[1], iy[1])
			cbox_y[2] = math.max(cbox_y[2], iy[2])
		end
	end
	if area == 0 then
		return
	end
	-- mass center (X, Y), area and maximal collision box bounds
	return x / area, y / area, area, cbox_x, cbox_y
end

-- Mass center of all visible (hidden = false) areas
function ft:_get_free_area(c_to_ignore)
	local area, x, y = 0, 0, 0

	for _, c in ipairs(self.containers) do
		if not c.hidden and c ~= c_to_ignore then
			local c_area = c.dim_x * c.dim_y
			x = x + (c.pos_x + c.dim_x / 2) * c_area
			y = y + (c.pos_y + c.dim_y / 2) * c_area
			area = area + c_area
		end
	end

	-- Default to bottom right
	if area == 0 then area = 1 end
	return self.width - x / area, self.height - y / area, area
end

function ft:render(iterations)
	iterations = iterations or 2

	self:_render_preprocess()

	for i = 1, iterations do
		local moved = false
		print("  ==> Iteration " .. i)
		for _, c in ipairs(self.containers) do
			-- Place, then move
			c.hidden = false
			local ix, iy, i_area, cbox_x, cbox_y = self:_get_intersection_info(c)
			if ix then
				local sx, sy, s_area = self:_get_free_area(c)
				print(("Free area: %.2f, %.2f"):format(sx, sy))
	
				-- Get movement direction
				local dx = sx - 2 * ix + (c.pos_x + c.dim_x / 2) --(sx + ix) / (s_area + i_area)
				local dy = sy - 2 * iy + (c.pos_y + c.dim_y / 2) --(sy + iy) / (s_area + i_area)
				local old_x, old_y = c.pos_x, c.pos_y
				local cx = cbox_x[2] - cbox_x[1]
				local cy = cbox_y[2] - cbox_y[1]

				if cy > cx then
					-- Move to free area in X
					c.pos_x = c.pos_x + math.sign(dx) * cx
					logme(" moveX " .. dx .. ";" .. cx, c)
				else
					-- Move to free area in Y
					c.pos_y = c.pos_y + math.sign(dy) * cy
					logme(" moveY " .. dy .. ";" .. cy, c)
				end
	
				local _, _, i_area2 = self:_get_intersection_info(c)
				if (i_area2 or 0) > i_area then
					c.pos_x, c.pos_y = old_x, old_y
				else
					moved = true
				end
			end
		end
		if not moved then
			break
		end
	end

	-- Enlarge if possible
	for _, c in ipairs(self.containers) do
		if not c.hidden and c.dim_x < c.lim_x[2] then
			-- Maximize X direction
			c.dim_x = c.lim_x[2]
			local _, _, _, cbox_x, cbox_y = self:_get_intersection_info(c)
			if cbox_x then
				logme("max X fail " .. (cbox_x[2] - cbox_x[1]) .. "x" .. (cbox_y[2] - cbox_y[1]), c)
				c.dim_x = math.max(c.lim_x[1], cbox_x[1] - c.pos_x)
			end
		end
		if not c.hidden and c.dim_y < c.lim_y[2] then
			-- Maximize Y direction
			c.dim_y = c.lim_y[2]
			local _, _, _, cbox_x, cbox_y = self:_get_intersection_info(c)
			if cbox_y then
				logme("max Y fail " .. (cbox_x[2] - cbox_x[1]) .. "x" .. (cbox_y[2] - cbox_y[1]), c)
				c.dim_y = math.max(c.lim_y[1], cbox_y[1] - c.pos_y)
			end
		end
	end

	return self:_render_make_formspec()
end

local function demo(iter)
	local colors = { "#F00", "#0FF", "#FAA","#0F0" }
	local function mk_box(w, h, fs, data)
		fs[#fs + 1] = "box[0.1,0.1;" .. w.. "," .. h..";" .. colors[data[1]] .."]"
		fs[#fs + 1] = "label[0.1,0.4;Box " .. data[1] .."]"
		return true
	end

	local tt = FSTile(12, 9)
	tt:add_container(0, 1,       5, {4, 8}, mk_box, { 1 })
	tt:add_container(3, 0,  {3, 7},      5, mk_box, { 2 })
	tt:add_container(0, 3, {8, 20},      1, mk_box, { 3 })
	tt:add_container(4, 4,  {3, 4}, {2, 3}, mk_box, { 4 })
	local fs = {
		"formspec_version[4]",
		"size[12,9]",
		tt:render(iter)
	}
	return fs
end
--print(table.concat(demo(10), '\n'))

minetest.register_chatcommand("a", {
	func = function(name, param)
		local fs = demo(tonumber(param))
		minetest.show_formspec(name, "baz", table.concat(fs, '\n'))
	end
})