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!



  • dave1707dave1707 Mod
    edited January 2014 Posts: 9,977

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

  • 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:


  • dave1707dave1707 Mod
    edited January 2014 Posts: 9,977

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

  • Posts: 535

    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 --License: GPL V3 --Copyright (c) 2014 Tommy March -- This program is free software: you can redistribute it and/or modify -- it under the terms of the GNU General Public License as published by -- 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 []. -- 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"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) -- Do your drawing here 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 addline(linePoints[j], linePoints[j+1]) end end function addline(a,b) local v = b - a local p = a + v * .5 m:addRect(p.x, p.y, v:len(), 2, -v:angleBetween(vec2(1,0))) 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
  • Thanks! I've found in most places now that using any graphical drawing method other than mesh is unbearably slow, haha.

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

Sign In or Register to comment.