Diamond-square algorithm with water erosion for game maps creation

This small work is to describe my experiences with generating maps for open source game Widelands. To get an idea visit https://www.widelands.org/maps/ and filter map by author ‘Tibor’ and ‘TiborB’ - both are me. My goal was and is to generate as realistic maps as possible. Part of my workflow is to import output of this map generation script (an txt file) into widelands editor. But this is out of scope of this my blog.

Diamond-square algorithm is great here, and very easy to implement. But if you look at real world terrain - local minimas are almost non-existent. I mean a complete valley completely encircled by slopes. The reason is that every point needs an water outflow way and is eventually connected to a sea that is generally lowest point on earth. With exception of few areas on the earth.

And diamond-square algorithm create local minimums and maximums as a feature.

What are basics of this algorithm:

• We start with raw diamond square filling up the TERRAIN array

• The water rains from sky as drops

• The number of drops is defined (parameter of scrip is drops per pixel)

• the lifetime of a drop is defined (parameter of scrip) as a number of iterations (epochs) and all drops live the same time

• each drop moves independently

• each iteration every drop “wake up” and looks if it can move downward

• multiple drops can be on the same spot

• TERRAIN is defined as 2D array and WATER is separate 2D array with count of drops per each field (pixel)

• individual drop in a water column on a single point does not have own “elevation”, we presume it is always positioned on the top elevation = TERRAIN[x,y] + WATER[x,y]

• Each drop initializes on random position and (as expected) increased water value in WATER 2D array

• Each drop when evaporates (after expiration of lifetime) decreases the water level on water 2D array

• When a drop moves it takes some soil with it if elevation difference is sufficient, so drop move changes WATER array always and TERRAIN array most of time

• Amount of moved soil is derived from TERRAIN[x,y] + WATER[x,y] differences between initial and target point. As a rule, final point terrain+water height cannot be higher than final terrain+water on starting point

• a drop can move only to one of 8 nearest points.

• erosion process wraps (map wrapping is also feature of diamond-square)

• exception to “each drop moved each iteration” - in fact only 3 drops from a single spot can move in each iteration. This is just a speed-up thing. Note that you can have water column high in hundreds.

• You can have rivers visible, but for the game map I used threshold for WATER values to have actual lakes visible only. So individual drops and rivers are usually very thin and gets filtered out

Here you can see example of erosion and over-erosion. So basically we can conclude that you need to pick right time to get map with expected features.

Also the last image indeed has more water than first because if drop lifetime is 300 iterations, the water will reach target amount only after 300 iterations. In fact I dont remember if final water amount was even achieved on the last image.

Ideas that might be considered:

• variations in soil hardness
• relation between evaporation and place of rain - simulation of a wind with static direction

But it is questionable if they are worth the effort

This is still work in progress, right now I have no material for part II, but I hope I will have some soon.