Mapgen4: river representation

I've reached the point in mapgen4 development when I just want it to be over. So I'm cutting all remaining features and am focusing on finishing. Most of the remaining work isn't interesting enough to blog about so I'm going to describe the river representation I started using last year. It's worked very well for the needs of this project. Take a look at the rivers in this screenshot:

Rivers are binary trees

The map is represented as a dual mesh. There's a Voronoi region mesh that is drawn with the red points representing regions, blue points for vertices, and white edges for the polygons. There's also a Delaunay triangle mesh that is drawn with the blue points representing triangles, red points for vertices, and black edges for the triangles.

Dual mesh

I generate rivers on the Delaunay triangle mesh (more details in last year's blog post). As water flows downstream, two rivers can join together ("confluence") but one river never splits into two (there are exceptions in nature but not in my map generator). I assign each triangle to be one of five types:

(ocean)
0 children (leaf)
1 child (left)
1 child (right)
2 children

This creates a binary tree for each river. There are multiple rivers, so that makes a binary tree forest. A common representation of a binary tree is to use a node object that has pointers to a left child and right child, either of which could be null. That structure makes it easy to go from the parents to the children. It also makes it easy to insert and remove children. For the map generator I only have two passes over the tree structure, and I don't need to modify the tree.

1. Construct the tree by starting from the coastlines and building rivers uphill. I start with the mouth of each river and go uphill, creating bends and forks until I end the tree with springs. This pass goes parent to child.


2. Simulate rainfall by going the other direction. I start with the leaves and make water flow down to the parents, down through the tree until it reaches the coastline. This pass goes child to parent.

Consider this example river tree of triangles (drawn with graphviz) that flow down to the coastline at triangle 15:

Binary tree representing a river

For this I can use an array representation. During the construction phase, I append to the array, writing the triangle IDs in breadth first search order:

0	1	2	3	4	5	6	7	8	9	10	11	12	13
15	9	23	41	18	72	35	80	5	17	54	51	87	48

The child nodes are always after the parent nodes. For example, in the tree, node 80 is a child of node 41, and in the array, node 80 at position 7 is after node 41 at position 3.

I also need a map from child node ID to parent node ID:

from	9	23	41	18	72	35	80	5	17	54	51	87	48
to	15	15	9	23	23	41	41	72	72	80	17	54	54

During the simulation phase, I traverse the array in reverse order. I first set the river flow to 0 everywhere. Then for each node:

1. Calculate the rainfall r


2. Increment the current node's river flow f by r


3. Find the parent node in the parent array, and increment the parent's river flow by f

For example, when visiting position 7, I would calculate the rainfall at node 80, add that to 80's river flow, see 80's parent is 41, and add 80's river flow to 41's river flow.

The standard representation of binary trees stores children at each node; I instead needed to know the parent of each node. I'm using an array of integer representation instead of the usual tree of objects representation. I mostly picked this to avoid memory allocations — I can allocate it when the program starts and then reuse the array — but it may also be slightly more cache friendly.

I'm pretty happy with the way the rivers work right now. One additional step I considered was to iterate forwards and backwards in the array again to make canyons look nicer. Right now there aren't that many canyons and I don't want to slow things down so I'm going to skip this for now.

I want to finish this project soon so I'm declaring feature freeze. I am going to fix bugs and add UI for things that currently require editing the code. I'd like to improve performance but that can wait. I'd like to improve the visuals but that can wait too.