Procedurally Generating Large Synthetic Worlds: Chunked Hierarchical Wave Function Collapse

TheWave Function Collapse (WFC) procedural content generation (PCG) algorithm can be used to automatically generate synthetic worlds using a small sample, such as a tileset. Recently, the algorithm has been used by video game developers to generate in-game world map layouts. However, its use cases are limited by its runtime performance, and homogeneity when generating large-scale outputs. We have extended the WFC algorithm to be hierarchical and chunked, and found fast backtracking heuristics to allow for the generation of large synthetic worlds. Our novel chunking method improves the performance of WFC for large outputs, and our backtracking heuristics allow for efficient backtracking on complex tilesets. Together these extensions to WFC can generate large or even infinite synthetic worlds.