Procedural City Generation

Source

Since seeing the city generation from the shelved Introversion Software game "Subversion" in action, I've wanted to to try writing a basic procedural city generator myself. The developers followed a method described in Parish and Müller's paper: Procedural Modelling of Cities (2001). The paper is well-written and accessible, apart from the authors' decision to define their algorithm as an L-system. The rules defined for the system are hard to interpret for a layperson and, as argued by one forum thread author,1 can be transformed into an equivalent but more familiar form. The demonstration below is the result of implementing this form of the algorithm with some of the 'global goals' and 'local goals' suggested by Parish and Müller. Pathfinding has also been added to this example, and can be seen when two separate road segments have been clicked.

Algorithm (gist)
The posts mentioned above do a good job of explaining the structure of the algorithm. The original pseudo-code from the linked forum thread is:


            initialize priority queue Q with a single entry: r(0, r0, q0)
            initialize segment list S to empty
           
            until Q is empty
              pop smallest r(ti, ri, qi) from Q (i.e., smallest ‘t’)
              accepted = localConstraints(&r)
              if (accepted) {
                add segment(ri) to S
                foreach r(tj, rj, qj) produced by globalGoals(ri, qi)
                  add r(ti + 1 + tj, rj, qj) to Q
              }
           
r is a road segment with parameters: ti - the time delay until the segment is placed in the world, ri - the geometrical properties of the segment, and qi - any additional metadata associated with the segment. Q is a list of segments yet to be placed in the world. In each iteration of the algorithm the segment with the smallest ti is removed from Q. localConstraints checks the segment for compatibility with all previously placed segments and may modify its geometry if necessary, for example to join the end of the segment to a nearby junction.

If the segment is found to be compatible, it is added to the list of placed segments S. The newly placed segment is then fed into globalGoals which decides what, if any, new segments should branch out from it in the future. The implementation of globalGoals is entirely up to the developer: I made the decision for roads to simply tend towards areas of high population density. The original authors added further constraints to create several distinctive categories of road patterns.

The behaviour of the algorithm can be visualised by turning on the debug view in the demonstration above. The highlighted path shows the order that segments are placed. Segments can be seen branching out from the main highways, and merging with parallel areas of growth as dictated by the local constraints. The consequence of queueing the segments by ti can also be seen, causing the network to grow roughly uniformly across its circumference and leaving no dangling segment inactive for long.

Coloured points on the debug view correspond to local constraints proposed by Parish and Müller (2001):

if "two streets intersect" then "generate a crossing".
if "ends close to an existing crossing" then "extend street, to reach the crossing".
if "close to intersecting" then "extend street to form intersection".
Population Density
Three layers of simplex noise were combined to define the population density map. The resulting map has two purposes. One is to guide the forward extension of existing road segments; if a random deviation will reach a higher population than extending the original segment straight ahead, the extension will match that deviation. The second purpose of the population map is to determine when normal road segments should branch off from a highway - when the population along the highway meets a defined threshold.

Building Placement
In the example above the separating axis theorem is used for collision detection, specifically to disperse buildings among the road network. The initial position of each building is randomly selected. To determine the final position of a building it is moved away from any overlapping roads or existing buildings along the axis of minimum overlap. If the building is still not in the clear after a fixed number of iterations, it is discarded.

Pathfinding
The A* algorithm was used for pathfinding, with Amit Patel's excellent guide as refresher material. During the generation process, each road segment is associated with those segments which connect directly to either end of it, allowing the network of segments to be traversed.

The movement cost of each segment is the time to travel along it: a function of its length and the maximum allowed speed. Playing around with the pathfinding in the demonstration above, you may notice that the highway segments, which have a higher maximum speed, are preferred over normal road segments. The speed is in turn a function of the capacity of the road i.e. the traffic currently using the road, and although all roads are currently defined as empty, the pathfinder has the ability to avoid busier roads.