Algorithms or resources for generating roads for small maps

[Jan Ekholm]

Hi,

I was told that this place perhaps could help out with some ideas for a small problem I'm having.

I work on a small strategy game for the iPad and it uses maps that vary in scale from 1x1 km to about 3x3 km. The maps are rural countryside and represent something like 18th to 19th century Europeanish terrain. They look something like this:

Attachment 60698

Currently the maps are created by hand using a crude map editor that I made for the game. The maps are saved in a simple vectorized format and then rendered in the game. Making the maps totally by hand is very tedious, as every terrain type has to be plotted point for point by hand. Making roads is mind numbingly boring. So I started making a small generator for the editor that can auto generate the basic structure of a map and then allow me to do some fine tuning by hand (add objectives, adjust units etc). So far I get quite nice woods and scattered trees based on some Perlin noise maps that I run some filters on.

The editor is open source if someone would be interested, but it is obviously totally tailored to my needs and is definitely no marvel of software engineering.

Now I'd like to add roads to the maps too. For this I have basically no idea how to proceed. There should be a few roads on the map and a crossroad or two. The roads would most likely exit the map on some edge and are basically old gravel roads, no straight autobahns. However I'm stuck as to what would be a good algorithm for making roads. Randomly doing it makes it all look like spaghetti and that's no good... So, does any wizard here know of some algorithm that would allow me to generate roads that are at least a bit sane? I only need a basic set of waypoints for the road, I can manually do some smoothing to get rid of sharp corners as well as create the polygons.

Any ideas? Algorithm names, papers, URL:s etc? I'd be very happy for some pointers.

[rgcalsaverini]

This thread is quite old and an answer at this point is most likely useless to the OP. But I've found it interesting and I have free time so I'll answer anyway

Edit: I got confused, the post is quite new, please never mind

So the problem of generating believable roads is not a particularly difficult one, and can be solved on a number of different ways. Actually if anyone is interested I could try to write something that would find road paths.

First lets work on a way to represent your map that favors the solution of this particular problem:

1. Map representation

You have an universe (your map) with discrete units with an associated traversing cost. This cost is a measure of how much time/energy one would spend to cross that particular spot, and would take into account some parameters:

(Fixed)
- Less flat terrain increases the cost.
- Dense vegetation increases the cost.
- Being flooded largely increases the cost.
- Extreme temperatures increase the cost

(Variable, we will take care of this later)
- Its cheaper to go down on the elevation than it is to go up (kinda like a river)
- Staying too long away from civilization increases the cost (road condition tends to deteriorate faster, you are more exposed to dangerous situations and you spend far too long without a place to resupply.
- Fallowing a geographic feature (river, coast, mountain range) is cheaper than not following it.

So a matrix data structure consisting of the numerical cost of traversing that map unit seems a useful representation. You still have to pre-process your map to generate it, and thus decide on:
- Unit size: Should represent the minimum building block of roads, small enough to be considered a road segment. Make it too big and you will have unrealistic road shapes, make it too small and you will have that plus a great computational cost.
- Traversing cost range: The cost should be an integer to speed up calculations, and range from 1 to N (not 0, because there's no such thing as free traversing on this situation). If N is too big you will have data noise interfering with the actual relevant data and weird random road paths. If N is too small you will ignore the difference between very different road options. At first I think that N=255 is good enough and fits a byte, but some experimentation would revel the right N.

So now we must think a bit about what a road actually is, and why they are built

2. Necessity of roads

A road costs a great deal of money to build, you have to employ (or enslave) a lot of workers and takes a fair amount of time, so it must be worth it. You have roads between points which many people travel frequently, so you clearly have an undirected graph type structure where the vertexes are the destinations and you have weighted edges between them with a numerical value of how many people travel between those places on a given time frame (or any analog measure).

Obviously in order to procede you have to have an idea about the movement of your people. This part largely depend on the kind of data you have, I'll lay out some options:

a) You only have the location of cities, not even population: Okay, so you have three options, assume that everybody travels to every city at the same rate. Or randomly select travel rates based on some distribution (say a normal). Or use some heuristics to give travel priorities (like assuming that coastal cities will be more visited, I don't know)

b) You have the populations: You can work out some better movement heuristics, like:
- Start with an equal (or random but with low variance) small weight on all edges.
- Usually people from neighboring small cities will visit bigger cities (to sell goods, find doctors, buy hard to find stuff etc). So you add a number on the weight of the edges connecting a city bellow a given threshold to the closer city bigger than the given threshold (or some other similar mechanic).
- Usually people from a small city will not travel great distances to another small city without first stopping on a bigger city along the way. So you can reduce the weight on the edges connecting a small city with another small city further then a pre-established distance.
- People from bigger cities will travel to other bigger cities.
- Many more that I cannot think of now.

c) You know something about their actual movement: Great, use that.

Great, now you know your people's road necessity and terrain road cost, now just build!

3. Road building

Now you just have a weighted shortest path problem with a few minor peculiarities, sorta like a TSP. The most well explored problem on earth

There are a number of ways you can go about solving it, on the top of my mind:

- Using Dijkstra or A* (or whatever other algorithm you may like). Will be quite easy, but might generate artificial looking roads.

- Using genetic algorithms to evolve a natural path

- Modelling the problem like the Ant Colony Optimization and spreading your pheromones around.

- Crawling automatons.

- An endless sea of better possibilites.

I'm tired of writing, I will return here with better ideas soon.

[rgcalsaverini]

Since you want this for a mobile game, you have serious time and computation cost constraints. You have to balance quality and time consumption, since I've never really implemented this for this exact purpose I don't know about result quality, you'll have to do some experimentation. Maybe this is a good enough solution:

- Create the graph, use the edges weight (as described above) to find the minimum spanning tree (MST) , then find the actual roads using A* over the edges of the MST and using the information about the terrain as added cost.

If the output looks a bit too perfect, maybe you could run a clustering algorithm (such as Kruskal if your data allows for hierarchical clustering, or use the bigger cities as the center of voronoi cells), and treat every cluster separately using the same algorithm as above, than once more connecting the centers (bigger cities on the cluster) to each other.


If you want more organic and natural looking roads, I would use the Ant Colony Optimization with a few changes:

Ants (people) will leave from one city and try to get to another (predetermined) city. Each city will start with a number of ants equal to either its population, the sum of the value of its edges or a combination of both, and they will try to get to all the other cities in a number proportional to the edge weight.

The individual ant will take longer to traverse the unit based on its cost, or the pheromones evaporate faster on more expensive terrain, so cheaper paths will stay with the most pheromones.

This is a quite expensive solution tho, will most likely not perform on real time and will be unsuitable for games. But will generate damn cool roads

Have you tried Stack Overflow or googling it? It sounds like the kind of problem that people solved many times before.

[Midgardsormr]

But if the map doesn't need to be generated at run-time, an expensive algorithm's not necessarily a problem. If he's (I'm assuming a Finnish Jan is male, yes?) making the maps manually right now, that suggests that prerendering is a viable solution.

[rgcalsaverini]

Oh, yeah, I missed that part. Being that the case, an AG with a carefully tailored fitness function, or a more specific implementation of the Ant Colony might do wonders after running overnight
I'm really curious to see the results, I'm betting that amazingly believable and organic roads would follow.

Maybe assume that the larger the city, the earlier it was founded (or provide city age as well) and do the road finding progressively by time. That way, as new roads to new villages are being created, some old ones might become abandoned, and roads that are well used for a very long time will be marked as better developed (paved with stones and wider).

Of course, if your goal is to save time, this is not the way to go Maybe the MST+A* way will be wiser for that purpose.