Spare Parts -- Walking a procedural path
~ written 17 May 2010 elsewhere ~
⁂
As one may be aware, my graduate studies at McGill were focused on procedural content generation (PCG) for videogames---the end result was a rather primitive-looking pipeline for generating terrain, road networks, and buildings. While I enjoyed the work, it was something of a let-down for me because the bar had already been set extraordinarily high, most notably by ETH Zürich graduates Parish and Müller in their "Procedural Modeling of Cities." Follow that link, read their paper, explore the site, and be bloody impressed.
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 applications. 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). 1
Being the consummate slacker that I am, I took one look at the algorithm in P&M's paper and dismissed it as too complicated to implement for the purposes of my thesis---I had other, more different fish to fry, after all. And so I turned my back on L-systems, which felt like something of an intellectual cop-out.
A year later though, we come to Spare Parts.
In a nutshell, Spare Parts will be "a procedurally-generated grave-robbing prototype." Thus far, I've stuck to simple methods to generate the graveyard borders and the terrain contained within: three intersected rectangles define the extent of the level, which is then filled in with a variety of tiles distributed according to a single-iteration Perlin noise function. If it sounds overly simplified, well, it is. But I have to say, I think the results aren't bad, if you'll forgive my (lack of) artistic skills:
If nothing else, I like to think they look like plausible levels, if not necessarily photorealistic. Either way though, it's still missing the finishing intermediate touch which inspired this whole darn post: randomly-generated roads. Because graveyards just aren't the same without an interminable winding path2. I decided that this was probably as good a time as any to return to L-systems, and perhaps redeem myself for having abandoned them so hastily.
Looking online for an appropriate starting point in Lua (scripting, you'll recall, being 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*. Read it at your leisure, but I'll go ahead and spoil the punchline: L-systems are bollocks. Well, not in every situation, but certainly in the case of road network generation.
* [10 Nov. 2020: The forum has since become defunct. The author has recreated the bulk of their original post here.]
P&M's L-system algorithm, like any L-system, relies on "production rules," which, on parsing a string of symbols, essentially just says "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 then comes from defining "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 vagaries3. 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 that forum post, is useless and complicated work, and I'm inclined to agree. The author then proceeds 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 is beautiful. It is the absolute height of simplicity. No housekeeping, no complicated symbols, just a priority queue and a simple loop. Developers can just focus on tailoring their globalGoals() and localConstraints() functions to the application at hand, and not worry about implementing a convoluted evaluation framework.
Needless to say, I immediately emailed the author of this forum post and offered him a beer; second, I got to work implementing his algorithm (the framework, at least) in my PCG library, and the global/local functions in Lua. For the purposes of Spare Parts, my needs are simple: roads can only be horizontal or vertical, and there are no necessary global patterns to speak of (if you've ever walked around certain parts of Père Lachaise Cemetery, you'll know what I'm talking about). I impose 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.
These are extraordinarily simple rules. But will they produce anything remotely interesting? Have a gander:
And of course, you can apply the same algorithm to the same tracts of land and still get different results...
It's all still fairly primitive, but I was primarily concerned with making "roughly believable" paths through these graveyards, and I'm happy with the results, even if they're not necessarily quite sophisticated, and lifelike. They should at least be fun to play.
1 If I'm not mistaken, the rad dudes at Introversion are using a similar system for Subversion.
2 This is something of a pun, of course, since the makers of The Graveyard also made The Path.
3 As a side-note: Przemyslaw Prusinkiewicz3a, who worked with Lindenmeyer, runs the Algorithmic Botany project at the University of Calgary, where you'll find an impressive collection of virtual plants generated by L-systems.
3a Rudzicz. Prusinkiewicz. They're cops. Polish cops.
x