Procedural City Generation in AdvertCity
On occasion, the procedural city generator in AdvertCity is compared to the one in Introversion's cancelled project Subversion. This blog post is adapted from a forum post in a discussion on that subject, going into detail behind the inspiration of the city generator.
Parish & Muller
The Introversion guys based the generator in Subversion on a Siggraph 2001 paper by Parish and Muller which is quite well known, you can see a PDF of it here. This has actually been a standard go-to for large city grid generation for a long time, and I did initially start by looking at the same paper when I first investigated procedural city generation. This is a very well-known paper - it's cited as a source in most procedural generation discussions, and is even a footnote in the Wikipedia page on procedural modelling. It's also generated a lot of secondary literature, some of which is scattered across the web but some of which is locked away in academic papers behind paywalls.
However, the method they apply has a number of serious shortcomings - they attempt to model an iterative process as a mathematical L-system, which, although a wonderful exercise in esoteric mathematics, isn't really well suited for fast generation or flexible rules. A very detailed analysis of their model and its flaws is found on this very informative Mollyrocket forum post, and anyone considering implementing a version of Parish & Muller's algorithm should definitely study that first. In fact I believe the Introversion guys have implemented at least some of the modifications recommended in this post.
Muller went on to produce further papers on procedural street layout, and a particularly interesting one was presented seven years later at Siggraph 2008: Interactive Procedural Street Modelling. This is interesting because it introduces the concept of tensor fields; their previous work only allowed for population centres and heightmap adjustments, and you can see this reflected in the radial / terrain-following style of Introversion's cities. Tensor fields allow far more subtle local relational layouts, however, such as closely packed neighbourhoods that are aligned in a particular way, while being bisected by major roads at odd angles.
L Systems and Beyond
My own work builds on all of these ideas, so it's not surprising that there's some similarity (and the fact that these do reflect real street maps quite realistically, so there's bound to be some convergence!). However, I rejected all use of L systems, and avoided the excessively simplified solution in the Mollyrocket post as well; The bottom line is that L-systems come from the conventions for procedural generation of plants, and sometimes landscapes. It's easy to see why - they're well suited to making things like ferns, and this procedural generation overview paper has some great examples of L-systems used to good effect.
However, real cities just don't really work like that - roads don't grow like branches on a tree. However, cities do tend to over time grow outward, and there is some merit to following the overall streets-first mapping approach, which is why I chose to do it this way, only without the L systems. (Side note: other methodologies for generating cities do exist in the literature, such as simulation of land use, or population based, or a fusion of methods - however these tend to be far slower to execute and either require very in-depth simulation, or produce excessively coarse and undifferentiated results).
I do apply something a little similar to the tensor fields, but they're maps calculated on a mix of realtime procedural projection and cached data about population layouts and terrain features (such as different terrain types, gradients, altitudes, population densities, whether the region should be considered urban or rural etc); the result is something that has the subtlety of the tensor field system, yet generates much larger cities than are feasible with the L-system at a far higher speed than possible with that design. The AdvertCity generator is an object-oriented system of roads, junctions and buildings that can be adjusted on the fly to interact with their immediate surroundings, so roads meet and cross at specific junctions, branch and fork (something not used in the L system design), and can also spontaneously degenerate from paved roads to footpaths etc as appropriate, due to terrain or other aspects of the landscape. Different classes of road or path can also have entirely different rules and code for how they react to different terrain types and other features, so it's possible to build a much more dynamic overall city map with those.
The Results
You can still get roads following coastlines, and motorway bridges spanning bodies of water that smaller roads don't try to cross:
But also more subtle mixes of straight and curved road segments, roads that are wiggly in the small scale to go around small obstacles but take a consistent route over a larger scale, and get evenly sized city blocks even in curving neighbourhoods:
It's also possible to get more realistic country roads that fork into a loop around a feature like a lake (see the background of the top image in the original post) or footpaths that can ascend to the tops of nearest hills by the easiest way possible, make realistic country walks and so on.
You can see more screenshots of differently tweaked iterations of the algorithm I'm using in this album of development screenshots.
Here's a timelapse video of the process of researching and programming a previous iteration of the city generator, which the one in AdvertCity is based on (strobe warning!):
Details
The engine understands the concept of suburbs (different traffic requirements, different travel direction requirements) as opposed to inner city or rural areas, but we're aiming to keep the overall playing field fairly centralised so you don't have to wander around too far. You do still get naturally outcropping villages in parts of the map, though.
The buildings are generally larger and taller than they would be in a contemporary city because this is a future cyberpunk setting. However, some smaller villages exist outside of the main city, too.
The generator can scale very well to different sized settlements - if there's demand, we could allow players to choose the size of the playing field for each game. Right now you can set the generation seed at startup, and different seeds already create very different looking cities, and they do differ in scale too. The only issue with smaller settlements is there may not be room to get in all the megacorporations that give the game variety.
Updated Detail
Editor's note: here we fast forward a few months. A lot of our early testers' feedback went along the lines of wanting to see more detail in the cities, so we've been working on some procedural textures for buildings and roads, as well as improved realism in lighting. Here's an update with some of the latest screenshots (click for higher resolution):
From the technical point of view, what you're seeing is:
Procedural building textures are composed of lit apartment windows; they're grouped together in bunches, and how many are lit in a given building depends on its population and the time of day. For instance, in an under-populated building, some apartments' lights will never turn on at all, at least until the population increases.
Building textures also have reflectivity maps baked into them, which define which areas are shiny windows, and which are matte sections between floors. Because this is a futuristic cyberpunk city, all the buildings are shiny metal and glass, in contrast to many modern cities which have more building variety - texturing a dystopian cyberpunk city is easier, since buildings look more similar overall in this particular sci-fi vision. Most of the apartments and offices have fluorescent lighting, and this fits into the overall colour balance of the scene.
The individual appartments have detail hinted at procedurally by subtle colours in the windows. Window light patterns do not repeat even on identical buildings, which took a bit of playing around to achieve.
From a distance, the population differences between buildings and parts of town are easily seen by the variations in their overall brightness.
The lighting for buildings is computed per-pixel now, which allows us to do proper specular reflections from the glassy surfaces - the buildings glint in the moonlight. This also increases the visual variety of the city form a distance, although it looks best while moving - still screenshots don't really do it justice.
The roads have procedural textures reflecting their realistic numbers of lanes, with anything from one-way single-lane residential roads to eight-lane motorways (or no lanes, just clear tarmac for footpaths).
The traffic directional flow is rendered in shader, so the orientations of the lights is always correct; In the city pictured here, they drive on the left (like in the UK and Japan), so the white lights coming towards you are always on the right and the red lights going away from you are always on the left, whichever angle you face the road from. It's a subtle effect, but a very important one to get right, I think.
Most importantly, all of this is done in compatibility with OpenGL2.1, so even older graphics hardware, Intel embedded chipsets and Macbooks will have no trouble rendering these scenes. In fact, with the optimisations I've made to the lighting, it runs even smoother than it did previously!
Final Result
Editor's note: Fast-forwarding to AdvertCity's release. Here is the release trailer, showcasing the city's procedural generation: