Generating heightmaps using particle deposition

I recently started a small personal project where I wanted to generate heightmaps. More specifically, heightmaps that represent islands.

I remembered seeing something about this in my copy of Game Programming Gems, a book I had purchased years ago. I did not have the cd-rom with the code samples anymore, but this turned out great, as it forced me to work out a particle deposition algorithm by myself with the book’s textual description rather than just having the code handed to me.

The algorithm

Particle deposition is well suited to generate heightmaps that represent volcanic islands but can also be used for other types of maps.

The algorithm works by depositing particles on a flat surface. You can imagine the particles being dropped by a canon from overhead unto the surface. After each particle is shot, the surfaced will be agitated so that the particle will settle in its final location.

A particle is considered stable if it’s exactly one higher than all of its neighbors. Otherwise, when it is agitated it will fall into one of the lower neighboring positions. You can have a fixed or random order to determine which lower neighbor it will fall in.

The stability radius, or how far from a particle the algorithm will look for a lower neighbor, will help control the slope at the drop points. For these values I often use values from 1 to 3. The greater the value, the gentler the slope.

The other variables to control the generation of the heightmaps are the number of drop points, the number of particle per drop points and the number of passes.

The number of drop points is the number of times the particle canon will be moved during the process.

The number of particle per drop is how many particles will be launched at each drop point. I have obtained better results by using a random number that falls between a min and a max value that I can define.

Finally the number of passes. I don’t believe this is in the traditional version of the algorithm so you could probably do away with it. What it does is as the number of passes increase, the drop points get more focused towards the center of the map, the passes include less and less drop points and less and less particles are found in each drop points.

Pseudocode

Here is some pseudocode that gives an overview of the algorithm.

for each pass
    create drops // here I create a random number of particle objects
    set next drop point location // make sure it's not on the edge of the map
    
    for each drop
        for each particle
            drop  // increase value of int array at location
            agitate  // move particle to it's final resting place

     change variables for next pass

blur final results

Blur

After some experimentation, the secret for me has been blurring. Blurring is typically used to smooth out the maps at the end, but I have found out that rather then generating a lot of points, I could generate a lot less points and apply heavier blurring to get a satisfactory result much more rapidly. Blurring, if done correctly will allow to generate the map faster then generating more particles. This has been a real difference maker in my implementation.

Here is an example of how blurring can turn a map that looks sparse and unsatisfactory into something decent and usable.

Unfiltered heightmap

Filtered heightmap

I will cover how I used blurring in a following blog post which should come out in the following days.