A Markovian Framing of WaveFunctionCollapse for Procedurally Generating Aesthetically Complex Environments
Franklin Yiu, Mohan Lu, Nina Li, Kevin Joseph, Tianxu Zhang, Julian Togelius, Timothy Merino, Sam Earle · 2025
Read A Markovian Framing of WaveFunctionCollapse for Procedurally Generating Aesthetically Complex Environments by Franklin Yiu, Mohan Lu, Nina Li, Kevin Joseph, Tianxu Zhang, Julian Togelius, Timothy Merino, Sam Earle (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-09919.txt.
Introduction
Franklin Yiu and 7 co-authors recast a popular level-building algorithm as a decision process in a 2025 game generation paper. WaveFunctionCollapse assembles tiled environments by propagating local fitting rules, but designers also chase global goals such as beauty or difficulty. Optimising tiles and goals together tangles the two jobs, and the authors propose splitting them cleanly apart.
Inside their Markov framing, the collapse machinery alone enforces every adjacency rule, while an outside optimiser pursues only the designer's objective. Across several domains of rising difficulty, joint evolutionary search struggled more and more, and the split version beat it consistently. Letting each mechanism do the job it is good at, the study argues, is what unlocks harder generation tasks.
Catalog record
| CREATOR | Franklin Yiu, Mohan Lu, Nina Li, Kevin Joseph, Tianxu Zhang, Julian Togelius, Timothy Merino, Sam Earle |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-09919
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Markovian Framing of WaveFunctionCollapse for Procedurally Generating Aesthetically Complex Environments Franklin Yiu, Mohan Lu, Nina Li, Kevin Joseph, Tianxu Zhang, Julian Togelius, Timothy Merino, Sam Earle Abstract Procedural content generation often requires satisfying both designer-specified objectives and adjacency constraints implicitly imposed by the underlying tile set. To address the challenges of jointly optimizing both constraints and objectives, we reformulate WaveFunctionCollapse (WFC) as a Markov Decision Process (MDP), enabling external optimization algorithms to focus exclusively on objective maximization while leveraging WFC’s propagation mechanism to enforce constraint satisfaction. We empirically compare optimizing this MDP to traditional evolutionary approaches that jointly optimize global metrics and local tile placement. Across multiple domains with various difficulties, we find that joint optimization not only struggles as task complexity increases, but consistently underperforms relative to optimization over the WFC-MDP, underscoring the advantages of decoupling local constraint satisfaction from global objective optimization. [[email protected]] [[email protected]] [[email protected]] [[email protected]] [[email protected]] [[email protected]] [[email protected]] [[email protected]] keywords WaveFunctionCollapse ,Markov Decision Process ,Evolution ,PCG † † venue: [EXAG 2025] AIIDE Workshop on Experimental AI in Games (EXAG 2025) † † copyrightyear: 2025 † † copyright: Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). † † address: New York University, United States 1 Introduction Procedural Content Generation (PCG) automatically creates game content through algorithmic methods often leveraging search or machine learning-based methods (PCGML). Learning-based methods in particular have enabled the automated creation of game content that optimizes designer-specified high-level objectives Todd et al. 2023 ; Nie et al. 2025 ; Khalifa et al. 2020 ; Earle et al. 2024 ; Summerville et al. 2018 that would be difficult to express or satisfy through traditional algorithms such as WaveFunctionCollapse (WFC) Cheng et al. 2020 . However, many existing learning-based PCG approaches are primarily applied to visually simplistic domains where the tile set imposes limited adjacency constraints Todd et al. 2023 ; Nie et al. 2025 ; Khalifa et al. 2020 ; Earle et al. 2024 . We suspect that even methods which already produce satisfactory results in a domain with more aesthetic adjacency constraints like Mario Lee and Simo-Serra 2023 ; Wang et al. 2022 ; Shu et al. 2021 , would achieve higher robustness and efficiency from offloading the learning of the adjacency rules. We hypothesize that optimization-based PCG methods struggle with complex aesthetic adjacency rules due to the combinatorial explosion of valid tile configurations. To test this hypothesis, we compare traditional approaches that must learn these constraints implicitly against our novel formulation that leverages WFC’s constraint propagation mechanism. While WFC is inherently limited in its ability to optimize global functional properties such as playability, it excels at enforcing fine-grained aesthetic coherence by propagating preferences over possible tile placements via constraint solving Kim et al. 2019 ; Karth and Smith 2021 . By reformulating WFC as a Markov Decision Process (MDP) and embedding an explicit objective function within this framework, we enable a more generalizable approach to guiding content generation toward designer-specified goals while simultaneously maintaining adherence to aesthetic adjacency constraints. We optimize this MDP by evolving an action sequence using \mu+\lambda evolution. To understand the implications of the MDP’s explicit adjacency constraint guarantees, we compare against evolving the tiles of the final artifact directly, via both naive \mu+\lambda evolution and Feasible Infeasible 2-Population (FI-2Pop) Kimbrough et al. 2008 , where the optimization algorithm must implicitly learn to resolve adjacency violations. We evaluate these optimization strategies across 3 domains. The binary domain, adapted from Khalifa et al. 2020 , imposes desired path length constraints as a simplified proxy for functional playability. Notably, varying the target path length allows us to dynamically adjust problem difficulty, enabling a systematic evaluation of how each optimization algorithm scales with increasing task complexity. On the other hand, the biome domains define objective functions that capture global topographic features of distinct biomes, guiding optimization toward semantically coherent and visually pleasing patterns. Finally, we integrate both binary and biome objectives, requiring solutions that jointly optimize metrics pertaining to form and function, thereby reflecting the multi-objective demands typical of real-world game design. Accross all domains and desired path lengths, non-MDP methods (which incorporate WFC-style constraints into objective functions instead of leveraging them via an MDP) perform noticeably worse; evolving the MDP action sequence leads to faster and more consistent convergence. However, on the most difficult objectives, evolving the action sequence converges very inconsistently, hinting at exploration limitations of \mu+\lambda evolution. Concretely, we offer the following contributions: • We demonstrate that forcing learning algorithms to learn local adjacency constraints leads to degraded performance in highly constrained domains. • We present a novel formulation of WFC as an MDP, along with a corresponding gym Brockman et al. 2016 environment to facilitate the evaluation of alternative optimization algorithms. 2 Related Work 2.1 WaveFunctionCollapse Algorithm and Modifications 2.1.1 WaveFunctionCollapse WFC is an algorithm for procedural content generation, particularly for tile-based environments. It can create coherent and visually consistent outputs based on simple input examples or constraints Gumin 2016 . The algorithm’s core functionality resembles constraint satisfaction with a quantum mechanics-inspired approach: maintaining a superposition of possible states for each tile that gradually “collapses” to definite states through observation and propagation steps Karth and Smith 2017 . The algorithm operates in two main modes: the simple tiled model, which uses explicit adjacency rules, and the overlapping model, which automatically extracts patterns from example inputs period Heaton 2018 In the overlapping model, WFC can be seen as a form of self-supervised learning that learns a distribution from minimal examples—often just one—and generates similar content by maintaining the learned adjacency patterns. While WFC excels at maintaining local adjacency constraints, it struggles with global optimization objectives that are critical for gameplay, such as ensuring level solvability or balanced resource distribution Kim et al. 2019 . 2.1.2 Enhancements to WaveFunctionCollapse Researchers have developed numerous modifications to improve WFC’s capabilities beyond its original formulation. Karth and Smith 2022 provide a comprehensive analysis of WFC as a constraint satisfaction problem, establishing its theoretical foundations and positioning it within the broader context of PCG approaches. To improve scalability to large environments, Nie et al. 2023 proposed Nested Wave Function Collapse (N-WFC), which decomposes the generation process into nested subproblems. This approach significantly reduces time complexity from exponential to polynomial while maintaining consistency across the generated content. For non-grid environments, researchers have developed graph-based extensions of WFC that enable content generation for arbitrary topologies, enabling applications to 3D worlds and non-uniform structures Kim et al. 2019 . LNU 2020 introduce additional extensions to WFC including the path constraint, which enforces global connectivity between specified tiles—addressing one of WFC’s key limitations regarding global structure control. This path constraint is distinct from the path-length objective optimized in the present work in that it focuses on paths between designer-specified tiles as opposed to any two most distant tiles on the map, and only ensures the existence of such a path, rather than making guarantees about its length. This distinction is significant because optimizing path length requires global reasoning about the entire map structure, which traditional WFC cannot perform. While the path constraint ensures connectivity exists, our work specifically optimizes the longest shortest path between any two points, creating