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.
Answer
You can generate the optimal path using A*, then distort it with midpoint displacement.
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:
Then show with the optimal path in red and the shifted path in blue:
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