The platonic Procedural Content Generation algorithm allows you to create entire universes by pressing a button:

We're not quite there yet, because it turns out to be a tough problem, but in this article, we wanted to offer a few thoughts that might bring us one step closer.

Procedural Content Generation (PCG) -- the algorithmic creation of anything from background scenery to symphonies to storylines -- is a compelling idea, right?

Manually creating gaming worlds takes time, and storing it all takes massive gobs of space. Since the days of Starflight and Elite, developers have worked towards getting computers to the point where they can be boundlessly creative.

Broadly, developers often lean on PCG for three reasons:

We also find that there's another, hidden benefit:

In this article, we'll talk about PCG's history, problems, solutions, and methods we've discovered while using it in our 2009 title, AaaaaAAaaaAAAaaAAAAaAAAAA!!! -- A Reckless Disregard for Gravity (Aaaaa! for short) and our upcoming 1... 2... 3... KICK IT! -- Drop That Beat Like an Ugly Baby (aka Ugly Baby).

Spoiler: We favor a modular, graph-based system to benefit from the upsides of PCG while mitigating some downsides. That's it in a nutshell. You are now free to either read the rest of the article or become the leader of a pack of Alaskan Malamutes.

Successes in Games

First off, there's some evidence that PCG is actually viable/useful, despite sometimes seeming like the flying car -- forever in sight, but never (yet) practical.

Rogue! It's still a great example of procedurally generated content in games. Created around 1980, the game empowered the computer, itself, to generate a fantasy world as you played, building subterranean rooms and twisty passages and populating them with (pre-created) potions, enemies, and weapons. This style of dungeon creation is successful (Hack, Moria, Larn, Nethack, Angband, Dungeon Siege, Dungeon Siege II, Diablo, Diablo II, and Diablo III, to name just a few), and relatively well-investigated, with many developers creating roguelikes and many resources for roguelike development.

We couldn't do an article on PCG without talking about Rogue, but we're using a screenshot from Temple of Apshai Trilogy for the ST instead, just to be different.

On a galactic sale, Starflight (1986) and its sequel gave us dozens of star systems and hundreds of worlds to explore. Each system contained a number of planets, and each planet was assigned a number of characteristics (surface temperature, gravity, weather, atmosphere, hydrosphere).

What was particularly amazing for the time was that you could land your planetary module on any number of these and explore winding coastlines and mountains, populated by mineral deposits (aluminum, molybdenum, and a dozen others) and living organisms (sessile and mobile), with density and type depending on elevation and planet type. The original could all fit on a double-sided 5.25" floppy. Braben/Bell's classic Elite (1984) is, perhaps, even better known for creating eight galaxies worth of planets you could fly and trade within.

Starflight 2 even included villages you could trade with.

More recently, Spore demonstrated procedural model generation and animation. Here, players could tweak the length and girth of a creature's bones, add limbs, eyes, ears, wings, and so forth, making creativity a part of gameplay.

Creature generation in Spore.

And .kkrieger wowed the world some years back by stuffing an entire first-person shooter into less disk space than this article.

.kkrieger, which uses only 97,280 bytes on disk.

PCG's been used throughout the history of games, and is still being used today. Surely, it should be used for everything...

...right?

PCG In Content Creation Tools

In our 2009 title, Aaaaa!, we wanted to explore both tools that automated tasks and those that aided creativity.

Aaaaa!, with PCG textures and level both PCG-created, then hand-modified.

Have you ever painted an image pixel by pixel? Or perhaps by POKEing memory locations? It's tedious, so developers created better tools for digital artists -- nowadays, you can move your mouse to light those pixels up, draw a filled rectangle, or render gradient-filled text.

Automation is important, as it saves time -- these tools generally do exactly what we expect them to. Click at one point on the canvas, then click at another. You now have exactly the filled rectangle you expected.

Aaaaa! is a BASE jumping game that took place amongst the buildings in a floating futuristic Boston, Massachusetts. We created much of this content by hand, placing skyscrapers, girders, walkways, signage, flying cars, and giant potatoes within our in-game editor.

The tools were technically fine, but we eventually, collectively, hit a rut -- things started to feel samey, in part because the tools made particular tasks easy, while others were difficult.

For example, it was easy to drop a few buildings into the level editor, and decorate them with scoring plates:

