1.5d Procedural Generation using Midpoint Displacement

Causeless

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!

dave1707

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

Causeless

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

toadkick

Speaking of using this algorithm for a lightning effect:

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

dave1707

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

tnlogy

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

Causeless

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

Causeless

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