I made another small, obnoxious prototype-y game, Everything is Wonderful.

Progress on the recently de-titlised procedural stealth game was slow (many random engine refactors), so I took a break to learn the LÖVE2D API, and see if I could throw together a game in a jam-like time frame (two days to a week).

Mission: Potentially Accomplished!

It was vaguely inspired by the G20 Summit, and the fun with nomenclature they clearly had in granting police unreasonable powers under the “Public Works Protection Act.” The rest just came from me being bored at work.

It’s not exactly a very deep or subtle game; nor, frankly, is it that much fun. But it came together on schedule, so I’m pleased. As others have said, putting together even cheap, short, and unpolished games can be a good thing at times.

Instructions

• Use the arrow keys to do everything.
• Don’t leave the designated area.
• Don’t get caught with illicit materials.

Download the game here.

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). ¹

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, as previously advertised.

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.

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 Prusinkiewicz^3a, 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.

I enjoy making videogames.

I also enjoy the concept of procedural content generation.

With a modest amount of intellectual calisthenics, you—the reader at home—can therefore deduce that I enjoy designing, and sometimes even making, videogames featuring procedural content generation (PCG). Now, I’ll be the first to admit that my track record thus far is somewhat underwhelming, but there really is only one way to address that: victory bonds.

Oh, we do have fun, don’t we? In any case, it became apparent to me recently that the only way to improve in this sort of field is through brute-force experience. The best games don’t necessarily come from the most technically savvy coders, or from the most ludologically-literate alumni of Mrs. Hubbard’s Royal School of Game Design. Not to belittle either of course, but by and large, it seems to me that the best way to get ahead is to simply hunker down and hammer out games.

Instead of switching directly to my rather larger-scale backburner project¹, I figured I’d aim somewhat lower, and try to put together something a) more manageable, and b) more instructional.

By “instructional,” I mean there were a few facets of game programming which I’d let atrophy (or had never actually exercised previously), and which I hoped to address with this new project. In particular:

• Shaders — Obviously, the most interesting visual effects are generally implemented through shaders, and, sadly, I’d never tinkered with them before. Now, a game like The American Dream clearly doesn’t really need that treatment, but future projects likely will.
• LUA — Scripting is great: it’s quick, intuitive, and ensures that oh-so-important separation of game engine and game logic. My previous projects suffered from being far too hard-coded, which made experimenting with and extending them difficult. Therefore, I wanted this new project to rely as much on scripting as possible.
• PCG algorithms — My thesis work was a little bit heavy-handed in the way it sought to enforce a certain PCG pipeline—landscape before cities before buildings, &c. In the interest of flexibility, I have since decided it would instead be best to simply create a PCG library that implements a few basic techniques and algorithms. This API could then be used by developers to simplify their work, in somewhat the same way that one uses SDL for graphics and input. Of course, that requires that I actually implement some algorithms, and so I wanted this potential project to make use of PCG techniques.

All I needed was a theme. Perhaps because Monaco had recently been generating increasing amounts of buzz, perhaps because of a growing fascination with roguelikes, or perhaps because of the 20-stone industrial vats of mescaline I’d been ingesting, the first idea to pop into my head was grave robbing. More particularly: a stealthy 2D top-down grave robbing game, wherein the objective is to scour a randomly-generated graveyard for body parts, all while avoiding patrolling English bobbies and wandering phantasms/zombies.

Thus was born “Spare Parts,” an evolving and only vaguely-defined prototype. As I say, it is primarily an exercise designed for me to level up my own skillset, and I don’t have much to show for it at the moment—nor should anyone expect much more than a barely-playable toy in the end. But one thing you can expect is to hear more about it in the coming weeks.

Let us—in the words of the great poets—do this thing.