Graph-defined Dungeons: Exploring Constraint Solving for the Generation of Action-Adventure Levels
Summary
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.