July 17, 2017

WaveFunctionCollapse is Constraint Solving in the Wild

Illustrations of WaveFunctionCollapse in action from the paper

ABSTRACT

Maxim Gumin’s WaveFunctionCollapse (WFC) algorithm is an example-driven image generation algorithm emerging from the craft practice of procedural content generation. In WFC, new images are generated in the style of given examples by ensuring every local window of the output occurs somewhere in the input. Operationally, WFC implements a non-backtracking, greedy search method. This paper examines WFC as an instance of constraint solving methods. We trace WFC’s explosive influence on the technical artist community, explain its operation in terms of ideas from the constraint solving literature, and probe its strengths by means of a surrogate implementation using answer set programming.

Full Text

Tags: procgen WFC papers research