Overview

A constraint-based generator is a generation technique that represents valid outputs as solutions to a set of constraints. In the procedural-content-generation setting, modeling generation as a constraint satisfaction problem supports both local and global constraints on generated outputs. Recent work on YORO pre-rolling describes this as a way to retain solver-based enforcement of global constraints while also shaping output statistics in WFC-like generators.

Constraint-based sampling pattern

In the CSP solution-generation formulation, let 𝒮 be the set of all solutions satisfying constraints 𝒞. A sampling procedure can operate over elements whose volumes are known, selecting an element e with probability proportional to its volume v(e) and then spawning a point uniformly inside that element.

The cited construction assumes:

• spawn(e) samples uniformly within element e, so for any point i ∈ e, the density is P(i | e) = 1 / v(e).
• An element e is selected with probability P(e) = v(e) / Σ v(e′) over the considered elements.
• The joint probability of selecting e and spawning i is therefore constant across points in the sampled region: P(e) · P(i | e) = 1 / Σ v(e′).

Rejection and validity

A spawned point may not satisfy the constraints. The procedure distinguishes elements whose points are guaranteed valid from elements that require checking:

• If e ∈ ℐ, all points in e satisfy 𝒞, so the spawned point is accepted.
• If e ∈ 𝒪, the spawned point is accepted only when it belongs to 𝒮; otherwise the sampling process is repeated.

This is a rejection-sampling step: invalid samples are discarded, and sampling continues until a valid solution is returned.

Uniformity property

For any particular solution i ∈ 𝒮, the probability of returning i is the probability that it is sampled on the first attempt plus the probability that an earlier attempt fails and i is sampled later. The cited proof derives:

P(i) = 1 / ((1 − P(fail)) · Σ v(e′))

where P(fail) is the probability that a uniform element from the sampled region does not satisfy 𝒞. Because this value is constant for every i ∈ 𝒮, the procedure proves uniformity over the solution set.

Role in generation systems

The technique is relevant when outputs must satisfy explicit constraints while the generator should also sample solutions without bias. In solver-based procedural generation, constraint-based generators can enforce global constraints that are difficult for non-solver methods to express, while sampling and ordering techniques can be used to influence statistical properties of the generated outputs.