One of the major challenges in procedural generation of game rules is evaluating the generated content. Since the effect of a rule on game balance and complexity might not be immediately apparent, one way to evaluate such a content is to simulate the gameplay. To achieve this, it is necessary to create an agent capable of both playing the game and adjusting to alterations in the game’s design, which is often referred to as a general game-playing agent.

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.

We analyze two popular tile-based Procedural Content Generation (PCG) methods, WaveFunctionCollapse and transformers, to explore different notions of conditional probability and their significant effect on the quality of results. Specifically, we seek to answer the question of which method produces higher-quality results for generating city road networks as 2D images. Road networks are an interesting domain since they have large scale structures which require consistency across many tiles. To experiment with this, first we use OpenStreetMap to create a dataset of 2D tiled images with additional information on the type of each road encoded in the tile tokens. We use this dataset to train two WFC models with different decision heuristics, and an additional transformer model with a sliding window inference process. We then compare the results of these models using a set of tile-based metrics (e.g. tile-frequency resemblance and edge-frequency resemblance) and urban-planning metrics (e.g. node density, road connectivity, etc.). Our results show that the transformer model outperforms the WFC methods in terms of generating high-quality city road networks, and demonstrate the potential of transformers for tile-based PCG methods, especially when a considerable amount of data is available.

Gumin’s WaveFunctionCollapse (WFC) algorithm attempts to generate output designs that resemble provided input designs. While the algorithm’s constraint-solving core is able to ensure that no local patterns are adjacent in the outputs that were not adjacent in the input, it does not accurately reproduce statistical properties of the input designs. Examining the algorithm’s behavior at the level of pattern adjacencies, we show that there are large gaps between the statistics of the input and output designs, even when applying Gumin’s search heuristic intended to influence output statistics. By offering a very small revision to this search heuristic, we show that the resemblance of outputs to inputs can be dramatically improved. Another way of improving resemblance is to increase the size of local patterns considered by WFC, but this can easily lead to a kind of overfitting that results in the outputs plagiarizing large portions of the input design. By contrast, our alternate revision increases resemblance without increasing pattern size. The simplicity of our method, requiring a very localized change to existing WFC implementations, allows it to be immediately applied to a wide range of applications.