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.

Today has been declared Ada Lovelace Day by the fine folks over at findingada.com. Exactly why they chose March 24 is still something of a riddle to me—ironically, women are also like riddles! A-ha! What a convenient segue!

Ada Lovelace Day is named after the Ada programming language (I’m like 60% positive), which itself is named after Ada Lovelace (1815–1852). Widely accepted as the first computer programmer, Lady Lovelace has become something of a figurehead for the burgeoning girl geek community, and so, on this day, findingada.com has asked for pledges from bloggers to post about inspiring women in tech and/or science. I felt compelled to oblige, as two immediately sprung to mind:

Jane Jensen and Roberta Williams.

Despite the elaborate build-up, I’ll keep it short and simply say that these two women had a genius-level gift for imagination and for writing compelling drama, and took me (and countless others) to some incredible places.

These games and stories and places were an inspiration to my younger self, and the impact they had cannot be overstated. The games may seem modest by today’s standards, but their legacy is timeless.

Ladies: thank you.

Huzzah!

For all those who wanted to get their grubby little paws on the source code for The American Dream (and who wouldn’t?), now’s your chance!

I’ve made the code available for download along with the rest of the project, here.

The source is horribly hard-coded and likely contains a lot of unnecessary fluff, so by no means should you take this as a lesson in game programming “best practices.” But I’ve swallowed my pride and put the code out there, not for me, but for the internets…OF THE FUTURE!

Excelsior!

PS: Yes, I know, no Mac version as of yet. I’ll get on that as soon as someone wants to buy me a Mac Mini for development.

In early December, the folks over at Kokoromi announced the GAMMA 4 game design challenge, which I generally refer to as GAMM4 because I think that’s infinitely more awesome, and makes both dollars and sense.

This year’s theme is “One-Button Games”: that is, the program can accept exactly one button as input, being in either a “pressed” or “released” state. No D-pads, no joysticks, no Wiimotes, no balance boards, no Powerglove—just a single button. Well, I suppose if you only read a single Powerglove button as input, you could use that and look pretty dapper while doing so. But you get the idea.

Here, then, is the story behind my own meager submission, and a correspondingly modest postmortem.

The Reveal
Without further ado, let me be the first to announce (and who else would do it?) my GAMM4 entry: THE AMERICAN DREAM: Are We Not Drawn Onward to New Era?. Pretty pictures!

To be brutally honest, yes, I’m aware that the game looks horrendous. Laughable, even. Play it, and you’ll see it also lacks a certain amount of polish. But I’m not sure that I mind. Let’s find out why.

The Background
When GAMM4 was first announced, I had no idea what kind of game to put together, so instead I started by thinking about the different inputs one could get out of a button. As Homer Simpson once put it: “This is the light switch. It functions in both the ‘On’ and ‘Off’ mode.” What a wise lesson indeed—that light switch is a lot like life; or, more to the point, like our one button. Obviously, all you can physically get out of it is BUTTON_PRESSED and BUTTON_RELEASED signals, and the magic comes from how you put these together. So I jotted down what I called various modes of button presses: single tap, hold, release, quick taps (think Mortal Kombat’s “Break the Block” minigame), rhythmic (one-button DDR, e.g.), and so on. I drew various square wave diagrams of these different modes, just to imagine the patterns of up-ness and down-osity.

And that’s when inspiration struck. You could interpret these square wave patterns one way, then flip them and run them backwards and inverted. I started to think about palindromical gameplay, where in one mode, say, you’re pressing a button rhythmically, until there’s a mode-flip, and instead you’re now releasing the button rhythmically, exploring the Mirror universe of the first mode. The bemonocled idea I had was to use these inverses to “explore the dualities of life,” in terms that my English teachers would have loved, but which are physically painful to write. My GAMM4 submission would be a minigame collection, with candidate pairings such as love/loss, tragedy/triumph, work/play, solitude/friendship, and so on. I came up with a few very rough ideas for minigames, and started moving ahead with the coding.

The Design
I knew from the start that I wouldn’t have the time to do something overly ambitious. I do work a full-time job, and smack-dab in the middle of the GAMM4 production period were the Christmas holidays—one would think this would be a boon, but in fact it meant spending so much time with my family (time I enjoyed, obviously, but during which I could not work on my game). Because of this, and because of my artistic talent (exactly nil), I decided to go the Rohrerian route of low-fi graphics and simple mechanics to examine a single theme (or collection thereof). I took an art design cue from my Atari Flashback 2 and Pong: black and white, and rectangles only.

Somewhere along the line, I had the idea for a ticking clock main menu (see image above). Life is a lot like a ticking clock, you see, because it’s round and has twelve notches in it. The “meat” of the game, the LIFE mode, would be a random succession of the various minigames, running for all of five minutes (the GAMM4-specified time limit). LIFE would be placed at the top of the clock, “Quit” at the bottom, and in between would be 10 minigames, each one set across from its “emotional opposite.”

