This research was first accepted by IEEE Conference on Games 2023 and was extended to journal paper for IEEE Transactions on Games 2024. We won the Best Paper Award🏆 for IEEE Conference on Games! Congratulations to all the authors and their contributions to this paper! Thanks to NYU Tandon Game Innovation Lab for supporting the publication of this paper!

1. What is Wave Function Collapse (WFC)?

image-20240414125416245

Wave Function Collapse (WFC) algorithm has been introduced by Maxim Gumin for Texture Synthesis. However, it quickly gained a lot of attention in Procedural Content Generation (especially scene/level generation). It can be used not only for 2D scene generation, but also for more complex game scene generation in 3D.

If you’re wondering how exactly this algorithm works, Gumin’s Github repository has a lot of examples explaining it. In addition, you can also check this Demo to see their visualization of WFC.

2. What is this paper about?

This paper optimizes the Time Complexity of the WFC from exponential level $O(C^n)$ to polynomial level $O(n)$. We propose an optimized algorithm: Nested Wave Function Collapse (N-WFC) to address the limitations of WFC’s current ability to produce only small-scale content. We provide the pseudo-code of the algorithm framework and the tileset norms (complete and sub-complete tileset) required to realize the algorithm.

image-20240414115559547

We also further prove that our optimized algorithm has good characteristics of:

  • Infinity: theoretically it can generate infinite content
  • Aperiodicity: under a large-scale generation, the generated content of the algorithm will not be repeated
  • Determinacy: it will not backtrack due to conflicts

For more information on this paper, please read the paper!

3. Awesome Experiments

We experimented the feasibility of our algorithm in two classic games, Super Mario Bros and Carcassonne. The results of the algorithm are amazing. 😮

The advantage for WFC is that it decouples the design and art of the tileset from the generative logic. Neither need be restricted by the other. In other words, tiles of different artistic designs are equivalent for the algorithm!

Super Mario Bros

image-20240414120316058

Carcassonne

image-20240414124435782

4. Cite the Paper

Nie, Y., Zheng, S., Zhuang, Z., & Togelius, J. (2024). Nested Wave Function Collapse Enables Large-Scale Content Generation. IEEE Transactions on Games.

@article{nie2024nested,
  title={Nested Wave Function Collapse Enables Large-Scale Content Generation},
  author={Nie, Yuhe and Zheng, Shaoming and Zhuang, Zhan and Togelius, Julian},
  journal={IEEE Transactions on Games},
  year={2024},
  publisher={IEEE}
}