However, creating something more intricate required tedious hand-placement of objects, and while we could have sucked it up and placed everything manually (perhaps hiring more level designers for more hours), a better solution involved automation -- for example, a script that simply generated a column of scoring plates, which we'd then drag into patterns.

A natural next step was to tweak and place the plates along randomized sinusoidal paths:

# Create 40 plates in a sinusoidal pattern:

for i in 0..40:

plate.x = sin(i*freq1)*amplitude

plate.y = sin(i*freq2)* amplitude

The real fun came when we started plugging high frequencies into them to create something ridiculous:

Things that were completely unplayable popped up, but so did some things that ended up being fun in ways we didn't expect. It's this bit that really interested us, because we were neck-deep in level design, and things like this provided a fresh look at things.

This is a trivially simple example of a "procedurally generated" level, but more than once, using simple scripts like it, we encountered things that made us grin. These changed the ways we built levels, and suggested new challenges for players.

Soon, we had a small collection of utility scripts that would create what we called "level skeletons". We'd abuse them to come up with things that delighted us ("Ah! We never intended for that to happen. That's neat!"), then hand-create the rest of the level.

Aaaaa! did really well for us, bringing us an IGF nomination, among other awards. So, buoyed by the confidence we gained here, we decided to throw caution to the wind: in our next game, we'd use PCG for all level design. After all, we're decent programmers... Wouldn't it be easy to just program everything?

(Spoiler: It was not.)

PCG is a Panacea That Will Cure Leprosy

Our next title, Ugly Baby, would play much like Aaaaa!, but we wanted it to generate all of its level structure algorithmically, at runtime, based on player-supplied media. This media could be anything from music, a la Audiosurf or Beat Hazard, to a video to a block of the Declaration of Independence. We describe the game like this:

"Battle your favorite drum 'n' bass track, or relax as you fly through that trance album. 'Ugly Baby' takes your MP3 music and creates floating worlds for you to fight through."

Our hopes were (and still are) that PCG would allow us to:

We wanted to create scripts that read in the music and spat out Aaaaa!-like levels with enemies, figuring that our understanding of floating architecture and generative art would make it simple. As it happened, a nine-month project turned into 24 months before we even began to get our footing.

We ended up hitting four major problems:

1. Manual creation's strengths are PCG's weaknesses.

Algorithms and hand-created content often have complementary strengths. Algorithms can beat hand-tweaking if you have an enormous mountain and want to see what happens if it undergoes erosion. While you could easily spend an entire day sculpting it by hand, running it through an erosion tool will take moments, and allow you to try different things.

On the other hand, if you want to add a few trees around the entrance to a cave, it's usually easier to just plop a few down by hand and nudge them around than to script that. If you want to carve the world "HELP" in a beach, it's easier to just select a tool and draw the word. We learned this the hard way, through this process:

So, we'd get into a mode where we created a promising script, tweaked endlessly, and hit a local maximum: the initial script would establish a certain type of level layout, and we'd spend hours exploring the best permutations of that rather than looking elsewhere. We'd later find that the distance between "not fun" and "fun" was small. But it can be time-consuming to experiment with an algorithm or to augment it to include interesting details.

Solution: experimentation is sometimes best done by hand; we can then learn from what we create, then have the algorithm mimic something that turns out looking good.

2. It's easy to create repetitive content.

We'll borrow a quote from Alex Norton's AltDevBlogADay post:

Why have world borders at all? Procedural generation code hasn’t changed much in the last 25 years. People are still stuck using fractals and diamonds and blobs to do everything, which becomes repetitive and quite simply looks like procedurally generated content. To any programmer looking at it, it virtually smells of procedural generation.

If we're not careful, we see the same stuff over and over again. For example, in Ugly Baby, either of the below levels is interesting for about 15 seconds, after which point they become tedious:

Since levels were each about 5 minutes long, that meant we'd want to switch things up a few dozen times over the course of a level. One common solution is to swap out different algorithms periodically, but that can be jarring -- imagine a PCG forest that ended sharply on a boundary. Another is to augment the algorithm with tidbits of new stuff along the way, and gradually morph between things, but we ran into problems with complexity, as we touch on in the next point.

3. As PCG algorithms become more expressive, they seem to become disproportionately more complex to design.

