A Meandering Subject

For the past few months I've spent some time away from Dragons Abound to pursue other hobbies and interests.  I've had a surprising number of people contact me to ask about my well-being.  I am very touched that people care enough to inquire!  I'm perfectly fine, but I find that (for me at least) “Forever Projects" like Dragons Abound work best if I allow my attention to be pre-empted by other projects and interests.  Sometimes I come back to the original project, and sometimes I don't, but I think that's better than getting caught up in trying to meet some preconceived notion of what I should be “accomplishing."  I have some much longer thoughts on Forever Projects that I'll try to post soon.

In the meantime, I recently had some thoughts about rivers and decided to spend a little time on that topic.

This map excerpt illustrates one aspect of Dragons Abound's rivers that bothers me.  Rivers often have stretches of wiggles as you see on the right-hand branch of the river in the plains.  This happens because the rivers are drawn from the center of one Voronoi polygon to the next, and three adjacent centers are almost never collinear, so rivers always have a kind of snaky path.

To some extent I can eliminate this by smoothing the river's path before drawing it.  In fact, the example above has been smoothed.  Without smoothing it looks like this:

You can see that smoothing has already greatly improved the look of the river.  

One possible solution is to increase the density of the Voronoi polygons that underlie the map.  The river will still wiggle, but at a finer scale that will be much less noticeable.  

Here (at 150%) you can still see some wriggles, but they're less noticeable and essentially invisible without some magnification. However, this solution creates other problems, most noticeably performance.  In this case I quadrupled the number of underlying polygons and increased the runtime by about 10x.

A better solution is to remove the river's strict tracing from the center of a Voronoi polygon to a neighboring polygon.  I'd like to do this in a way that eliminates the small wiggles while retaining (as much as possible) the overall path of the river.  Conveniently, there's an algorithm to do exactly this -- Visvalingam's algorithm.   I've written about this algorithm previously, when I used it to (ironically) simplify river paths when attaching labels.  There's a detailed explanation in that previous posting, but the simple version is that algorithm removes the point that creates the least change in the path.  You then do that repeatedly until you (say) remove 50% of the points in the path.  This has the effect of removing the highest frequency “noise" first.  Here's the river with 70% (!) of the path removed:

Visvalingam's algorithm is so good you have to remove a surprising amount of the path to make a noticeable difference, but you can see that it has retained the shape of the river and the broader curves while eliminating the wiggles.  Unfortunately, it has created a new problem.   One of the junctions of two rivers is now wrong, and the joining river overshoots.  This happens because the point where the two rivers joined has been removed.  To fix this problem, I have to modify Visvalingam's algorithm so that it doesn't try to remove any point where rivers join.  I already have that fix in place for the smoothing algorithm, so it's mostly a matter of applying the same logic.

Now the wiggles are gone but (at least to my eye) the rivers lack character.  They're reasonable, and they look a lot like other procedurally-generated rivers, like these from Azgaar's generator:

Most procedurally-generated rivers look like wandering lines with some side-to-side perturbation.  Real rivers seem to have more radical bends to them.  For example, this is a stretch of the New River in Virginia:

Note how the river bends so much that it actually reverses direction four or five times along this stretch.  There's nothing particularly unusual about this stretch of river.  You'll see this on almost any river you examine.  I actually picked the New River because it is (ironically) the oldest river in the US, and I figured it would have fewer bends than younger rivers.

In the example above, the New River is winding around hills.  Where the terrain is flatter, rivers can form meanders with even more dramatic bends:

But you'll rarely (never?) see this sort of river on a procedurally-generated map.  There are a number of reasons, but the primary reason is that procedurally-generated terrain only looks realistic at certain scales.  It doesn't have the right characteristics for drainage that mimics the real world.  And most procedurally-generated worlds don't implement realistic river erosion, either.  Whatever the reasons, the Dragons Abound rivers don't have realistic bends and twists, so I want to see if I can add some.

The first difficulty is that I have to recode the representation of rivers.  Currently, rivers are generated as a sort of linked list between Voronoi locations.  It's only when the river is being drawn that it is converted to a path.  In order to add more realistic curves to the rivers, I need to do is convert the rivers to paths immediately after they're created rather than right before they'd drawn, and then use these paths for the rest of the map creation.  This isn't too hard conceptually, but it involves recoding in a number of places.

[After a few sporadic days of refactoring.]

For various uninteresting reasons, that was much more difficult than it should have been, but the refactoring improved the code a bit, so it was (perhaps) a good investment.

Before I get to work on meanders, I want to see about adding some variety to the width of the river.  For various reasons having to do with the way terrain is generated and smoothed, the width of rivers tend to be smooth, slowly increasing curves, as can be seen in this example:

While there's some variation here, it's generally a pretty smooth curve.  To add some interest, I'll vary the width slightly using a noise source.  Here's an initial attempt:

That's a bit too extreme a variation.  After tweaking the noise parameters a bit to get something I like a little better:

So that adds some interesting variation to the river.  One minor problem is that these width variations are always symmetric, but if that bothers me enough I'll address it later.

