Diamond Square Procedural Map Generation

Show off your games, demos and other (playable) creations.
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Diamond Square Procedural Map Generation

Post by darkfrei »

Gunroar:Cannon() wrote: Thu Jun 24, 2021 10:33 pm The map always seems incomplete, even at a high field.
I'm not familiar with this diamond-square, is there a possible way for me to show more of the map in a smaller area?
We can make chunks:

A chunk is a square (for example size 32 tiles [with sides 33x33]).
If the agent/player is in the chunk, then we are need to check neighbour chunks.
If neighbour chunks don't exist, create them. Don't overwrite existing pixels, but take them for interpolation.

So, chunk [0, 0] with size 32 has verticles: {{0,0},{32,0},{0,32},{32,32}}, the next one is [1, 0] with {{32,0},{64,0},{32,32},{64,32}}.

Note that we starting from 0 and from 0 to 32 is 33 tiles. The next chunk has one tile overlap: from 32 to 64 is also 33 tiles.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Diamond Square Procedural Map Generation

Post by Gunroar:Cannon() »

Oh, thnx. There's no option to change the frequency then?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: Diamond Square Procedural Map Generation

Post by pgimeno »

You can bandpass the images; basically, to apply a certain degree of blur (to reduce the higher frequencies), and to subtract a blurred version of it to another certain degree of blur (to reduce the lower frequencies). But blurring is slow. Also, you lose the original values at the vertices, so the method is not seamless when working in chunks.

I've done that with gimp, which has this method in Filters > Render > Clouds > Plasma (but you have to separate the R, G and B channels afterwards with Colours > Components > Decompose). The result was pretty convincing as noise.
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Diamond Square Procedural Map Generation

Post by Gunroar:Cannon() »

Hey, while experimenting, I made map_n 8 (roughness still 2) then kept chunk_size constant at 2^5 and that made a nice zoomed out map...but I had to make the default value of max to one and min to zero in get_random in case they were nil and that causes small holes in the map at some points. It really looks perfect if it wasn't for that fact. Any fix?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Diamond Square Procedural Map Generation

Post by darkfrei »

Gunroar:Cannon() wrote: Sat Jul 31, 2021 6:17 pm Hey, while experimenting, I made map_n 8 (roughness still 2) then kept chunk_size constant at 2^5 and that made a nice zoomed out map...but I had to make the default value of max to one and min to zero in get_random in case they were nil and that causes small holes in the map at some points. It really looks perfect if it wasn't for that fact. Any fix?
Show the screenshot, the code and where is the problem. Normally this function gives the middle value.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Diamond Square Procedural Map Generation

Post by Gunroar:Cannon() »

It's easy to recreate. Just make chunk_size = 2^5 in load function and map_n = 8 in love.load
main.lua

Code: Select all

-- License CC0 (Creative Commons license) (c) darkfrei, 2021

get_color = require ('sea-mountain-colors')
function load ()
	width, height = love.graphics.getDimensions( )
	
	map = {}
	
	
	map_size = 2^map_n + 1 -- 1025
	chunk_size = 2^5--map_size - 1
	roughness = 2
	
	local corners = {{i=1,j=1}, {i=map_size,j=1}, {i=map_size,j=map_size}, {i=1,j=map_size}}
	
	for _, corner in pairs (corners) do
		local i, j = corner.i, corner.j
		local value = math.random ()
		value = 0.5-0.5*math.cos(value*math.pi)
		map[i] = map[i] or {}
		map[i][j] = value
	end
	
	states = {square = 'square', diamond = 'diamond'}
	state = states.square
	
	pause = false
end

function love.load()
    
    
	local ddwidth, ddheight = love.window.getDesktopDimensions( display )
	if ddheight > 1080 then
		print('ddheight: ' .. ddheight)
		love.window.setMode(1920, 1080, {resizable=true, borderless=false})
	else
		love.window.setMode(ddwidth, ddheight-200, {resizable=true, borderless=false})
	end
	
	
	map_n = 8
	load ()
