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.
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.