A Method for 'Growing' Rivers

A Method For 'Growing' Rivers In A Randomly Generated World

|| Home ||

In response to a question on rec.games.roguelike.development, I coded up a demo on how one might make randomized rivers that originate in a part of the world that hasn't been generated yet.

The Problem

You are building a world region by region (as the player explores them), so you do not the the layout of the entire planet in advance. How to create long rivers that can span into regions that haven't be created yet? I'll present here an explanation of how this can be done and provide a demo written in Python.

Summary of Algorithm (Although it's simple enough to almost not qualify as an algorithm!)

Suppose you generate a 20X20 area of the world that looks like this:

. . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~          ~ = water
. . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~          . = plains
. . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~          # = trees
. . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~          ^ = hills/mountains
. . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~
^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~
^ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~
^ ^ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~
^ ^ ^ ^ ^ . . . # # # . . . . . . ~ ~ ~
^ ^ ^ ^ ^ . . # # . . . . . . . . . ~ ~
^ ^ ^ ^ ^ ^ # # # # . . . . . . . . . ~
^ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .

Your world generation algorithm determines this lake/ocean will have a river flowing into it. Start drawing a river backwards from the ocean. For my simple demo, I used the following stopping condition for the river: If river was about to cross from an area of higher elevation to an area of lower elevation, terminate the loop. Additionally, I started with a 5% chance of terminating the river and each time the drawing loop iterates, I increase that by 5%.

One particular run of my demo made the following map:

. . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
^ . . . . . . . . . . ~ . ~ ~ ~ ~ ~ ~ ~
^ ^ . . . . . . . . ~ . . . ~ ~ ~ ~ ~ ~
^ ^ ^ . . . . . . ~ . . . . . ~ ~ ~ ~ ~
^ ^ ^ ^ . . . . ~ . . . . . . . ~ ~ ~ ~
^ ^ ^ ^ ^ . ~ ~ # # # . . . . . . ~ ~ ~
^ ^ ^ ^ ~ ~ . # # . . . . . . . . . ~ ~
^ ~ ~ ~ ^ ^ # # # # . . . . . . . . . ~
~ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .

If your river reaches the border of a region, again terminate it. (Note that it should also terminate before crossing into region that has already been generated, my demo doesn't do this). At this point, you need to store the fact that a river has terminated at a border of the region. Python is OOP-enabled, so it was quite easy for me to add this information to the region class. I stored the instance of the terrain, it's coordinates and the last move the drawing algorithm was about to make (so I can continue drawing it in the same general direction when it is time to build the next region).

When the player cross into an previously unexplored region, you will have to pass the details of already generated neighbouring regions, providing access to their lists of border features. If a neighbour is null, it hasn't been made yet and can be ignored. In the demo, when a new region is made, we see that it has a neighbour to the east, and that a river terminated at the border (row 12, column 0). After the new region is created, we need to draw a river starting at (row 12, column 19). Using the same algorithm, we draw until we hit a termination condition. In this case, the river started in the hills, so it will continue until it hits a border, or is about to cross from the hills (high elevation) to the plains (lower elevation).

A sample run of my demo produce:

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
# # # # # # # # . . . . . . . . . . . .
# . . . . . . . . . . . . . . . . . . .
# # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# # # . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# # # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^
# # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^
# # # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^
# # # # # # # . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# # # # # # # . . . . . . . ^ ^ ^ ^ ^ ~
# # . . . . . . ^ ^ ^ ^ ^ * ^ ^ ^ ^ * ^
# # # # . . . . . . ^ ^ ^ ^ * ^ ^ * ^ ^
# # # # # # # # . . ^ ^ ^ ^ ^ * * ^ ^ ^
# # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^
# . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
. . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^
. . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

(The river created is marked with *'s so they stand out a little better).

Putting them side by side:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
# # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
# # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . . ~ . ~ ~ ~ ~ ~ ~ ~
# # # . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . ~ . . . ~ ~ ~ ~ ~ ~
# # # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . ~ . . . . . ~ ~ ~ ~ ~
# # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . ~ . . . . . . . ~ ~ ~ ~
# # # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . ~ ~ # # # . . . . . . ~ ~ ~
# # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ~ ~ . # # . . . . . . . . . ~ ~
# # # # # # # . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ~ ~ ~ ^ ^ # # # # . . . . . . . . . ~
# # # # # # # . . . . . . . ^ ^ ^ ^ ^ ~ ~ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
# # . . . . . . ^ ^ ^ ^ ^ * ^ ^ ^ ^ * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
# # # # . . . . . . ^ ^ ^ ^ * ^ ^ * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
# # # # # # # # . . ^ ^ ^ ^ ^ * * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
# # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
# . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
. . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . .
. . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .

A nice, slightly winding river is created in one region, then continued in the bordering region when it comes time to generate the neighbour.

Notes About The Demo

The demo was slapped together in about an hour, so please don't judge my coding skills on it! It probably has bugs, invalid assumptions, poor coding standards/styles, inefficiencies and/or redundant code!
There are probably plenty of ways to generate nicer looking rivers, I just used a couple of ideas that popped into my head while coding. Mine often generates straight lines, which look silly (it took me a couple tries to get a nice looking river for this page). But again, that wasn't the point of the demo!
The termination condititions could be improved. For instance, if you are stopping because you are about to cross into another region, you could back the drawing up one square so it doesn't look like the river originates at the border of two elevations.
It would be neat to look for good likely termination points. Suppose a lake was generated at the same (or higher) elevation as the river, it would make a good candidate for a termination point. (Hmm - confusing terminology - when I speak of termination point, I mean where the algorithm stops drawing, which is the origin point for the river in the geographic sense)
The demo doesn't generate terrain, I don't know if my roguelike is going to have random or fixed wildernesses, I just wanted to offer a solution to the question on the newsgroup.
The demo is cooked to draw a river that starts at the lake and ends at the border of the first region (the cooked functions are labeled as such). See previous point.
My method only draws rivers from the mouth of the river backwards to the spring, but it woulddn't take a great leap to make a version that draws from a spring to a terminatition point. Indeed, since you would be drawing into a region that has not been determined, you could force the generator to create a nice termination point for your river.
Written and tested in Python 2.2.1, probably works with Python 2.x.x, might even work with Python 1.5.x

There are three main classes used in the demo:

Terrain - represents an individual square of terrain. Uses fields ch (the character to display), type (the type of terrain and elevation - integer saying how high the terrain is. I used ocean/lake = 0, plains/trees = 1 and hills = 2. An interesting idea would be to store a floating point number and use that to determine where the river should flow from the geography of the land?

Region - stores information about the section of the world this represents. In the demo, this is essentially a collection of Terrain squares and a little additional info used in the demo (such as the border features of this region). In a full game, this would need to store a fair amount of additional information.

RegionGenerator - builds a region of land. Note that in the demo, the regions are cooked and the river in the first region is partially cooked.

The code is offered without warranty or guarantee as an idea for folks writing map generators. If you want to use a substantial part of the code in your game, please ask permission. Here is grow_river.py.txt (named so because browsers sometimes complain about .py extentions, save it your harddrive and rename it grow_river.py before running).

You can reach me at dana@pixelenvy.ca with questions, suggestions, etc.