Support_MapGeneration/terrain.lua

-- Terrain generation code
-- Used by maps

if not exists("Support_MapGeneration_Loaded") then
	require("util")
	dofile("add-ons/_misc/createbrick.lua")
	pngImage = require("png")
	require("colormatch")
	
	Support_MapGeneration_Loaded = true
end

-- modter brick names
local modterHeightName = {
	[2] = " Steep",
	[1] = "",
	[0.5] = " 1/2h",
	[0.75] = " 3/4h",
	[0.25] = " 1/4h",
}
local modterTypes = {
	["Cube"] = true, ["Wedge"] = true, ["CornerA"] = true, ["CornerB"] = true, ["Ramp"] = true, ["Crest"] = true, ["Corner Wedge"] = true, ["Corner Wedge L"] = true, ["Corner Wedge R" ] = true,
}
local modterTypesNoInv = {
	["Cube"] = true, ["Wedge"] = true,
}
local function modterUiNameFromSize(type, width, height)
	local ext = modterHeightName[height] or error("invalid modter cube height "..height)
	local pre = ""
	if type=="Cube" and ext=="" and width>4 then ext = " " end
	if type=="Cube" and ext=="" and width==4 then pre = " " end
	if type:find("Inv") then
		type = type:gsub(" *Inv.?", "")
		assert(modterTypes[type] and not modterTypesNoInv[type], "Invalid modter inv type "..type)
		type = type:gsub("Corner", "Cor")
		return pre..width.."x "..type..ext.." Inv."
	else
		assert(modterTypes[type], "Invalid modter type "..type)
		return pre..width.."x "..type..ext
	end
end
-- physical bricks
local function getBrickString(brick)
	return table.concat( {
		brick.uiName,
		brick.pos.x, brick.pos.y, brick.pos.z,
		brick.angleId,
	}, "_").."|"
end
local function deleteBrick(brick)
	if ts.isObject(brick.id) then
		ts.callobj(brick.id, "delete")
	end
	brick.id = nil
end
local function makeBrick(brick)
	local id = createbrick(brick.uiName, brick.pos, brick.angleId, brick.color, true)
	if id and ts.isObject(id) then
		brick.id = id
		if brick.printName then
			setbrickprint(id, brick.printName)
		end
	else
		print("failed to create terrain brick at "..tostring(brick.pos)..": " ..brick.uiName)
	end
end
local function syncBricks(old, new)
	--assert(old.uiName == new.uiName, "attempt to sync bricks with different uiName")
	--assert(old.pos == new.pos, "attempt to sync bricks with different position: "..getBrickString(old)..", "..getBrickString(new))
	--assert(old.angleId == new.angleId, "attempt to sync bricks with different angleId")
	assert(getBrickString(old)==getBrickString(new), "attempt to sync bricks with different info: "..getBrickString(old)..", "..getBrickString(new))
	local id = old.id
	new.id = id
	if old.color ~= new.color then
		ts.callobj(id, "setColor", new.color)
	end
	if old.printName ~= new.printName and new.printName then
		setbrickprint(id, new.printName)
	end
end
-- virtual bricks
local function realPosFromGridPos(x, y, z, mapLowerPos, cubeWidth, cubeHeight, notCube)
	local cubeWidthTU = cubeWidth/2
	local cubeSize = vector{cubeWidthTU, cubeWidthTU, cubeWidthTU*cubeHeight}
	local brickBottomCenterOffset = vector{cubeWidthTU/2, cubeWidthTU/2, 0}
	local brickPos = mapLowerPos + vector{x-1, y-1, z}*cubeSize + brickBottomCenterOffset
	if notCube then brickPos = brickPos + vector{0, 0, cubeWidth*cubeHeight/4 - 0.1} end
	return brickPos
end
local function addBrick(ter, uiName, brickPos, angleId, color, printName)
	local brick = {
		uiName = uiName,
		pos = brickPos,
		angleId = angleId,
		color = color,
		printName = printName,
	}
	ter[getBrickString(brick)] = brick
