Figure 1: Fuzzy linkography allows for the rapid translation of user activity logs from digital creativity support tools (and other traces of creative activity) into rough graphical summaries, suitable for visual and quantitative inspection by researchers.

Gumin’s WaveFunctionCollapse (WFC) algorithm attempts to generate output designs that resemble provided input designs. While the algorithm’s constraint-solving core is able to ensure that no local patterns are adjacent in the outputs that were not adjacent in the input, it does not accurately reproduce statistical properties of the input designs. Examining the algorithm’s behavior at the level of pattern adjacencies, we show that there are large gaps between the statistics of the input and output designs, even when applying Gumin’s search heuristic intended to influence output statistics. By offering a very small revision to this search heuristic, we show that the resemblance of outputs to inputs can be dramatically improved. Another way of improving resemblance is to increase the size of local patterns considered by WFC, but this can easily lead to a kind of overfitting that results in the outputs plagiarizing large portions of the input design. By contrast, our alternate revision increases resemblance without increasing pattern size. The simplicity of our method, requiring a very localized change to existing WFC implementations, allows it to be immediately applied to a wide range of applications.

Procedural content generation is impossible: insofar as it is popularly understood as the generation of artifacts that can give us the same experience as if a human had crafted them by hand, it involves an intrinsic contradiction. If a thing has been generated once, it can be generated again. Kate Compton has introduced a term for this unending content: liquid art. Compton’s category of the “Bach faucet” describes the way that the endless supply of generativity destroys rarity. Conceptual art provides some examples of navigating this paradox. The PCG community is uniquely positioned to provide direction because of its existing understanding of the properties of generativity as an art form.

In this article, we describe WaveFunctionCollapse (WFC), a new family of algorithms for content generation. WFC was recently invented by independent game developer M. Gumin and has since been adopted and adapted by other game developers. Trends in academic research on content generation have only recently suggested the use of ideas from constraint solving and machine learning, so it is surprising to see these manifested in in-the-wild algorithms developed outside of an academic context. We illuminate the common components in this family of algorithms by way of a rational reconstruction. Through experiments with the reconstruction we probe the impact of design choices made in various adaptations of WFC (e.g., the role of backtracking, search heuristics, or pattern classification and rendering strategies). This article highlights a mode of incremental content generation that has been overlooked by past surveys of content generation methods.

Existing game description languages (GDLs) aspire to generality, but their focus on the specification of low-level mechanics leaves game generators that target these GDLs in the awkward position of having to invent combinations of mechanics that work well together from scratch. As a result, many existing game generators are good at producing games that contain novel and surprising combinations of mechanics, but bad at generating games that are readily interpretable by players as cultural artifacts. To address this problem, we introduce the concept of a genre-specific game description language (GSGDL): a game description language that deliberately encodes assumptions about a particular genre of games as a cultural form. As a proof of concept, we demonstrate the use of an internal representation of game structure used by the game creation tool GB Studio as a GSGDL for top-down 2D roleplaying games targeting the Game Boy. The use of this GSGDL gives us leverage to rapidly iterate on game generation features targeting a specific game genre and platform; to work with an existing toolchain that offers graphical editing, code generation, and automated play testing; and to more readily generate games that are interpretable by players as examples of a particular cultural form.

We introduce a hybrid neural + symbolic approach to map generation that combines neural discrete representation learning with symbolic constraint solving methods. In application to WarCraft II and Super Metroid map designs, we show how a vocabulary of directly manipulable latent tiles can be inferred from the raw pixels of design training data. Despite working with a very small tile vocabulary, our method is able to express a very large effective set of unique tiles at the level of pixel appearances. This work shows new ways of combining generative methods, resulting in directly controllable generators for domains that are primarily specified only by visual design examples.

Procedural content generation via machine learning (PCGML) is typically framed as the task of fitting a generative model to full-scale examples of a desired content distribution. This approach presents a fundamental tension: the more design effort expended to produce detailed training examples for shaping a generator, the lower the return on investment from applying PCGML in the first place. In response, we propose the use of discriminative models, which capture the validity of a design rather the distribution of the content, trained on positive and negative example design fragments. Through a modest modification of WaveFunctionCollapse, a commercially-adopted PCG approach that we characterize as using elementary machine learning, we demonstrate a new mode of control for learning-based generators. We demonstrate how an artist might craft a focused set of additional positive and negative design fragments by critique of the generator's previous outputs. This interaction mode bridges PCGML with mixed-initiative design assistance tools by working with a machine to define a space of valid designs rather than just one new design.

Most discussions of procedural content generation have focused primarily on the artifacts that generators produce or the process by which these artifacts are created. Less focus, however, has been placed on the methods by which generators interpret their input. Many generators take complex input, act as part of a generative pipeline, are part of a mixed-initiative communication with the user, or otherwise need to take context into account during generation. In these cases, the process by which the generator reads and makes sense of its input is often just as interesting as the process by which it produces an output artifact. It is worthwhile to take a closer look at how generators read. Via a case study of two erasure poetry generators, we propose the concept of a generativist reading: a process of reading that produces generative models. Many existing generators have dual input/output or reading/writing processes that are presented as a monolithic unit, but our understanding of both processes and results is enriched when we clearly distinguish between how generators write and how they read.

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.