Sunday 22 August 2010

Proceduralism: Part Three (What is Procedural?)

[You'll probably want to read the original article series that inspired this follow up, then start with parts one and two of this series.]

Alongside the attempt to define a taxonomy of procedural content, my other main goal for the PCG wiki was to list what games featured procedural content - expanding on the inadequate wikipedia entry to create a definitive go to guide if you were looking for a procedural fix. But this building this list has stumbled for two main reasons: a lack of time and contributors - which results in the majority of articles being stubs, with more polished entries where someone else has taken an interest, and a more fundamental problem with deciding whether a game is procedural or not.

But surely it should be clear whether a game is procedural? Take Elite - the canonical example of a procedural game, with an infinitely explorable universe generated from a starting seed. Elite is clearly procedural because of this infinite sandbox. Or is it?

It turns out the universe of Elite is in fact finite enough that it was possible for the founders to check the name of every planet to ensure that there were no curse words included in the final release. And if you are willing to accept a seeded universe but constant content as a starting definition for procedural, then is Eve Online procedural? What about Star Wars: Galaxies? Darwinia? Far Cry 2? Far Cry?

Well if Elite is not a good model to follow, then how about Rogue? Infinite, accessible dungeons - which implies accessibility to newly content is a prime requisite for procedurally generated games. But strategy games like Civilisation have had random maps almost as long as the strategy genre has been played on a computer, and listing every strategy game with a random map generator as a procedural game will be an enormous and potentially futile project.

So it's not simply a matter of random map generation, then how about other content like randomly varying the loot that you find. But that makes World of Warcraft as procedural as Borderlands and Left4Dead procedural because it dynamically mixes and matches zombie bodies to ensure variety in the horde.

But Left4Dead is procedural: because of the AI director, in the same way that Far Cry 2, but not the original Far Cry, is procedural because it has dynamic fire propagation. It's the emergence of interesting properties that makes a game procedural.

But this makes any game with a half-way adequate AI procedural, which is again not a useful definition from the point of view of building a wiki listing procedural games. And does a game like Deus Ex qualify as procedural because of the emergent property of using limpet mines to climb buildings? Maybe it is but Warren Spector didn't intend it that way.

We are left with two possible definitions which seem more robust but neither of which are ultimately satisfying: did the developer intend the game to be procedural, which leads to the problems of divining authorial intent, or is it procedural because I know procedural when I see it?

(I'll return to the matter of perspective later in this article series, but it is worthwhile noting that Minecraft feels more procedural than Populous because of the perspective the player sees the game from, in the same way that a first person shooter or platformer with random maps and AI feels more procedural than a top down strategy game with the same features. It is for this reason I've added a perspective category to games on the PCG wiki).

I want to avoid an argument about definitions for the moment, and try to look at some minimal examples of what we can mean by procedural. Take the following BASIC code:

10 PRINT HELLO WORLD
20 GOTO 10

Which if you run it, results as follows:

HELLO WORLD
HELLO WORLD
HELLO WORLD
...

The output of this code results in infinite content, and the code itself clearly defines a procedure for generating this content. But you and I both would have extreme difficulty in describing this as procedural content, because it is not very interesting.

What do I mean by interesting? That is the heart of whether a piece of content can be adequately described as procedural or not. If we just consider the output of an infinite number of HELLO WORLDS, we can see the content is not very interesting, because the underlying code required to generate this content is not particularly complex, and the result completely predictable.

But at the other extreme, apparently complete randomness isn't terribly complicated an algorithm either, such as this Python implementation of a multiple with carry random number generator shows. The output of this algorithm is too random for any human to detect the underlying pattern, while the pattern itself is compressible in a sense that true random numbers, such as thermal noise, are not.

The fact that a less than one page long algorithm can generate 'random' output as far as a person is concerned implies there is a not terribly complicated threshold past which someone is incapable of distinguishing an algorithm from random noise.

What fascinates me about procedural content is my belief that there another useful boundary between trivially predictable output and effectively random output - what I've called elsewhere biased randomness - that is randomness produced by an underlying discoverable rule set. That is not to say that randomness is uninteresting - given sufficient incentives, we can become horribly addicted to random output - but I think there is more value in exploring biased randomness than coming up with better ways to package completely random content in a compelling format.

You may be thinking here of the mathematical concept of 'chaos' - but while this may be a useful analogy, don't confuse the two. There are plenty of chaotic systems which can be easily comprehended by a person (the outcome just can't be predicted), and just as there are plenty of ordered systems which are similarly incomprehensible. Even the predictable behaviour of two body planetary motion was unknown until the recent past in terms of the overall human evolution of thought.