end


update = {}

function get_value (i, j)
	if map[i] and map[i][j] then
		return map[i][j]
	end
end


function get_random (min, max)
max = max or 1 min = min or 0
	local r = 4*(math.random ()-0.5)^3 + 0.5
--	https://www.desmos.com/calculator/toxjtsovev
	return min + r*(max-min)
end

function get_square_value (i, j, half)
	local value = 0
	local n = 0
	local min, max
	for _, corner in pairs ({{i=i, j=j}, {i=i+chunk_size, j=j}, {i=i, j=j+chunk_size}, {i=i+chunk_size, j=j+chunk_size}}) do
		local v = get_value (corner.i, corner.j)
		if v then
			min = min and math.min (min, v) or v
			max = max and math.max (max, v) or v
			value = value + v
			n = n + 1
		end
	end
	return value/n, min, max
end


update.square = function ()
	local half = chunk_size/2
	for i = 1, map_size-1, chunk_size do
		for j = 1, map_size-1, chunk_size do
			local value, min, max = get_square_value (i, j, half)
			map[i+half] = map[i+half] or {}
			map[i+half][j+half] = get_random (min, max)
		end
	end
	
	state = states.diamond
end


function get_diamond_value (i, j, half)
	local value = 0
	local n = 0
	local min, max
	for _, corner in pairs ({{i=i, j=j-half}, {i=i+half, j=j}, {i=i, j=j+half}, {i=i-half, j=j}}) do
		local v = get_value (corner.i, corner.j)
		if v then
			min = min and math.min (min, v) or v
			max = max and math.max (max, v) or v
			value = value + v
			n = n + 1
		end
	end
	return value/n, min, max
end

update.diamond = function ()
	local half = chunk_size/2
	for i = 1, map_size, half do
--		for j = 1, map_size-1, chunk_size do
		for j = (i+half)%chunk_size, map_size, chunk_size do
--			print ('i: '..i .. ' j:'.. j)
--			if (i + j)%half == 0 then
				local value, min, max = get_diamond_value (i, j, half)
				map[i] = map[i] or {}
				map[i][j] = get_random (min, max)
--			end
		end
	end
	
	chunk_size = chunk_size/2
	roughness = roughness/2
	if chunk_size <= 1 then pause = true end
	state = states.square
end
 
function love.update(dt)
    
	if not pause then
		buffer = buffer or 0
		if buffer > 0.1 then
			buffer = buffer - 0.1
		else
			buffer = buffer + dt
			return
		end
		update[state]()
	end
end

function get_power (value)
	local n = -1
		while value > 1 do
			n=n+1
			value = value/2
		end
	return n
end

function love.draw()

	love.graphics.setColor(1,1,1)
	love.graphics.print(chunk_size,0,0)
	love.graphics.print(map_n,0,20)
	
	local rez = height/(map_size+2)
--	print (rez .. ' '..get_power (rez))
	rez = 2^get_power (rez)
	if rez < 1 then rez = 1 end
	
	for i = 1, map_size do
		for j = 1, map_size do
			local c = map[i] and map[i][j] or nil
			if c then
				
				if c > 1 then 
					c = 1
				elseif c < 0 then
					c = 0
				end
				love.graphics.setColor(get_color(c^2))
				
				if rez > 1 then
					love.graphics.rectangle("fill", rez*i, rez*j, rez, rez)
				else
					love.graphics.points(i, j)
				end
				

				if map_n < 5 then
					if c < 0.75 then
						love.graphics.setColor(1,1,1)
					else
						love.graphics.setColor(0,0,0)
					end
					love.graphics.print(math.floor(c*100), rez*i, rez*j)
				end
			end
		end
	end
	
end

function ser (tabl)
	local str = string.char (10) .. "{"
	for i, v in pairs (tabl) do
		if type (v) == "table" then
			str = str
			str = str ..ser (v)
