Road Network Generator

The aim of this project was to create a tool to procedurally generate the road network of a town.

The generator system takes a population density map as input (represented by red in the images above), then grows roads toward areas of high population density, similar to plants growing toward light.

Highways are grown first connecting the peak population centers to each other. Next roads branch out from highways following the contour of the population map, and finally streets grow out from those roads.

Each road type was configured with different growth behavior to better model that road type. For example highways and roads can twist and turn as they grow, whereas streets generate in a more rigid pattern.

Implementation

The first iteration of this project was inspired by a paper Procedural Modeling of Cities, which uses an L-system to generate the road network. An L-system is an algorithm used to simulate the growth of structures such as plants. The structure is represented by a string of symbols representing actions or instructions. Iterating over and replacing elements of the string results in a fractal structure.

The implementation based on L-systems was successful, however was made overly complicated by abstraction of growth rules to L-system grammar. After additional research I decided to abandon L-systems and implement the underlying behavior directly in code.

Following suggestions and examples found in this blog post and this Procedural City Generation implementation I implemented a new system using a priority queue to place potential road segments in order of importance. After being placed potential branches could then be put onto the queue.

Without the formalization of L-systems this implementation was simpler, making it far easier to debug and extend.

Generating Population Density Map

A value from 0-1 is generated for each "tile" of the map, to represent the population density at that position. This is visualized by red in the images above. The values are generated with fractal simplex noise and combined with a falloff map to concentrate high density values in the center.

After iteration time became a problem with a CPU based implementation of noise generation I took the opportunity to implement it with a compute shader. This involved passing the map resolution and fractal noise parameters to the compute shader, and having it populate a compute buffer with the noise values of each tile.