How to create a realistic river without knowing the whole map beforehand?

Question

Intro

I'm developing a real time game that have dynamically generated map and I'd like to add rivers going from mountains to the sea.

Brief info about the map

In my game, when a player moves to the edge of currently generated map, new chunks (small, square piece of map) of map are being loaded on server. If there are no chunks found for the requested location, they are generated using the same seed which is used in other parts of map. Currenly, there is no limit in map size or total amount of generated chunks. I'm using Perlin noise to generate the map. I treat it as a hight map, with every field having a range of values it occupy e.g. shallow water starts from -0.12 inclusive ending on 0 exclusive.

I already read about how to make the river look realistic:

• Is my river map even remotely realistic?
• How do I simulate the path of a river?
• Creating a realistic world map - Waterways

Question

How do I add rivers to the map when I don't know how the whole maps look like? If I don't know where the mountains are I cannot place the river source. And if I have some part of the map already generated I cannot just add the river a little later when a player encounters a mountain chain.

Similarities

Similar scenario (I think) is in Minecraft. There too, map generates as player moves using a seed and there are rivers which continue to swirl while the map generates on. Sadly, I don't know the technique used there.

Screens from the game

Chunk loading temporarily disabled, to show the boundaries:

Answer 1

The problem is unsolvable as asked. You may end up generating a river which the player traces back to the top of a minor hill in the middle of a desert.

There are a few alternatives that can make this work:

LOD and physics:

You can sub- and super- sample perlin noise in order to create multi-resolution maps. If your tiles there are 1 tile per 1meter, you can create the entire map at a more manageable level, say 1 tile per 1km, calculate realistic spring points and a rough river path, and then subdivide down, to say 1 tile per 100m - at that level you know where the river flows to an accuracy of within 10 tiles, work out where the river flows along that path, and then where the river flows through those smaller tiles recursively, etc, until you arrive at your full detail level.

It's better to precalcualte this and store it, if possible. You can still run this on-demand, but it's not trivial to code.

LOD and 1D perlin

As above, on your low resolution map, find the high point where a spring would come from, find the closest sea level point, draw a straight line. Now use 1D perlin noise to make the river wind perpendicular to the line.

This is much easier to code - it can have some unrealistic artefacts, but for a 2D tile game like this you're unlikely to notice them.

Fake it

Have 2 styles of rivers. One going "uphill", one going "downhill". Create tiles to show the river coming from a spring and forming in to a full river, and one showing a full river draining into a small below ground feature.

If the perlin noise value for a coastal area is a very precise value, then it spawns an "uphill" river. This travels to the highest edge point in the tile which doesn't border an explored tile, which then when the next tile loads, goes to the next highest point. If it detects it's gone to a local max (there's no higher point) or all neighbouring tiles were already explored, backtrack to about the middle, put a tile which shows the river coming out of a cave or spring or something else below ground, so the user doesn't see the river starting from the top of a small hill.

If the perlin noise value for a mountain is a very precise value, then it spawns a "downhill" river, follow to the lowest other border of an unexplored tile, and if it gets to a local minimum, or a chunk with no unexplored neighbours, put a tile in which shows the river disappearing below ground.

This is usually good enough for a tile based 2D game.

2 (or more) perlin channels

Currently you're running the perlin generator once per tile, to give a single value. I'd suggest run it multiple times per tile (with different seeds of course, and usually different scaling factors). The use those multiple values to populate the tiles, instead of just one;

This can help break the expectation that beech is next to plains, plains is usually next to forest, forest is usually next to mountains, etc.

If you run it twice - I'd suggest humidity and elevation. If you run it 3 times, I'd suggest feature size (sand / rock, ice / snow, or baren -> grassland -> scrub -> trees), humidity (desert -> fertile -> river -> swamp), and elevation (water -> plains -> hills -> mountains). 4 times maybe would include a temperature too.

Rather than focus on running your river "downhill", try to run it where the humidity is within a particular contour range. While the river wont "realistically" flow downhill, in a tile game like what you're showing elevation is obscured, you're better off ensuring that trees grow near rivers, rivers aren't bordered by desert, and the land near rivers is fertile farmland.

Answer 2

How do I add rivers to the map when I don't know how the whole maps look like? If I don't know where the mountains are I cannot place the river source. And if I have some part of the map already generated I cannot just add the river a little later when a player encounters a mountain chain.

You cannot do it entirely within a chunk. If you are on the edge of a chunk and there appears to be a local minimum you have two choices.

1. Extend the terrain invisibly around the minimum until you find the perimeter of that minimum in the as yet unexplored chunk. You don't have to complete the whole of the new chunk because by then you know where the pool will drain to. This will either be back into the current chunk or to somewhere, as yet incomplete, in the not yet explored chunk. In other words you have to extend beyond what is visible/has been explored. You could call this just-in-case programming.

2. Have a deterministic algorithm that deals specifically with this eventuality. I.e. deliberately close off any possible outlets into the new chunk. Effectively you have built a dam. This will almost certainly lead to fake-looking artefacts.

Note that using local minima in this way (assuming non-permeable terrain) will allow the grain to be as fine as you wish. This could even allow you to show springs and other small sources of the river.

Answer 3

Some years ago I wrote an algorithm for an RPG game that worked in similar way.
Think in "Minesweeper". When you discover a mountain square there is a x% probability there will be water. But that square influence probability of chunk next to it being mountain. Which influence the appearance of water. For each map you might impose water sources. Map is started from a range 0-100 number is chosen. It's the amount of water sources. The more the map is un-shadowed the more probability of water showing up rise.

Now, to aid you nature came with this nifty thing that brooks appear and then it seep into crack and dissapear. Nowaday with modern technology we can trace where it come back but in "discovery" phase one source might show as 3 or 4 different brooks. SO they don't need to be one continous line from discovered source to "somewhere". It might end after 4 or 5 chunks.

So you might just end the water generated chunks when player meet already discovered "dry" chunk.
OR

Create a fun change in your map. With time (player move) dry chunk became wet ones when generator try to link biggest water "puddle" (if lower). Generator might also have probability of creating creek so it won't go in straighest line.

Remeber that your player act a typical human. So they might discover river source, it might flow into undicovered regions but just by divocery and their presence they change how the water flow.

Answer 4

The simplest algorithm is for rivers to "snap" to a mountain valley whenever an existing river is within some threshold distance (and perhaps angle) to a valley that meets the minimum requirements.

Let's say you have a river generated by whatever algo you happen to be using. There is no existing source yet, and it ends at the "fog of war" on your map. But the player moves to reveal that, and you use the algo to again generate the missing pieces.

Presuming that your algo occasionally generates mountains, if mountains/valleys are created withing n units from the "end" of the river and at any angle shallower than +/-45 degrees of the tangent of the river, then generate a river path from that point to the mountain valley and place a glacier there.

If the river endpoint is farther away than n units, start to generate its path and if that path comes within n units of the valley, do as above.

It would be necessary to generate mountains first, and then overlay the river on top of such a map.

You might even manage to allow it to connect to several mountain/valleys if there are multiple potential sites, and this would give you tributaries feeding into a main sea-bound river.

This of course relies on a two-part map generation scheme, where most map features are generated, and rivers are "painted" onto the top of that. It would work for Minecraft, for instance, which I believe does this. If your game were more sophisticated and used elevation to determine the paths of rivers, this would be unviable.