Page 1 of 1
Simple midpoint displacement terrain generation
Posted: Sun Jul 24, 2011 6:02 pm
by ivan
A while ago I was playing around with some terrain generation algorithms in the AGen engine and decided to port one of my scripts to Love2D. Check out the attached .love demo. The space bar generates a new map.
Some limitations of the algorithm include:
-maps dimensions must be power of 2
-the algorithm is implemented recursively which is not very efficient
-although fast, the output is not as good as diamond/square
Re: Simple midpoint displacement terrain generation
Posted: Sun Jul 24, 2011 6:18 pm
by GijsB
its nice
maybe a good idea,try creating the beginging middle point somewhere else
Re: Simple midpoint displacement terrain generation
Posted: Sun Jul 24, 2011 6:20 pm
by kraftman
ivan wrote:A while ago I was playing around with some terrain generation algorithms in the AGen engine and decided to port one of my scripts to Love2D. Check out the attached .love demo. The space bar generates a new map.
Some limitations of the algorithm include:
-maps dimensions must be power of 2
-the algorithm is implemented recursively which is not very efficient
-although fast, the output is not as good as diamond/square
Does light/dark represent relief? It seems to be black in the center quite a lot, and sometimes you can see distinct lines between quadrants
Re: Simple midpoint displacement terrain generation
Posted: Sun Jul 24, 2011 6:21 pm
by GijsB
kraftman,
i think how darker how higher, and why the middle is always dark is because that's the first point
(atleast that's what i think)
Re: Simple midpoint displacement terrain generation
Posted: Sun Jul 24, 2011 8:44 pm
by Trappingnoobs
I like. It'd be more usefull if love had a 3D API, but it's rather hard to implement these sort of map generation techniques into a 2D engine. Unless you cut out one column and implemented that.
Re: Simple midpoint displacement terrain generation
Posted: Sun Jul 24, 2011 11:06 pm
by tentus
Very nice! Good old cloud filter, you are so handy in photoshop...
Ivan, I hope you don't mind, there was a feature I wanted, so I implemented it. Basically, space still generate a random map based on the os.time, but you can use backspace and the number keys to change your seed value manually, effectively allowing you to reproduce maps easily. Just enter in the key you want and hit return. The seed value is shown at the bottom of the window. Also, the window is smaller and has a caption, and Escape quits.
Re: Simple midpoint displacement terrain generation
Posted: Mon Jul 25, 2011 12:16 am
by GijsB
my own made one from scrath(in 1 hour o_e)
(this was first actualy a begin of diamond sqaure algorithm thingy, but i dont really understood the sqaure step ._.)
Code: Select all
irritations = 9--sorta size
math.randomseed(os.time())
sqaures ={
{
{0,0,math.random(1,4)},--left up
{10,0,math.random(1,4)},--right up
{0,10,math.random(1,4)},--left down
{10,10,math.random(1,4)},--right down
}
}
rratio = 2^irritations
ratio = 2^irritations
function routine()
for i = 1,#sqaures do
v = sqaures[i]
np1 = {--middle
(v[1][1]+v[2][1]+v[3][1]+v[4][1])/4,
(v[1][2]+v[2][2]+v[3][2]+v[4][2])/4,
(v[1][3]+v[2][3]+v[3][3]+v[4][3])/4+math.random(-ratio,ratio)
}
np2 = {--top middle
(v[1][1]+v[2][1])/2,
(v[1][2]+v[2][2])/2,
(v[1][3]+v[2][3])/2
}
np3 = {--right middle
(v[2][1]+v[4][1])/2,
(v[2][2]+v[4][2])/2,
(v[2][3]+v[4][3])/2
}
np4 = {--bottom middle
(v[3][1]+v[4][1])/2,
(v[3][2]+v[4][2])/2,
(v[3][3]+v[4][3])/2
}
np5 = {--left middle
(v[1][1]+v[3][1])/2,
(v[1][2]+v[3][2])/2,
(v[1][3]+v[3][3])/2
}
s1 = {v[1],np2,np5,np1}--left up
s2 = {np2,v[2],np1,np3}--right up
s3 = {np5,np1,v[3],np4}--left down
s4 = {np1,np3,np4,v[4]}--right down
sqaures[i] = s1
table.insert(sqaures,s2)
table.insert(sqaures,s3)
table.insert(sqaures,s4)
end
end
for i = 1,irritations do
routine()
ratio = ratio/2
end
imgData = love.image.newImageData(512,512)
for i,s in pairs(sqaures) do
for i,p in pairs(s) do
c = p[3]
--if c <= 0 then
--imgData:setPixel(p[1]*50, p[2]*50, 0, 0, 255, 255)
--elseif c < rratio/6 and c > 0 then
--imgData:setPixel(p[1]*50, p[2]*50, 255, 246, 143, 255)
--elseif c >= rratio/6 and c < rratio/6*5 then
--imgData:setPixel(p[1]*50, p[2]*50,0, 255, 0, 255)
--elseif c >= rratio/6*5 then
--imgData:setPixel(p[1]*50, p[2]*50,255,255,255, 255)
--end
if c < 0 then
c = 0
end
imgData:setPixel(p[1]*50, p[2]*50,c*(255/rratio),c*(255/rratio),c*(255/rratio), 255)
end
end
img = love.graphics.newImage(imgData)
function love.draw()
love.graphics.draw(img,0,0,0,1,1,0,0)
end
Re: Simple midpoint displacement terrain generation
Posted: Mon Jul 25, 2011 2:18 pm
by ivan
Hey, that's pretty cool, tentus.
However, I left a bug in the code while porting it to Love2D.
In theory, map sizes should be power of 2 + 1 (513x513 instead of 512x512).
Notice the commented assertion:
Code: Select all
--local pow2 = (nw - 1)/2
--assert(math.floor(pow2) == pow2)
Also, the displacement variable (dis) is the maximum random value by which the terrain can change between cells.
This value is hard coded at 0.5 and is divided by 2 after each recursive call to "midpointDis".
Increasing the 'dis' value should generate more contrasting terrain although this is not too visible since the heights are later normalized between 0 and 1 (for easier rendering).
The following is the entire algorthm:
Code: Select all
-- Midpoint displacement algorithm (recursive)
function midpointDis(l, t, r, b, d)
local cx = math.floor(l + (r - l)/2)
local cy = math.floor(t + (b - t)/2)
local lt = map[t][l]
local rt = map[t][r]
local lb = map[b][l]
local rb = map[b][r]
local a = (lt + rt + lb + rb)/4
local dis = math.random()*(d*2) - d
a = a + dis
map[cy][cx] = a
map[t][cx] = (lt + rt)/2
map[b][cx] = (lb + rb)/2
map[cy][l] = (lt + lb)/2
map[cy][r] = (rt + rb)/2
if r - l > 2 and b - t > 2 then
local hd = d/2
midpointDis(l, t, cx, cy, hd)
midpointDis(l, cy, cx, b, hd)
midpointDis(cx, t, r, cy, hd)
midpointDis(cx, cy, r, b, hd)
end
end
Re: Simple midpoint displacement terrain generation
Posted: Tue Jul 26, 2011 8:25 am
by Taehl
Pretty nice. It seems to me that if this is supposed to be making terrain heightmaps, though, that it has too much of a tendency to create big horizontal and/or vertical lines, and sometimes it'll put them together and make diamonds. Not very natural.
Re: Simple midpoint displacement terrain generation
Posted: Tue Jul 26, 2011 5:30 pm
by GijsB
taehl,
that's exact the problem of the midpoint displacement technic xD