end
-- map translation - columns
local function addColumnStep(step, brickType, angleId, ter, mapLowerPos, x, y, h1, h2, cubeWidth, cubeHeight, color, printName)
	if cubeHeight <= 2/step then
		while h2-h1 >= step do
			local brickPos = realPosFromGridPos(x, y, h1, mapLowerPos, cubeWidth, cubeHeight)
			local uiName = modterUiNameFromSize(brickType, cubeWidth, cubeHeight*step)
			addBrick(ter, uiName, brickPos, angleId, color, printName)
			h1 = h1 + step
		end
	end
	return h1
end
local function addColumn(brickType, angleId, ter, mapLowerPos, x, y, h1, h2, cubeWidth, cubeHeight, color, printName)
	if h2>0 then
		h1 = h1-1
		if h1<0 then h1 = 0 end
		if cubeHeight==0.5 then
		if cubeWidth<64 then
		h1 = addColumnStep(8, brickType, angleId, ter, mapLowerPos, x, y, h1, h2, cubeWidth, cubeHeight, color, printName) end -- because no 64x cube steep
		h1 = addColumnStep(4, brickType, angleId, ter, mapLowerPos, x, y, h1, h2, cubeWidth, cubeHeight, color, printName) end
		if cubeHeight==0.25 then
		h1 = addColumnStep(3, brickType, angleId, ter, mapLowerPos, x, y, h1, h2, cubeWidth, cubeHeight, color, printName) end -- for 0.75x
		h1 = addColumnStep(2, brickType, angleId, ter, mapLowerPos, x, y, h1, h2, cubeWidth, cubeHeight, color, printName) 
		h1 = addColumnStep(1, brickType, angleId, ter, mapLowerPos, x, y, h1, h2, cubeWidth, cubeHeight, color, printName)
		
	end
end
-- map translation - cube marching
local function getHeightMapBox3(box, getHeight)
	local heightMap = {}
	local minZ, maxZ = 1000, 0
	for x = box[1]-2, box[3]+2 do
		heightMap[x] = {}
		for y = box[2]-2, box[4]+2 do
			local z = getHeight(x, y)
			heightMap[x][y] = z
			if z > maxZ then maxZ = z end
			if z < minZ then minZ = z end
		end
	end
	local box3 = {box[1]-1, box[2]-1, math.floor(minZ)-2, box[3]+1, box[4]+1, math.ceil(maxZ)+1}
	box3 = map(box3, math.round)
	return heightMap, box3
end
local function getCornerStr(corners)
	return table.concat(map(corners, function(x) return x and "1" or "0" end))
end
local function getCornerFromStr(cstr)
	local t = {}
	for i = 1, #cstr do
		local c = cstr:sub(i, i)
		table.insert(t, c=="1")
	end
	return t