Unfortunately, coming up with five known life dichotomies, or ten themes in total—ones which could be translated into short, quickly-understood one-button games—proved the greatest challenge. The game’s framework (loading and randomly switching between minigames) was coming along, but eventually I hit a hard wall: I had no actual minigames to design and implement. I tried paring the list down, writing the list over from scratch, browsing Wikipedia’s list of human emotions, but nothing was coming. I knew I liked Work/Play (WORK was the first minigame implemented, as it’s the simplest), so I tried building on that. I eventually realised that Birth/Death should also play a part, since the game was about life after all. And somehow—I think perhaps in reading just those four concepts in sequence to myself (Birth, Work, Play, Death)—it started to reveal itself as the American Dream; or at least, a cynical bastard’s view of it. With that guiding principle finally fixed, and after freeing myself from the arbitrary constraint of strict life “pairs,” a number of other themes/minigames presented themselves, and I was on my way.

The Game
A download link is forthcoming. If it wasn’t already obvious, the game is extraordinarily simple and unrefined. Select one of the themes to the left or right of the main clock, and you play a tutorial version of that minigame. Select LIFE, and play through the five-minute parade of North American mediocrity, gaining points along the way. It’s fun for the nuclear family.

I think I did manage to capture the spirit of these activities well enough, at least for a beginner at this sort of thing.

• BORN is a struggle and, of course, a requirement for all the rest.
• WORK is arbitrary, repetitive, imposed, and boring. But it makes you the most points.
• PLAY is more improvised than work, and is simple to understand, but I hope moderately challenging. I tried to find some way of achieving flow; it was originally going to be a puzzle game, but this one just occurred to me as more natural.
• SHOP is an endless stream of random products of trivial distinction. And it can make you fat.
• FUCK is about synchronization and attentiveness. Max out your points by maintaining equal levels of arousal.
• KIDS requires you to lead a somewhat unpredictable sprite through various obstacles. Allowing the parent-sprite to absorb the hits loses less points than the child-sprite.
• PRAY is a meditative break from the other minigames. With the promise of huge points in the after-LIFE.
• DEAD is inevitable. Hold on all you like, but it will make no difference. Also, I needed to enforce the five-minute limit.

The Good
And so we move on to the traditional “Say X good and bad things” segment of any good postmortem.

• Some constraints are good. Initially, each minigame was to have its own unique visual “style”, and take up the whole screen/window. I quickly realised, however, that time was fleeting, and that I shouldn’t waste time on superficial visual flair. I settled on a “miniframe” inside the main window (see WORK screenshot above) which would surround each minigame, and allow me to post HUD elements around the outside. This unified “look and feel” gave me a system within which to work, and simplified some of the visual decisions down the line.
• I kind of like the games. WORK and PLAY are, I believe, particularly effective at getting their theme across. The games are perhaps obvious or lacking in design subtlety, but I think they’re playable at least.
• It’s a finished product. Nothing is more important in game design, they say, than finishing your project. And so, here it is. Just another notch on my bedpost.
• It’s not a Canabalt clone. It’s fairly evident that the GAMM4 theme was heavily inspired by Adam Saltsman’s massive one-button hit. More than anything, I wanted to avoid doing something similar, even though, for a long time, my concept for the PLAY minigame was going to be platformer-based, as no other ideas seemed to be forthcoming. I’m glad the final game moved away from that entirely—not a single platform is to be found.

The Bad

• Productivity. I’m a horrible procrastinator. Honestly, a dedicated/experienced programmer would have designed and implemented this game in a week or less. Only as the GAMM4 deadline loomed close did I establish a rigid schedule for myself. I must do so much earlier next time. But at least part of the delay was the result of…
• Designing on the fly. As noted above, my original theme list was much more abstract and difficult to actually turn into minigames. I managed to spend some time coding the underlying framework, but without even so much as a concept for some of the minigames, my work lacked direction. Things become much easier once I’d pinned down what each minigame would be.
• Some constraints are bad. As a corollary to the last point, trying to force myself to come up with a given number of perfectly opposing, abstract themes was crippling. The idea of dichotomies was interesting and helpful to begin with, but it put too much pressure on me to come up with legitimate, easily-implemented pairs. Moving away from that constraint was the biggest boon to the project; I only wish I’d realised it earlier.
• Bonus fail: No shiny polish. I wanted to add such things as leaderboards, proper “game over” screens, interesting game transitions, and more. By the end of the project, though, I was pressed for time (see “Productivity”…) and just focused instead on the main minigames. Unfortunately, that did take a toll on the overall polish of the game…if you can even say that it has any. But, look to the future! More planning, more time in the design phase, and more consideration of those small details will certainly benefit my next project.

The Ugly
Well jeez, just look at it.

And now the conclusion
This postmortem may be a bit verbose for such a simple game. I certainly don’t expect THE AMERICAN DREAM to be selected as one of the GAMM4 finalists played at the upcoming Game Developers’ Conference; this year received a record number of submissions, the majority of them from people with much more experience and talent than I.

On the other hand, this game is a completed project. The goal was to make a low-fi, slightly satirical collection of minigames, and by the power of Greyskull, I think I’ve succeeded in that much at least.