# Procedural river or road generation for infinite terrain

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:

• since rivers "flow" it could be easy to determine rivers by simply using noise to determine the point of origin, after that simply use your raw heightmap data to determine path.
– War
Jul 17, 2013 at 18:16
• roads could be a bit more challenging though, I considered building roads based on use, if a player / all players regularly walked over some terrain it would become path.
– War
Jul 17, 2013 at 18:17
• @user19142 OK, not a duplicate then. You may find some use from this question/answer as well: gamedev.stackexchange.com/questions/53400/… And I'll include the previous links again as "related" gamedev.stackexchange.com/questions/45403/… gamedev.stackexchange.com/questions/29044/… gamedev.stackexchange.com/questions/31263/… Jul 17, 2013 at 23:32
• I think roads will not be very believable if generated with noise. Roads are created by intelligence instead of by physics and time. While they may resemble each other at times, they're different enough that you likely couldn't use the same algorithm for both. Jul 17, 2013 at 23:39
• The roads in that project were contour lines that followed specific heights, so you could possibly generate them locally. It worked there but the height maps not generated with Perlin noise. Jul 18, 2013 at 1:15

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.

• Do you have any examples of hash function? I've got the same goal (infinite world which uses voronoi for roads) but I can't seem to get a handle on how this should be done. Every voronoi lib I can find expects coordinates of a bounding box which immediately defeats the purpose. Oct 1, 2016 at 1:53
• No, the hash function is just for assigning a startseed to the cell. Can be something as trivial as x * prime1 + y * prime2 + z * prime3. Where the primes are unequal to each other and ideally large, you should calculate here with 64bit integers/unsigned. Its not a problem if the lib uses a bounding box, because for each cell you just have to consier all points in the cell plus all points of the neighborhood cells (which are 8 neighborhood cells). Oct 1, 2016 at 19:39
• You will propably run into precision issues with single precision if the lib uses single precision or if you use single precsion. To bypass the problem if the lib just uses single precision and you don't do as follows: Before converting the positions to single precision subtract the global position of the center cell from them, then put this as floats into the lib, then transform the results back. Oct 1, 2016 at 19:43
• I actually never implemented this algorithm but the hash function can be indeed an trivial one. Oct 1, 2016 at 19:44

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.

• +1 just because I liked the paper. Really didn't fit in with how I'm wanting to attempt to generate the roads/paths/rivers WHILE dynamically generating the terrain. Jul 23, 2013 at 1:00

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.

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.

• I modified the question again to make it more understood that I am not interested in realism anywhere near as much as I am in the way the algorithm would need to work. I do appreciate the answer nonetheless though mostly for some of the terms used. Try to think of my desire more like infinite random length squiggles able to be generated with minimal data needed (like height map). Jul 24, 2013 at 3:26