Dan_Patterson

Terrain creation.... diamond-square algorithm

Blog Post created by Dan_Patterson Champion on Dec 27, 2017

Natural terrain is so fickle.  Wouldn't it be nice to have a sink-less terrain so that your flowdirection, flowaccumulation and stream generation would go as nature planned.

 

If you have a need to test algorithms, then natural surfaces aren't the best, but generating artificial terrain can be a pain.  They tend to have repetitive patterns and lack the finesse that real surface has.  

 

This is a brief look at one of the many algorithms that have been employed in early gaming software and largely ignored by the 'derivative' people.  The algorithm is pretty simple.... provide random seeds to the corners of a square array/raster, then divide it into triangles and squares in a predictable fashion calculating the averages of the intervening space, assigning the central location, the value of the pattern points.  Now, to mix it up, one can add some randomness to the calculated values to 'roughen' the surface to so speak.

 

The following is the sequence of the pattern generation... the code is on my GitHub account and the Code Sharing site for those that want to explore on their own.  I repurposed an implementation adding a few twists, like leaving out the random jitters and the ability to replicate in both rows and columns should you want to generate a surface with some repetition.

 

More importantly, this is for fun and is a good way to learn how to use numpy arrays to work with array data that forms images or rasters in the GIS sense of the term.

 

Input template array with 4 corners defined...  The empty space is represented
by 'nan' aka, 'not a number', you could use zero, but 'not a number' is a
raster null, without having to get into the issues of masks and the like.

Step 1... throw in 4 corners

[[ 0.250  nan  nan  nan  nan  nan  nan  nan  0.750]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.500  nan  nan  nan  nan  nan  nan  nan  1.000]]

Step 2... calculate the central location...

[[ 0.250  nan  nan  nan  nan  nan  nan  nan  0.750]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  0.625  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.500  nan  nan  nan  nan  nan  nan  nan  1.000]]

Step 3...
Split into the diamond structure and calculate the compass points

[[ 0.250  nan  nan  nan  0.542  nan  nan  nan  0.750]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.458  nan  nan  nan  0.625  nan  nan  nan  0.792]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.500  nan  nan  nan  0.708  nan  nan  nan  1.000]]

Step 4....
Calculate the central values for the squares

[[ 0.250  nan  nan  nan  0.542  nan  nan  nan  0.750]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  0.469  nan  nan  nan  0.677  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.458  nan  nan  nan  0.625  nan  nan  nan  0.792]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ nan  nan  0.573  nan  nan  nan  0.781  nan  nan]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.500  nan  nan  nan  0.708  nan  nan  nan  1.000]]

Step ....
Repeat......
[[ 0.250  nan  0.420  nan  0.542  nan  0.656  nan  0.750]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.392  nan  0.469  nan  0.578  nan  0.677  nan  0.740]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.458  nan  0.531  nan  0.625  nan  0.719  nan  0.792]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.510  nan  0.573  nan  0.672  nan  0.781  nan  0.858]
[ nan  nan  nan  nan  nan  nan  nan  nan  nan]
[ 0.500  nan  0.594  nan  0.708  nan  0.830  nan  1.000]]

Repeat
[[ 0.250  nan  0.420  nan  0.542  nan  0.656  nan  0.750]
[ nan  0.383  nan  0.502  nan  0.613  nan  0.706  nan]
[ 0.392  nan  0.469  nan  0.578  nan  0.677  nan  0.740]
[ nan  0.463  nan  0.551  nan  0.650  nan  0.732  nan]
[ 0.458  nan  0.531  nan  0.625  nan  0.719  nan  0.792]
[ nan  0.518  nan  0.600  nan  0.699  nan  0.787  nan]
[ 0.510  nan  0.573  nan  0.672  nan  0.781  nan  0.858]
[ nan  0.544  nan  0.637  nan  0.748  nan  0.867  nan]
[ 0.500  nan  0.594  nan  0.708  nan  0.830  nan  1.000]]


Step.... finally... all the squares and triangles are filled in

[[ 0.250  0.351  0.420  0.488  0.542  0.604  0.656  0.704  0.750]
[ 0.342  0.383  0.443  0.502  0.559  0.613  0.663  0.706  0.732]
[ 0.392  0.427  0.469  0.525  0.578  0.630  0.677  0.714  0.740]
[ 0.438  0.463  0.503  0.551  0.601  0.650  0.694  0.732  0.754]
[ 0.458  0.493  0.531  0.577  0.625  0.673  0.719  0.757  0.792]
[ 0.496  0.518  0.556  0.600  0.649  0.699  0.747  0.787  0.812]
[ 0.510  0.536  0.573  0.620  0.672  0.725  0.781  0.823  0.858]
[ 0.518  0.544  0.587  0.637  0.691  0.748  0.807  0.867  0.908]
[ 0.500  0.546  0.594  0.646  0.708  0.762  0.830  0.899  1.000]]

 

Of course, the image that follows uses a much larger array (1025x1025).  The generated array, was sink-less, and flow properties and a stream network was generated from the result.  Pretty smooth eh?

 

Next up... terrain generation from polygons and other vector geometry

Outcomes