#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# 1.5d Procedural Generation using Midpoint Displacement

edited January 2014 in Examples Posts: 68

On Codea Community, I just uploaded a midpoint displacement algorithm for anyone that is interested. It could be used, for example, to procedurally generate backgrounds for side-scrolling games.

Something I've noticed: the random number generator seems to have very predictable patterns, as you may be able to see when moving the seed slider. Clearly the algorithm used could be better!

Tagged:

• Mod
edited January 2014 Posts: 7,810

@Causeless Interesting program. Setting the passes to 5 and the roughness to .5 and sliding the seed back and forth reminds me of an electrical arc. The random number generator is a pseudo random number generator. The same seed will result in the same string of numbers. You can't write a program to create random numbers.

• Posts: 68

Haha, yeah, I was thinking it could make a lightning effect, too! The actual generation code runs perfectly at 60fps, even with 10 passes, it's just the line drawing that slows it down, btw.

I understand how random number generators work, I just mean, there's a clear and obvious pattern where there shouldn't be. With seed = n and seed = n + 1, the results should be significantly different, but here there is a clear colleration between the seed and the resulting pseudo-random numbers, and is predictable (incrementing the seed results in the random value incrementing too).

• Posts: 580

Speaking of using this algorithm for a lightning effect:

http://twolivesleft.com/Codea/Talk/discussion/1142/a-crappy-plasma-globe

• Mod
edited January 2014 Posts: 7,810

@toadkick I totally missed that program back in June 2012. Nice effects. I wonder how I missed it.

• Posts: 502

Nice example. You can rewrite it using a mesh to keep the FPS higher.

``````--# Main
--------------------------------------------------------------
--Project: Midpoint Displacement
--Version: Alpha 1.2
--Author: Tommy March

--    This program is free software: you can redistribute it and/or modify
--    the Free Software Foundation, either version 3 of the License, or
--    (at your option) any later version.
--
--    This program is distributed in the hope that it will be useful,
--    but WITHOUT ANY WARRANTY; without even the implied warranty of
--    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
--    GNU General Public License for more details.
--
--    You should have received a copy of the GNU General Public License
--    along with this program.  If not, see [http://www.gnu.org/licenses/].

-- Midpoint Displacement

-- Use this function to perform your initial setup
function setup()
m = mesh()
startPoint = vec2(0, HEIGHT * 0.5)
endPoint = vec2(WIDTH, HEIGHT * 0.5)
linePoints = {startPoint, endPoint}
FPS = 60

parameter.watch("FPS")
parameter.integer("passes", 0, 10, 0, function() recalculate() end)
parameter.number("roughness", 0, 1, 0.5, function() recalculate() end)
parameter.integer("seed", 0, 100000, 0, function() recalculate() end)
math.randomseed(seed)
linePoints = midpointDisplacement(linePoints, roughness, passes)
end

-- This function gets called once every frame
function draw()
-- This sets a dark background color
background(40, 40, 50)

FPS = (FPS * 0.9) + (0.1 / DeltaTime)

-- This sets the line thickness
strokeWidth(2)

m:draw()
end

function drawLines(linePoints)
m:clear()
for j in pairs(linePoints) do
if j == table.maxn(linePoints) then -- if on last point, break from loop (as last point has no next one)
break
end

end
end

local v = b - a
local p = a + v * .5
end

function recalculate()
math.randomseed(seed or 0)
linePoints = {startPoint, endPoint}
linePoints = midpointDisplacement(linePoints, roughness or 0.5, passes or 0)
drawLines(linePoints)
end

--# MidpointDisplacement
function midpointDisplacement(linePoints, roughness, iterations)
newLinePoints = {}
tableLen = #linePoints
displaceRange = linePoints[1]:dist(linePoints[tableLen])

for i=1, iterations do
for j in pairs(linePoints) do
if j == tableLen then -- if on last point, break from loop as last point cannot connect to one after
break
end

local displacement = lerp(0, displaceRange, math.random()) - (displaceRange * 0.5) -- Because math.random with min/max only returns integers, also lerp is incorrect with negative numbers so work with positive then negate half of value

local midpoint = vec2lerp(linePoints[j], linePoints[j+1], 0.5)
midpoint.y = midpoint.y + displacement
table.insert(newLinePoints, midpoint)
end

for k in pairs(newLinePoints) do
table.insert(linePoints, k*2, newLinePoints[k])
end
tableLen = #linePoints
newLinePoints = {}

displaceRange = displaceRange * roughness
end
return linePoints
end

function vec2lerp(p0, p1, t)
return vec2(p0.x + (p1.x - p0.x) * t, p0.y + (p1.y - p0.y) * t)
end

function lerp(a, b, amount)
return (a + (b - a)) * amount
end
``````
• Posts: 68

Thanks! I've found in most places now that using any graphical drawing method other than mesh is unbearably slow, haha.

• Posts: 68

@Toadkick It's pretty cool, seeing the differences in implementation (you did a recursive appraoch, i did iterative).

• edited August 2015 Posts: 116

I made something similar, but mine could work faster(i say could, because i dont fully understand your code) :-\$

``````function setup()
size = WIDTH/2
points = {-0.1,HEIGHT/2,HEIGHT}
parameter.action("next",next)
parameter.integer("scl",1,100,1)
end
function draw()
scale(scl)
strokeWidth(1/scl)
background(40, 40, 50)
for num,pt in ipairs(points) do
if num > 1 then
line(size*(num-2),points[num-1],size*(num-1),pt)
end
n = num
end
end
function next()
for i = 1, n-1 do
table.insert(points, i*2,0)
points[i*2] = rndh(i*2)
end
size = size * 0.5
end
function rndh(number)
lim1 = math.floor(points[number-1])
lim2 = math.ceil(points[number+1])
if lim1 > lim2 then
return math.random(lim2,lim1)+math.random()
elseif lim2 > lim1 then
return math.random(lim1,lim2) +math.random()
else
return math.random(lim2,lim1) +math.random()
end
end
``````