The problem

The problem with rivers is that they shouldn't be drawn the same way roads are. While roads are supposed to be fairly straight in order to make transport easier, rivers don't follow this rule and run through where the terrain is lowest, serpenting more and more as they wash their banks away with time... Of course, RLs aren't meant to be photorealistic, but using the same method for drawing rivers and roads is... mundane...

Now, while making a road is easy, drawing a nice looking random river is a pain in the arse. How should its course be determined? Bresenham lines are out of question. One may use a vector and Perlin noise approach and alter the next river cell's position according to a vector determined by the 1d Perlin noise value, but that gives a boring result similar to roads, only more zigzaggy. Besides, there is no guarantee that the river will actually end where planned. Random walk (fractional Brownian motion) is even worse, since its path is totally unpredictable and it tends to generate loops all the time. How are we supposed to solve this?

The solution

All is not lost, there are ways of creating nice, random looking rivers. I'll describe a rather complicated looking way of doing that, but trust me, it's not that difficult to implement! Let's start from the beginning...

The noise

First of all, we need to generate 2d fractional Brownian motion do determine the possible paths for the river to take. Of course, we will also need to process the generated noise, since its normal form, with value ranges from -1 to +1, is far from looking like a net of river banks that we need. An easy way of achieving such a result is using absolute values of the fBm. Take a look at the image below and judge for yourself: does it look hot or what?

Fractional Brownian motion: absolute values

The distances

Good old Mr. Dijkstra will lend us a hand at this step (I suppose that A* would bear the same effects, so don't worry if you have a different pathfinding algorithm in your roguelike). View the noise we've generated not as a heightmap, but rather as a guide telling Dijkstra what is the movement cost of each map tile. To make it simple, movement cost is directly proportional to the noise's value on each map cell. Why? Because this way our algorithm will avoid going through high cost tiles and will prefer to stay where noise values are closest to 0.

Enough chitchat, let's get to work. We need to tell Dijkstra to calculate distance values from the river's starting point on an edge of the map. Bear in mind that it shouldn't take in account impassable tiles nor anything similar, but rather treat the map as if it were an open space. Each step has its base cost (like 5 for horizontal/vertical movement and 7 for diagonal) that will be multiplied by the noise value.

A word of advice, however: the noise values need to be processed further to obtain good results. We need to sum 1 to all values and possibly multiply them to make it really worthwhile and "effort saving" for the river to go around areas with high noise value rather than going straight through them. Why raising the values by 1? Consider this situation: the river reaches a cell that has noise value 0. Step value multiplied by 0 is 0 and it may result that there are no adjacent cells with lower distance values for the river to continue; either it will stop there or enter an infinite loop, depending on how we construct our shortest path finder.

Once the fBm values are tweaked and Dijkstra has created a grid of distances from starting point, we may proceed to the last step of the process.

Dijkstra's distances from starting point

The river

Once all this has been done, we can now draw our river, beginning at the end point and going towards the starting point by checking the distance values of all adjacent cells and proceeding in the direction of the one that has the lowest distance value. The function should serpent between the high noise values, generating a really good result.

Final result: a great looking river

More rivers

Have a look at the images below representing more rivers made using the exact same method.