author: Jan Douwe Beekman
title: Grammar Check Your Dungeon with Probabilistic Grammars
keywords: probabilistic grammar, procedural content generation
topics: Algorithms and Data Structures , Case studies and Applications , Creative
committee: Vadim Zaytsev ,
Marcus Gerhold
started: April 2021


This project is a crossover of game studies and generative programming.

On one side, we have procedural content generation, a powerful technique that allows to replace the static content created carefully (and expensively!) by the game designer, with the dynamic possibility to generated such content on demand. This greatly increases replayability of a game while decreasing its development costs, and opens the door to many opportunities unthinkable before, like adapting the generated content to the actual player based on the accumulated observations of the player. In one form or another, PCG has been used in Diablo, Civilization, Minecraft, Dwarf Fortress and many other innovative and commercially successful games.

On the other side, we have probabilistic grammars, capable of expressing the notion of structural correctness. When "normal" (non-probabilistic) grammars are used to express programming languages, database schemata, XML/JSON formats and communication protocols, probabilistic ones can be used to predict DNA sequences, handle uncertain and unreliable data, automate reasoning in healthcare, generate popular tweets, infer types in programs and detect rhymes in rap lyrics. So why not game content?

For example, by randomly combining symbols L and R and rotating the result by 45ยบ, one can effortlessly create maps like this:

With some more effort, one can generate prettier locations like these:

This project is specifically about generating locations like playable levels or dungeons. It is also possible to generate other artefacts like characters and groups.

The project will be supervised by dr. Marcus Gerhold, an expert on probabilistic systems and automata, and dr. Vadim Zaytsev, specialised in grammars and generative techniques, both enthusiastic and invested in procedural content generation.