end
local cornerBricksInit = { -- uiName, angleId, coverageStr -X +X -Y +Y -Z +Z at given angle ID
	["11111111"] = {"Cube"          , 0, "111111"},
	["10101111"] = {"Ramp"          , 0, "010010"},
	["00111111"] = {"Wedge"         , 0, "010110"},
	["10111111"] = {"CornerB"       , 0, "010110"},
	
	["00101011"] = {"CornerA"       , 0, "000000"},
	["10101011"] = {"CornerA"       , 0, "000000"},
	["00101111"] = {"CornerA"       , 0, "000000"},
	["00111011"] = {"CornerA"       , 0, "000000"},
	
	["10111110"] = {"Crest"         , 1, "000010"},
	["00111110"] = {"Corner Wedge"  , 1, "000000"},
	["10100011"] = {"Corner Wedge R", 0, "000000"},
	["10001011"] = {"Corner Wedge L", 1, "000000"},
	
	["00001010"] = true,
	["00100011"] = true,
	["00001011"] = true,
	["00000000"] = true,
	
	["00000010"] = true,
	["00101010"] = true,
	["10101010"] = true,
	["00000011"] = true,
	
	["00111100"] = true,
	["00001111"] = true,
	["10000010"] = true,
	["10000011"] = true,
}
local function reorderStr(str, order)
	assert(#str == #order, "reorderStr - lengths are different")
	local str2t = {}
	for i = 1, #str do
		local idx = tonumber(order:sub(i, i))
		str2t[idx] = str:sub(i, i)
	end
	local str2 = table.concat(str2t)
	assert(#str2 == #order)
	return str2
end
local cornerStrRotations = {
	"12345678",
	"34781256",
	"78563412",
	"56127834",
}
local cornerStrZFlip = "21436587"
function transformCornerStr(cstr, rot, inv)
	cstr = reorderStr(cstr, cornerStrRotations[rot+1] or error("transformCornerStr - invalid angle ID "..rot))
	if inv then cstr = reorderStr(cstr, cornerStrZFlip) end
	return cstr
end
local coverageStrRotations = {
	"123456",
	"431256",
	"214356",
	"342156",
}
local coverageStrZFlip = "123465"
local function transformCoverageStr(cstr, rot, inv)
	cstr = reorderStr(cstr, coverageStrRotations[rot+1] or error("transformCoverageStr - invalid angle ID "..rot))
	if inv then cstr = reorderStr(cstr, coverageStrZFlip) end
	return cstr
end
local function addCornerBrick(cornerBricks, cstr, brick, rot, inv)
	cstr = transformCornerStr(cstr, rot, inv)
	if type(brick)=="table" then
		local brickType = brick[1]
		local angleId = brick[2]
		local coverageStr = brick[3]
		if not cornerBricks[cstr] then
			cornerBricks[cstr] = {brickType..(inv and " Inv" or ""), (angleId+rot)%4, transformCoverageStr(coverageStr, rot, inv)}
		end
	else
		cornerBricks[cstr] = true
	end
end
local function makeCornerBrickTable()
	local cornerBricks = {}
	for cstr, brick in pairs(cornerBricksInit) do
		addCornerBrick(cornerBricks, cstr, brick, 0, false)
		addCornerBrick(cornerBricks, cstr, brick, 1, false)
		addCornerBrick(cornerBricks, cstr, brick, 2, false)
		addCornerBrick(cornerBricks, cstr, brick, 3, false)
		addCornerBrick(cornerBricks, cstr, brick, 0, true )
		addCornerBrick(cornerBricks, cstr, brick, 1, true )
		addCornerBrick(cornerBricks, cstr, brick, 2, true )
		addCornerBrick(cornerBricks, cstr, brick, 3, true )
	end
	return cornerBricks
end
local cornerBricks = makeCornerBrickTable()
function getBrickForCorners(corners)
	local cstr = getCornerStr(corners)
	local brick = cornerBricks[cstr]
	if brick then
		if type(brick) == "table" then
			return brick, cstr
		else
			return nil
		end
	else
		print("No brick for corner str "..cstr)
		return nil
	end
end
local function addBrickGrid(ter, box3, brickGrid, mapLowerPos, cubeWidth, cubeHeight, getColor, printName)
	local cubeWidthTU = cubeWidth/2
	local cubeSize = vector{cubeWidthTU, cubeWidthTU, cubeWidthTU*cubeHeight}
	local brickBottomCenterOffset = vector{cubeWidthTU/2, cubeWidthTU/2, 0}
	
	for x = box3[1]+1, box3[4]-1 do
		for y = box3[2]+1, box3[5]-1 do
			local color
			for z = box3[3]+1, box3[6]-1 do
				local brick = brickGrid[x][y][z]
				if brick then
					local brickType = brick[1]
					local angleId = brick[2]
					color = color or getColor(x, y)
					local uiName = modterUiNameFromSize(brickType, cubeWidth, cubeHeight)
					local brickPos = mapLowerPos + vector{x-1, y-1, z}*cubeSize + brickBottomCenterOffset
					addBrick(ter, uiName, brickPos, angleId, color, printName)
				end
			end
		end
	end
end
local adjacent2 = {
	vector{-0.5, -0.5}, vector{-0.5,  0.5},
	vector{ 0.5, -0.5}, vector{ 0.5,  0.5},
}
local function getCornerGridFromHeightMap(box3, heightMap)
	local cornerGrid = {}
	for x = box3[1]-0.5, box3[4]+0.5 do
		cornerGrid[x] = {}
		for y = box3[2]-0.5, box3[5]+0.5 do
			cornerGrid[x][y] = {}
			--local heightSum = 0
			--local heightMin = 1000
			--local heightMax = 0
			--local basepos = vector{x, y}
			--for _, adj in ipairs(adjacent2) do
			--	local pos = basepos + adj
			--	local height = heightMap[pos.x][pos.y]
			--	heightSum = heightSum + height
			--	if height < heightMin then heightMin = height end
			--	if height > heightMax then heightMax = height end
			--end
			--local heightAvg = heightSum/#adjacent2
			--local height = heightMax
			local height = heightMap[x-0.5][y-0.5]
			for z = box3[3]-0.5, box3[6]+0.5 do
				local ground = z <= height
				cornerGrid[x][y][z] = ground
			end
		end
	end
	return cornerGrid
end
local adjacent3 = {
	vector{-0.5, -0.5, -0.5}, vector{-0.5, -0.5,  0.5},
	vector{-0.5,  0.5, -0.5}, vector{-0.5,  0.5,  0.5},
	vector{ 0.5, -0.5, -0.5}, vector{ 0.5, -0.5,  0.5},
	vector{ 0.5,  0.5, -0.5}, vector{ 0.5,  0.5,  0.5},
}
local function getBrickGridFromCornerGrid(box3, cornerGrid)
	local brickGrid = {}
	for x = box3[1], box3[4] do
		brickGrid[x] = {}
		for y = box3[2], box3[5] do
			brickGrid[x][y] = {}
			for z = box3[6], box3[3], -1 do
				local basepos = vector{x, y, z}
				local corners = {}
				for i, adj in ipairs(adjacent3) do
					local pos = basepos + adj
					corners[i] = cornerGrid[pos.x][pos.y][pos.z]
					if corners[i]==nil then print("no corner at "..tostring(pos)) end
				end
				local brick, brickCStr = getBrickForCorners(corners)
				if brick then
					brickGrid[x][y][z] = brick
					local realCorners = getCornerFromStr(brickCStr)
					for i, adj in ipairs(adjacent3) do
						if not realCorners[i] then
							local pos = basepos + adj
							cornerGrid[pos.x][pos.y][pos.z] = false
						end
					end
				end
			end
		end
	end
	return brickGrid
end
local function addCornerVisBrick(ter, pos, colorId)
	addBrick(ter, "2x2x2f", pos, 0, colorId, nil)
end
local function addCornerGridVis(ter, box3, cornerGrid, mapLowerPos, cubeWidth, cubeHeight)
	for x = box3[1]-0.5, box3[4]+0.5 do
		for y = box3[2]-0.5, box3[5]+0.5 do
			for z = box3[3]-0.5, box3[6]+0.5 do
				local corner = cornerGrid[x][y][z]
				local pos = realPosFromGridPos(x, y, z, mapLowerPos, cubeWidth, cubeHeight, true)
				if corner then
					addCornerVisBrick(ter, pos, 5)
				else
					addCornerVisBrick(ter, pos, 32)
				end
			end
		end
	end
end
local adjacentFaces3 = {
	vector{-0.5,  0  ,  0  }, vector{ 0.5,  0  ,  0  },
	vector{ 0  , -0.5,  0  }, vector{ 0  ,  0.5,  0  },
	vector{ 0  ,  0  , -0.5}, vector{ 0  ,  0  ,  0.5},
}
local function getBrickCoverage(brick)
	local coverage = {}
	local cstr = brick[3] or error("brick has no coverage str: "..brick[1].." "..brick[2])
	for i, adj in ipairs(adjacentFaces3) do
		if cstr:sub(i, i)=="1" then
			table.insert(coverage, adj)
		end
	end
	return coverage
end
local function getCoverageGridAndRemoveCubes(box3, brickGrid)
	local coverGrid = {}
	for x = box3[1], box3[4] do
		for y = box3[2], box3[5] do
			for z = box3[3], box3[6] do
				local brick = brickGrid[x][y][z]
				if brick then
					if brick[1]=="Cube" then
						brickGrid[x][y][z] = nil
					end
					local coverage = getBrickCoverage(brick)
					local basePos = vector{x, y, z}
					for i, rel in ipairs(coverage) do
						local pos = basePos + rel
						coverGrid[pos.x] = coverGrid[pos.x] or {}
						coverGrid[pos.x][pos.y] = coverGrid[pos.x][pos.y] or {}
						coverGrid[pos.x][pos.y][pos.z] = (coverGrid[pos.x][pos.y][pos.z] or 0) + 1
					end
				end
			end
		end
	end
	return coverGrid
end
local function brickShouldBeCoverageCube(coverGrid, x, y, z)
	local ucf = 0
	local hasAir = false
	local basePos = vector{x, y, z}
	for i, adj in ipairs(adjacentFaces3) do
		local pos = basePos + adj
		local cov = coverGrid[pos.x] and coverGrid[pos.x][pos.y] and coverGrid[pos.x][pos.y][pos.z]
		if cov and cov==1 then
			ucf = ucf + 1
		end
		if (not cov) or cov==0 then
			hasAir = true
		end
	end
	return ucf>0 and not hasAir
end
local function addCoverageCubesToBrickGrid(ter, box3, coverGrid, brickGrid)
	for x = box3[1]+1, box3[4]-1 do
		for y = box3[2]+1, box3[5]-1 do
			for z = box3[3]+1, box3[6]-1 do
				local brick = brickGrid[x][y][z]
				if not brick then
					if brickShouldBeCoverageCube(coverGrid, x, y, z) then
						brickGrid[x][y][z] = {"Cube", 0, "111111"}
					end
				end
			end
		end
	end
end
local function addCoverageGridVis(ter, box3, coverGrid, mapLowerPos, cubeWidth, cubeHeight)
	print(box3)
	for x = box3[1]-0.5, box3[4]+0.5, 0.5 do
		for y = box3[2]-0.5, box3[5]+0.5, 0.5 do
			for z = box3[3]-0.5, box3[6]+0.5, 0.5 do
				if coverGrid[x] and coverGrid[x][y] and coverGrid[x][y][z] then
					local cov = coverGrid[x][y][z]
					local pos = realPosFromGridPos(x, y, z, mapLowerPos, cubeWidth, cubeHeight, true)
					addCornerVisBrick(ter, pos, cov)
				end
			end
		end
	end
end
local function addOptimizedColumns(ter, box3, brickGrid, mapLowerPos, cubeWidth, cubeHeight, getColor, printName)
	for x = box3[1]+1, box3[4]-1 do
		for y = box3[2]+1, box3[5]-1 do
			local color
			local firstType = nil
			local firstAngleId = nil
			local numOn = 0
			for z = box3[3], box3[6] do
				local brick = brickGrid[x][y][z]
				if brick and brick[1]==firstType and brick[2]==firstAngleId then
					numOn = numOn + 1
					brickGrid[x][y][z] = nil
				else
					if numOn>0 then
						assert(firstType and firstAngleId)
						local h1, h2 = z-numOn+1, z
						color = color or getColor(x, y)
						addColumn(firstType, firstAngleId, ter, mapLowerPos, x, y, h1, h2, cubeWidth, cubeHeight, color, printName)
					end
					if brick and (brick[1]=="Cube" or brick[1]=="Wedge") then
						firstType = brick[1]; firstAngleId = brick[2]; numOn = 1;
						brickGrid[x][y][z] = nil
					else
						firstType = nil; firstAngleId = nil; numOn = 0;
					end
				end
			end
		end
	end
end
function GenerateTerrain(mapLowerPos, box, cubeWidth, cubeHeight, getHeight, getColor, printName)
	local ter = {} -- map of brick string -> brick id
	
	local heightMap, box3 = getHeightMapBox3(box, getHeight)
	local cornerGrid = getCornerGridFromHeightMap(box3, heightMap)
	local brickGrid = getBrickGridFromCornerGrid(box3, cornerGrid)
	local coverGrid = getCoverageGridAndRemoveCubes(box3, brickGrid)
	addCoverageCubesToBrickGrid(ter, box3, coverGrid, brickGrid)
	
	addOptimizedColumns(ter, box3, brickGrid, mapLowerPos, cubeWidth, cubeHeight, getColor, printName)
	addBrickGrid(ter, box3, brickGrid, mapLowerPos, cubeWidth, cubeHeight, getColor, printName)
	
	--addCornerGridVis(ter, box3, cornerGrid, mapLowerPos, cubeWidth, cubeHeight)
	--addCoverageGridVis(ter, box3, coverGrid, mapLowerPos, cubeWidth, cubeHeight)
	
	return ter
end
-- interface to GenerateTerrain
function DeleteTerrain(ter)
	for brickString, brick in pairs(ter) do
		deleteBrick(brick)
	end
end
function BuildTerrain(ter)
	for brickString, brick in pairs(ter) do
		makeBrick(brick)
	end
end
local function replaceTerrain2(old, new)
	for brickString, brick in pairs(new) do
		if (not old[brickString]) then
			makeBrick(brick)
		elseif (not old[brickString].id) then
			makeBrick(brick)
		elseif (not ts.isObject(old[brickString].id)) then
			makeBrick(brick)
		else
			syncBricks(old[brickString], brick)
		end
	end
end
function ReplaceTerrain(old, new)
	for brickString, brick in pairs(old) do
		if (not new[brickString]) then
			deleteBrick(brick)
		end
	end
	schedule(1000, replaceTerrain2, old, new)
end

local function getTestMap()
	local heightScale = 0.3
	local hmimg = pngImage("add-ons/support_mapgeneration/heightmap.png")
	local box = {1+2, 1+2, hmimg.width-2, hmimg.height-2}
	--local box = {1+2, 1+2, 3+4, 3+4}
	local heightMap = {}
	local colorMap = {}
	for x = box[1]-2, box[3]+2 do
		heightMap[x] = {}
		colorMap[x] = {}
		for y = box[2]-2, box[4]+2 do
			--heightMap[x][y] = (math.sin(x/2+2)+1 + math.sin(y)*1)*1 + 5
			local pix = hmimg.pixels[x][y].R * heightScale
			heightMap[x][y] = pix
			colorMap[x][y] = 5
		end
	end
	return box, heightMap, colorMap
end
function TestGenerateTerrain()
	local box, heightMap, colorMap = getTestMap()
	local printName = "modter/bricktop"
	
	local function getHeight(x, y) return heightMap[x][y] end
	local function getColor (x, y) return colorMap [x][y] end
	local ter = GenerateTerrain(vector{0, 0, 0}, box, 16, 0.5, getHeight, getColor, printName)
	
	if exists("TestTerrain") then
		ReplaceTerrain(TestTerrain, ter)
	else
		BuildTerrain(ter)
	end
	TestTerrain = ter
end
--TestGenerateTerrain()