Mapgen4: river appearance

From Red Blob Games's Blog

Earlier this week I moved all the heavy computation into its own thread. The rest of the week I wanted to work on rivers. The last time I worked on rivers, I replaced the slow CPU-based renderer with a fast GPU-based renderer. However, the output was ugly:

The main problems were:

1. The rivers are too jagged.
2. Some rivers become wide and then narrow again for no obvious reason.
3. Some rivers go up the side of mountains.

This renderer uses the triangle structure of the map's dual mesh. Each of the Delaunay triangles can be one of four types:

1. Ocean
2. Source of a river. Water flows out but no water flows in.
3. River bend. Water flows in one side and out another side. Bend can be left or right.
4. River fork. Water flows in two sides of the triangle and out the third side.

Once I know which type it is, I pick a texture to apply to the triangle. The main complication is that the width of the river can vary. I constructed a 2D array of textures, using the column for the incoming river width and the row for the outgoing river width. You'd think the incoming and outgoing widths are the same, and therefore there's no need for a 2D array of every combination. Although the physical width is the same, the texture width varies, because the sides of the triangle can be different lengths. So I need to calculate the width in texture coordinates and use that to look up the row and column in the texture array.

For river sources, the incoming width is zero. For river forks, … there are two incoming widths. That means I really should have a 3D array of textures. Yikes. So I tried to be "clever" and made the fork veer off to the other side of the triangle so that it can touch the other incoming edge without taking its width into account. Essentially I did this so that I wouldn't need to draw the other river flowing in:

The first step to understanding the problem was to add debug information to the view. I made the forks red and the bends blue. I put yellow and cyan markers at the ends of the river segment, and a purple marker at the center of the triangle.

Ok, looking at this, I can see that the blue segments aren't too bad. They could be nicer, but they're not terribly jagged. Looks like they're most jagged at the purple points. That's because I draw a line from the triangle edge to the center, then from the center to the other edge. That's easily fixed with a bezier curve. The other problem is that the red segments are really bad. My clever trick to have them go to the opposite edge backfired.

I think it'd be better if they were all bezier curves, like this:

The first step was to change the blue segments to bezier curves. I implemented the easy version of this, and will work on the more complicated version another day. The result looked a little better.

The harder step was to fix the red segments. Instead of attempting a 3D array of textures, I decided it would be simpler to draw a fork as both bends on top of one another. Sounds simple, right? Well, it took a bit of work.

To make this tool acceptably fast I've tried to precompute as much as possible, and load as much as I can into GPU memory ahead of time. Rivers are drawn as texture mapped triangles. Each triangle is 3 vertices: x,y, u,v. Since x,y didn't change over time, I put x,y into a separate vertex array and loaded it into GPU memory ahead of time, and then I populated u,v based on which river texture I needed.

If I'm going to draw forks as a bend on top of another bend, I need to draw the same triangle twice, with different u,v coordinates. That means I can't load all the x,y into the GPU ahead of time. I had to merge the function that calculates x,y into the function that calculates u,v. I had to switch from a fixed number of triangles to a variable number of triangles and also update the shader to take the input in a different format. At each step of the restructuring I wrote the output to a PNG file and compared it to what I started with, to make sure I hadn't changed anything. During this process I also found a few bugs and glitches.

The bad news is that the new code runs a little slower than the old code. It's sending more data to the GPU for one thing, but I think there's something else going on, which I will investigate when I get back to performance. The good news is that the rivers look a lot better! They don't look great, but they're definitely better:

I'm pretty happy with the progress I made here. There are more things to do of course but this was 80% of what I wanted. I made a list of river work for next time:

1. Use a variable width curve instead of a fixed width curve. This will require that I calculate the points myself instead of using the built-in bezier spline drawing.
2. Investigate whether distance fields can help here. It'd be nice if they could handle the variable width without my having to create lots of separate textures.
3. Add noise so that the river curves don't look perfect. This may be unnecessary, as the irregularity of the triangles already provides some of it.
4. Use straight segments instead of curves for steep areas. I don't want the curve to go up the side of a hill. I may not need this; I'll wait and see.
5. Figure out why rivers sometimes go along coastlines instead of directly flowing into the ocean.
6. Figure out why rivers sometimes get narrower downstream. I think the effect isn't terrible so I may keep it, but I'd like to understand why it's happening.
7. Fix glitches in the texture that are causing extra dots in the water.

However, since I'm happy with the way things turned out, I'm going to leave those items for later. I have a higher priority item to work on: biomes. I haven't yet decided how I'm going to make them work, so I will need to experiment a bit.

Labels: mapgen4 , maps , project , triangles