I've been revisiting my island/continent generation stuff, and have started on something that I've been puzzling over for awhile: generating rivers on a randomized fractal terrain cheaply. As I mentioned in an earlier entry, I've come up with an approximation to erosion by simulating raindrops propagating across the map, smoothing out terrain as they go. Well, as it turns out, I was able to modify this to simulate, at the same time, deposition of residual water at each node that a raindrop crosses. By accumulating the residue of each drop to cross a point of the heightmap, I can construct a map where the most heavily traveled areas have a higher buildup value. These higher buildups occur in valleys, draws, and arroyos of the watershed.
The technique is fast, taking only a couple seconds for a large map, and the rivers it generates are pretty decent. It has its limitations, though, in that water accumulation and construction of lakes does not take place. However, it gives me a place to start.
Here is a sample fBm terrain, and it's eroded version:
Here is the watershed map generated by applying an equal amount of water to each cell, then propagating:
Areas that are brighter white represent areas of heavier accumulation of water, and denote major rivers on the map.
Here is an overlay showing the rivers in blue on the original eroded map:
As you can see, while it still needs some work, it produces a fairly acceptable watershed pattern that can be used for the placement of rivers, streams, and brooks.