An extremely simple Erosion Algorithm

In this article I will Describe how and why I implemented a really simple Erosion Algorithm in Lua. The code can be found here and you can play around with the algorithm and the parameters. Generate a grid in the terminal simply by running: lua test.lua.

For a Love2D Game Prototype I was working on I needed to procedurally generate a, basic but believable, 2D hill terrain. Something like this:

Pixel art hills

One could use something like Perlin noise, but this is a really complicated algorithm that frankly I never managed to understand.

Another, in concept much simpler, Idea would be to simulate Erosion. After some googling I came across this GitHub Repository by GitHub user dandrino. The steps for simulating are described nicely in this chapter. The basic Idea is that water (e.g. rain) is running downhill and takes sediment with it.

I did not check out the code in said repository but after reading through the steps I came up with the following algorithm, which is basically a simplified version of the algorithm in the GitHub Repository:

Initialize a grid
Assign random heights for each column
Spawn a "raindrop" randomly
If the raindrop hits "sediment (non-empty cell) try to pull the sediment downhill

Dandrino's version is much more involved and considers, among other parameters, how much sediment can be dissolved in water, how steep the terrain is and evaporating water. But I wanted see how well this really simple algorithm works.

So let's go through the Algorithm step by step.

1 & 2 Initialize the Grid

Initially we simply generate a 2D array(nested tables in Lua) and set random heights to all columns. The array consist of empty cells, represented by " " and sediment, represented by "#"

function levelgen.rain.generate(sizex, sizey)
    local level = {}
    for x = 1, xsize do
        level[x] = {}
        for y = 1, ysize do level[x][y] = "#" end
    end
    return level

    for x = 1, #level do
        local height = math.random(#level[x])
        for y = 1, height do level[x][y] = " " end
    end

    return {level = level}
end

Basically we could stop here and hope our algorithm generated some nice hills already, but it will most likely look very chaotic :).

3 spawn and simulate the raindrops

In fancier simulations, determining the precipitation is a mayor factor in shaping how the result will look. But I simply randomly spawned sizex * 44 raindrops and that actually worked fairly well.

The Code simply does the following

Generate Raindrop at random X Position and Y Position = 1
Let the Raindrop fall down until it hits sediment (cell == "#)
If we hit sediment, check if the left or right neighbor cell are free and move there

How the sediment is moved will be described in the next step


function levelgen.rain.generate(sizex, sizey)

    --existing code in generate function same as before

    -- good working default I found by experimenting
    local steps = sizex * 44

    for i = 1, steps do levelgen.rain.spawn_raindrop(level) end

end

function levelgen.rain.spawn_raindrop(level)
    local spawnPosX = math.random(#level)
    levelgen.rain.simulate_raindrop(level, spawnPosX, 1)

end

function levelgen.rain.simulate_raindrop(level, posX, posY)

    if posY > #level[posX] then return end

    if level[posX][posY] == " " then
        levelgen.rain.simulate_raindrop(level, posX, posY + 1)
        return
    end

    -- try to move sediment somewhere else
    level[posX][posY] = " "

    -- where to next try to find
    if levelgen.isFree(level, posX - 1, posY) and
        levelgen.isFree(level, posX + 1, posY) then
        if (math.random(100) < 50) then
            levelgen.rain.move_sediment(level, posX + 1, posY)
        else
            levelgen.rain.move_sediment(level, posX - 1, posY)
        end
    elseif levelgen.isFree(level, posX - 1, posY) then
        levelgen.rain.move_sediment(level, posX - 1, posY)

    elseif levelgen.isFree(level, posX + 1, posY) then
        levelgen.rain.move_sediment(level, posX + 1, posY)
    else
        -- nowehere to move sediment. Setting sediment to where it was 
        level[posX][posY] = "#"
    end

end

4 Move sediment downhill

Moving the sediment is quite similar to how raindrops work. We recursively fall down, until we reach the bottom of the world or there is nowhere to flow to.

function levelgen.rain.move_sediment(level, posX, posY)

    -- reached the bottom. We have to stop here
    if posY > #level[posX] then
        level[posX][posY - 1] = "#"
        return
    end

  -- where to next
    if level[posX][posY] == " " then
        levelgen.rain.move_sediment(level, posX, posY + 1)
    elseif levelgen.isFree(level, posX - 1, posY) and
        levelgen.isFree(level, posX + 1, posY) then
        if (math.random(100) < 50) then
            levelgen.rain.move_sediment(level, posX + 1, posY)
        else
            levelgen.rain.move_sediment(level, posX - 1, posY)
        end
    elseif levelgen.isFree(level, posX - 1, posY + 1) then
        levelgen.rain.move_sediment(level, posX - 1, posY)

    elseif levelgen.isFree(level, posX + 1, posY + 1) then
        levelgen.rain.move_sediment(level, posX + 1, posY)
    else
        -- nowehere to move sediment. depositing above me
        level[posX][posY - 1] = "#"
    end
end

The generated terrain will become more and more flat if we increase the number of raindrops/steps. The value sizex * 44 is a good default. It mostly leads to neither too rugged or too flat terrain.

Here is an example using ASCI-art:

                                                             
                 ####                              #   ##### 
               #########                           ##########
               ##########                        # ##########
              #############                     #############
              ###############                 ###############
              ################                ###############
              ################               ################
              ##################             ################
              ###################           #################
              ################### ## #  # ###################
              ######################### #####################
             ################################################
            #################################################
           ##################################################
           ##################################################
          ###################################################
         ####################################################
         ####################################################
#       #####################################################
###   #######################################################
#############################################################
#############################################################
#############################################################
#############################################################

Eliminating columns

I think the results so far are pretty great, especially considering how simplified the algorithm was. The only annoyance I found is that sometimes weird columns are left standing. One simple solution is to simulate "wind" to collapse the columns. The rules for a cell could be as simple as: If a cell has no neighbor to the lower left and lower right, move the sediment down on either side.


function levelgen.rain.generate(sizex, sizey)

    --existing code in generate function same as before

    levelgen.rain.eliminateColumns(level)

     return {level = level}

end

function levelgen.rain.eliminateColumns(level)
    for x = 1, #level do
        for y = 1, #level[x] do
            if level[x][y] == "#" and levelgen.isFree(level, x-1, y + 1) and
                levelgen.isFree(level, x + 1, y + 1) then
                level[x][y] = " "
                if (math.random(100) < 50) then
                    levelgen.rain.move_sediment(level, x + 1, y + 1)
                else
                    levelgen.rain.move_sediment(level, x - 1, y + 1)
                end
            end
        end
    end
end

That's all you need for generating somewhat believable hills in around 100 lines of Lua. I'm fascinated again and again by procedural generation and how little code is necessary to generate cool results.

The code can be found here and you can play around with the algorithm and the parameters. Generate a grid in the terminal simply by running: lua test.lua.