Procedural City Generation

I was originally inspired to look into procedural city generation after reading Shamus Young’s article about creating a simple night-time procedural city using no geometry or texture assets (only code). I made my own version, but I wasn’t happy with a simple grid layout for the city and decided to take it a but further. I looked into the relevant literature concerning procedural city generation and it seems the seminal work in this area is this paper by Müller and Parish.
Pascal Müller went on to found Procedural and develop CityEngine into a full-featured product, and Procedural was then acquired by ESRI. We used CityEngine at Slant Six Games to allow us to develop sprawling worlds for our games. It’s a great product.

Road Grid Generation

As described in the paper by Müller and Parish, one can create a fairly realistic looking road grid using a variant of an L-system algorithm, extended to take into account global goals (such as population density) and local constraints (such as detecting road intersections and following coastlines). Once road grids are created, subsequent steps extract city blocks from the grid and divide the blocks into lots (also called “parcels”).
I wrote a testbed program to experiment with road, block, and lot generation:

.. and then extended my original city generator to include the road and lot information:

Like Shamus Young’s original, no textures or geometry were used to create the city. It’s all generated 100% procedurally.

Here it is in action:

It's not quite as pretty as Shamus's demo, but I was concentrating on realistic road grids and not rendering. There's plenty of road variation in there, and even some altitude changes (though I'm not drawing a ground plane, so you can see the roads float up into the sky occasionally).

Building Generation

My city generator now was a fair bit more procedurally “correct” in terms of how an actual city would be laid out, but I wasn’t happy with the hard-coded C++ algorithms for building generation.
The next logical step would be to actually try to write something akin to CGA Shape Grammar, as described by the Parish & Muller paper, and as implemented in CityEngine. CityEngine includes its own CGA parser and geometry engine, but they have no runtime component. Their geometry is all built in the tool and exported, which results in extremely large geometry datasets. What I decided to do was implement a runtime parser for CGA files. The goal was to create a system where I could create infinite worlds with very little in the way of static assets. I could fly through a world forever and generate new roads, lots, and buildings on the fly from a set of CGA files. I'll leave that for a later post.