You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCG
This addresses a limitation in constraint-based generators for procedural content generation, allowing better control over perceived quality through statistics, but it is incremental as it builds on existing methods like WaveFunctionCollapse.
The paper tackles the problem of controlling statistical properties like design element distributions in constraint-based procedural content generation, which cannot be expressed as hard constraints, by introducing You-Only-Randomize-Once pre-rolling to craft decision variable orderings for constraint solvers, showing it effectively controls tile-grid output statistics while enforcing global constraints using off-the-shelf SAT solvers.
In procedural content generation, modeling the generation task as a constraint satisfaction problem lets us define local and global constraints on the generated output. However, a generator's perceived quality often involves statistics rather than just hard constraints. For example, we may desire that generated outputs use design elements with a similar distribution to that of reference designs. However, such statistical properties cannot be expressed directly as a hard constraint on the generation of any one output. In contrast, methods which do not use a general-purpose constraint solver, such as Gumin's implementation of the WaveFunctionCollapse (WFC) algorithm, can control output statistics but have limited constraint propagation ability and cannot express non-local constraints. In this paper, we introduce You-Only-Randomize-Once (YORO) pre-rolling, a method for crafting a decision variable ordering for a constraint solver that encodes desired statistics in a constraint-based generator. Using a solver-based WFC as an example, we show that this technique effectively controls the statistics of tile-grid outputs generated by several off-the-shelf SAT solvers, while still enforcing global constraints on the outputs.1 Our approach is immediately applicable to WFC-like generation problems and it offers a conceptual starting point for controlling the design element statistics in other constraint-based generators.