Space Colonisation Based Procedural Road Generation

Student: Gabriel Dias Fernandes
Supervisor: António Ramires

Abstract

Procedural generation of content has been studied for quite some time and it is increasingly relevant in scientific areas and in video-game and film industries. Procedural road layout generation has been traditionally approached using L-Systems, with some works exploring alternative avenues. Although originally conceived for biological systems modelling, the adequacy of L-Systems as a base for road generation has been demonstrated in several works.

In this context, this work presents an alternative approach for procedural road layout generation that is also inspired by plant generation algorithms: space colonisation. In particular, this work uses the concept of attraction points introduced in space colonisation as its base to produce road layouts, both in urban and inter-city environments. As will be shown, the usage of attraction points provides an intuitive way to parameterise a road layout. The original Space Colonization Algorithm (SCA) generates a tree like structure, but in this work, the extensions made aim to fully generate a inter-connected road network. As most previous methods the method has two phases. A first phase generates what is mostly a tree structure growing from user defined road segments. The second phase performs the interconnectivity among the roads created in the first phase. The original SCA parameters such as the killradius help to control the capillarity of the road layout, the number of attraction points used by each segment will dictate its relevance establishing a road hierarchy naturally dependent on the distribution of the attraction points on the terrain. An angle control allows the creation of grid like or more organic road layouts. The distribution of the attraction points in the terrain can be conditioned by boundary maps, containing parks, sea, rivers, and other forbidden areas. Population density maps can be used to supply an explicit probabilistic distribution to the attraction points. Flow-fields can be used to dictate the flow of the road layout. Elevation maps provide an additional
restriction regarding the steepness of the roads. The tests were executed within a graphic toolbox developed simultaneously. The results are exported to a geographical information file format, GeoJSON, and then maps are
rendered using a geospatial visualisation and processing framework called Mapnik. For the most part, parameter settings were intuitively reflected on the road layout and this method can be seen as a first step towards fully exploring the usage of attraction points in the context of road layout.

Thesis Download (PDF)

Paper in ICGI 2018 (Best Paper Award) (LINK)