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