Wednesday, September 18, 2019

algorithm - Road / river generation on 2d grid map


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



Answer




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.



No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...