Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

enter image description here

share|improve this question
    
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. –  Wardy Jul 17 '13 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. –  Wardy Jul 17 '13 at 18:17
1  
@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/… –  Byte56 Jul 17 '13 at 23:32
4  
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. –  Byte56 Jul 17 '13 at 23:39
1  
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. –  amitp Jul 18 '13 at 1:15

4 Answers 4

up vote 6 down vote accepted
+50

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.

diagramm from wikipedia

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.

share|improve this answer

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.

share|improve this answer
    
+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. –  Tim Winter Jul 23 '13 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.

share|improve this answer

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.

share|improve this answer
1  
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). –  Tim Winter Jul 24 '13 at 3:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.