Simple midpoint displacement terrain generation

[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

[GijsB]

its nice

maybe a good idea,try creating the beginging middle point somewhere else

[kraftman]

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

[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)

[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.

[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.

[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

[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

[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.

[GijsB]

taehl,

that's exact the problem of the midpoint displacement technic xD