I feel the urge of stating the obvious: randomness in Procedural Generation refers to the perceived randomness of the outcome; not the randomness of the input parameters.

In some sense this is “obvious” but, at the same time, is one of the most common mistake I see when developers tackle procedural content generation in their games. It is an understandable mistake, though. There are two assumptions we subconsciously make when we approach randomness: 1) we think that uniformly random parameters produce uniformly random outputs (that’s blatantly false), and 2) we think that uniformly random outputs yield to uniformly random perception in the human (even more false).

These are two easy points to fail at design phase. How we will see later, even big companies find out the “obviousness” of these two points only years after their product release.

Randomness in the output

First, we need to convince ourselves that it is false that uniformly random input parameters produce uniformly random results. For this, we can imagine a PCG algorithm as a function that takes some parameters \( x_1,x_2,\ldots x_n \) as input and returns something $latex y$ as output. The wrong assumption is that if we replace \( x_1,\ldots x_n \) with random variables \( X_1,\ldots X_n \) with a uniform distribution, then the function will return a random variable $latex Y$ with uniform distribution.

A trivial counter example is the function \( f(x) = 0 \). I think it is clear that the function output is not only not-uniform, but it is not random at all. However, this example tell us nothing on the problem. A more interesting and famous example is a function returning a random point in a circle. For simplicity, we assume a radius 1 circle. The generator function will be something like the following:.

This is a standard polar coordinate system, where we can use \( \rho \) in the interval \(

\), and \( \theta \) in the interval \(

\). As it is known, for each pair \( (\rho,\theta) \) we get a unique point in the circle.

In order to generate uniformly distributed point in the circle, our first idea is to chose \( \rho \) and \( \theta \) with a uniform distribution. However, the result is far from uniform.

As you can see, the points group around the center. Why? It easy to see that, according the way we are generating the points, half of the points will be in the \( \rho < 0.5 \) circle while the other half will be in the \( \rho > 0.5 \) ring. However, the area of the small circle is just 25% of the total area of the circle! We are, indeed, pushing half the point in a quarter of the area.

What we want is to generate uniform points on the area of the circle. In other words, we want that half of the points we generate will be placed in half the area (and the same for any other ratio). In the circle problem, this can be easily solved by taking the square root of \( \rho \) before generating the points. You can do the math, or look at the example below.

The circle example is a classic and well-known example, but we can apply the same reasoning to any PCG algorithm. When you are uniformly picking the input parameters of your dungeon generator are you generating uniformly distributed dungeons? If this does not work for simple circles, I think it is unlikely that it works for dungeons. Unfortunately, the solution here is much more complex, but it is worth to take the problem in mind.

Random in the perception

This is another common problem. I talked a bit about this in a previous article, but the problems returns many times even in different fields. It appears in games, when you want random abilities that seems fair to the player (that’s why a lot of MOBA use pseudo-random number generators) or music players such Apple iPods or Spotify shuffle their playlists. The problem is so common that we have the name for it: gambler’s fallacy. In short, we confuse randomness with “equally and evenly distributed events”.

The main problem here is that the final player does not always perceive true randomness as randomness. If your algorithm produces thousands of slightly different objects, even if they are technically random, if the player perceives them as “mostly the same thing” your algorithm has failed to achieve its purpose from a PCG point of view.

As a consequence, even if you have an algorithm that produce uniform randomness in the output (see above), if your output space is not uniform from a perception point of view, you still fail to achieve “true perceived randomness”. Unfortunately, understanding what means “perceived randomness” in many PCG domain is even harder that producing uniform output. For dungeon generators, this could depend on many faetures of the dungeon. For instance topology (long maze-like corridors vs. large rooms connected by short hallways), the tiles, the enemies or something else. In any case, it is not possible to guess this in advance. For this, it is important to analyze the players’ feedback in the specific game.

Combining the two

We can then conclude that we can achieve “true randomness” in PCG with the combination of two properties:

1. The algorithm should produce random results uniformly distributed in the output space.
2. The output space should contain a uniform distribution of “perceived random” results.

Both these properties are just guidelines, because it is impossible to turn them into practical rules, or even verify them, in any PCG algorithm more complex than a random number generator. Nevertheless, these are two important aspects that a PCG developer should keep in mind.

If you are interested in this topic, in literature, the combination of these two aspects takes the name of Expressive Range (click on the link for the paper on Expressive Range in PCG). But for us, this is a story for another time.