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.