research-article

Open access

Better Resemblance without Bigger Patterns: Making Context-sensitive Decisions in WFC

Authors:

Adam SmithAuthors Info & Claims

FDG '23: Proceedings of the 18th International Conference on the Foundations of Digital Games

Article No.: 20, Pages 1 - 11

https://doi.org/10.1145/3582437.3582441

Published: 12 April 2023 Publication History

All formats PDF

Abstract

Gumin’s WaveFunctionCollapse (WFC) algorithm attempts to generate output designs that resemble provided input designs. While the algorithm’s constraint-solving core is able to ensure that no local patterns are adjacent in the outputs that were not adjacent in the input, it does not accurately reproduce statistical properties of the input designs. Examining the algorithm’s behavior at the level of pattern adjacencies, we show that there are large gaps between the statistics of the input and output designs, even when applying Gumin’s search heuristic intended to influence output statistics. By offering a very small revision to this search heuristic, we show that the resemblance of outputs to inputs can be dramatically improved. Another way of improving resemblance is to increase the size of local patterns considered by WFC, but this can easily lead to a kind of overfitting that results in the outputs plagiarizing large portions of the input design. By contrast, our alternate revision increases resemblance without increasing pattern size. The simplicity of our method, requiring a very localized change to existing WFC implementations, allows it to be immediately applied to a wide range of applications.

References

[1]

[1] Supratik Chakraborty, Daniel Fremont, Kuldeep Meel, Sanjit Seshia, and Moshe Vardi. 2014. Distribution-aware sampling and weighted model counting for SAT. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 28.

[2]

[2] Huiwen Chang, Han Zhang, Lu Jiang, Ce Liu, and William T. Freeman. 2022. MaskGIT: Masked Generative Image Transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, New Orleans, LA, USA, 11315–11325. https://doi.org/10.1109/CVPR52688.2022.01103

[3]

[3] Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever. 2020. Generative pretraining from pixels. In International conference on machine learning. PMLR, 1691–1703.

[4]

[4] Seth Cooper. 2022. Sturgeon: Tile-Based Procedural Level Generation via Learned and Designed Constraints. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 18, 1 (Oct. 2022), 26–36. https://doi.org/10.1609/aiide.v18i1.21944

Digital Library

[5]

[5] Patrick Esser, Robin Rombach, and Bjorn Ommer. 2021. Taming Transformers for High-Resolution Image Synthesis. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, Nashville, TN, USA, 12873–12883. https://doi.org/10.1109/CVPR46437.2021.01268

[6]

[6] Maxim Gumin. 2016. Wave Function Collapse Algorithm. https://github.com/mxgmn/WaveFunctionCollapse

[7]

[7] Isaac Karth and Adam M Smith. 2019. Addressing the fundamental tension of PCGML with discriminative learning. In Proceedings of the 14th International Conference on the Foundations of Digital Games. 1–9.

Digital Library

[8]

[8] Isaac Karth and Adam M. Smith. 2022. WaveFunctionCollapse: Content Generation via Constraint Solving and Machine Learning. IEEE Transactions on Games 14, 3 (2022), 364–376. https://doi.org/10.1109/TG.2021.3076368

[9]

[9] Solomon Kullback and Richard A Leibler. 1951. On information and sufficiency. The annals of mathematical statistics 22, 1 (1951), 79–86.

[10]

[10] Thijmen Stefanus Leendert Langendam and Rafael Bidarra. 2022. MiWFC - Designer Empowerment through Mixed-Initiative Wave Function Collapse. In Proceedings of the 17th International Conference on the Foundations of Digital Games (Athens, Greece) (FDG ’22). Association for Computing Machinery, New York, NY, USA, Article 66, 8 pages. https://doi.org/10.1145/3555858.3563266

Digital Library

[11]

[11] Paul Merrell. 2007. Example-Based Model Synthesis. In Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games (Seattle, Washington) (I3D ’07). Association for Computing Machinery, New York, NY, USA, 105–112. https://doi.org/10.1145/1230100.1230119

Digital Library

[12]

[12] Roger Mohr and Thomas C Henderson. 1986. Arc and path consistency revisited. Artificial intelligence 28, 2 (1986), 225–233.

