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.

River networks generation for game terrains

Small disclaimer: This post will be a bit off topic - when looking on a title of my blogs here, yet this something that I am interested in.

Generating of realistic looking rivers with branching for computer games is not an easy task. First, I talk here about large-scale maps, in games like Settlers, where a player is looking on the map from upside perspective. Of course drawing maps manually is quite possible and sometimes easier and less time consuming, but on the other hand purely random rivers have specific look, similar to terrain generated via fractals algorigthms, f.e. diamond-square algorithm.

In fact initially my idea was to use terrain generated by diamond square algorithm and put rivers there. It is not easy, at all. My second attempt was rivers generated randomly and fractal mountains created around them. This works. Though my rivers just do not branch. They are just lines growing thicker near to the lake where they flow to. Here is screenshot from finalized map used in Widelands game:

.

Both game and map (can be downloaded from homepage, map separately from section 'maps', look for Sprider Lake map) are free, so you can look at the map in details.

Such (no branching rivers) are not bad but still...

So here I present..

...my attempt to create branching rivers.

Ideas and/or assumptions I used are:

• Rivers are created of rain water.
• The amount of felt rain water is the same everywhere (this is something that can be modified of course)
• Rainwater do not soak into ground and do not evaporate (this would be easy to implement though)
• No erosion and deposition is taking place (in fact the map has no height defined in this stage at all)
• The land (map) is made of squares and each of them has a slope and water from it is flowing to one and only one of 8 neighbors.
• The "end points" are to be defined beforehand. All water that flow will end in one of end points. No random lakes are generated on the map.
• When map is generated the way that you can track every single drop (water originating on a field) to one of endpoints.
• You can count number of drops flowing over every single square and use threshold to say "this is small or big river here, or no river at all"
• Map wraps (expected from such maps)

Algorithm:

We have grid and every field (square) can has 2 states:

• directed (we can say 'processed' as well): the square has an arrow on it or circle meaning endpoint of rivers
• the other (not directed yet) quares

Rivers are generated in iterations, on the image below every picture presents one iteration. Steps within iteration are:

1. Get list of fields that have at least on adjacent field in "directed" state
2. Choose some of fields from the list (not all)
3. For every selected field identify all directed neighbors pick one of its neighbors and put an arrow on the field pointing to that neighbor. (It becomes directed from now on)
4. Repeat iteration (iterate until all pixels are directed)

And almost all :). The step by step progress is shown here:

Well rivers on the last image are bit funny or ugly, but on larger-scale they looks better, see below.

But return one step back - to get a rivers we have to track every single drop from source square to one of endpoints and every square on map has count of drops that passed over it. So here in this map 12x12 drops will end in the end point.

Rivers itself are generated based on thresholds, every single pixel that exceeds a threshold is made into river. 

On my sample images the shade reflects amount of water on the fields, but in real game the thickness of rivers might be modified. 

Here is the example of final river networks, and with two "end points". Also note wrapping in action...

Also, modifications to algorithm are possible, f.e. you can manipulate amount of rained water, or create spring wells. But here I used other feature - I created "obstacles" - see image below. Pixels in red are impassable for water, and as you see my algorithm put random crosses on map to simulate mountains. Also you can notice there were isolated square sections created where no water is flowing from...

Of a lot of work remains until the scheme is made into playable map, but this is not a part of this blog post.

I hope the algorithm is obvious enough:)

If any questions feel free to ask, I am interested in any feedback