I'm self-answering my question, but please don't let that deter any other answers! I'm definitely curious to see if there are any other common techniques.
In the previous question about coastlines, Samuel's answer pointed out that fractal landscape techniques can work very well for simulating coastlines. The degree of self-similarity is often startling. I've implemented an algorithm to do that, and it's produced very good results. It also turns out that rivers, too, exhibit fractal-like patterns, and over areas that are relatively flat, they can be simulated - by fractals! Fractal river modeling is actually a very effective technique, and is often used.
The first step to generate such a river is to determine the terrain. If you want, you can use fractal techniques using the diamond-square algorithm, for instance. You can also figure it out via various other methods; I've used random methods that begin with a circular region, then randomly increase the decrease the elevation while moving inwards - weighted, of course, with a tendency to go upward, rather than downward. After that, you could add even more detail by modeling erosion patterns using, for instance, cellular automata; Jasper McChesney wrote an awesome post on the Worldbuilding blog about this. Even without using Jasper's algorithm, I've already found some results I like. Here are some examples (these are shown as contour maps; green, yellow, orange, and red are above sea level):
I bring these up in particular because they have interesting features: Valleys and sharp downward gradients, as well as sections of flat land going down to the sea. The valleys mean that I can figure out where a river might go. In places where there is a clear downhill path, it's simple to figure out a river's path. However, some of the valleys are still wide, and they all eventually end, leading to flat areas with no clear path for the rivers to take. How, then, can I simulate where the rivers will go? One answer, of course, is fractals.
Here's a version of the (commonly used) method I've been using for coastlines, adapted and modified for rivers:
- Pick two points, the places where you want this portion of the river to start and end. Call them $p_1(x_1,y_b)$ and $p_2(x_2,y_b)$, and put them in the set of points, $P$. I give them the same $y$-values, for simplicity's sake; you can rotate the map any angle you choose, and we might as well keep things horizontal. Let's also set $y_b=0$.
- Draw a line segment between the two points. Divide it into $N$ subintervals, each of length
$$l=\frac{|x_2-x_1|}{N}$$
- At the center of each interval, pick a random length $d$ between $-\frac{l}{a}\frac{1}{j+1}$ and $\frac{l}{a}\frac{1}{j+1}$, where $a$ is some constant and $j$ is the iteration number. We begin with $j=0$ when running this for the first time.
- Add another point, with the $x$-coordinate at the center of the interval and the $y$-coordinate being $d$.
- Add all of the new points to $P$, reordering $P$ in terms of how they are connected to each other.
- Repeat steps 3-5 as many times as desired.
- If you want, you can then using some sort of spline to make a nice, smooth curve encompassing all of the points.
You now have a segment of a river! Simply insert it onto your map between the desired points, and see how the world evolves. Do this for as many segments and rivers as you desire, although be careful to do this mainly in flat regions, where the topography won't have a major impact.
The bests results I've gotten are actually for $N=1$ and $a=10$, over four iterations. There are, of course, some duds - cases where the river crosses over itself, for instance - but there are also some gems where you get proper, repeated meanders, like a real river:
(The code used to create these is now on GitHub.)
Note that the vertical scale is expanded for effect. The swings aren't really as wild as they appear; they're actually much smaller, and the river doesn't deviate drastically from a straight line - just enough to get some realistic meandering.
I know what some people are thinking right now. "But HDE, couldn't you just use a random walk?" Well, yes, you could use a Gaussian random walk method. That's rather simple, and might actually be computationally simpler. To make it realistic, all you'd have to do is vary the step size randomly. There are, however, a couple issues I have with using a random walk in this case:
- There's no guarantee you'll reach your desired endpoint, which is a problem. I suppose you could start random walks from both endpoints simultaneously, and see where they match, but that could take quite some time. They might never meet.
- It's not very hard for the walk to cross back over itself. If you implement the fractal midpoint algorithm, it's true that you'll have some cases where the river crosses itself, and that can be a little annoying. However, most runs will not have this kind of issue. The same can't be said for the random walk method.
This is why fractals are much better suited for river modeling, coastline creation, and terrain generation than random walks are. You have more control, while still ensuring that there's plenty of healthy variation over the course of the river.
Here's another thought. Perhaps you don't want your river to run perfectly straight. You've generated your terrain already and have determined a general path for the river to follow, in accordance with the elevation. At this point, it might seem that the fractal method is pointless. It isn't. All you have to do is adapt the algorithm to a straight line, replacing $l$ with the arc length along the curve from point $p_i$ to $p_{i+1}$, and the slope of the line perpendicular (and passing through) the midpoint of each (now curved) segment with a line normal to the curve (i.e. perpendicular) at that point. The rest is simple; in fact, after each step, you can redo the spline, creating a new curve each time, with more detail. Alternatively, you can wait until the end and do something similar to what we did before, in effect, just using the initial path as the basis for the first iteration only. I haven't tried any of this myself, but it's a promising method.
There are a couple things to take into account here:
- You'll need a parametric description of the initial curve, i.e. writing the curve $C(t)=(x(t),y(t))$ as a function of $t$.
- You'll also need to know certain values through which the curve goes.
- You'll have to calculate arc length if you want to figure out the exact midpoint of each segment. That shouldn't be too challenging numerically.
You could - if you really want - eyeball these steps, but I'd prefer to compute them.
Here's a case of what I'm talking about, with all parameters and curves estimated by hand (well, by Paint). The river to the west is just a modified straight line, with one iteration of the original algorithm. The river to the east uses an initially curved path dictated by the terrain, with a secondary bend:
I should add one final note, because some people reading this may be confused by now. Fractals and self-similarity are also often applied to rivers, but in terms of the generation of tributaries, i.e. how a river branches off. These are two different things, and absolutely should not be confused. I apologized if I have anyone puzzled by this; the coincidence is not ideal.
