Why Oatmeal is Cheap: Kolmogorov Complexity and Procedural Generation
This provides foundational insights for game developers and researchers in procedural generation, though it is incremental in linking existing theory to practical design.
The paper tackles the problem of understanding the theoretical limits of procedural content generation in games by proving a relationship between Kolmogorov complexity of artifacts and generator possibility space size, identifying constraints on knowledge, output density, and artifact intricacy.
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.