Now that I have the river as a polyline, I can look at adding curves to the river.  In the real world, the basic process that creates meanders is pretty simple -- a combination of erosion on the outside of curves and deposition on the inside of curves.  

As water moves through a curve, the water at the outer part of the curve pushes against the bank and erodes it away, causing that bank of the river to move outward.  At the same time, the water moves more slowly on the inside of the curve, which gives any material in the water a chance to settle out, so sand and other materials get deposited on the inside of the curve.  The result is that the curve keeps shifting farther out.

I had a good idea of how to implement this, but coincidentally as I was working on this, Robert Hodgkin released a page describing his Meander project, which contains a better description of my idea than I could have written myself, so I encourage you to read his page.  The “TLDR" is to move each point on the river towards the outside of the current curve and also in the direction the river is flowing at that point.  By modifying the way these two elements combine, you can create various kinds of meandering.

If you read his explanation, Robert's method depends on something he calls the “modified bitangent" of the path of the river.  These look like this:

These lines are perpendicular to the path of the river, point to the outside of the curve, and their length is proportional to the amount the river is curving.  

I have a routine to calculate the normals of a polyline, which are similar but not quite the same:

These vectors are normalized to a length of one and don't always point to the outside of the curve.  To get to the modified bitangent, I have to calculate the curvature of the river at each point, and then scale the vector by that curvature.  To calculate the curvature, I use Menger's Curvature which looks very complicated but is actually simple to implement.  It's also a signed curvature, which means that negative curves will be inward and positive curves will be outside (or vice versa).  The last thing I have to think about is the range of the curvature.  If you look at Robert Hodgkin's example above, it's obvious that he is limiting the curvature measure -- all of the curves below a certain radius have the same length bitangent.  This is necessary because the curvature can have a large range and we don't necessarily want to apply thousands of times more erosion force at one point in the river than in another.

With the curvature measure implemented and forced to a limited range, I can multiply the normals by the curvature to get the “modified bitangents."

However, these modified bitangents are only one part of what I need.  The other part is the tangent.  As it turns out, to generate the bitangent I generate the tangent and rotate it 90 degrees, so conveniently I already have the tangents.  It's a little harder to visualize the tangents because they point straight down the river:

The two vectors are then combined into a vector that points somewhere in-between the two:

