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:
- It allows us to empower creators to produce content more quickly.
- It allows a game to react to players in real-time in ways otherwise impossible.
- It allows us to reduce the on-disk footprint of content.
We also find that there's another, hidden benefit:
- It allows us to become more creative through experimentation.
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...
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:
- Generate (essentially) an infinite number of interesting levels that were more distinct than the hand-generated ones in Aaaaa!
- Generate all level content at runtime based on the player's own media.
- Allow players to participate in the world creation process by tweaking "level DNA" and "growing" their own levels.
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:
- STEP 1: Create an algorithm that generates a level skeleton. (1 hour)
- STEP 2: Test to determine that the buildings are too far apart; increase the density but finagle it so that they don't overlap. (15 minutes)
- STEP 3: Test to determine that that didn't work at all; skew the path so that the buildings weaver a bit. (15 minutes)
- STEPS 4-9: Rinse, repeat. (15 minutes apiece.)
- STEP 10: Curse that the approach isn't working, when it would be so easy to tweak by hand. (5 minutes.)
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:
- Pick a random 3D model in our library (cubes, triangles, curves).
- Pick a number N and a number M.
- Create N evenly-space rings of the model, with M instances of the model in each ring.
- Go back to step 1.
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:
- We end up clipping out some interesting branches that might surprise/delight us (goodbye, Captain Rock McSpectacular).
- We quickly fill our algorithm with special cases, and it becomes impossible to manage.
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:
- Generate the sphere of cubes.
- Apply color to the pieces (for example, by saturating them, and selecting a hue based on the object's position around a central axis).
- Change the cubes to crosses.
- Only instantiate the objects around a certain portion of the sphere.
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:
- Sequencers are modules that create things -- a sphere, a column, a grid, a cylinder, and so forth.
- Selectors return a set of all objects that satisfy a set of conditions, such as everything on one side of a plane, or all objects bigger than a breadbox.
- Mutators apply changes to objects, typically based on its properties. Examples include changing colors based on position or scaling based on orientation.
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.
# 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.
# 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.
# 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.
# Turn pieces to face the player's falling (z) axis:
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.
# 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.
# 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 be extremely 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