Combining wave function collapse and evolutionary algorithms for controlled content generation

Abstract

Wave Function Collapse (WFC) is a procedural content generation algorithm introduced by Maxim Gumin that has risen in popularity in recent years. The Wave Function Collapse algorithm utilizes two distinct models, the Overlapping and the Simple Tiled model, to divide input bitmap-based or tiled-based images into patterns of various shapes and consistently generate output images of a larger scale, which feature the same patterns. Although WFC is able to create images that are visually stunning in massive numbers, there hasn’t been many attempts to generalize it, in order to make it able to be applied for game content generation. Specifically, the images that are generated can be used as textures for games and sometimes as levels, but the playability of these levels is not guaranteed. In this thesis, WFC is combined with an evolutionary algorithm in an attempt to control the generated outputs of WFC and push them towards a more playable nature. The implemented algorithm evolves patterns, in the form of tiled images, that will then be used as input for the WFC algorithm. The idea is to first create visually flawless images through an evolutionary procedure, using a given tileset, that will result in the generation of similarly flawless images and then elaborate further so that some control over the generated content of the WFC algorithm is established. First, we go through every parameter of our evolutionary algorithm, like the selection method, the fitness function, the genetic operators and the population size, exploring the impact that each of them can have on the produced results and then we propose an optimal setup for our approach. The proposed setup managed to have a very promising performance and within a reasonable amount of computational resources. Furthermore, the algorithm managed to maintain the same performance when tested on totally random tilesets, while the results that were being produced through the WFC algorithm were increasing in complexity for larger tilesets, while maintaining the algorithm’s wide expressive range. Finally, despite the good performance of our implementation, there is definitely some room for improvement. In this approach we explored many of the parameters that can have an impact on the evolution of the input patterns, but there is still much research to be done in determining the best approach. Alternatively, this approach can be utilized by future implementations that want to address similar problems.