Roblox Terrain Generator

terrain.lua

local Terrain = game.Workspace.Terrain


--==========================================================================================================--
--                                 Persistent noise generation code                                       ==--
--==========================================================================================================--
--
-- Generating perlin noise is the most expensive part of the terrain generation. It is also however, totally
-- predictable, so we can pre-generate most of the perlin noise that we will need before the main terrain
-- generation is done.
--
-- Unfortunately we need to store the width/length here, rather than with the main generation code, since
-- the noise pre-gen needs it, but it is unlikely that we will want to change it between rounds, so this
-- is a fair trade for the faster terrain generation. 
--
local WIDTH = 512
local LENGTH = 512

--frequncies that we will need in the code. These are the frequencies that the noise generator will
--try to cache a few copies of each.
local NoiseCacheHint = {14, 25, 28, 30, 40, 50, 60, 70, 80, 90, 100, 200}
local CachedNoise = {}
local NeedsCachingChange = Instance.new('BoolValue')
local NeedsCaching = {}
for i, lambda in pairs(NoiseCacheHint) do
	NeedsCaching[i] = lambda
end
--
local perm = {
	151,160,137,91,90,15,
	131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
	190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
	88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
	77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
	102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
	135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
	5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
	223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
	129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
	251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
	49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
	138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180,
	151,160,137,91,90,15,
	131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
	190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
	88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
	77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
	102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
	135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
	5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
	223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
	129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
	251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
	49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
	138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
}
local floor = math.floor
local function grad( hash, x, y )
    local h = hash%8;          -- Convert low 3 bits of hash code
    local u = h<4 and x or y;  -- into 8 simple gradient directions,
    local v = h<4 and y or x;  -- and compute the dot product with (x,y).
    return ((h%2==1) and -u or u) + ((floor(h/2)%2==1) and -2.0*v or 2.0*v);
end
local function PerlinNoise(x,y)
    local ix0, iy0, ix1, iy1;
    local fx0, fy0, fx1, fy1;
    local s, t, nx0, nx1, n0, n1;

    ix0 = floor(x); -- Integer part of x
    iy0 = floor(y); -- Integer part of y
    fx0 = x - ix0;        -- Fractional part of x
    fy0 = y - iy0;        -- Fractional part of y
    fx1 = fx0 - 1.0;
    fy1 = fy0 - 1.0;
    ix1 = (ix0 + 1) % 255;  -- Wrap to 0..255
    iy1 = (iy0 + 1) % 255;
    ix0 = ix0 % 255;
    iy0 = iy0 % 255;
    
	t=(fy0*fy0*fy0*(fy0*(fy0*6-15)+10));
	s=(fx0*fx0*fx0*(fx0*(fx0*6-15)+10));

    nx0 = grad(perm[ix0 + perm[iy0+1]+1], fx0, fy0);
    nx1 = grad(perm[ix0 + perm[iy1+1]+1], fx0, fy1);
    n0 = nx0 + t*(nx1-nx0);

    nx0 = grad(perm[ix1 + perm[iy0+1]+1], fx1, fy0);
    nx1 = grad(perm[ix1 + perm[iy1+1]+1], fx1, fy1);
    n1 = nx0 + t*(nx1-nx0);

    return 0.5*(1 + (0.507 * (n0 + s*(n1-n0))))
