Procedural river drainage basins

Note: the /x/ series of posts on my site are mostly unpolished mini posts. This was an exploration of some ideas which I ended up using in mapgen4^[1]. Also see the data structures I used^[2].

In my polygon map generator from 2010^[3] I first decided on the coastline, then grew mountains up from the coast, then made rivers flow down from the mountaintops, then created drainage basins (watersheds^[4]). It was cool but it’s not the only way to do things. This paper^[5] explores building rivers up from the coast and then assigns a height map to the match the drainage network. I thought that was a pretty cool way to do things! The paper is fantastic in many other ways — they make different types of rivers and streams based on velocity and slope, they build a hierarchy of procedural generation elements, and they can mix procedural and user-specified terrain elements — and it’s presented very nicely too. Great paper! I’m not going to do anything as advanced as what they did. I’m going to generate river basins first, then rivers, then assign elevation afterwards. I’ve always done it in the other order so this will be new and interesting for me.

Will this work out? I was optimistic at first but after working with it for a week I am becoming more pessimistic about finding a way to make elevation fit the generated river basins. update: also see the next week’s experiment^[6] for a followup.

SIGGRAPH paper#

I’m going to use the data structures from last week’s blog post about triangle mesh representation. The SIGGRAPH 2013 paper^[7] works on the Voronoi cells (white polygons) and assigns elevations to the Voronoi corners (blue points). A polygon can have three types of (white) edges:

1. Ridges: no water flows across this edge
2. Entry: water flows into the polygon from this edge
3. Outlet: water flows out of the polygon through this edge

There can be any number of ridges and entry edges, but only one outlet edge. Once the edges are labeled, they create a river path within the polygon. Here’s figure 12 from the paper showing a polygon with three entry (e) edges, two ridge edges, and one outlet edge (s):

They construct these river paths within a polygon based on the Rosgen classification^[8], which depends on slope and type of material (bedrock, stones, gravel, sand, etc.), and determines whether the river is meandering, braided, confined, muddy, etc. This is all pretty cool, and I recommend reading the paper for more details.

Triangle basin#

The paper presents a cool system but I wanted to try something inspired by, but different from, their approach. I’m working on the triangle level (black lines). This greatly reduces the complexity inside each land region. With only three edges, the possibilities are limited to:

1. Source: triangle has two ridges, zero entries, one outlet
2. Bend: triangle has one ridge, one entry, one outlet
3. Fork: triangle has zero ridges, two entries, one outlet

You can think of this as a binary tree^[9]. A source is a leaf node with no children. A bend has one child. A fork has both children.

In addition to these types of land regions, there will be water regions (oceans, lakes) that have no rivers running through them.

Random assignment#

The easiest thing to do is to randomly assign one of the four types to each triangle. It’s not going to work well but it’s something to start with. It’s mostly so that I can get the data representation and rendering working.

You can see two major problems here. One is that the triangles on the edge are terrible. I plan to put those under the ocean so I’m going to work around it by adding some points on the outer boundary. The other problem is that random water flow doesn’t always reach the ocean, and it might go in cycles. Let’s fix that.

Tree construction#

Starting from the exterior triangles, I can run breadth first search to visit all the triangles. I mark each triangle with one of the already visited neighboring triangles. That’s the direction the water will flow. Here are the drainage basins that form:

Looks better! All the water will reach the borders of the map. It’s all connected in a branching structure.

This structure is rather uniform. Everything flows to the nearest map border. It’s essentially a large four-sided pyramid with water flowing down each side. You can see the diagonals dividing the space up into four large triangles. Even though it’s procedural there’s not much variation. Try clicking on it to regenerate a new set of drainage basins; it’ll look almost the same.

Directing tree growth#

The uniform structure from the previous step was because I visited all nodes in breadth first search order. It uniformly walks up from the border of the map to the center of the map. Let’s apply a noise function to the walking order. The tree generator will prefer to move in a direction with lower values, but the noise won’t entirely determine the direction.

Hey, this is looking pretty cool. Click to generate another map. The drainage basins are no longer symmetric around the center of the map. These could form reasonable country borders. There are many different noise patterns that could produce different effects.

The algorithm is a hybrid between Breadth First Search and Dijkstra’s Algorithm^[10], and it builds a binary tree as output. On my 2013 laptop it runs at 1-3 million triangles per second (in javascript).

Strahler Number#

The previous diagrams made it easy to see the drainage basins, but I also want to see the structure inside each basin. I decided to use the Strahler Number^[11], a way of marking tree branches based on where they are in the tree.

• A source of a river (triangle type 1) is assigned 1
• A bend in the river (triangle type 2) with entry number a has outflow number a
• A fork in the river (triangle type 3) with entries a and b has outflow number a+1 (if a=b) or max(a,b) (if a≠b)

The higher the Strahler Number, the thicker the line in this diagram:

Hey, the rivers look reasonable. There’s some meandering in there too.

The algorithm is post-order binary tree traversal^[12]. On my 2013 laptop, it runs at 4-7 million nodes per second (in javascript).

Sketch directed drainage basins#

One of the goals in the game we’re working on is that designers can sketch their desired map, and the procedural generator will fill in the details. I sketched out a map in a drawing program, then made the drainage basin algorithm work with the image:

This works ok. The streams start in the mountains and flow towards the ocean. A game designer can sketch out the high and low elevation areas and the system will place drainage basins that fit. I’ll revisit this later.

Sketch directed rivers#

The designer may also want to decide where a river goes. Try drawing a path; the procedural drainage basin generator will try to make rivers follow that path.

This works reasonably well. This algorithm almost always has a river following the path you drew. Here’s a map I drew with rivers; the generated rivers almost all match my hand-drawn rivers:

This would allow a game designer to choose the major land masses, oceans, and rivers, and then the procedural terrain generator would figure out how to fill in the rest.

Next steps

This blog post is about procedurally building the drainage basins. I’m reasonably happy with them. I’m not making all the patterns from here^[13] but it’s enough variety for now. Although I drew the rivers with the Strahler Number, it doesn’t offer the variety I want.

1. Not all triangles should contain a stream/river
2. Some areas of the map should get more rainfall than others

I’ll revisit these later; maybe I should look at Murray’s Law^[14] and Hack’s Law^[15].

The next step is to try to build a height map that is consistent with the drainage basin. I don’t yet know whether that will work. If not, I’ll try a different approach, maybe inspired by this article from entropicparticles.com^[16]. That’s why this is in my /x/ directory — these are experiments I’m doing to learn new techniques, and then I’ll write up the things that work in a longer article.

The notes for the next experiment are here^[17].