Walking the path


Originally posted on 17 May 2010 as
Spare Parts — Walking a Procedural Path
The current version has been modified for clarity.

My graduate work back at McGill (2006–2009) was focused on procedural content generation (PCG) for video games — the end result was a rather modest pipeline for generating terrain, road networks, and buildings. In the course of those studies, I came across the (much more advanced) work by ETH Zürich graduates Parish and Müller in their “Procedural Modeling of Cities.” It was an impressive project back then, and they’ve continued to develop it beyond that.

P&M’s fantastic-looking algorithm is based on a heavily-modified implementation of L-systems, named for Hungarian Aristid Lindenmeyer, who developed them to model branching systems seen in plant development; later it was applied to blood vessel networks, fractal imagery, and a few other domains. P&M made their version context-aware and applied a two-step process of 1) proposing “global goals” (e.g., roads follow a circular or other global pattern) and 2) adapting proposed roads to local constraints (e.g., roads don’t go into the water, and can intersect with previously-built roads).

While I didn’t use that approach in my own thesis work, the algorithm stuck with me for a long time afterwards, until I eventually started work on a small project I called Spare Parts. In a nutshell, it was to be “a procedurally-generated grave-robbing prototype.” The first draft used simple methods to generate the graveyard borders and the terrain contained within: three intersected rectangles for the extent of the level, which is then filled in with a variety of tiles distributed according to a single-iteration Perlin noise function. It was incredibly simplified, but the results were serviceable.

Note the small white gateway, which marks where the player starts each map.

The final touch was to add paths to the graveyard (there is precedent), and so I decided that this was probably as good a time as any to return to L-systems.

Looking online for an appropriate starting point in Lua (learning a new scripting language was one of my motivators for this prototype), and still fully expecting it to be a long and complicated process, I happened to come across this forum post. Long story short, in practical terms, L-system implementations can be drastically simplified.

P&M’s L-system algorithm, like any L-system, relies on a set of “production rules” that specify “when you see substring X, turn it into Y,” with probabilities and/or conditions sometimes associated with a given rule. The magic of L-systems is in the definition of “branch” symbols, and balancing a certain regularity of pattern with some element of chance; plants, for example, are often mathematically precise, and yet still subject to environmental vagaries. But looking at P&M’s rule set shows that about half of their rules ignore the “global goals/local constraints” pattern and are used instead for simple housekeeping: prepare a symbol (road) for deletion, delete roads in the next turn, propagate time-delay information, and so on. This, argues the author of the above forum post, is non-productive and complicated work. They proceed to systematically deconstruct the L-system algorithm given by P&M, approaching the underlying, functional core of the procedure; that is, to maintain a list of “proposed” roads, and then evaluate them in some order, see if they are acceptable (with or without some minor modifications), and then store each accepted road while “proposing” a handful more branching from it. The post gives the following (slightly modified) pseudo-code:

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
…}

Here, r(ti, ri, qi) represents any proposed road: ti is the time-step delay before this road is evaluated, ri is the actual representation of the road (e.g., a vector), and qi contains meta-information relevant to to our globalGoals function (e.g., for circular roads it might describe the polar angle, or it might declare the segment to be a highway as opposed to a country road, &c). The localConstraints() function evaluates a given road (passed by reference, so that the road can be modified—snapped to local intersections, for instance), and then determines if the road is acceptable or not. If it is, the road segment is added to segment list S, and the globalGoals() function uses that road to suggest new branching roads, which are then added back to priority queue Q with an incremented delay.

This represents a much-welcomed simplification of the original L-system algorithm, as frequently implemented. No housekeeping, no complicated symbols, just a priority queue and a simple loop. Developers can focus on tailoring their globalGoals() and localConstraints() functions to the application at hand, and not worry about implementing a convoluted evaluation framework.

I immediately got to work implementing his algorithm (in an even further-reduced form) in my PCG library, and the global/local functions in Lua. For the purposes of Spare Parts, my needs were simple: roads were only horizontal or vertical, and there were no global patterns to speak of (if you’ve ever walked around certain parts of Père Lachaise or older cemeteries, you’ll understand). I imposed the following constraints on the paths: that they form proper intersections; that, if two paths are parallel, they must be separated by a given minimum distance; and finally, that a certain minimum fraction of the terrain tiles must be “near enough” to a path. The initial results are shown below.

The results were simple, but I was primarily concerned with making “roughly believable” paths through these graveyards, and I’m happy with the results, even if they were not necessarily all that sophisticated, and lifelike. They provided a veil of verisimilitude to an otherwise empty world, and offered some varied gameplay (as per the initial design) besides.

Rocks and trees added as decorative obstacles. Eye-bleeding yellow used for contrast.
These three pictures show the same terrain, but with different generated paths.