[13]

[13] Nintendo. 1986. Legend of Zelda. [Family Computer Disk System].

[14]

[14] Alexandre Papadopoulos, Pierre Roy, and François Pachet. 2014. Avoiding plagiarism in Markov sequence generation. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 28.

[15]

[15] Adam M Smith and Michael Mateas. 2011. Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games 3, 3 (2011), 187–200.

[16]

[16] Sam Snodgrass and Santiago Ontanón. 2016. Controllable Procedural Content Generation via Constrained Multi-Dimensional Markov Chain Sampling. In IJCAI. 780–786.

[17]

[17] Adam Summerville, Sam Snodgrass, Matthew Guzdial, Christoffer Holmgård, Amy K. Hoover, Aaron Isaksen, Andy Nealen, and Julian Togelius. 2018. Procedural Content Generation via Machine Learning (PCGML). IEEE Transactions on Games 10, 3 (Sep. 2018), 257–270. https://doi.org/10.1109/TG.2018.2846639

[18]

[18] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017. Attention is All you Need. In Advances in Neural Information Processing Systems, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Vol. 30. Curran Associates, Inc., Long Beach, CA, USA. https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf

[19]

[19] Li-Yi Wei and Marc Levoy. 2000. Fast texture synthesis using tree-structured vector quantization. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques. 479–488.

Digital Library

Cited By

Katz JBateni BSmith A(2024)You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCGProceedings of the 19th International Conference on the Foundations of Digital Games10.1145/3649921.3649995(1-11)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3649921.3649995
Bateni BWhitehead J(2023)Structure and Coherence in City Road Network Generation2023 IEEE Conference on Games (CoG)10.1109/CoG57401.2023.10333182(1-8)Online publication date: 21-Aug-2023
https://doi.org/10.1109/CoG57401.2023.10333182

Index Terms

Better Resemblance without Bigger Patterns: Making Context-sensitive Decisions in WFC
1. Applied computing
  1. Computers in other domains
    1. Personal computers and PC applications
      1. Computer games
2. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Machine learning
    1. Machine learning approaches
      1. Logical and relational learning
        Statistical relational learning

Recommendations

miWFC - Designer Empowerment through mixed-initiative Wave Function Collapse
FDG '22: Proceedings of the 17th International Conference on the Foundations of Digital Games

Wave 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, ...
You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCG
FDG '24: Proceedings of the 19th International Conference on the Foundations of Digital Games

In procedural content generation, modeling the generation task as a constraint satisfaction problem lets us define local and global constraints on the generated output. However, a generator’s perceived quality often involves statistics rather than just ...
Better bug reporting with better privacy
ASPLOS XIII: Proceedings of the 13th international conference on Architectural support for programming languages and operating systems

Software vendors collect bug reports from customers to improve the quality of their software. These reports should include the inputs that make the software fail, to enable vendors to reproduce the bug. However, vendors rarely include these inputs in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

FDG '23: Proceedings of the 18th International Conference on the Foundations of Digital Games

April 2023

621 pages

ISBN:9781450398558

DOI:10.1145/3582437

Editors:
Phil Lopes
Lusófona University
,
Filipe Luz
Lusófona University
,
Antonios Liapis
University of Malta
,
Henrik Engström
University of Skövde

Copyright © 2023 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: 12 April 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

FDG 2023

FDG 2023: Foundations of Digital Games 2023

April 12 - 14, 2023

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 152 of 415 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
318
Total Downloads

Downloads (Last 12 months)235
Downloads (Last 6 weeks)50

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Katz JBateni BSmith A(2024)You-Only-Randomize-Once: Shaping Statistical Properties in Constraint-based PCGProceedings of the 19th International Conference on the Foundations of Digital Games10.1145/3649921.3649995(1-11)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3649921.3649995
Bateni BWhitehead J(2023)Structure and Coherence in City Road Network Generation2023 IEEE Conference on Games (CoG)10.1109/CoG57401.2023.10333182(1-8)Online publication date: 21-Aug-2023
https://doi.org/10.1109/CoG57401.2023.10333182

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

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