AAAI Publications, Eighth Artificial Intelligence and Interactive Digital Entertainment Conference

Font Size: 
Fast Procedural Level Population with Playability Constraints
Ian D. Horswill, Leif Foged

Last modified: 2012-10-07


We examine the use of constraint propagation for populating indoor game levels with enemies and other objects.  We introduce a notion of path constraints, which bound some function over the possible paths a player might take, and show how to efficiently place objects while guaranteeing path constraints.  This allows the system to guarantee that power-ups are balanced to the number of enemies occurring in the level, that they’re placed early enough to be useful, that keys are not hidden behind the doors they are intended to unlock, and so on. We describe a constraint solver based on interval methods that allows natural processing of numeric constraints and show that it is efficient enough to be used even on very low-end platforms.


Declarative representations; constraint solving; procedural content generation

Full Text: PDF