Graph-defined Dungeons: Exploring Constraint Solving for the Generation of Action-Adventure Levels

Abstract

Procedural generation is an interesting field to assist the creative process. Recently, constraint solving methods have been getting more focus. An advantage is that they allow for a declarative specification of content. These methods typically restrict themselves to a grid structure. We explore if constraint solving can be applied to dungeon generation and if we can abandon the grid-based nature of these methods. We created a system where designers can define a graph that governs the topology of a dungeon, we then use constraint solving to find pieces that fit this layout. This is done with backtracking and a modified version of Mackworth’s AC3 algorithm.