Those darn rivers

For a while now, I have been implementing different approaches to river-generation. It's been pretty tricky, and there's been a lot of failures. But now finally, I seem to be on the right track. (Who knows what tomorrow brings though. My pillow insists on pitching me "good" ideas!)

It's not by any means perfect yet, but at least I feel like I am getting somewhere. I thought I would try to explain  my current approach, and why some other approaches had to be discarded.

So, what points are important for me?

• Algorithm performance. Handcrafted maps do not have this challenge, but tools that will be available online definitely do. Complete maps of decent size should be generated within seconds.
• Rivers need to have twists and turns that look somewhat "realistic" (Note the quotation marks here; Not really sure what realistic means. Looking at some real-world maps, rivers can pretty much look like anything!). 
• Rivers need to follow some rules. An example would be that all rivers need to end in a body of water. (lakes or the ocean). Another rule is that two rivers can never cross each other. They should converge to one (larger) river. 

My approach

I'm not going to describe all the approaches I tried and failed with. That's really not what I'd like to focus on.

Let's just say that realistically forming rivers from mountain tops, and continually going downhill, always searching for the steepest descent until we reach bodies of water, is .. just .. too .. darn .. slow.

It works sufficiently for 1024*1024 maps. But traversing like this on 8192 * 8192 maps just does not work.  Sorry. I might end up offering  this approach for people who have extremely good time

So what did I do?

With heightmaps as my basis, I wrote an algorithm that searches for bays/coves in the landscape. I decided these are among the locations that I will want cities in the future, and also where I want rivers to end up. From these locations with the help of the "bay algorithm", I can find optimal angles for the river mouth. Rivers have random length, but their starting point should be along the axis of the river's optimal angle. (This angle is shifted if the starting point turns out to be in water). 

The river curving itself is made through the use of Bezier splines. The pro's of using these is that the river curving will look natural without doing alot of computing (it's fast!). The largest drawback is that you cannot easily foresee all the points along the river before it is generated. So, even if a straight line from the river mouth to the river start point only crosses land, the curving river might overlap with water.

If this is the case, I search for a new start point, and I try generating again. At the same time, the river length is gradually decreased until the curving river only crosses land. In some cases though, the algorithm decides that a river does not fit, and it gives up. These are often corner cases involving the corners of an image, an island, or very thin stretches of land.

Once I've found a suitable river path, I apply another algorithm that performs some basic erosion around the river, so that it lowers its surrounding terrain.

I'm going to show some screenshots soon, I just want to fix some tiny problems first. Until then.