Heightmap generation using the Diamond Square algorithm — Part 1
An overview and C++ implementation
The algorithm
The Diamond Square algorithm is a method for generating random heightmaps. The algorithm can be applied on a two-dimensional square array with a size of 2ⁿ+1. As the name implies, the algorithm consists of two steps: the diamond step and the square step. The basic idea is to set a midpoint of a square as the average of the four corners plus a random value.
The diamond step: for each square in the array the midpoint is set to the average of the four corners plus a random value.
The square step: for each diamond the midpoint is set to the average of the four corner points plus a random value.
Here we are faced with the first problem that can arise when developing this algorithm. The midpoints on the side of the array will have only three values available to compute the average, with the fourth resulting out of the array bounds. Different strategies can be adopted to solve the problem. Here there are some: use a random value; use only the three available values; take the value from the other side of the array (wrapping).
In my implementation I’ve chosen to use only three values.
At each iteration the step size is halved as well as the multiplier for the random values. Choosing an high value for the random multiplier and initializing more squares before the algorithm starts allow us to obtain a more random result, with several areas having different ranges of values.
The implementation
I’ve implemented the algorithm in C++ with a class hierarchy that allowed me to implement different versions of the algorithm.
The first thing to do is to initialize the array with random values on the corners of the initial square(s). I use the step variable to identify the size of the initial square(s) and later during the execution the size of the sub-squares to be computed on each iteration. This value is also equal the distance between the midpoints of adjacent squares.
Once the array is initialized the algorithm can start to perform the necessary iterations, each consisting of a diamond step and a square step.
In the diamond step we make a pass on the midpoint of each square to be processed during the iteration. Knowing that the size of a square is equivalent to step it is sufficient to start from a value equivalent to step / 2 (half) and move by step to reach the next midpoint. The code is self-explanatory for the recovery of the corner values.
The square step cycles are a bit more complicated. I suggest to simulate the execution of the loops on a small array on paper to understand the meaning of indexing. Inside the loops we can find the necessary checks for the ghost values outside the array.
Results
Here are some images obtained with the algorithm. All images were generated in 4k in uncompressed bmp format and converted in compressed jpg. My implementation is capable of generating images up to 16k.
This is what can be achieved with a simple image coloring algorithm based on range of values and interpolation of colors. As you can see, by increasing the initial random multiplier and the number of randomly initialized squares different effects resembling a zoom-out are obtained.
Conclusions
I hope this article will be useful. There are few online resources regarding this algorithm and all of them discordant with each other, leading to confusion.
In the second part we will see a parallel implementation on GPU using CUDA.
You can find the source code on Github.