More Web Proxy on the site http://driver.im/

research-article

Open access

Enhancing wave function collapse with design-level constraints

Authors:

Arunpreet Sandhu,

Joshua McCoyAuthors Info & Claims

FDG '19: Proceedings of the 14th International Conference on the Foundations of Digital Games

Article No.: 17, Pages 1 - 9

https://doi.org/10.1145/3337722.3337752

Published: 26 August 2019 Publication History

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.

References

[1]

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}.

[2]

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.

[3]

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.

[4]

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.

[5]

No Man's Sky. Hello Games, 2016.

[6]

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.

[7]

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.

[8]

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.

[9]

ExUtumno, Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics.: mxgmn/WaveFunctionCollapse. 2019.

[10]

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.

Digital Library

[11]

Bad North. Plausible Concept, 2018.

[12]

Caves of Qud. Freehold Games, 2019.

[13]

"mxgmn / Basic3DWFC." {Online}. Available: https://bitbucket.org/mxgmn/basic3dwfc. {Accessed: 12-Jan-2019}.

[14]

M. O'Leary, Oisín: Wave Function Collapse for poetry. Contribute to mewo2/oisin development by creating an account on GitHub. 2019.

[15]

I. Karth and A. M. Smith, "Addressing the Fundamental Tension of PCGML with Discriminative Learning," ArXiv180904432 Cs Stat, Sep. 2018.

[16]

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.

[17]

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.

[18]

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.

Digital Library

Cited By

Facey KCooper SCardona-Rivera RCooper S(2024)Toward space-time WaveFunctionCollapse for level and solution generationProceedings of the Twentieth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment10.1609/aiide.v20i1.31863(25-34)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1609/aiide.v20i1.31863
Cooper SBazzaz M(2024)Literally Unplayable: On Constraint-Based Generation of Uncompletable LevelsProceedings of the 19th International Conference on the Foundations of Digital Games10.1145/3649921.3659844(1-8)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3649921.3659844
Heese R(2024)Quantum Wave Function Collapse for Procedural Content GenerationIEEE Computer Graphics and Applications10.1109/MCG.2024.344777544:5(54-66)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/MCG.2024.3447775
Show More Cited By

Index Terms

Enhancing wave function collapse with design-level constraints

Recommendations

Hierarchical Semantic Wave Function Collapse
FDG '23: Proceedings of the 18th International Conference on the Foundations of Digital Games

There are few proposals to improve the interactivity and control of wave function collapse (WFC) in a mixed-initiative setting. Moreover, most WFC algorithm variants operate on an simple, unstructured set of tiles. This limitation on the level of ...
GAN applied to Wave Function Collapse for procedural map generation
SIGGRAPH '22: ACM SIGGRAPH 2022 Posters

This 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 2020
Abstract
Procedural 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

FDG '19: Proceedings of the 14th International Conference on the Foundations of Digital Games

August 2019

822 pages

ISBN:9781450372176

DOI:10.1145/3337722

Conference Chair:
Sebastian Deterding
University of York
,
General Chair:
Foaad Khosmood
California Polytechnic State University
,
Program Chairs:
Johanna Pirker
Graz University of Technology
,
Thomas Apperley
CEGCS Tampere University

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 August 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FDG '19

FDG '19: The Fourteenth International Conference on the Foundations of Digital Games

August 26 - 30, 2019

California, San Luis Obispo, USA

Acceptance Rates

FDG '19 Paper Acceptance Rate 46 of 124 submissions, 37%;

Overall Acceptance Rate 152 of 415 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
2,619
Total Downloads

Downloads (Last 12 months)660
Downloads (Last 6 weeks)75

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Facey KCooper SCardona-Rivera RCooper S(2024)Toward space-time WaveFunctionCollapse for level and solution generationProceedings of the Twentieth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment10.1609/aiide.v20i1.31863(25-34)Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1609/aiide.v20i1.31863
Cooper SBazzaz M(2024)Literally Unplayable: On Constraint-Based Generation of Uncompletable LevelsProceedings of the 19th International Conference on the Foundations of Digital Games10.1145/3649921.3659844(1-8)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3649921.3659844
Heese R(2024)Quantum Wave Function Collapse for Procedural Content GenerationIEEE Computer Graphics and Applications10.1109/MCG.2024.344777544:5(54-66)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/MCG.2024.3447775
Christie RKitchen BTumilowicz WHooper SWünsche B(2024)Procedurally Generating Large Synthetic Worlds: Chunked Hierarchical Wave Function Collapse2024 39th International Conference on Image and Vision Computing New Zealand (IVCNZ)10.1109/IVCNZ64857.2024.10794452(1-6)Online publication date: 4-Dec-2024
https://doi.org/10.1109/IVCNZ64857.2024.10794452
Wang BChang C(2024)Wave Function Collapse Algorithm in Roguelite Game Level Design: An Analysis of Strategies and Challenges2024 10th International Conference on Applied System Innovation (ICASI)10.1109/ICASI60819.2024.10547926(359-361)Online publication date: 17-Apr-2024
https://doi.org/10.1109/ICASI60819.2024.10547926
Hind DHarvey C(2024)Using a NEAT approach with curriculums for dynamic content generation in video gamesPersonal and Ubiquitous Computing10.1007/s00779-024-01801-z28:3-4(629-641)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00779-024-01801-z
Lan DChen KXu Z(2023)Underground Parking Layout Generation Based on the WaveFunctionCollapse AlgorithmBuildings10.3390/buildings1311289813:11(2898)Online publication date: 20-Nov-2023
https://doi.org/10.3390/buildings13112898
Beukman MIngram BLiu IRosman BEger MCardona-Rivera R(2023)Hierarchical WaveFunction collapseProceedings of the Nineteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment10.1609/aiide.v19i1.27498(23-33)Online publication date: 8-Oct-2023
https://dl.acm.org/doi/10.1609/aiide.v19i1.27498
Michel ÉBoubekeur T(2023)MesoGen: Designing Procedural On-Surface Stranded MesostructuresACM SIGGRAPH 2023 Conference Proceedings10.1145/3588432.3591496(1-10)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.1145/3588432.3591496
Bailly RLevieux G(2023)Genetic-WFC: Extending Wave Function Collapse With Genetic SearchIEEE Transactions on Games10.1109/TG.2022.319293015:1(36-45)Online publication date: Mar-2023
https://doi.org/10.1109/TG.2022.3192930
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents