Nested Wave Function Collapse Enables Large-Scale Content Generation
Yuhe Nie, Shaoming Zheng, Zhan Zhuang, Julian Togelius · IEEE Transactions on Games · 2024
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.