Arunpreet Sandhu
ABSTRACT
Wave Function Collapse (WFC) is a non-backtracking, greedy search algorithm that is commonly known for its ability to take an example image and generate similar images. Since its inception, technical artists have explored the algorithm's extensibility and usability through various implementations spanning from 3D world generation to poetry creation. However, there has been no integration of design constraints into the generative process. In this paper, we explore WFC as a constraint satisfaction solver to integrate design principles and practices by modifying components within the algorithm. First, we extend the local constraint reasoning by incorporating non-local constraints as well as upper and lower bounds. Next, we further manipulate the generative space by introducing weight recalculation and dependencies. Lastly, we evaluate our design-focused variant of WFC against the original implementation to examine the associated costs in computational time and memory usage. In summary, this paper describes a technical implementation of integrating design constraints into WFC and analyzes the computational trade-offs.
- R. Moss, "7 uses of procedural generation that all developers should study." {Online}. Available: /view/news/262869/7_uses_of_procedural_generation_that_all_developers_should_study.php. {Accessed: 12-Jan-2019}.Google Scholar
- N. Shaker, A. Liapis, J. Togelius, R. Lopes, and R. Bidarra, "Constructive generation methods for dungeons and levels," in Procedural Content Generation in Games, Cham: Springer International Publishing, 2016, pp. 31--55.Google Scholar
- M. J. Nelson and A. M. Smith, "ASP with Applications to Mazes and Levels," in Procedural Content Generation in Games, Cham: Springer International Publishing, 2016, pp. 143--157.Google Scholar
- Y.-G. Cheong, M. O. Riedl, B.-C. Bae, and M. J. Nelson, "Planning with applications to quests and story," in Procedural Content Generation in Games, Cham: Springer International Publishing, 2016, pp. 123--141.Google Scholar
- No Man's Sky. Hello Games, 2016.Google Scholar
- A. M. Smith and M. Mateas, "Answer Set Programming for Procedural Content Generation: A Design Space Approach," IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, pp. 187--200, Sep. 2011.Google Scholar
- J. Togelius, G. N. Yannakakis, K. O. Stanley, and C. Browne, "Search-Based Procedural Content Generation: A Taxonomy and Survey," IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, pp. 172--186, Sep. 2011.Google ScholarDigital Library
- D. Ashlock, S. Risi, and J. Togelius, "Representations for search-based methods," in Procedural Content Generation in Games, Cham: Springer International Publishing, 2016, pp. 159--179.Google Scholar
- ExUtumno, Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics.: mxgmn/WaveFunctionCollapse. 2019.Google Scholar
- I. Karth and A. M. Smith, "WaveFunctionCollapse is constraint solving in the wild," in Proceedings of the International Conference on the Foundations of Digital Games - FDG '17, Hyannis, Massachusetts, 2017, pp. 1--10. Google ScholarDigital Library
- Bad North. Plausible Concept, 2018.Google Scholar
- Caves of Qud. Freehold Games, 2019.Google Scholar
- "mxgmn / Basic3DWFC." {Online}. Available: https://bitbucket.org/mxgmn/basic3dwfc. {Accessed: 12-Jan-2019}.Google Scholar
- M. O'Leary, Oisín: Wave Function Collapse for poetry. Contribute to mewo2/oisin development by creating an account on GitHub. 2019.Google Scholar
- I. Karth and A. M. Smith, "Addressing the Fundamental Tension of PCGML with Discriminative Learning," ArXiv180904432 Cs Stat, Sep. 2018.Google Scholar
- G. Smith, J. Whitehead, and M. Mateas, "Tanagra: Reactive Planning and Constraint Solving for Mixed-Initiative Level Design," IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, pp. 201--215, Sep. 2011.Google Scholar
- A. Liapis, G. Smith, and N. Shaker, "Mixed-initiative content creation," in Procedural Content Generation in Games, Cham: Springer International Publishing, 2016, pp. 195--214.Google Scholar
- E. Butler, A. M. Smith, Y.-E. Liu, and Z. Popovic, "A mixed-initiative tool for designing level progressions in games," in Proceedings of the 26th annual ACM symposium on User interface software and technology - UIST '13, St. Andrews, Scotland, United Kingdom, 2013, pp. 377--386. Google ScholarDigital Library
Index Terms
- Enhancing wave function collapse with design-level constraints
Recommendations
GAN applied to Wave Function Collapse for procedural map generation
SIGGRAPH '22: ACM SIGGRAPH 2022 PostersThis paper describes the use of Generative Adversarial Network (GAN) applied to the Wave Function Collapse (WFC) algorithm for procedural content generation. The goal of this system is to enable level designers to generate coherent 3D worlds with brand ...
Automatic Generation of Game Levels Based on Controllable Wave Function Collapse Algorithm
Entertainment Computing – ICEC 2020AbstractProcedural content generation automatically creates game content through methods such as pseudo-random numbers, which helps save labor or create games that can be played repeatedly and indefinitely. The wave function collapse algorithm is an ...
miWFC - Designer Empowerment through mixed-initiative Wave Function Collapse
FDG '22: Proceedings of the 17th International Conference on the Foundations of Digital GamesWave Function Collapse (WFC) is a powerful generative algorithm, able to create locally-similar output based on a single example input. One of the inherent limitations of the original WFC is that it often requires users to understand its inner workings, ...
Comments