Dynamic vs Static Procedural Generation

Preface: These are some rough notes written for #NotGDC 2017, a non-event for those game developers who couldn’t attend GDC. Feedback welcome.

Lately I’ve been interested in the concept of using dynamic or static elements in procedural generation. I’m not sure if this has been discussed in any great length, so I decided to write this article and hopefully seed some ideas. This article assumes you know what procedural generation is, and are familiar with its use in games such as Elite, Minecraft, Spelunky, Nethack, and Dwarf Fortress.

Definitions

We can define dynamic generation to mean the generation of content that occurs during the execution of the game. In Minecraft, for example, different regions of the world are not generated until the moment a player is in range.

Static generation, on the other hand, is any procedural generation that occurs before the game is run. The output of that generation could then be loaded at run-time or be incorporated in some other way into the code or system.

The term procedural generation within games typically refers to dynamic generation, whereas procedural generation in film and stories (see NaNoGenMo) is static.

Many approaches to generation will incorporate some dynamic and some static elements. For instance, Spelunky dynamically stitches together pre-built parts to create its dungeons. Another example is the Perlin Noise algorithm, which incorporates a statically-computed table that dramatically improves its efficiency. A last example, Speedtree, is a modelling system that is used to create static tree meshes using procedural generation techniques.

My main interest in this topic is not in definitions — I’m interested in how a designer can incorporate different aspects of procedural generation to make interesting and amazing worlds. With that goal in mind let’s look at the pros and cons of each approach, using the generation of an entire game world as an example. (These points aren’t entirely exclusive, and much research in dynamic generation has mitigated some disadvantages. See, for example, aesthetic selection research in the field of computational creativity.)

Dynamic Generation: Pros and Cons

Consider we have built a system that can, at run-time, generate an entire populated world. There are many advantages to doing this dynamically:

• Infinite variation ¹: System never runs out of generated worlds;
• Infinite size ¹: System can make a world that goes on forever;
• Infinite detail ¹: System can add ever-increasing amounts of detail to all aspects of a world;
• Can be fast: With lazy evaluation we only need to generate what the player sees, although in practise this leads to less interesting worlds; and,
• Can use player/system input: System can use inputs from player (such as their name) as part of the generation procedure;

The first two points are the typical motivation for procedural generation in games. A developer might elect to have generated content in order to offer the player an infinite variety of games, and/or an infinite expanse to explore. By implementing the algorithm at run-time, the player’s system has complete freedom to generate the world. The third point, infinite detail, has not been well-explored in games, beyond its use in algorithmic texture systems (see e.g., Allegorithmic).

Using player behaviour and situation as inputs to the generation is an intriguing and largely unexplored avenue. One example would be to use the player’s actions in one game to generate the history of the world in their next game. A more sophisticated example: Monitor what the player’s attention is on as they play the game and flesh out new stories and aspects of the world that complement’s that interest.

Dynamic procedural generation is not without its disadvantages. Here are a few:

• Computational complexity affects player: To generate more interesting worlds, the player has to wait longer;
• Limited control over output: Incorporating a designer into the system can only be done at the algorithm design stage;
• Complex: The complexity of the algorithm typically explodes the more design/intent/creativity/excitement the world has; and,
• Language-bound: The algorithms typically have to be written in the same language as the game engine.

Static Generation: Pros and Cons

Now consider the alternative, in which we generate a world to be shipped with the game. It may be a game with one extremely complex world, or the game may randomly select from thousands of worlds. Some native advantages of statically generating content are:

• Can choose best results: You can generate thousands of worlds and only ship the interesting ones;
• Can combine with other tools: You can use the generation as part of a general content-creation process;
• Computational complexity doesn’t affect player: You can use as many computational resources as you can afford (for example you could hire a cluster of supercomputers to simulate a complex history of a planet); and,
• Can use any language/system: You aren’t restricted to using the language your game is built with.

The first point involves procedural generation as a design assistant — it suggests designs and we select the ones we like. We can feed those suggestions back into the system to drive further designs (as in the process of aesthetic selection) or throw an Amazon Mechnical Turk at it to help sift through the design space.

Combining algorithms within a content-creation process is standard practise in films and games.

The third point on computational complexity can trade algorithm development for computation time. As efficiency is not a priority, you can now substitute simulation (see e.g., Karl Sims’ work) and probabilistic algorithms to find decent solutions to your content creation. We see this already in games, with light-baking that caches a light simulation, and I think it can apply equally as powerfully to procedural methods.

The last point (not being restricted to the same language as your game engine) can be extremely liberating. Many systems used in data processing, data science, and machine-learning, for instance, are complex and would be very difficult to incorporate within a game engine. You could use these systems, and other open source software, to generate a range of interesting worlds, and then package the worlds directly with your game.

The primary disadvantages of static generation are based on the amount of data that is required:

• Data-heavy: Assuming your algorithms aren’t available at run-time, your pre-generated worlds could require a lot of disk space;
• Limited to a finite quantity: You can only ship N worlds. If N is bigger than the number of worlds your players expect then this is not an issue; Limited to a finite detail: The amount of detail affects data, so you are naturally bound to limiting this too; and,
• Can’t respond to dynamic events: Static content cannot respond to player input.

The Infinite World Is Not Enough

Procedural generation has come a long way in games, from 30 years ago with Elite, up to the recent No Man’s Sky. These games use dynamic generation to offer an entire galaxy’s worth of content with minimal data. But the allure of the infinite galaxy is wearing off. If your galaxy doesn’t have sufficient novelty, even if you have billions of worlds in your game, then a player will see the patterns and begin to get bored.

If we are not allured by the promise of infinite content, the benefits of dynamic generation start to dwindle. Procedural generation is a machine for generating infinite content, but it can also be much more. The examples are many:

• Use a cluster to simulate a complex and rich history for your game world;
• Statically generate a set of rough levels, which are dynamically refined;
• Use algorithms to statically fill in all the tiny details of your universe;
• Pre-generate a corpus of content that is dynamically stitched together; or,
• Build a game that generates its levels on a supercomputer and then distributes this new world to its players each day.

Static generation is a largely unexplored space in game development, and I’d like to see games incorporate more aspects of it. So consider the above points when designing your next project, as you may not need the dynamic form of procedural generation at all. Let me know what you come up with!

Footnotes:

1. Infinite worlds, size, and detail are inevitably bound by computational resources.

Author Bio: Hi, I’m a game developer working on a game called Moonman. I think about procedural generation a lot. Talk to me at @eigenbom.