Road / river generation on 2d grid map

Question

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 1

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.

Answer 2

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.

Answer 3

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.