This combined vector shows the direction (and scaled distance) the path of the river will move as the curves erode to create meanders.  (Note that combining the tangent and the bitangent this way is equivalent to just rotating the tangent vector 45 degrees.  But it's perhaps easier to visualize this way.)

A couple of things to note about the meander process.  First of all, it's an iterative process.  I need to change the path of the river a little bit according to the combined vectors, then recalculate the vectors and repeat.  If you try to do it all in one shot, you just get a weirdly exaggerated version of the original path.  Second, this process will change the length of the river.  If I want to keep the same uniform distance between points on the river, I'll need to resample the path or add in new points where the existing points have grown to be far apart.  Lastly, there are some points on the river I have to keep the same -- notably the spots where two rivers join each other -- or else I'll have problems where the rivers join.

To start with, I'll do a single iteration at the scale of the visualization and see what that looks like.  Before meander:

After meander:

You can see that the meander process is starting to exaggerate curves in the river.

Here it is with 10 iterations, with smoothing and re-interpolation between each iteration:

It's instructive to vary the direction of the combined vector and see the results.  Here's a version using 90% bitangent and 10% tangent:

This exaggerates the curves.  (And as you would expect, 90% tangent adds only small curves.)  Increasing the strength of the vector also exaggerates the curves:

All these examples have looked mostly okay, bad things can happen when meandering:

This is obviously exaggerated, but illustrates a couple of different problems.  First, meanders can cause a river to cross itself or another river.  Second, meanders can cause problems where rivers meet other rivers or enter the ocean, by creating unrealistic paths.  Multiple approaches will be required to tame these various problems.

I'll start off by avoiding meanders not just where rivers join other rivers or the ocean, but also for a distance on either side.  The easiest cases to handle are the start and end of the river.

The river now meets the ocean cleanly, but there's an abrupt and obvious transition where meandering kicks in.  The solution is to have a “mask" that tapers in the meander:

Here the last part of the river is not meandered at all and then the next part slowly gets more meander.  Now I need to apply the same masking principle to all the joins on the rivers.

Now let me address rivers crossing themselves.  When this happens, the river can be repaired by removing the loop and adding a new point where the intersection occurred.  If I step through the river a segment at a time and see if the current segment intersects any of the later segments, that will provide the new intersection point as well as all the segments that can be eliminated.  In the real world, when this happens the cutoff portion of the river becomes an oxbow lake.  For my purposes, I'll just eliminate the cutoff.

If you compare this map with the one two above, you'll see a river loop has been removed in the area circled in red.

Dealing with rivers crossing other rivers is more difficult.  Here's an example:

Inside the circled area a river crosses one of its tributaries several times.  If this were to happen in real life, the two rivers would join at the crossing point, removing the downstream portion of one of the rivers.  That would be very difficult to implement in Dragons Abound, so instead I'll simply detect when this happens and reject that meander.  A second difficulty is that there can be quite a few rivers on a map, so checking all of them for intersections after every meander iteration will likely be slow.  To address this, I'll only check to see if a river intersects with a river it joins to.  It's very unlikely that a river will intersect with a river that it doesn't join at some point; but if this happens a lot I'll find a way to deal with it.

Here's is the same map with the meanders stopped before they created an intersection:

Now the rivers get very close to each other but do not cross.  However getting very close is not very realistic either, so let me adjust the code to create a buffer between the rivers.  The basic idea is to notice when part of a river is getting too close to another river and freeze that part so that it cannot be meandered further.  I can extend that same idea to self-intersections, so that I don't get spots like in the lower right of the above map where the river is so close to itself the border is lost.  Technically it doesn't intersect, but it gets drawn incorrectly.

With that in place the meanders look like this:

The guardrails do a pretty good job of keeping the rivers from getting into unrealistic paths because of the meanders.  Now I need to think about how I want to use meanders.

Obviously I don't want to meander every river to the extent shown in the examples above.  Meanders ought to be a sort of “special interest" feature like swamps or a deserted coast line.  I could achieve this by treating meanders the same way I do deserted coast lines -- at most one on a map, and often none.  However, unlike deserted coast lines, meanders are infinitely variable, so another possibility is to use only small amounts of meander on most of the map and significant meander in only some places.

In real life, meanders form in river valleys where the down-valley slope is gentle.  Dragons Abound has a measure of slope for each segment of a river, so I can try using that to control the amount of meander applied to the rivers. To start with, I can restrict meanders to the flattest quarter of the rivers:

A small amount of meander is applied to all rivers, but only the center part of the Fine Bight River gets fully-developed meanders.  I've also added a parameter so that on any map at most one river gets the full meander treatment.  A small improvement is to use a noise map to control the amount of base meander applied to rivers.  This will result in rivers in some parts of the map remaining straight while others will develop some gentle curves. 

Here the main meanders remain on the upper Jellyfish River but the Kaumgun River has had it's curves gently exaggerated.

Testing on a different map reveals a problem:

Tributaries are getting detached from their rivers.  Some debugging reveals that my calculations for curvature are broken if two adjacent points on the river are the same; that's fixed by filtering out repeated points, but the above problem remains.  After a couple of days of increasing intense debugging, I finally found the error in a piece of utility code that checks where to not move the rivers.  I had assumed that code was correct (it has been around a while) but it wasn't -- a check of the code base revealed that I'd never actually used it before.  Oh, well.  Don't assume when you are debugging!

With that debugged, meanders are working on this test map as well:

With the meanders more-or-less working (I tend to tweak features for quite a while as I study them more) the next (and last step for this blog post) is to work on naming.

One problem with naming is immediately evident: meandered rivers will never get a label.  This is because rivers use path labels that (more-or-less) follow the river, and with very sinuous rivers the label can never get snug enough to the river to warrant display (or at least not along the sinuous part).  Second, I'd like meandered rivers to get a name that reflects the character of the river, e.g., something like “The Meanders" or “Snake River."  There are a few names like this in the river name generator, but of course they won't necessarily come up on the meandered river.  Finally, in the case (as above) where the meandered river later straightens out and continues on, I'd like to give the meandered part a separate name from the rest of the river.

Since I'll later need to treat the meandered section of a river as a separate river, I'll break it off from the rest of the river and actually make it a separate river.  Then I can give that river its own name.

Unfortunately, this breaks the connections between the rivers and tributaries flowing to the sea, so that the meandered river just ends abruptly and the remainder of the river thinks it is starting from that location.  Fixing that will be very difficult / impossible, so I will have to seek a different solution.

Instead, I will mark the area of the river that has been meandered and save the original river path.  Then when I get to naming I'll add a second name to the meandered portion of the river.  That gives me this:

For the meander, I let the label overlap with the river and try to center it somewhere roughly in the middle of the meanders.  This works okay, but I might have to tweak it a bit in the future if it is too hard to distinguish.

In the map above, the river name was hard-coded.  I need to be able to generate a variety of names for meanders.  In this case, I generate two kinds of names.  One kind is variants of  “The Meander" using different synonyms for meander, both obvious ones like Rambles and archaic ones like “Cringle-Crangles."  The other kind is variants on “The Snake River" with different synonyms for snakes and other snake-like things.

Here it has been called the “Anaconda."  Technically, this is still part of the Moor River, but given how meanders are created, there will always be a join between the meandered part of the river and the other part, so the names don't clash.

In the map above, you might notice that some of the meanders go into the forests, while elsewhere the forests avoid the rivers.  This happens because the forests look at the actual water flux to decide where to avoid, but of course in creating the meanders I've moved the river to places where the flux is low and there wouldn't normally be a river.  So I need to fix how forests detect rivers to a method that looks at the actual river paths.

With that in place, the forests now properly edge back from the meanders.

That's a good stopping point for now.  Next time ... well, I'm not sure what, but don't expect weekly updates as in the past!