Rivers Routed Downhill

[fbfree]

I'd like to see rivers routed preferentially towards the nearest drop in elevation instead of towards the nearest water.

The behaviour I'd like to avoid is that of automatically generated rivers running across mountain faces or avoiding the valley bottom.  This can be seen in the two attached pictures, and in a post on the experimental branch.

Having taken a quick look at the code that generates rivers, it seems that the rivers route to the nearest water, then tries to find a valid route that flows downhill.  For me, the ideal behaviour would be to have an algorithm that produces a temporary water puddle, extends it randomly using a singly linked tree to the parent puddle tile, then when a drop in elevation or another body of water is encountered, make a connection and form a route along the linked list.  I imagine that there is an acceptable solution that uses existing Simutrans code and route builders instead of this ideal algorithm.

[Dwachs]

Any improvement on this subject is welcome

[jamespetts]

This seems like a sensible idea...

[wlindley]

One possible algorithm would be to place "one drop" of water on each map tile; then move each drop to an adjacent tile with lower elevation (if more than one, choose randomly), accumulating "drops" on the new tile and setting the moved-from tile's drop count to zero.

Continue the process until all accumulated "drops" get placed in an ocean.  During the process, If the number of "drops" on a tile exceeds some threshold, draw a small river, or larger rivers at higher thresholds. 

Variation: Instead of starting each tile with one drop, the number of initial water-drops on a tile could be increased with altitude.

[prissi]

But then many drops will never reach the ocean but end in the middle of nowhere. Also river will only start at lower altitudes, since at high places not much drops are available. And on plains the density can be easily to low for drops to from a river.

That is why rivers are routed between a source and a point in the sea. In between rivers only go downwards.

[fbfree]

In a bit more detail, the algorithm I was thinking of goes along this line:

class puddle map {

   struct map_of_tiles{
     elevation
     is covered by drop?
     pointers to growing edges
     pointer to parent tile (normally points to null)
  }

 struct growing_edges {
    pointer to both adjacent edges
    coordinate of parent tile
    size

 struct river_tile_list {
    array of coordinates, drop_elevation[force, force_no_drop, don't_care]?
 }
 
 last_tile

 private:

 grow()
 tilelist makeriver(daughter tile, (opt.) forced elevation)
 growing_edges()
 extend_edges()


 public:
 list_of_river_tiles makerivers(**source locations)


 edge extend_edges( original_edge, new tile ) {
    delete original_edge
    assign other three edges around new tile
    else (new edge at higher elevation)
      delete edge.
    check for duplicate edges
    return null

 grow() {

    randomly select growing edge
    assign puddle to other side of edge
    extend_edges(original edge, new tile)  
 }

 makerivers(**source locations) {
    initialize map_of_tiles
    assign river source locations to map_of_tiles
    loop ( highest elevation , to lowest elevation ):  {
      loop over river sources: {
        construct edgelist from map_of_tiles
        while (edgelist){
           grow()
        }
        if( river does not find lower elevation ): {
           edgelist = boundary of puddle
           while (edgelist){
              grow()
          }
          if( river does not find lower elevation): {
             end the river in dry lake.
          }
          else {
            makeriver(last_tile, elevation)
            assign sources to lower elevation
        }            
        else {
           makeriver(last_tile)
           assign sources to lower elevation
        }
      }
    }
 }

Given that there are already tools in simutrans for finding ways, and making sure they flow to lower elevations, I think that that would be a better option than writing a whole new set of code based on the above algorithm.  If the existing code could preferentially flow towards lower elevation than just to water, that may be a good solution.

P.S., I'm a physicist, so don't expect me to contribute good code.

[prissi]

I am also not a professional coder; good or bad code is more of art than of following rules ...

But the current code with the wayfinder already flows always downhill. I fail to see the difference here. And rivers in dry lakes does not make much sense in a transport simulator.

[fbfree]

The difference is that the existing code will cross a mountain pass to get to the nearest water, or travel across a valley to get to a river that had already been layed down rather than going straight downhill.

[prissi]

In the current code a river will not go upward. If there is no way down to the sea, no river will be formed.

[TrainMith]

Prissi:  Yes, the river does not flow uphill.  The river may run alongside the top of a ridge for an extended distance and _then_ decide to drop to the lower elevation, which is extremely fake looking.  An example of this is in the river exiting on the lower left (south?) of the view in the second image of the OP's post.  The other situation is crossing what would have been a watershed border, where the terrain would have a slightly higher elevation causing the division but appears "flat" at the top in simutrans.  This is due to simutrans having heights restricted to tile based heights and not a 3D height terrain.  Both pictures actually show examples of this.  Also in the second picture, two rivers head towards the same valley but, instead of joining together like they naturally should, they head off in different directions.  Because of this, rivers are not navigable sooner upstream than they naturally would.
It is examples like this that make it unrealistic and unseemly.  Also, rivers can extend far longer without increasing in size as normal.  From a trade route perspective, towns that really should have been next to a navigable river are not so.  
Hence, this affects gameplay.

[prissi]

To join river that cross another river is relatively simple.

To go downwards faster is also possible using a height based weight for routing.

Rivers do get larger the more rivers join a rivers up to ten rivers. However, at the moment there are no graphics for that. Navigation of rivers depends thus on pak set.