Procedural Generation of Road Networks

Which are the fundamental mechanisms behind the growth of a transportation network? How have we humans created our roads, and which (not only physical) factors in this process contributed the most? In most countries, the creation of the road network took many centuries of decentralized use shaped by common and/or individual benefit. How have all these small contributions created the complexity observed in the actual network is something that fascinates us. This project is our contribution towards a deeper understanding of this spontaneous beauty.

In the following, we proceed in steps, creating first model landscape, defining the cities of various sizes, and finally constructing the road network connecting some of the cities:

1. Our board is a Voronoi graph generated from a random distribution of points in the surface. Cities and towns will be located at the vertices and roads will follow the edges of this graph. The "cost" for building a road between two vertices of the graph will be proportional to the total distance. That is, the "cost" is the sum of the length of the edges that form the path connecting both vertices.

2. We use a type of Perlin Noise to generate mountains and lakes. The difference in elevation between two connected vertices will also contribute to the "cost" for building a road in that vertex. Indeed, when we build roads we try to avoid steep slopes. In addition, building a bridge to cross a lake has a significant additional cost as well!

3. We randomly choose edges where to locate the cities (27 red dots in this example). We assign a population following Zipf's Law which is know to reproduce the population rank-distribution of almost every country (the size of the dots represents the population). We calculate the pair-wise distance matrix of the cities and use it for ranking of the priority for building a road: we use the Gravity Model of migration (population of first city times population of the second city over the square of the distance between them) which favors to connect cities that are close and cities that are big.

4. We create the road between the first pair of cities in the ranking along the shortest path in the graph using the "cost" as weight. Once the path is obtained, we update the weights reducing them by half for those edges that constitute the road. With this rule, it will be cheaper for the next path to follow a road that already exists than creating a brand new one. In this fashion, we continue with every pair of cities following the ranking until all the cities are connected.

It is nice to see in this example the pattern created by the road network (black lines connecting the red dots). The roads do avoid lakes and steep mountains. The biggest city centralizes the traffic (represented by the width of the lines) and the structure of the network, as seen with capital cities in many countries.

Here we have repeated the process but located a city or town in every vertex of the network, and obtaining the shortest path to the capital city following the same rules for the ranking and the weights.

We are now ready to obtain the isochrones and reproduce our own lovely Road Tree!