ABSTRACT

Although procedural generation is popular among game developers, academic research on the topic has primarily focused on new applications, with some research into empirical analysis. In this paper we relate theoretical work in information theory to the generation of content for games. We prove that there is a relationship between the Kolomogorov complexity of the most complex artifact a generator can produce, and the size of that generator’s possibility space. In doing so, we identify the limiting relationship between the knowledge encoded in a generator, the density of its output space, and the intricacy of the artifacts it produces. We relate our result to the experience of expert procedural generator designers, and illustrate it with some examples.

THEOREM

• |G| is the minimal length of the generator's source code
• P(G) is the number of artefacts in the generator's possibility space, p(G) is the log2 of that number
• K*(G) is the highest Kolmogorov complexity among all the artefacts in the possibility space
• K(G) is the average

|G| ≥ K*(G) - p(G) ≥ 0

P(G) ⋅ K(G) ≥ |G|