Procedural Image Generation Using Markov Chain Wave Function Collapse

Advances in Artifical Intelligence & Applied Cognitive Computing. Transactions on Computational Science and Computational Intelligence

Wave Function Collapse (WFC) is an iterative constraint solving algorithm that performs texture synthesis on input samples to generate procedural outputs. The two commonly used WFC implementations are the Overlapping WFC(OWFC) and Tiling WFC(TWFC) implementations. OWFC incurs a performance cost in identifying constraints whereas TWFC receives pre-determined constraints in the form of metadata. Pre-determining the metadata, however, is a non-trivial process and requires substantial design time before the execution of the algorithm. The proposed Markov-chain WFC(MkWFC) implementation aims to reduce the time involved during the metadata design stage while maintaining the performance benefits of the TWFC implementation. This is achieved by using Markov-chains to determine constraints from a set of input samples and introduces a pre-processing step to the TWFC implementation. By automating constraint identification, the MkWFC implementation reduces both the metadata generation time as well as the scope for human error. This paper compares TWFC against MkWFC on a set of 6 different procedural image generation problems using 3 sizes for inputs and outputs in a total of 720 trials. When comparing the MkWFC implementation against TWFC, there is an increase in the number of identified and used constraints from input and output respectively, which increases with image size. The performance of TWFC and MkWFC was compared by measuring their respective execution times for all trials. MkWFC was able to identify over 1.5 times more constraints for a 5x5 tiled image in 1.03 ± 0.09 ms α = 0.05 and almost 3 times more constraints in 25x25 tiled image in 28.19 ± 2.58ms α = 0.05. This is substantially faster than the TWFC methodology where these constraints have to be manually identified and entered into the meta-data file. Image generation for TWFC for a 25x25 tiled image was 25.15 ± 4.60ms α = 0.05, while MkWFC achieved a time of 60.71 ±8.82ms α = 0.05. The increase in time is due to the larger amount of constraints identified, which provides more diversity in output images. While MkWFC executes output generation slower than TWFC in larger images it still performs in millisecond range and is capable of real-time execution. The automated meta-data generation and nominal increase in execution time allows for MkWFC to scale where TWFC can not.