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:

Comments

  • dave1707dave1707 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.

  • 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

    :D

  • dave1707dave1707 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 --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 [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) -- 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).

  • 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
    
Sign In or Register to comment.