end
function PerlinNoiseMap(lambda)
	local cache = CachedNoise[lambda]
	if cache and #cache > 0 then
		local map = cache[#cache]
		cache[#cache] = nil
		--
		if #cache == 0 then
			NeedsCaching[#NeedsCaching+1] = lambda
			NeedsCachingChange.Value = not NeedsCachingChange.Value
		end
		--
		return map
	end 
	--
	local key = math.random()*10000
	local map = {}
	for x = 1, WIDTH do
		map[x] = {}
		for z = 1, LENGTH do
			map[x][z] = PerlinNoise(x/lambda, z/lambda + key)
		end
	end
	return map
end


-- the main noise cache generator deamon
Spawn(function()
	while true do
		--generate cache values
		while #NeedsCaching > 0 do 
			local lambda = NeedsCaching[#NeedsCaching]
			NeedsCaching[#NeedsCaching] = nil
			--
			local key = math.random()*10000
			local map = {}
			local lastPause = tick()
			for x = 1, WIDTH do
				map[x] = {}
				for z = 1, LENGTH do
					local t = tick()
					if t-lastPause > ((1/30)/2) then
						wait()
						lastPause = tick()
					end
					map[x][z] = PerlinNoise(x/lambda, z/lambda + key)
				end
			end
			--
			if not CachedNoise[lambda] then CachedNoise[lambda] = {} end
			CachedNoise[lambda][#CachedNoise[lambda]+1] = map
		end
		--wait for more values to be requested
		NeedsCachingChange.Changed:wait()
	end
end)


--force pre-generate the cache, just in case
function ForcePregenCache()
	while #NeedsCaching > 0 do 
		local lambda = NeedsCaching[#NeedsCaching]
		NeedsCaching[#NeedsCaching] = nil
		--
		local key = math.random()*10000
		local map = {}
		for x = 1, WIDTH do
			map[x] = {}
			for z = 1, LENGTH do
				map[x][z] = PerlinNoise(x/lambda, z/lambda + key)
			end
		end
		--
		if not CachedNoise[lambda] then CachedNoise[lambda] = {} end
		CachedNoise[lambda][#CachedNoise[lambda]+1] = map
	end
end



--==========================================================================================================--
--==                                    The terrain generation code                                       ==--
--==========================================================================================================--
--
-- The main terrain generation is implemented as a function which both clears old terrain and builds
-- up new terrain. The process should take just under 30 seconds on average.
-- Note:
--   Most of the body of the generate function is a set of functions. These functions are purely for
--   extra syntactic and sectional division, not for code reusability. The various stages are actually
--   fairly closely linked, and there is too much data to pass between phases while still maintaining
--   readbility.
--   So, don't edit the part of the code that calls those functions to do stuff like call them twice,
--   this will not work as expeced in some cases. It is preferred to edit the bodies of the inner
--   functions or add new ones for new features.
--
function Generate()
	------------------------------------------------------------------------------------------------------
	-- code for generating a nice message telling players what the generation progress is
	------------------------------------------------------------------------------------------------------
	local GenerationProgressGuis = {}
	local CurrentGenerationProgressMessage = ""
	local function AddGenerationProgressGui(player)
		local screenGui = Instance.new('ScreenGui', player:FindFirstChild('PlayerGui'))
		local frame = Instance.new('Frame', screenGui)
		      frame.Style = 'RobloxRound'
		      frame.Name = 'MainFrame'
		      frame.Size = UDim2.new(0,500,0,150)
		      frame.Position = UDim2.new(0.5,-250,0.1,0)
		local text = Instance.new('TextLabel', frame)
		      text.Name = 'MessageContent'
		      text.Size = UDim2.new(1,0,1,0)
		      text.TextColor3 = Color3.new(1,1,1)
		      text.TextStrokeColor3 = Color3.new(0.5,0.5,0.5)
		      text.TextStrokeTransparency = 0.5
		      text.Font = 'Arial' text.FontSize = 'Size24'
		      text.Text = CurrentGenerationProgressMessage
		GenerationProgressGuis[#GenerationProgressGuis+1] = screenGui
	end
	for _, p in pairs(game.Players:GetChildren()) do
		if p:IsA('Player') then AddGenerationProgressGui(p) end
	end
	local PlayerAddedCn = game.Players.ChildAdded:connect(function(p)
		if p:IsA('Player') then AddGenerationProgressGui(p) end
	end)
	local function UpdateGenerationProgressMessage(text)
		CurrentGenerationProgressMessage = text
		for _, gui in pairs(GenerationProgressGuis) do
			--gui.MainFrame.MessageContent.Text = text
		end
		--game:SetMessage(text)
		wait()
	end
	local function KillGenerationProgressMessages()
		for _, gui in pairs(GenerationProgressGuis) do
			gui:Destroy()
		end
		--game:ClearMessage()
	end


	------------------------------------------------------------------------------------------------------
	-- Easy pausing code, which will only wait at most once every 1/9 second
	------------------------------------------------------------------------------------------------------
	local LastPause = tick()
	local function pause()
		if tick()-LastPause > 1/6 then
			wait()
			LastPause = tick()
		end
	end
	local StartAt = 0
	local function begin_profile()
		StartAt = tick()
	end
	local function end_profile(name)
		print(string.format("Step `%s` took %.1f seconds.", name, tick()-StartAt))
	end


	------------------------------------------------------------------------------------------------------
	-- Tree and GameLocation model management
	------------------------------------------------------------------------------------------------------
	local function GetTreeModel()
		local model = game.Workspace:FindFirstChild('TreeModel')
		if not model then
			model = Instance.new('Model', game.Workspace)
			model.Name = 'TreeModel'
		end
		return model
	end

	local function GetGameLocationsModel()
		local model = game.Workspace:FindFirstChild('GameLocation')
		if not model then
			model = Instance.new('Model', game.Workspace)
			model.Name = 'GameLocation'
		end
		return model
	end
	local function AddGameLocation(x,y,z,name)
		local ref = Instance.new('Vector3Value')
		ref.Value = Terrain:CellCenterToWorld(floor(x),floor(y),floor(z)) + Vector3.new(0,8,0)
		ref.Name = name
		ref.Parent = GetGameLocationsModel()
	end
	local function ClearGameLocations()
		for _, ch in pairs(GetGameLocationsModel():GetChildren()) do
			ch:Destroy()
		end
	end



	------------------------------------------------------------------------------------------------------
	-- Main settings for generation
	------------------------------------------------------------------------------------------------------
	local CLIFFS_PER_SQ = 1/2000
	--
	local TREES_PER_SQ =  1/100
	--
	local MINES_PER_SQ =  1/15000
	local MINE_MAX_SIZE = 5
	--
	local LAKES_PER_SQ =  1/10000
	local LAKE_MAX_SIZE = 3000
	--
	local MIDDLE_RIDGE_RADIUS =   40  --the base radius of the middle ridge
	local MIDDLE_RIDGE_VARIANCE = 50  --how much to vary the boundary by
	local MIDDLE_RIDGE_FADE =     35  --how large a distance to fade the mountains on around the boundary
	--
	local BASE_RADIUS = 20    --how large an area is allocated to bases (base & tween into surroundings)
	local BASE_ELEVATION = 4  --what elevation to place the bases at (they are at a fixed elevation,
		                      --otherwise getting placed at a lower elevation by chance would give you
		                      --an unfair advantage)



	------------------------------------------------------------------------------------------------------
	-- Utility functions
	------------------------------------------------------------------------------------------------------

	--is a function in the bounds ( x elemof [1,WIDTH], z elemof [1,LENGTH] )
	local function InBound(x, z)
		return x >= 1 and x <= WIDTH and
		       z >= 1 and z <= LENGTH
	end
	local function at(heightMap, x, z)
		if x > WIDTH  then x = WIDTH  end
		if x < 1      then x = 1      end
		if z > LENGTH then z = LENGTH end
		if z < 1      then z = 1      end
		return heightMap[x][z]
	end

	--local copies of the standard mathematical functions for speed
	local floor =  math.floor
	local ceil =   math.ceil
	local sqrt =   math.sqrt
	local sin =    math.sin
	local cos =    math.cos
	local max =    math.max
	local min =    math.min
	local abs =    math.abs
	local random = math.random

	--curving functions. They are smooth curves that may values in [0,1] -> [0,1] in usefull ways. In 
	--particular they are used to change the distribution of perlin noise to generate more natural hills
	local function quad_curve(n) --slightly S shaped curve, with tangent -> 2 as x -> 0.5
		if n < 0.5 then
			return n*n + 0.5*n
		else
			return -n*n +2.5*n -0.5
		end
	end
	local function root2_curve(n) --S shaped with a vertical tangent as x -> .5
		if n < 0.5 then
			return 0.5-sqrt(0.5^2 - n^2)
		else
			return sqrt(0.5^2 - (1-n)^2)+0.5
		end
	end
	local function sin4_smallbias_curve(n) --Like quad_curve but biased to smaller outputs
		return sin((0.5*3.141592653)*n)^4
	end
	local function sin4_largebias_curve(n) --like quad_curve but biased to larger outputs
		return 1-sin((0.5*3.141592653)*(1-n))^4
	end



	------------------------------------------------------------------------------------------------------
	-- Clear the terrain, readying the game for a new generation.
	------------------------------------------------------------------------------------------------------
	local function ClearTerrain()
		UpdateGenerationProgressMessage("(1/12) Clearing Old Terrain")
		--clear the game locations from last round
		ClearGameLocations()

		--first, clear the foliage. If we don't clear the foliage the game will crash when clearing the
		--terrain with so many parts colliding with it. We can just destroy it as it will be generated
		--again when the code needs it, we haven't stored a reference to it yet here.
		GetTreeModel():Destroy()
		wait()

		--now we clear the terrain. Do it in 15 block strips once every 1/30 second. This way it will
		--take about 1.5 seconds to clear the whole map, ond not lag.
		local ext = Terrain.MaxExtents
		local minc,maxc = ext.Min,ext.Max
		for x = minc.x,maxc.x,5 do
			pause()
			Terrain:SetCells(Region3int16.new(Vector3int16.new(x,    minc.y, minc.z),
			                                  Vector3int16.new(x+15, maxc.y, maxc.z)), 
			                 0, 0, 0)
		end
	end	


	------------------------------------------------------------------------------------------------------
	-- Make the base layer, a hieghtmap that is relatively flat hills and valleys covering the
	-- whole map.
	-- Returns: A WIDTHxLENGTH table heightmop representing the base of the map.
	------------------------------------------------------------------------------------------------------
	local function MakeBaseLayer()
		UpdateGenerationProgressMessage("(2/12) Generating Base Layer")
		--first, get all of the perlin maps that we need
		local BaseLayer =     PerlinNoiseMap(70)
		--
		local IsPlainsMap =   PerlinNoiseMap(80) --where should the area be flatter?
		local MedFreqHills =  PerlinNoiseMap(28)
		local HighFreqHills = PerlinNoiseMap(14)
		local Quantity =      PerlinNoiseMap(60) --how sparse or dense areas of hills should be
		local IsCrags =       PerlinNoiseMap(100)
		local CragsMap =      PerlinNoiseMap(30)
		--
		local baseLayer = {}
		for x = 1, WIDTH do
			baseLayer[x] = {}
			for z = 1, LENGTH do
				--------
				-- I hope this is readable enough.... that's the best that I can do. Rest assured, it's
				-- doing a whole pile of fiddling with perlin noise. The general strategy uses 3 parts:
				-- 1) A Base Layer -     Just typical perlin noise scaled by some amount.
				--
				-- 2) A Mask Layer -     Determines where the base layer should show up, through 
				--                       multiplication with the base layer.
				--
				-- 3) A Freqency Layer - The mask layer is also raised to a power. The higher the power,
				--                       The more sparsely distributed the feature will be.
				--
				local quant = Quantity[x][z]
				local hf = quad_curve( HighFreqHills[x][z] )
				local mf = quad_curve( MedFreqHills[x][z]  )
				--
				baseLayer[x][z] =   quad_curve(BaseLayer[x][z])*8
				                  + max( 
				                      85* CragsMap[x][z]^(2.5+  0  )     *max(0, IsCrags[x][z]-0.3    ),
				                      12*             mf^(1.5+quant)     *min(1, IsPlainsMap[x][z]+0.5)
				                    )
				                  + 6* hf^(2.0+quant) *IsPlainsMap[x][z] 
				--------
			end
		end
		return baseLayer
	end


	------------------------------------------------------------------------------------------------------
	-- A function which carves small cliff faces into themap.
	-- These small cliff faces give the map the appearance that water has been flowing through it, in
	-- contrast to just having the hilly terrain that raw noise will give you.
	------------------------------------------------------------------------------------------------------
	local function ApplyCliffs(baseLayer)
		UpdateGenerationProgressMessage("(3/12) Eroding Cliffs")
		--First get a noise map of how cliffey different areas of the map are. This gives some variation
		--rather than just having all parts of the map have cliffs on them.
		local CliffMap = PerlinNoiseMap(70)

		-- generate an inermediary hight map to store changes to the map as a result of applying cliffs.
		-- this is important because we want to clamp the maximum effect that cliffs can have on the map 
		-- to something around +/-5. Which is most efficiently done with another hight map.
		local cliffs = {}
		for x = 1, WIDTH do
			cliffs[x] = {}
			for z = 1, LENGTH do
				cliffs[x][z] = 0 --for summing, initialize to 0 
			end
		end

		--Now, we need to apply the cliffs in two phases. For every cliff we first see exactly what kind
		--of feature it would create, and then if it creates a "good" one go through again and actually
		--apply it to the heightmap. For example, if a cliff ends up being a "pothole", that is, a really
		--small circular dent, then discard it.
		--It turns out that the fastest way to do things is just guessing cliffs and seeing which ones
		--end up good, rather than using a more complex approach.

		--generate a good number of cliffs. 1 cliff / 2000 studs^2 turns out to be best
		for CliffNum = 1, WIDTH*LENGTH*CLIFFS_PER_SQ do 
			pause()
			--
			--first, generate the stats of this cliff
			local x, z = random(2,WIDTH-1), random(2,LENGTH-1) --random position
			local radius = random(20,50)                       --random radius of effect
			local amplitude = random(2,10)                     --random amplitude the +/- of heigh generated

			--the plane to make the "cut" at. We generate a normal and then solve for the plane at the
			--position chosen and with that normal. That plane is then used to find the height of the cut
			--at each affected cell.
			local cliffAtElevation = baseLayer[x][z]
			local norm = Vector3.new(random()*0.5-0.25,1,random()*0.5-0.25).unit
			local planeA, planeB, planeC = norm.x,norm.y,norm.z
			local planeD = -(planeA*x + planeB*cliffAtElevation + planeC*z) 
			local function elevationAt(x,z)
				return -(planeA*x + planeC*z + planeD)/planeB
			end

			--first, check for potholes (and other bad features that you may want to).
			--we do this by counting the number of squares pushed up and number pushed down. This may
			--seem odd but it is a good fast hueristic. Generally petholes occurr when less than 20%
			--of the squares are pushed down.
			--if we hit exactly on a straight line we would expect 50%-50%, and most good features are in
			--the 25%-75% range. 
			local upCount, downCount = 0,0
			for dx = -radius,radius do
				for dz = -radius,radius do
					local xp,zp = x+dx,z+dz
					local r_2 = dx*dx + dz*dz
					--
					if (r_2 < radius*radius) and InBound(xp,zp) then
						local avrHeight = (at(baseLayer,xp+1,zp  ) + at(baseLayer,xp-1,zp  ) + 
						                   at(baseLayer,xp  ,zp  ) +
						                   at(baseLayer,xp  ,zp+1) + at(baseLayer,xp,  zp-1))/5
						if avrHeight > cliffAtElevation then
							upCount = upCount+1
						else
							downCount = downCount+1
						end
					end
				end
			end

			--now, if we aren't in that bad 20% on either end, apply the changes to the heightmap
			if downCount/(upCount+downCount) > 0.2 and upCount/(upCount+downCount) > 0.2 then
				for dx = -radius,radius do
					for dz = -radius,radius do
						local xp,zp = x+dx,z+dz
						local r = sqrt(dx*dx + dz*dz)
						--
						--for every square which in-bounds square in the range of the effect
						if (r < radius) and InBound(xp,zp) then
							--find the average hieght at this square, and compare it to the 
							local avrHeight = (at(baseLayer,xp+1,zp  ) + at(baseLayer,xp-1,zp  ) + 
							                   at(baseLayer,xp  ,zp  ) +
							                   at(baseLayer,xp  ,zp+1) + at(baseLayer,xp,  zp-1))/5
							local nearnessToCenter = (radius-r)/radius
							local cliffiness = quad_curve(CliffMap[xp][zp])
							if avrHeight > elevationAt(xp,zp) then
								cliffs[xp][zp] = cliffs[xp][zp] + nearnessToCenter*amplitude*cliffiness
							else
								cliffs[xp][zp] = cliffs[xp][zp] - nearnessToCenter*amplitude*cliffiness
							end
						end
					end
				end			
			end
		end

		--now, apply all of the changes stored in the cliffs map to the baseLayer, clamping the
		--cliffs value to +/- 4 in the process.
		for x = 1, WIDTH do
			for z = 1, LENGTH do
				local v = cliffs[x][z]
				if v >  4 then v =  4 end
				if v < -4 then v = -4 end
				baseLayer[x][z] = baseLayer[x][z] + v
			end
		end
	end	


	------------------------------------------------------------------------------------------------------
	-- Next we have to generate a high mountain layer to separate the two sides of the combat.
	-- Rather than using some heavily built up recursive noise, only a couple layers of noise are used,
	-- this gives the effect of valleys between the peaks, that let players find a nice strategic path
	-- to get to the other side of the map or prevent the opponents from as a part of the gameplay.
	--
	-- Returns: MountainMask, MountainHeight
	------------------------------------------------------------------------------------------------------
	function ApplyMountains(baseLayer)
		UpdateGenerationProgressMessage("(4/12) Building Mountain Ridge")
		--first, we need the noise for the mountain layer itself
		local SteepMountains =   PerlinNoiseMap(40)
		local ShallowMountains = PerlinNoiseMap(50)
		local SwitchMap =        PerlinNoiseMap(90) --which of steep or shallow to use
		
		--
		--now we need to generate the mountain "mask", which is where the mountains will be shown
		--down the center of the map.
		local mountainMask = {}
		local RidgeWidthMap = PerlinNoiseMap(60)
		for x = 1, WIDTH do
			mountainMask[x] = {}
			--
			local radius = ceil(MIDDLE_RIDGE_RADIUS + MIDDLE_RIDGE_VARIANCE*RidgeWidthMap[x][1])
			local center = floor(LENGTH/2)
			--lead up to 
			for z = 1, LENGTH do
				local distToCenter = abs(center-z)
				if distToCenter < radius - MIDDLE_RIDGE_FADE then
					mountainMask[x][z] = 1
				elseif distToCenter < radius + MIDDLE_RIDGE_FADE then
					mountainMask[x][z] = 
						((radius+MIDDLE_RIDGE_FADE)-distToCenter) / (MIDDLE_RIDGE_FADE*2)
				else
					mountainMask[x][z] = 0
				end 
			end
		end

		--now, using the mountainMap weighted average between the mountain values and the base values
		--once we've done that we have to scale them up to make maximum usage of our available vertical
		--space. The highest peok should be at exactly y=64
		--We reuse the SteepMountains array as a place to write the results out to before we do a
		--seoond round scaling them up.
		local maxValue = 0
		for x = 1, WIDTH do
			for z = 1, LENGTH do
				local steepFrac =   SwitchMap[x][z]
				local shallowFrac = 1-steepFrac
				--
				local mountainHeight =   steepFrac  *sin4_smallbias_curve(SteepMountains[x][z])
				                       + shallowFrac*ShallowMountains[x][z]
				if mountainHeight > maxValue then maxValue = mountainHeight end
				SteepMountains[x][z] = mountainHeight
			end
		end
		local scaleFactor = 63/maxValue --1 less or else we get cut off without doing an extra floor()

		--now, scale and add the mountain layer to the baseLayer. We can do both of these steps in the
		--same loop. This time we will re-use the SteepMountain layer as the total scaled mountain layer
		--to.
		for x = 1, WIDTH do
			for z = 1, LENGTH do 
				local mountainLayer = SteepMountains[x][z]*scaleFactor
				SteepMountains[x][z] = mountainLayer
				baseLayer[x][z] =  (1-mountainMask[x][z])*baseLayer[x][z]
				                  +(  mountainMask[x][z])*mountainLayer
			end
		end

		--return the values
		return mountainMask, SteepMountains
	end


	------------------------------------------------------------------------------------------------------
	-- There may be some holes left over, fill them.
	-- Any areas which are <= 0 in the base layer we're building are holes, and should be changed to
	-- a value of 1
	------------------------------------------------------------------------------------------------------
	local function FillHoles(baseLayer)
		UpdateGenerationProgressMessage("(5/12) Filling Holes")
		for x = 1, WIDTH do
			for z = 1, LENGTH do
				if baseLayer[x][z] < 1 then
					baseLayer[x][z] = 1
				end
			end
		end
	end


	------------------------------------------------------------------------------------------------------
	-- Now that the heightmap is fully constructed, coloring.
	-- All of the coloring is done as post-process using only various hightmaps from previous phases. The
	-- advantage of this is that it is easy to change the look and feel of the map when adding new
	-- features, as opposed to if a persistent coloring state were maintained as the heigh-map is
	-- build up, where you would have to worry about ovecdraw from following phases.
	-- It also turns out to be faster to do it this way. It is qutie tricky to decide how to color in
	-- phases based on what previous and furture phases do, as opposed to in a single coloring pass here.
	--
	-- Returns: A map of CellMaterial codes, or special color codes, that can be used in drawing out the
	--          heightmap to the terrain.
	------------------------------------------------------------------------------------------------------
	local function ColorMap(baseLayer, mountainMask, mountainMap)
		UpdateGenerationProgressMessage("(6/12) Coloring Map")
		--first, make a map that we will use to decide where to put sand, and where to put grass
		local SandMapA = PerlinNoiseMap(100)
		local SandMapB = PerlinNoiseMap(50)
		local SandMapC = PerlinNoiseMap(25)

		--the map to write the colors out to
		local ColorMap = {}

		--now, we do a single pass over every square in the map, and color it
		for x = 1, WIDTH do
			ColorMap[x] = {}
			pause()
			for z = 1, LENGTH do
				--first, weneed to find all the heights of all of the nearby squares, so we can calculate
				--both an average height at this location, and a total variance at this location.
				local _1,_2,_3,_4,_5,_6,_7,_8,_9 =
					at(baseLayer,x+1,z+1),
					at(baseLayer,x+1,z  ),
					at(baseLayer,x+1,z-1),
					at(baseLayer,x  ,z+1),
					at(baseLayer,x  ,z  ),
					at(baseLayer,x  ,z-1),
					at(baseLayer,x-1,z+1),
					at(baseLayer,x-1,z  ),
					at(baseLayer,x-1,z-1)
				local h = _5
				local avr = (_1+_2+_3+_4+_5+_6+_7+_8+_9)/9
				local tot = (abs(_1-avr) + abs(_2-avr) + abs(_3-avr) + 
				             abs(_4-avr) + abs(_5-avr) + abs(_6-avr) + 
				             abs(_7-avr) + abs(_8-avr) + abs(_9-avr))

				--now, using those values, color the map.
				if abs(h-avr) > 1 then
					--if the average is far from the height then we are in a sharp slope region. We give
					--these areas a special color code so that where they are drawn they will not just
					--be single color columns like the rest, which would lead to vertical striping
					ColorMap[x][z] = 1001
				else
					local mountainHeight = mountainMask[x][z]*mountainMap[x][z]
					local sandy = SandMapA[x][z]+SandMapB[x][z]+SandMapC[x][z]
					--
					if tot>5 or (sandy > 1.5 and mountainHeight > 40) then
						if tot<5 then
							--we are are really high up, place snow here
							ColorMap[x][z] = 7 --snowey
						else
							--we are in a steep area in the mountains, but not a really steep area
							--reuse the sandy map for a bit of variation in the mountain material
							if sandy > 1.5 then
								ColorMap[x][z] = 13
							else
								ColorMap[x][z] = 14
							end
						end
					elseif mountainHeight > 30 then
						--it's boh not steep, and high in the mountains. These areas are snow-covered
						--peaks, color them snowey
						ColorMap[x][z] = 7
					else
						--it's a smooth area. Decide whether to place sand or grass. Sand should only be
						--placed in concave areas which are not in the mountains:
						--        (not in mountains)             (concave)     (not too high either)
						if (sandy*(1-mountainMask[x][z])>1.5) and (h<=avr) and (baseLayer[x][z] < 15) then
							ColorMap[x][z] = 2 --sand
						else
							ColorMap[x][z] = 1 --grass
						end
					end
				end
			end
		end

		--done, return the color map
		return ColorMap
	end


	------------------------------------------------------------------------------------------------------
	-- Recolors and edits the heightmap in a given area for a base. 
	-- The center 50% of the radius near (x,z) is perfectly flat, and the other 50% is used to tween
	-- between the other terrain and where we want to place the base. 
	------------------------------------------------------------------------------------------------------
	local function PlaceBase(baseLayer, baseMask, colormap, x, z, r)
		for dx = -r,r do
			for dz = -r,r do
				local rad = sqrt(dx*dx+dz*dz)
				if rad < r then
					local xp,zp = x+dx,z+dz
					if rad/r < 0.5 then
						baseMask[xp][zp] = 1
						baseLayer[xp][zp] = BASE_ELEVATION
						colormap[xp][zp] = 5 --asphalt
					else
						local f = quad_curve(1-(rad/r-0.5)/0.5)
						baseMask[xp][zp] = f
						baseLayer[xp][zp] = (  f)*BASE_ELEVATION
						                   +(1-f)*baseLayer[xp][zp]
					end
				end
			end
		end	
	end


	------------------------------------------------------------------------------------------------------
	-- Generate the bases and return a mask specifying where the bases are
	------------------------------------------------------------------------------------------------------
	local function PlaceBases(baseLayer, colormap)
		UpdateGenerationProgressMessage("(7/12) Placing Bases")
		--make the base mask
		local baseMask = {}
		for x = 1, WIDTH do 
			baseMask[x] = {}
			for z = 1, LENGTH do 
				baseMask[x][z] = 0
			end 
		end

		--generate two bases 
		PlaceBase(baseLayer, baseMask, colormap, floor(WIDTH/2), 25,        BASE_RADIUS)
		PlaceBase(baseLayer, baseMask, colormap, floor(WIDTH/2), LENGTH-25, BASE_RADIUS)

		--record the positions of the bases
		AddGameLocation(floor(WIDTH/2), BASE_ELEVATION, 25       , 'Base1')
		AddGameLocation(floor(WIDTH/2), BASE_ELEVATION, LENGTH-25, 'Base2')

		--return the bases mask
		return baseMask
	end


	------------------------------------------------------------------------------------------------------
	-- Recolors and edits the heightmap in a given area for a base. 
	-- The center 50% of the radius near (x,z) is perfectly flat, and the other 50% is used to tween
	-- between the other terrain and where we want to place the base. 
	------------------------------------------------------------------------------------------------------
	local function PlaceMines(baseLayer, colormap)
		UpdateGenerationProgressMessage("(8/12) Placing Mines")
		--find the number of mines and where to place them
		local mineCount = floor(WIDTH*LENGTH*MINES_PER_SQ)
		--
		local modWidth =  WIDTH  - MINE_MAX_SIZE
		local modLength = LENGTH - MINE_MAX_SIZE
		--
		local xcount = floor(modWidth/(MINE_MAX_SIZE*4))
		local xstep = modWidth/xcount
		local zcount = floor(modLength/(MINE_MAX_SIZE*4))
		local zstep = modLength/zcount
		
		--place mines
		local usedPos = {}
		for i = 1, mineCount do 
			local cell;
			repeat
				cell = random(1, xcount*zcount)
			until not usedPos[cell]
			usedPos[cell] = true
			--
			local x = cell%xcount + 1
			local z = ceil(cell/xcount)
			--
			local mineSize = random(1,3)
			--
			local bestDeviation = 100
			local bestX, bestZ = 1, 1
			local bestMinH;
			for i = 1, 15 do
				local tx = ceil( (x-random())*xstep )
				local tz = ceil( (z-random())*zstep )
				--
				local minh,maxh = math.huge,-math.huge
				for dx = 0,mineSize+2-1 do 
					for dz = 0,mineSize+2-1 do 
						local y = baseLayer[tx+dx][tz+dz]
						if y > maxh then maxh = y end
						if y < minh then minh = y end
					end
				end
				--
				local deviation = maxh-minh
				if deviation < bestDeviation then
					bestDeviation = deviation
					bestX, bestZ = tx, tz
					bestMinH = minh
				end
			end
			x,z = bestX,bestZ
			--
			--now draw the border
			for xp = x, x+mineSize+1 do 
				for zp = z, z+mineSize+1 do 
					baseLayer[xp][zp] = bestMinH
					colormap[xp][zp] = 5 --asphault
				end
			end
			--now draw the center
			for xp = x+1, x+mineSize do 
				for zp = z+1, z+mineSize do 
					colormap[xp][zp] = 8 --gold
				end
			end

			--and write out the reference
			AddGameLocation(x+mineSize/2+0.5, bestMinH, z+mineSize/2+0.5, 'Mine'..mineSize)
		end
	end


	------------------------------------------------------------------------------------------------------
	-- Now, we actually draw out the level to the Terrain instance.
	------------------------------------------------------------------------------------------------------
	local SharpColors = {4,11,12,13}
	local function DrawTerrain(baseLayer, colormap)
		UpdateGenerationProgressMessage("(9/12) Drawing Terrain")
		for x = 1, WIDTH do 
			for z = 1, LENGTH do 
				local c = colormap[x][z]
				local y = baseLayer[x][z]
				local xc = x-floor(WIDTH/2)
				local zc = z-floor(LENGTH/2)
				--
				pause()
				--
				if c == 1001 then 
					--sharp slope color code, special handling
					for i = 1, y do
						c = SharpColors[random(1,#SharpColors)]
						Terrain:SetCell(xc, i, zc,
						                c, 0, 0)
					end
				else
					--just apply the color
					Terrain:SetCells(Region3int16.new(Vector3int16.new(xc, 0, zc),
					                                  Vector3int16.new(xc, y, zc)), c, 0, 0)			
				end
			end 
		end
	end


	------------------------------------------------------------------------------------------------------
	-- Next we draw lakes into the map.
	-- The lake drawing process finds local minima in the map, and then flood-fills them to as
	-- high a level as it can without the flood-fill spilling into a very large area. This seems
	-- inefficient but it actually does not take that much time to fill a reasonable number of local
	-- minima using this approach.
	-- We need to take the base mask as a parameter so that we ensure the lake fills do not spill into
	-- the areas reserved for the bases.
	--
	-- Returns: A mask of where water was placed
	------------------------------------------------------------------------------------------------------
	local Directions = {{1,0,1},         {-1,0,1},       {0,1,1},        {0,-1,1},
                    {-1,-1,sqrt(2)}, {-1,1,sqrt(2)}, {1,-1,sqrt(2)}, {1,1,sqrt(2)}}
	local function PlaceLakes(baseLayer, baseMask)
		UpdateGenerationProgressMessage("(10/12) Filling Lakes")
		--first generate the water mask
		local waterMask = {}
		for x = 1, WIDTH do
			waterMask[x] = {}
			for z = 1, LENGTH do 
				waterMask[x][z] = 0
			end
		end

		--generate a certain density of lakes
		for i = 1, WIDTH*LENGTH*LAKES_PER_SQ do
			--select a random position
			local x,z = random(1,WIDTH), random(1,LENGTH)

			--now, we need to find the local minimum nearest to this position
			local prevdx,prevdz;
			while true do
				--see if we will drop down in any of the directions
				local leastDir, leastChange = nil,100
				local h = baseLayer[x][z]
				for _, dir in pairs(Directions) do 
					local nx,nz = x+dir[1],z+dir[2]
					if InBound(nx,nz) then
						local hn = baseLayer[nx][nz]
						if hn < h and abs(hn-h) < leastChange then
							leastDir = dir
							leastChange = abs(hn-h)
						end
					end
				end
				if not leastDir then
					break
				end
				x = x + leastDir[1]
				z = z + leastDir[2]
				if leastChange == 0 then
					break
				end
			end

			--(x,z) is now the local min nearest the random location. If there is not already a
			--water-feature there then try to generate one.
			if waterMask[x][z] == 0 then
				--now, in order to get the deepest possible lake, we try to generate one at sereval
				--heights, starting with the deepest. Doing anywhere from 1 deep to 3 deep works nicely.
				for y = floor(baseLayer[x][z])+5, floor(baseLayer[x][z])+1, -1 do
					pause()
					--we need to make a temporary map to store this attpmt's changes in, rather than
					--just applying them right to the water mask.
					local tmpWaterMask = {}
					for x = 1, WIDTH do
						tmpWaterMask[x] = {}
						for z = 1, LENGTH do
							tmpWaterMask[x][z] = waterMask[x][z]
						end
					end

					--now do a flood-fill
					local filledCount = 0
					local function FloodFill(x,z)
						if not InBound(x,z) then return true end
						if baseMask[x][z] > 0 then
							return false
						else
							if tmpWaterMask[x][z] == 0 or y > tmpWaterMask[x][z] then
								if y > floor(baseLayer[x][z]) then
									--place water here
									tmpWaterMask[x][z] = y
									filledCount = filledCount+1
									--
									if filledCount > LAKE_MAX_SIZE then
										--bail out early, don't flood bases
										return false
									end
									--
									if not FloodFill(x-1,z  ) then return false end
									if not FloodFill(x+1,z  ) then return false end
									if not FloodFill(x  ,z-1) then return false end
									if not FloodFill(x  ,z+1) then return false end
								else
									--flag as tested
									tmpWaterMask[x][z] = -1
								end
							end
							return true
						end
					end
					if FloodFill(x,z) then
						--we found a good lake, now add it to the waterMask (we can do this with just
						--assignment because we were editing a copy of the old water mask)
						waterMask = tmpWaterMask
						break			
					end
				end
			end
		end

		--now, draw out the water
		for x = 1, WIDTH do 
			for z = 1, LENGTH do 
				local tx,tz = floor(x-WIDTH/2),floor(z-LENGTH/2)
				for y = floor(baseLayer[x][z])+1, waterMask[x][z] do
					pause()
					Terrain:SetWaterCell(tx,y,tz,0,0)
				end
			end
		end

		--and return the waterMask
		return waterMask
	end


	------------------------------------------------------------------------------------------------------
	-- Next we smooth the terrain. 
	-- Now that both the main terrain and water are placed, we smooth things.
	------------------------------------------------------------------------------------------------------
	local function SmoothTerrain()
		UpdateGenerationProgressMessage("(11/12) Smoothing Terrain")
		Terrain:AutowedgeCells(Terrain.MaxExtents)
	end


	------------------------------------------------------------------------------------------------------
	-- Finally we draw trees to the surface.
	-- We generate a noise treemap, and then trees are placed:
	--   In grassy areas
	--   Which are not covered in water
	------------------------------------------------------------------------------------------------------
	local function DrawTrees(baseLayer, waterMask, colormap)
		UpdateGenerationProgressMessage("(12/12) Drawing Trees")
		local Base = Instance.new("Part")
		Base.Name = "Trunk"
		Base.formFactor = "Custom"
		Base.TopSurface = 0
		Base.BottomSurface = 0
		Base.Anchored = true
		Base.BrickColor = BrickColor.new("Reddish brown")
		local Leaves = Base:Clone()
		Leaves.Name = "Leaves"
		Leaves.CanCollide = false
		Leaves.Anchored = true
		Leaves.BrickColor = BrickColor.new("Dark green")
		local leafmesh = Instance.new("SpecialMesh")
		leafmesh.MeshType = "FileMesh"
		leafmesh.MeshId = "http://www.roblox.com/asset/?id=1290033"
		leafmesh.TextureId = "http://www.roblox.com/asset/?id=2861779" 
		leafmesh.Parent = Leaves
		local basemesh = Instance.new("SpecialMesh",Base)
		basemesh.MeshType = "Head"
		local leaf_mult = {
			Vector3.new(1.5,1.5,1.2);
			Vector3.new(1.5,1,  1.5);
			Vector3.new(1.2,1.5,1.5);
			Vector3.new(1.5,1.5,1.5);
		}
		local function dot(c1,c2)
			local m = CFrame.Angles(math.pi/2,0,0)
			return (c1*m).lookVector:Dot((c2*m).lookVector)
		end
		local function Branch(base,c)
			if c <= 0 then
				local leaves = Leaves:Clone()
				local vol = base.Size.x+base.Size.y+base.Size.z
				leaves.Mesh.Scale = leaf_mult[math.random(1,#leaf_mult)]*math.random(vol/3*10,vol/3*12)/10
				leaves.Size = leaves.Mesh.Scale*0.75
				leaves.CFrame = base.CFrame * CFrame.new(0,base.Size.y/2,0)
				leaves.Parent = base.Parent
			else
				local pos = base.CFrame*CFrame.new(0,base.Size/2,0)
				local height = base.Size.y
				local width = base.Size.x
				local nb = math.random(2,2) 
				local r = math.random(45,135) 
				local da = math.random(20+55/c,40+40/c)
				local ba = math.random(-da/3,da/3)
				for i=0,nb-1 do
					local branch = base:Clone()
					branch.Name = "Branch"
					local h = height*math.random(95,115)/100 
					local new = branch.CFrame * CFrame.new(0,height/2,0) * CFrame.Angles(0,0,math.rad(ba))
					new = new * CFrame.Angles(0,i*(math.pi*2/nb)+r,math.rad(da/2)) * CFrame.new(0,h/2,0)
					local w = dot(new,branch.CFrame)*width*0.9
					branch.Size = Vector3.new(w,h,w)
					branch.CFrame = new
					branch.Parent = base.Parent
					Branch(branch,c-1)
				end
			end
		end
		local function GenerateTree(location,complexity,width,height)
			local tree = Instance.new("Model")
			tree.Name = "Tree"
			tree.Parent = GetTreeModel()
			local base = Base:Clone()
			base.Parent = tree
			base.Size = Vector3.new(width,height,width)
			base.CFrame = CFrame.new(location) 
			              *CFrame.new(0,height/2,0)
			              *CFrame.Angles(0,math.rad(math.random(1,360)),0)
			Branch(base,complexity)
			return tree
		end
		------------------------------------------------------------------------
		local TreeMapA = PerlinNoiseMap(200)
		local TreeMapB = PerlinNoiseMap(100)
		--
		for i = 1, WIDTH*LENGTH*TREES_PER_SQ do --1 tree / ~100 blocks^2
			local x,z = random(4,WIDTH-4),random(4,LENGTH-4)
			local treeDensity = TreeMapA[x][z]+TreeMapB[x][z]
			--
			if treeDensity > 1.1 and colormap[x][z] == 1 and waterMask[x][z] <= 0 then
				pause()
				local tree_at_h = baseLayer[x][z]
				local tx,tz = floor(x-WIDTH/2), floor(z-LENGTH/2)
				local tree_at = Terrain:CellCenterToWorld(tx, tree_at_h, tz)
				GenerateTree(tree_at, random(1,random(1,2)), random(4,7), random(11,18))
			end
		end
	end


	------------------------------------------------------------------------------------------------------
	-- And finally call on all of the generation code
	------------------------------------------------------------------------------------------------------
	UpdateGenerationProgressMessage("Generating Terrain")
	wait(1)
	do
		local t = tick()
		begin_profile()
		                                  ClearTerrain()
		end_profile('ClearTerrain')
		begin_profile()
		local baseLayer =                 MakeBaseLayer()
		end_profile('MakeBaseLayer')
		begin_profile()
		                                  ApplyCliffs(baseLayer)
		end_profile('ApplyCliffs')
		begin_profile()
		local mountainMask, mountainMap = ApplyMountains(baseLayer)
		end_profile('ApplyMountains')
		begin_profile()
		                                  FillHoles(baseLayer)
		end_profile('FillHoles')
		begin_profile()
		local colormap =                  ColorMap(baseLayer, mountainMask, mountainMap)
		end_profile('ColorMap')
		begin_profile()
		local baseMask =                  PlaceBases(baseLayer, colormap)
		end_profile('PlaceBases')
		begin_profile()
		                                  PlaceMines(baseLayer, colormap)
		end_profile('PlaceMines')
		begin_profile()
		                                  DrawTerrain(baseLayer, colormap)
		end_profile('DrawTerrain')
		begin_profile()
		local waterMask =                 PlaceLakes(baseLayer, baseMask)
		end_profile('PlaceLakes')
		begin_profile()
		                                  SmoothTerrain()
		end_profile('SmoothTerrain')
		begin_profile()
		                                  DrawTrees(baseLayer, waterMask, colormap)
		end_profile('DrawTrees')
		print(string.format("Generating took %.1f seconds.", tick()-t))
	end
	UpdateGenerationProgressMessage("Finishing Generation")
	wait(1)
	KillGenerationProgressMessages()
end

Generate()