Procedural river or road generation for infinite terrain

Question

I should say paths, not roads as I'm thinking more medieval-like. Also, not looking for realism. The answer I'm looking for will be to fit into the mold I describe rather than realism.

I am looking for a method to generate procedural roads/rivers in a curvy sort of fashion, but I'm wanting to do so for a infinite terrain type system. Just like how perlin noise generates blobs, I'm wanting to generate random length line segments (possibly infinite length).

I'm aware of strategies like the suggested answer found here, however it relies on a specified start and end point to work, I don't have a specified start and end point. I'd like to be able to simply call a function using arbitrary coordinates and have it return whether the specific coordinates are part of the river/road.

I am not wanting to require terrain to be generated in advance. That includes a heightmap (like used for rainfall simulations or similar). I would also not want to require a start/end point.

Is there such an algorithm or tweak to a noise algorithm someone might know of to accomplish what I'm trying to explain?

The closest I've came to so far is multi-ridged fractals, if I'm using the name properly. I'm just taking the absolute value of value noise (assuming it is scaled to -1 to +1) and setting a threshold. My primary issue with this is the lines overlap way too often, are mostly circular, sometimes converge to form large lakes which is neat but undesired, and often times the thickness of the lines vary too much.

Here's a picture of what I have so far in 2D, but at a very high frequency to show more detail:

Answer 1

Just my idea to archive this what you want without (much) precomputation and the possibility for an infinite world.

The first pice of the algorithm is the usage of Voronoi-Diagramms. You divide your world into grids, each grid does have an adress in the form (xgrid, ygrid). For each cell in which you need to create roads you put the xgrid and ygrid variables into a hash function which returns a number CellSeed. You use CellSeed as the seed for a random number generator which generates the coordinates of the points for the Voronoi Diagramm.

Now you need to search the edges of the diagram and the nodes where multiple edges collide. You can also store the information into a graph for more easy access.

After this step you can search paths through the network which are valid.

For valid paths you can now create the roads (they do have sharph edges).

Note: You also need to generate the coordinates of the Voronio diagram for all neightbor cells so you don't have borders on the edges of the cell.

If you don't want sharph edges you can calculate the middlepoint of each connection and use the direction as a tangent for a bezier interpolation between two edges in the graph.

About the usage of Voronoi-Diagramms

To archive city like road structures the points from the pseudo random function can be aligned on a grid, so the ways are rectangle shaped.

For more county like roads the points have to be more unordered.

About the Pseudo Random function to generate the positions of the points for the Voronoi-Diagramms

It can be a normal random function or a Hammersley set for a more uniform non-clumpy distribution of the points.

Answer 2

For road (and city) creation, the best paper I found is this one :

Procedural Modeling of Cities by Y Parish and P Müller

This uses L-System and it can generate US and EU road patterns. If you don't want to generate roads for a whole city, you can just generate the main roads. It can take a height map, a water map and a population density map in input.

Answer 3

http://vterrain.org/Culture/Roads/ section "Generating 3D Roads" has some information on road generation.

The problem with roads is that they connect landmarks (although they often follow the terrain instead of going straight from A to B).

Personally, I'd generate the terrain, then place rivers (maybe using erosion, see http://vterrain.org/Water/ section "hydrogeology"), then place cities in places where it makes sense (e.g. near a river or other source of water, or in a place where water could be transported to using aqueducts or water towers and pipes) and finally generate roads between cities.

To make this more easy to use in a procedural world, you could create intermediate points on the terrain where roads would be most likely to go when generated in that place, then connect the intermediate points if a road is actually created in that place.

Answer 4

First, rivers and roads are very different. Roads tend to follow isolines (same/similar elevation) - the reason being it is much easier to travel on roads that don't rise or fall much. Rivers, on the other hand, travel perpendicular to isolines/isoclines (downhill). Rivers form in basins (collections of mountains that all flow downwards to a given valley) and tend to form tree-like structures. Additionally, roads often travel perpendicular to rivers, in order to form logical bridges. Best idea is to first generate rivers, and then create logical roads (i.e. roads between cities). I don't have time to go into more detail unfortunately but hopefully this will get you on the right track.

It might seem obvious, but look at Google maps at various types of terrain and roads; you will get a better sense of how they should look.