It is also likely the case that compelling biased randomness is even more complex than the algorithm required to implement effective randomly content - just in the same way that the real world is more complex a place than an aggregation of random elements. This will also be a challenge for biased randomness: justifying the additional time and expense above strictly random content.

So my answer to the question 'what is a procedural game?' is that the game presents a biased randomness where discovering the underlying rules is a necessary part of play. That doesn't help much when it comes to deciding what games should be in the wiki, but at least I have a set of criteria which feels more objective than those I outlined at the start of this article.

Whether the biased randomness in a game is interesting is a subjective exercise: one person's discoverable rule set is another person's fiat from the gods. But I don't believe this is an unsolvable problem: there are definite strategies to discovering whether something is interesting, and ways of dealing with the most common criticisms of procedural content generation. And the question of what people find interesting isn't just an issue for game design; with procedural content, it allows us to build a more precise model of the mind.

And I'll be talking about that in part four.

5 comments:

Rune Skovbo Johansen said...

> listing every strategy game with a random map generator as a procedural game will be an enormous and potentially futile project.

That's not exactly a good argument for not defining them as procedural, is it? :)

I think it would be best to again return to thinking of procedural generation as a continuum where you cannot clearly define a dividing line between what is a "procedural game" and what isn't.

As for which games to include on the wiki, why not just avoid the "gotta catch 'em all" mentality and instead just include the ones you actually think are interesting and encourage others to do the same? So what if there's some games out there that have procedural elements yet are not on the wiki? If they're not interesting from a procedural generation perspective, just ignore them.

I also think the definition "The game presents a biased randomness where discovering the underlying rules is a necessary part of play" is utterly confusing, at least to me. What does "discovering the underlying rules" mean? In a game about solving mazes, which feature procedurally generated mazes, the player doesn't have to understand which maze generation algorithm was used in order to play the game, yet I would definitely define it as a "procedural game".

I don't find the 'biased randomness' concept too useful either in determining if something is procedural generation or not. It sort of only makes sense for me with regards to plain arrays of values - as soon as an algorithm is also involved I'm not sure what makes the generation 'biased' or not in your terms.

Andrew Doull said...

Rune: I'm not trying to define them as not procedural; I'm trying to figure out why they feel 'less' procedural.

As always, I'm happy to resort to prototype theory to explain how meaning is distributed. Here I'm trying to figure out what the features are which make something less or more prototypically procedural.

> I also think the definition "The game presents a biased randomness where discovering the underlying rules is a necessary part of play" is utterly confusing, at least to me. What does "discovering the underlying rules" mean? In a game about solving mazes, which feature procedurally generated mazes, the player doesn't have to understand which maze generation algorithm was used in order to play the game, yet I would definitely define it as a "procedural game".

You're conflating the rules used to generate the terrain with the rules used to explore that terrain. In the maze example, the discoverable rule might be 'always follow the right hand turn'.

Similarly you don't need to understand the Copernican model of the solar system to know that moss grows on the south side of the tree (At least in my neck of the woods).

I'll agree that I could definitely improve the clarity of what I'm trying to say: I'll try a rewrite.

Dan Kline said...

There's a mathematical concept of complexity, which is pretty much as you describe (ever changing systems that follow a set of rules). Here chaotic/complex/static forms an axis.

The concepts extend to many other fields as well (biology, chemistry, economics). It's a fairly new academic field of its own.

The Game of Life would be a canonical example of a complex system.

Rune Skovbo Johansen said...

> I'll agree that I could definitely improve the clarity of what I'm trying to say

Yeah, I'm not really trying to disagree here; my main point is just that I'm a bit confused over the definitions used. :)

jdunson said...

A quick thought: in discussing "procedurally generated content" and whether a game qualifies, it sounds like the question here is less "what is 'procedural'?" and more "what is 'content'?".

Perhaps if we started talking about "procedurally generated filler" vs. "procedurally generated content" it would provide some ideas.

In (standard single-player) Civilization, the map is the scenario; small differences in output can generate significant differences in play, and choosing world generation scripts is a major part of picking what sort of game experience you want to have. By contrast, a nearly identical map generator used to generate background planets for a space shooter would be just creating filler; so one cannot tell from the procedure itself (absent of context) whether it's generating content or not.

Switching to a different train of thought, I tend to distinguish between "procedurally generated" and "randomly generated" (although they're a continuum in some ways). To me, "procedurally generated" implies some sort of intent or feedback in the procedure. Examples might be a map generator that attempts to refine an initially random world heightmap to look more like a plausibly-real continent; or a level generator that attempts to create a flow of play with something akin to classical dramatic structure (with sequences of rising action, climax, falling action). The simply random map generated by, say, an artillery dual game, or an older JRPG's random encounters, is IMO not really "procedural"; although it's possible that it may be a small component of a larger procedural whole.