--			str = str .. string.char (10)
		elseif type (v) == "number" then
			str = str .. math.floor(v*255)
		else
			str = str .. v
		end
		str = str .. ','
	end
	return str .. "}"
end

function love.keypressed(key, scancode, isrepeat)
	if key == "space" then
		pause = not pause
	elseif key then
		map_n = map_n + 1
		load ()
	elseif key == "r" then
		load ()
	elseif key == "s" then
		map_n = math.max(1, map_n - 1)
		load ()
	elseif key == "k" then
--		love.filesystem.write( "test.lua", table.show(map, "loadedhero"))
--		love.filesystem.write( "test.lua", "a")
--		love.filesystem.write( "test.lua", "b")
		love.filesystem.write( "map-"..map_size..".lua", "return	" .. ser (map))
	elseif key == "f11" then
		fullscreen = not fullscreen
		love.window.setFullscreen( fullscreen )
		
	elseif key == "escape" then
		love.event.quit()
	end
end
Sorry for image brightness
Attachments
If you look close you can see the black dots
If you look close you can see the black dots
Screenshot_2021-07-31-22-44-29.png (45.79 KiB) Viewed 9956 times
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Diamond Square Procedural Map Generation

Post by Gunroar:Cannon() »

darkfrei wrote: Tue Jun 22, 2021 8:12 pm
Gunroar:Cannon() wrote: Tue Jun 22, 2021 7:32 pm So it's like Perlin/Simplex noise. Can it go on forever or only a defined size can be generated when you want it(good either way).
.
You can add another square near the old one.
Smallest field is 3x3, the next one is 5x5, the next one is 17x17. Yeah, side = 2^N + 1.
Wait, will the map continue or will it be different?
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: Diamond Square Procedural Map Generation

Post by darkfrei »

Gunroar:Cannon() wrote: Wed Aug 11, 2021 8:03 pm
darkfrei wrote: Tue Jun 22, 2021 8:12 pm
Gunroar:Cannon() wrote: Tue Jun 22, 2021 7:32 pm So it's like Perlin/Simplex noise. Can it go on forever or only a defined size can be generated when you want it(good either way).
.
You can add another square near the old one.
Smallest field is 3x3, the next one is 5x5, the next one is 17x17. Yeah, side = 2^N + 1.
Wait, will the map continue or will it be different?
You are need at least fourth base points, all another points are just interpolation of them.
But you can also make 6, 8 (for rectangles, not square) or another amount of base points.

The middle point of that base points can be also fixed, the interpolation is not necessary.
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
pgimeno
Party member
Posts: 3541
Joined: Sun Oct 18, 2015 2:58 pm

Re: Diamond Square Procedural Map Generation

Post by pgimeno »

It's possible to make it seamless, but there are still artifacts at the seams. Perlin noise also suffers from something similar, incidentally, but not simplex noise from what I've read. I haven't seen a decent simplex noise generator to check.
Attachments
diamondSquareSeamless.love
(2.27 KiB) Downloaded 263 times
User avatar
Gunroar:Cannon()
Party member
Posts: 1085
Joined: Thu Dec 10, 2020 1:57 am

Re: Diamond Square Procedural Map Generation

Post by Gunroar:Cannon() »

pgimeno wrote: Thu Aug 12, 2021 11:23 pm It's possible to make it seamless, but there are still artifacts at the seams. Perlin noise also suffers from something similar, incidentally, but not simplex noise from what I've read. I haven't seen a decent simplex noise generator to check.
Wow, nice pgimeno! You're really smart. But it seems to complicated for me to implement in my project. I generate different maps for different positions (corner)
1: x=0,y=map_size
2:x=map_size,y=map_size*2
...
It seems to work but sadly I can't get canvases split into chunks :cry: .
The risk I took was calculated,
but man, am I bad at math.

-How to be saved and born again :huh:
Post Reply

Who is online

Users browsing this forum: No registered users and 14 guests