Monday, August 24, 2020

Delta Drawn (Part 1)

Since I'm apparently on the topic of rivers, I decide to take a look at adding deltas to rivers.  River deltas form where a river enters a slow-moving or stagnant bay.  Sediment in the river deposits out and “grows" land at the mouth of the river, usually in the form of a large fan.  If Dragons Abound implemented a full model of rivers including sediment deposition, this would happen naturally during world generation.  But Dragons Abound's river model is simplistic and doesn't do this.

Simply adding some land area to the mouth of rivers is not very interesting but the way deltas are created has an interesting side effect.  The river can only deposit sediment where it flows, so it can never build up land that is higher than the level of the water.  As the sediment builds up to almost as high as the water level, the river turns aside and finds another path.  Meanwhile wind and rain and other forces may push the sediment into piles higher than the water level.  The end result of all this is that the delta tends to grown into a fan of river branches across the delta:
(Lower Cook Inlet, Kachemak Bay. Alaska, from NOAA Photo Library)
Unlike a simple fan of land at the end of a river, a fan of branching rivers looks pretty interesting, so that's what I'll work on adding to the map.  But to start off, let's go back to that uninteresting bump at the river's mouth.

Adding a bump to the mouth of a river might be uninteresting, but that doesn't mean it is easy.  Naively, you might think that it's only a matter of finding a river mouth and then building up the land around that point.  But here's what happens when I do that:
You can see a (ridiculously exaggerated) semi-circle of lighter-colored ocean where I've added the new land.  It is getting displayed as “shallow ocean" rather than land.  Why is that?

The reason has to do with how Dragons Abound generates land.  In order to get detailed coastlines, Dragons Abound generates land using a dense Voronoi grid.  However, using a dense grid drastically slows down subsequent world generation routines (such as calculating wind, precipitation and rivers).  To avoid that, once the land has been defined, Dragons Abound saves the detailed coastlines and reduces the size of the grid.  From that point on, the coastlines define the land, so raising parts of the ocean doesn't change the land.  So there's a bit of a Catch-22 here: until I have the rivers defined I don't know where to add a delta, but after the rivers are defined I can't change the shape of the land!

Of course, it's only code so nothing is really impossible.  But rather than simply raise the ocean where I want new land, I have to do something more tricky, like intersecting the coastline of the new land with the coastline of the old land.  This sort of thing can be pretty finicky, but might as well give it a shot.

The first step is to find the outline of the new land.  I do this by drawing around all the locations I have raised up out of the ocean:
This illustrates a couple of problems.  First, there may be islands that create “holes" in the outline.  This is less likely with a more reasonably-sized delta, but still a possibility.  Second, this outline doesn't actually correspond to the coast, because it is based on the coarser Voronoi grid.  So if I try to “add" this coastline to the existing coastline, I'll end up with holes.  A better solution is probably to make an outline from the whole circle:
Now I need to find where the circle intersects with the coastline.
This has been easy enough so far but not yet very useful.  What I really need is to create the union of the red circle with the existing coastline.  This is called a boolean polygon operation, or polygon clipping.  You can imagine how you might do it in this case, but in its most general form it's quite a challenging problem.  Fortunately, Alexander Milevski has essentially solved this by implementing the Martinez-Rueda polygon clipping algorithm in Javascript.  So I will apply that code to create a coastline that includes the circle:
So now in theory I should be able to replace the existing coastline with the new combined coastline:
That almost works.  The land is not being rendered correctly, the islands create some problems, and the coastline looks jagged and primitive due to the reduced resolution.  Some of these problems will likely be non-issues with a smaller delta, but I will address them anyway.

I'll start with the jagged coastline.  Since the added land will be a river delta, it should look okay if I relax the circle to create a smoother outline.  (In fact, since I'm creating the new coastline by a union with the circle, I can create the circle however I want, so I don't actually have to work on the coarser Voronoi grid.  But this way is easiest.)  I'll interpolate the new coastline for a bit more detail and then apply some smoothing:
That looks okay, at least for now.  (For the future: Rather than use a semicircle for the delta, I could use a distorted semicircle or some other more natural shape.)

To take care of the islands, I can use the union function I used above.  I can union each island with the mainland, and if the result is just one coastline (meaning the island was inside the mainland), I can delete the island.  Unfortunately, all these unions are slow but I only envision doing 1 or 2 deltas on a map, so perhaps it will be acceptable.
Now let me see about the odd land color.  Since the island is still showing up as a correct land color, I suspect the new land I'm creating is missing some attribute.  When the coarse Voronoi grid is created, each spot gets marked as land if it overlaps at all with the coastlines or not land if it is entirely outside.  The new locations I've included are still marked as being “not land" and hence are not getting colored in.  Marking them land fixes that problem:
Now the land color is being added, but there's no markings for the biome.  But that's not incorrect; its just that this part of the world doesn't receive much precipitation and is a desert.  If I artificially add precipitation, I can force it to display as a swamp:
So everything seems to be working, and I can try dialing the size back to something more realistic.
Looks pretty good.  Not shown here, but I also added some logic to keep cities from being placed on deltas.

Now that I've finished the “easy" part, next time I'll work on creating the actual tangle of rivers on the delta.