Fast Procedural Level Population with Playability Constraints

Abstract

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.