Extend Wave Function Collapse to Large-Scale Content Generation
This addresses a bottleneck in procedural content generation for game design, offering a theoretical basis for commercial applications, though it appears incremental as it builds on the existing WFC framework.
The paper tackles the problem of Wave Function Collapse (WFC) being unable to generate large-scale or infinite content due to constraint conflicts and high time complexity, by proposing a Nested WFC (N-WFC) algorithm that reduces time complexity and uses a tileset preparation strategy to enable aperiodic and deterministic infinite content generation.
Wave Function Collapse (WFC) is a widely used tile-based algorithm in procedural content generation, including textures, objects, and scenes. However, the current WFC algorithm and related research lack the ability to generate commercialized large-scale or infinite content due to constraint conflict and time complexity costs. This paper proposes a 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 aperiodic and deterministic infinite content. We also introduce the weight-brush system that combines N-WFC and sub-complete tileset, proving its suitability for game design. Our contribution addresses WFC's challenge in massive content generation and provides a theoretical basis for implementing concrete games.