Nested Wave Function Collapse Enables Large-Scale Content Generation

Yuhe Nie, Shaoming Zheng, Zhan Zhuang, Julian Togelius

    Research output: Contribution to journalArticlepeer-review


    The Wave Function Collapse (WFC) algorithm is a widely used tile-based algorithm in procedural content generation, including textures, objects, and scenes. However, the current WFC algorithm and related optimized algorithms based on it lack the ability to generate commercial-scale or infinite content due to constraint conflicts and high time complexity. This paper proposes the Nested WFC (N-WFC) algorithm framework to reduce time complexity. To avoid conflict and backtracking problems, we offer a complete and sub-complete tileset preparation strategy, which requires only a small number of tiles to generate infinite, aperiodic, and deterministic content. We use Mario and Carcassonne as two game examples to describe their application and discuss potential research value. Our contribution addresses WFC's challenge in massive content generation and provides a theoretical basis for implementing concrete games.

    Original languageEnglish (US)
    Pages (from-to)1-11
    Number of pages11
    JournalIEEE Transactions on Games
    StateAccepted/In press - 2024


    • Algorithm Optimization
    • Backtracking
    • Constraint Satisfaction Problem
    • Games
    • Indexes
    • Procedural Content Generation
    • Task analysis
    • Tessellation
    • Three-dimensional displays
    • Time complexity
    • Wave Function Collapse
    • Wave functions

    ASJC Scopus subject areas

    • Software
    • Control and Systems Engineering
    • Artificial Intelligence
    • Electrical and Electronic Engineering


    Dive into the research topics of 'Nested Wave Function Collapse Enables Large-Scale Content Generation'. Together they form a unique fingerprint.

    Cite this