It's really easy to create an algorithm that generates a simple level -- but as we made things more complex, implementation became disproportionately more difficult. For example, in Ugly Baby, we had early success creating a script that scattered buildings around a map. However, augmenting that resulted in this internal conversation:

"That looks great; what happens if we group those in clusters?"

"Okay, but they're now too regular. Mix them up a bit."

"Let's add some scoring plates, tunnels, moving platforms, and fan blades."

"Oops, the scoring plates are intersecting the buildings. Move them apart. And center the fan blades in the tunnels except when preceded by a moving platform, but not if there were fan blades centered in tunnels before, because that gets boring."

"Well, now, nothing works."

In the same way that a neophyte game developer can see a 3D character walking around a grassy terrain will say, "Hey, I can make that MMORPG, easy!", we figured that if simple scripts created interesting results, we could simply extend them ad infinitum to create proportionally more awesome ones. Interesting structures start to require support mechanisms and carefully engineered exclusions.

4. Interesting PCG often creates either 1) stupid or 2) boring content.

The simplest random name generator we've seen looks like this:

# Generate random letters, yo:

for i in 1..random_number():

name += random_ character()

It's possible to generate every awesome fantasy, sci-fi or baby name you can possibly imagine -- given enough iterations, it'll come up with "Captain Rock McSpectacular," which is a great name. But it'll mostly generate junk like "ergihwe`=-ufaw38o72wenufse," which is completely useless to you. Probably.

In Ugly Baby, we did similar -- a relatively unconstrained algorithm that spat random pieces around a central axis created a simple, playable tunnel. The algorithm went something like this:

On one run, that produced this:

Visually interesting, and actually useful to us -- it was a tunnel! Running the same script a second time generated an interesting sequence of hairy, finger-looking things, followed by another tunnel:

Also interesting and unexpected, and still useful. It was something the player could fly through. A third run:

This produced a completely impenetrable path comprising enough polygons to tank the framerate. It was pretty, and potentially useable elsewhere, but didn't compose a tunnel.

One solution to this problem is to start constraining parameters. In the earlier example of the name generator, perhaps we construct a grammar (consonant + vowel + consonant + vowel + consonant), or to keep a list of common first names and surnames, and simply string those together ("Billy Margaret Smith"). Similarly, in our tunnel example, perhaps we only construct tunnels out of pieces that are less than a certain volume, or limit the total number of high-poly base pieces.

The (sub-)problem with this is:

A Modular Approach to Level Structure

In the three years we've been working on Ugly Baby, we haven't solved all of these problems, but we've had some success when combining simple, modular concepts to produce complex results.

Early successes in programmatically creating level skeletons in Aaaaa! were a boon, so we went back to those roots. It's actually pretty easy to create visually interesting things by taking simple structures and iterating on them. Take, for example, a sphere made out of cubes:

This time, instead of adding complexity to that algorithm, we took the output and iteratively modified it:

The end result doesn't look like a sphere at all:

What's so interesting to us about this simple concept is threefold: first, we can feed slightly different parameters in and get significantly different geometry out; second, in Ugly Baby, we can tie those parameters to the audio stream, so that the music drives the level's appearance; and finally, the modification pass is independent of the base structure, so we could just as easily apply the above to a grid of cubes and get something completely novel and (possibly) useful.

This was promising, so we formalized this. An Ugly Baby level generator consists of three types of modules:

Here's all that in action:

Step 1: The player flies along a linear path, so let's start by simply creating a simple column of blocks along the falling axis.

Code:

# Instantiate the column:

sequencer_column = sequencer.Column()

queue = sequencer_column.iterate()

Step 2: This level's like a rails shooter, so let's create something that looks more like a tunnel. Let's swap out the single column for six of them (essentially the edges of a cylinder). This takes some basic parameters, such as the vertical distance between blocks and the number of columns of blocks around the axis.

Code:

# Instantiate the cylinder:

sequencer_cylinder = sequencer.Cylinder(layer_delta=4, blocks=6)

queue = sequencer_cylinder.iterate()

Step 3: Apply a scale to every piece that the sequencer generates.

Code:

# Change every piece's scale:

mutator.scale(queue, [1, 4, 1])

Step 4: We wrote a mutator node that simply reorients a piece such that one side faces the Z- axis, and apply that to all pieces.

