Procedural city


The program is capable of generating totally random city road maps on top of which, the visual aspects of the city are them rendered (i.e. buildings and roads). The generation process focuses on creating dense sections of an inner city by dividing up convex Voronoi polygons into smaller plots of land and those plots into building foundations.


The city generation at its heart focuses on creating a randomly distributed road network and then fills that in with buildings. The road network is generated in such a way so that it represents recognisable aspects of a city while still being purely random, a multitude of techniques are used to achieve this effect.

The base of the city is made up of a Voronoi diagram. The application uses a form of Fortune’s sweep line algorithm (taken from here) to generate the diagram. Once generated the Voronoi edge data is cleaned and all incomplete cells are removed, the edges are then duplicated in order to start operating on the cell interiors.

To simulate reasonably accurate road structure once the base cells(blocks) have been produced the roads are given junctions at equal increments along their edge. This process allows for a reasonably accurate connection between blocks creating cross junctions between multiple roads. The difficult part of this is then taking all the junctions from a block and connecting them in a way so that consistently sized inner plots are created without producing impossible or unlikely shapes.

It took many iterations until the results started to represent something resembling an inner-city road network. The implementation settled on, takes the first junction from the longest road in the block and checks all other junctions looking for the connection closest to perpendicular to the start road. Once this connection has been found the same process is repeated for the remaining junctions in the road. Except instead the road is compared to the inner road created by the first junction looking for the connection most parallel to this. This process is repeated for each road until there are no optimum connections left to create.

The final set of roads created was the closest representation achieved. It has a balanced distribution of unique useable shapes while keeping familiar looking road structure. Here is a representation from a prototype using SFML. The white lines are the outer Main roads and the red lines are the inner roads. The prototype was an extreme help in planning out how the road network was built. It allowed a simple representation of all edge data without having to do any complicated rendering.

Road network representation in early prototype

Road network representation in early prototype

Once all plots have been generated the final stage is to generate the foundations for each of the buildings sitting within the plot. The method for subdividing plots is one that is common within this style of project (see here and here). It is a simple algorithm that divides each plot perpendicular to its longest edge until a minimum area requirement is met. The minimum area can be controlled to allow buildings of differing area in each part of the city. Below is the results from the algorithm displayed in the prototype using the same seed as above.

Building plot generation. White = roads, Red = building boundaries

Building plot generation. White = roads, Red = building boundaries

The building heights are randomly selected between a minimum and maximum height range for each building. The maximum and minimum decrease as the building location progresses further away from the city centre, on top of this there is a small chance that the maximum height will double creating small numbers of towering skyscrapers within the vicinity of the city centre. All of this data is then used to generate static building meshes at the given size shape and location.

Perlin noise is used to create the grass texture seen in the demo. Perlin noise was used mostly out of necessity, as all textures available were far too close and detailed which looked horrific when looking at the city from up high. The effect was created by layering high-frequency noise on top off eight-octave fractional Brownian motion. This helped to add the look of grass at a low level while giving it a patchy look from up high. The right colouring was then figured out by trial and error and the final function ended up as.

R = noise2, G = noise, B = (1 - noise) / 10

Where noise is the sampled noise value in the range [0, 1], and each letter represents the colour values red, green and blue respectively. A strange combination, however, it provided excellent results.

Procedurally generated grass texture

Procedurally generated grass texture

The atmospheric light scattering is taken from GPU Gems here. The effect is created in two passes. The first pass called the “occlusion pass” renders all occluding objects black and the textured light object to a render target. In the second pass, a radial blur is applied to the occlusion texture radiating from the light position in screen space. This creates the rays emanating from the light. Finally the texture is additively blended with the scene making everything look far brighter when the light is visible and darker when it is not. The effect really comes to life when you straddle both areas showing off the crepuscular rays in all their glory.

Light shafts visible through adjacent buildings

Light shafts visible through adjacent buildings


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s