Graph Based Wave Function Collapse Algorithm for Procedural Content Generation in Games

Hwanhee KIM  Teasung HAHN  Sookyun KIM  Shinjin KANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.8   pp.1901-1910
Publication Date: 2020/08/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019EDP7295
Type of Manuscript: PAPER
Category: Computer Graphics
Keyword: 
wave function collapse (WFC),  procedural content generation (PCG),  Voronoi diagram,  navigation mesh,  game content,  

Full Text: PDF(3.7MB)>>
Buy this Article




Summary: 
This paper describes graph-based Wave Function Collapse algorithm for procedural content generation. The goal of this system is to enable a game designer to procedurally create key content elements in the game level through simple association rule input. To do this, we propose a graph-based data structure that can be easily integrated with a navigation mesh data structure in a three-dimensional world. With our system, if the user inputs the minimum association rule, it is possible to effectively perform procedural content generation in the three-dimensional world. The experimental results show that the Wave Function Collapse algorithm, which is a texture synthesis algorithm, can be extended to non-grid shape content with high controllability and scalability.