5
\$\begingroup\$

I created an algorithm to procedurally generate 2d worlds based on a heightmap grid. (I used a 2d simplex noise algorithm mapped on the inverse of the distance of each pixel from the center, to "center" the island and keep it from running off the screen, if you're interested). See below.

example world

Now, I want to create natural-looking rivers which flow "downhill" from random points or artificial lakes to the ocean. I would like the rivers to generally travel downhill, but since you will only ever see then in a 2d view in a small window, they don't have to be 100% realistic. Its ok if they flow uphill over small bumps.

The naive approach of just checking all adjacent squares for one of lower elevation, then moving there gets stuck very easily in small holes/valleys.

My next was to use an A* star algorithm to find paths from the start point to random points random points in the ocean, using the negative difference in height between too squares as the move cost. This also seemed to get hung up and randomly fails a lot. It's probably just an issue with my code, but I can't find the bug and its also really expensive, so I was wondering if there was any conventional wisdom about how to do this.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ It's multivariable calculus heavy. I think most generators approach this by first simulating rain fall for several generations. Which, that can get pretty complicated. This would probably be done while taking into consideration of wind belts, rain-shadows, temperature, seasons, and proximity to large bodies of water. Once that is done, some calculus is done to find creases with depths of some threshold, and flood them based on the run off. \$\endgroup\$
    – moonshineTheleocat
    Oct 22, 2015 at 21:16
  • \$\begingroup\$ It might be easier to carve the rivers into the terrain instead of finding suitable path. What you describe is is pretty complex topic, you can start by reading about gradient descent you described as the naive solution (and then move onto similar algorithms that are not susceptible to get stuck at local minimum that much) \$\endgroup\$
    – wondra
    Oct 22, 2015 at 22:20

2 Answers 2

Reset to default
4
\$\begingroup\$

The naive approach of just checking all adjacent squares for one of lower elevation, then moving there gets stuck very easily in small holes/valleys.

That happens all the time in real life; they're called endorheic basins of which the Great Basin is an example. What you could do is simply form lakes when this happens, or ignore the rivers that don't end up in the ocean.

amitp has a great example of generating rivers, which can be summarised as:

  • Find a random point in the mountains to start the river
  • Follow the steepest downhill slope to the next point in your map
  • Keep going until you reach the ocean

downslope graph

You can add a bit of noise to make the river look better, and remember to increase the width of the river as you get further away from the source, but that's about it - water flows downhill.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

I don't know how it will work, but couldn't you reverse the process, going from the sea and taking a direction where elevation is same or higher. If there is no more such direction, (ie you are at a local apex)
- if there is a higher point a bit further, then modifiy the height in between
- or stop the river (depending on the distance from sea ?)

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .