Delta Drawn (Part 2)

At the end of the last post, I had created land part of a delta at the mouth of a river:

Now I need to fix the river so that it actually crosses the delta, and then add in the branches.

To start off, I'll send the river across to the middle point of the delta.  Rivers are normally created as part of a process that traces the flux of water across the Voronoi grid.  I can't do the same thing here but I'll have to make sure my new invented river course has all the proper attributes and values.  The first step is to find the midpoint of the new delta, and connect the existing river to that:

Well, that sort of worked.  But the new river segment is narrowing down to nothing at the mouth of the river.  The problem turns out to be a missing divisor in a calculation and that is easily fixed:

Okay, so now we have the river reaching the ocean, which is a good start.  Right now it's just a single straight segment from the old end of the river to the ocean.  We can break that up into a few segments and add some variation.

Now the final segment is fairly indistinguishable from the original river.  However, there's a slight trace of line across the mouth of the river.  This happens because I've drawn the river exactly to the shore, and (because lines have thickness) some of the coastline is still showing.  The solution is to project the river a little bit further into the ocean.

Now I need to fill in the rest of the criss-crossing rivers of the delta.

The basic idea is that I'll repeatedly branch one of the existing rivers in the delta and then run the new river to some point on the coastline of the delta.  Something like (bad graphics warning):

Each time I split off a branch, I'll split some of the river's flow off to go with it.  I don't care if rivers cross each other, but one thing I want to avoid is a river with an impossible or highly unlikely flow, like this:

To keep this from happening, I'll force branches to go somewhere close to the mouth of the river they are branching from.  The farther back they branch, the farther away from the mouth they can go.

I'll start by just creating a branch manually to see if I can get that to work:

That sort-of worked.  There are a couple of problems.  First, the river is hitting the shore at a very oblique angle, which causes problems.  Secondly, the start of the river where it branches off the main river is very narrow.

The latter problem occurs because prior to creating deltas, I've never had a river split off of another river.  I've only had rivers join with other rivers.  Every river starts from nothing, so Dragons Abound always draws rivers starting from a point and growing to their initial width.  What I need to do is add a test to detect when a river is branching off of another river, and then suppress the narrow start.

That seems to have worked.  The problem of the oblique approach to the coast is more troublesome; with an irregular coast and a thick river, making them meet seamlessly in all cases is challenging.  For now I'm going to ignore it and see if I can get the rest of the delta drawn.

My idea for drawing the delta is to start at the point furthest from the coast, pick one or more random spots on existing rivers to branch from, then move a little closer to the coast and repeat.  By varying the number of branches and the space between branches and other variables, I should be able to tweak until I get something I think looks good.  We'll see.

Here's the first attempt, with decorations turned off (so all the rivers are straight):

This looks surprisingly un-terrible.  One problem seems to be that the very short rivers right at the coastline are a mess, so it might make sense to end the river splitting early.

That looks better.  Let me now introduce some noise into the paths of the rivers.

That is starting to look okay.  One noticeable problem is that sometimes the river branches run through other branches.  I'd like to notice when a river hits another river and then terminate it there.  This would create short connectors between branches.  Unfortunately, that turned out to be very difficult to program.  First it was difficult to detect intersections and correct the rivers to merge, and then these short connectors broke all the succeeding delta creation.  Eventually I had a “duh" moment and realized I could keep the short connectors as rivers but drop them from all the subsequent delta processing, and then things more-or-less fell into place.

I also did some experimenting with various parameters for the branching trying to find a combination that would give me something pleasing to the eye and avoiding some of the more obvious problems.  Here are some examples at slightly enlarged size:

These all look pretty good to me, so I'm willing to declare victory on the basic concept.  

The last step is parameterize the code.  Up to this point I've hard-coded the delta onto the longest river on the map, and hard-coded the values for the parameters that control branching, etc.  Now that I've got a working version, I can go through and parameterize the code so that I can have more than one delta and the deltas can have different characteristics.

Here's a kind of interesting result after that work:

Here the generator has randomly plopped a lake down right on top of a delta.  I'm not sure what to think about that.  On the one hand, the code does a pretty good job of rendering the situation.  The northern-most river is implausible because it connects to the lake in two places, but other than that I'm not sure this isn't a real-world possibility.  There's a lot of weird terrain in the world.

Here's another weird one:

What the heck happened here?  Let's look at the river without the delta.

The problem is that the delta algorithm somehow put the mouth of the river on the far left of the delta rather than near the middle.  This occurred because the semicircular delta added to the map intersected with the coastline in more than two spots.  It cuts off a little bit of the bay just above the river bend, and the algorithm puts the river mouth there, causing the acute turn in the river.  The fix is to use the first and the last intersections rather than the first two intersections.

Oops.  Well, maybe not.  Without going into too many details, this happens because the delta happens to get added where the coast wraps around, so the “center" found by the algorithm is in the whole rest of the coast rather than on the delta!  This is actually a rather tricky problem to detect, much less to fix.  After thinking about it for a couple of days, I decided there wasn't a solution that didn't require a lot of painstaking bookkeeping.  So I've decided to simply detect this case and reject this delta.

Of course, in most programming jobs you can't simply decide to skip something because it would be hard.  But a map doesn't have to have a delta. If I decide to add a delta to the map, I can also “undecide" that later on if it is too hard to do.  Of course, if I do that too much I may run into trouble, but I've found that the 80 / 20 rule is a good guide -- I can throw out about 20% of the problem cases without too much negative impact.

Adding the tests to avoid the case above turned up a couple of other bugs in the implementation which took a while to correct.  I also had a few maps that took a very long time to run, so I made one of my periodic performance investigations.  One of the big culprits was the code that tests whether a point is within a polygon.  My implementation was based upon code I found here.  I did some research on efficient point in polygon algorithms, and found an interesting discussion on the topic by Dan Sunday.  Dan suggests that a proper implementation of the “winding number" algorithm is both more correct and faster than other implementations, so I tried a Javascript implementation of his algorithm, based on code by Vlad Lasky that you can find here.  This indeed was about 10% faster than the old algorithm.  

The more interesting discovery is that every once in a while a map takes much, much longer to run than normal.  I suspect this happens when the JIT compiler in the browser has to compile the Dragons Abound code, but I'm not sure, and there doesn't seem to be any easy way to tell.  (Send me an email or a comment if you know how to suss this out.)

That pretty much wraps up deltas for now.  Here's a random map (click for full-size) showing a delta in context:

This is literally just the first random map I generated, but it happens to have cluster islands opposite the mouth of the delta, which is a nice touch.