Code:

# Turn pieces to face the player's falling (z) axis:

mutator.face_axis(queue)

Step 5: An "Every-N" selector node simply grabs one out of every N pieces fed into it. Here, we want to select every fourth piece and use a mutator to turn them red.

Code:

# Get a list of every 4th pieces that comes into the queue:

every_4th_piece = selector.every_n(queue, 4)

# Turn those pieces reddish:

mutator.set_color(every_4th_piece, [255, 32, 0])

Step 6: Finally, let's orient them sinusoidally over vertical distance.

Code:

# Pan from -45..45 depending on a piece's position along the player's falling axis:

mutator.cyclic_rotate(queue, freq=0.1, low=[-45, 0, 0], high=[45, 0, 0])

From here, we can do a number of things:

1. As each of these effects is separated out, we're able to swap things in and out. This modularity helps us try new things and new patterns out of old ones.

2. Ugly Baby is about a connection between visuals and music. We can take advantage of the fact that we know where the player's going to be at any given point in the music, so we can take a look at the audio signal and construct things based on that.

For example, we've done this by constricting the tunnel during louder parts of a song or changing piece colors based on the high frequency components of the audio signal.

3. We can allow the player to tweak some of these values to create their own levels. What if, instead of six columns, they want two? Or, what if the pieces should all beextremely fat?

Small changes in mutator parameters led to understandable but tangible changes in the level. Here, we just played with number and scale of the columns, along with the base model that comprises the columns:

We then created a vocabulary of these (e.g. a grid of objects, below, to the left), and combined them (a grid plus a ring of objects, lower right).

That's worked well for more abstract things, but we also wanted to see if this worked with more organic structures.

Modules in Organic Model Creation

In Ugly Baby, we complement the abstract, geometric level design with models that were more organic. To wit, we created a graphical, node-based utility within Maya, called DING. Here's the process of creating an insect within that environment.

We begin by generating a cylinder. Above are two screenshots -- the top one displays the graph (the left node creates a cylinder; the right node displays it).

The lower image displays the resulting model. DING creates the geometry, and Maya displays it (and later exports it to FBX).

We then apply a (non-destructive) taper to the cylinder, making it fatter in some places, and thinner in others. The graph you see is the taper's profile -- we set this manually, starting out fat, pulling in at the joint, and eventually tapering at the foot.

We toss in nodes (in red) to reorient the piece vertically, then add a "ring" node, which creates a ring of six of the shape.

We add in a sphere node, then merge that (boolean union node) with the ring. It's beginning to look something like a spider.

As we tapered the leg before, we now add a contour node to the entire thing. This pinches the whole model's middle. We also subdivide the mesh to make it smoother.

Finally, let's squash the heck out of the front, contouring along the perpendicular axis. The resulting shape looks something like a tick.

As the model's not generated at runtime, it's not reactive to the music, the way the level structure is. But it does satisfy two of our goals, in that it has allowed us to create interesting content quickly (this approach is accessible to our team members not familiar with Maya), and it allows us to experiment a great deal. Since all of these operations are nondestructive, we can increase decrease the number of legs in the ring; change the contour profile (below); or even swap out the cylinder or sphere primitives and see what happens. Next on our Christmas wishlist is a "randomize" button.

It's worth noting that graph-based tools exist for all sorts of uses. We went abstract for Ugly Baby's level design and organic for the enemies, but in our 2011 follow-up to Aaaaa! (called AaaaaAAaaaAAAaaAAAAaAAAAA!!! for the Awesome), we wanted realistic textures, for which we went with the excellent node-based Genetica by Spiral Graphics.

Conclusion

While "going modular" isn't new, and connecting nodes together hasn't magically solved all our level generation problems of intersecting objects or nonsensical output, it has helped us become more productive and "clip off the degenerate branches" of content generation while keeping the useful output.

As such, we've been able to retain PCG's strengths (quicker content generation, dynamic content, smaller on-disk footprint, and enhanced creativity through happy accidents) while mitigating their downsides (avoiding a spaghetti mass of code makes things more manageable, etc.). And while PCG isn't a panacea, we think we're using it to successfully create compelling content otherwise inaccessible to us.

So, that's that! We're not PCG experts, but we hope that this article has added a few more data points in your quest for the flying car.