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.

This is a newbie question, but here it goes:

My map is a 2d grid, and I want to generate roads and rivers. The route from the starting to ending point must not be the optimal route in number of tiles. Instead, they should have a certain level of randomness (turns).

Is there a standard algorithm for this kind of thing?

Cheers!

UPDATE:

This is the result of playing with weights on the grid, and applying a shortest path algorithm (Bellman-Ford) using the jgrapht library. I went with Donutz' answer after all.

http://pastebin.com/AGQGK5ik

share|improve this question
    
Are there any obstacles on the map? –  Byte56 Jun 27 '12 at 21:25
    
Not yet, the river will be the first obstacle to be placed. –  Markos Fragkakis Jun 28 '12 at 11:07
add comment

3 Answers

up vote 15 down vote accepted

You can generate the optimal path using A*, then distort it with midpoint displacement.

enter image description here

This will ensure your endpoints are met and allow you to control the randomness to a great degree. For example, I would not randomize roads as much as rivers. Whatever intelligence is building roads typically attempts to be optimal about it.

Take care to ensure that if your map has obstacles, you check after each iteration that you're not crossing through those obstacles.

Another method would be to generate Perlin noise after finding the optimal path, then shift your points based on the noise generated. For example, using this noise:

enter image description here

Then show with the optimal path in red and the shifted path in blue:

enter image description here

Notice how the shifted path has "settled" into the darker areas of the noise. The same way a river might flow through a valley.

One benefit of the Perlin noise choice is you can factor in your obstacles and avoid them as part of the algorithm.

share|improve this answer
    
Thanks a lot.+1 –  Markos Fragkakis Jun 28 '12 at 6:43
1  
How do you do this point shifting base on the noise? –  Khoi Jan 16 '13 at 4:15
1  
It depends on how you're storing the noise and generated line. You could find the nearest/lowest noise perpendicular to the line at the center first, then at the mid points between center and ends, and so on. –  Byte56 Jan 16 '13 at 5:11
add comment

The A* algorithm will also allow you to assign values to tiles indicating their suitability. For instance, you can assign the lowest cost scores to low land for rivers, to flat land (but not swamp) for roads, and generate based on that. This doesn't give you the shortest route, but it does give you the most efficient route. Apply a little randomness to your tile values and you can get some sub-optimal routes.

share|improve this answer
add comment

What about when height is a factor? I can make a heightmap with diamond square algorithm. I was thinking of adding some random water to each tile and then iterating through and moving water to lower elevations until it was all settled, but that would slow, and would probably make lakes, not rivers.

I was also thinking of looking at normals for each tile. If 2 normals point towards each other, then that must be a valley. Water would collect in a valley. If they point in the same direction or away from each other, water wont collect. This would probably be faster than the iteration method, but might not make lakes, only rivers. I'd have to play around with it to keep from turning every instance of tiles point towards each other into a river.

share|improve this answer
add comment

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.