Apparently, EA just announced Spare Parts.

That’s great for them. I guess it’s just a shame that I ANNOUNCED IT FIRST!

That’ll teach me to finish my prototypes sooner…

Sigh. Well, I guess in the interest of not getting sued immediately, I’ll start referring to my (probably much better) game as something entirely different, like My Graverobbing Prototype. Has a certain zing to it.

Many moons ago, I had some blood work done as part of the process of donating my blood to the researchers where I work.

Yesterday, we had a repeat performance, during which it was ascertained that my blood is frakking awesome. Peruse the data for yourself, and tremble before my high-density lipoproteins.

Yes, this update is pointless. No, I don’t particularly care.

Montreal has grown into something of a videogaming hub over the past 10 years or so, with some of the biggest studios setting up shop here to put out some seriously triple-A titles; meanwhile, it still maintains a healthy ecosystem of smaller professional development and middleware companies. Nevertheless—near as I can figure it—it’s never had much of a non-professional gaming “scene.” That is, while there are certainly a number of more “indie” game devs/shops in town1 along with a few fledgling university programs and digital art societies2, there’s never been much impetus to get all these disparate entities and individuals together to chat and make games. Toronto, Ottawa, and Chicago (among others) have groups for the purpose—it felt as though it was time Montreal had the same.

After some back-and-forth on the subject by a number of parties on Twitter, both Mr. Matthew Gallant and Mr. Darius Kazemi independently pointed me in the direction of one Mr. Stephen Ascher, who had been interested previously in starting such an enterprise. And what do you know: a few beers and coffees later, we announced an Amazing Montreal Indie Meetup Extravaganza.

We met up last Wednesday at L’Amère à Boire brewpub (which has a fine upstairs bar equipped with a projector and even a laser pointer). The turnout was, even by my optimistic expectations, fantastic. Truly, as Kevin Costner once said: if you build it, they will tweet about it, maybe. It seems like word got out, and people really only needed a time and a place to meet—the reason and interest already being a given.

No Fun Games (of Pax Britannica fame) got things started demoing their latest: Tea Time Quarrel, created for this year’s TOJam. The night then became a bit more free-form, with developers lining up to demo works-in-progress or just rock out on some cool indie games (with Fez making a surprise and more than welcome appearance), while the rest of the (30+!!!) attendees sat, drank some fine beers, and chatted. Let us peel back the veil of time, and witness it once again in glorious Technicolor:

To shorten this post a tad, I’ll simply say that I was absolutely blown away by the response we received, and by the number of really awesome folks that came out. Stephen and I are working towards coming up with a totally rad (and more official) name for the group and the meetups, and a subsequent website where all future announcements will be made (and to which I’ll link from this site, when the time comes). Until then, I can’t wait to do it all again. Santé, mes ami(e)s.

1 See: Polytron Corporation and the Kokoromi Collective.

2 E.g., Concordia’s CART and CCGD.

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.

Getting cracked sucks. A lot. But as a wise Internet advertisement once said, when God gives you lemons, you find a new god.

It turns out that my site wasn’t necessarily specifically targeted for attack; browsing through the cracker’s manifesto and searching online for their handle (which I shall not utter here) brought up a good number of sites, each—I assume—subject to the same WordPress vulnerability.

In any case, since all of my layout files were wiped out (and not backed up¹), I whipped up a new look & feel (PROTIP: You are looking at it right now). I like it because it’s a) easy to code, and b) reduced pretty much to the functional minimum. Occam’s Design Razor, for the victory.

A few images will be missing here and there, and you’ll probably notice a few extra sidebar items popping up in the coming days, but for the most part this baby’s back on her feet.

I come back to you now, (to blog about normal boring stuff) at the turn of the tide! ²