Modifying Wave Function Collapse for More Complex Use in Game Generation and Design Notes

Introduction

• Procedural Content Generation (PCG):

  • Definition: Creating content through algorithms.
  • Commonly used for video game content but can extend to images, art, and other designs.
  • Examples:
    • Buildings and city layouts (Cullen and O’Sullivan; Lipp et al.).
    • Visual art applied to games (Guzdial et al.).
  • Benefits:
    • Reduces content generation time.
    • Generates background assets like terrain or NPCs.
    • Generates entire levels.
    • Early application: dungeon levels for the game Rogue (1980).
  • PCG Algorithms:
    • Use hand-crafted game content combined with algorithms, parameters, rules, and constraints to generate new content.
    • Uncommon for PCG algorithms to extract rules from finished game content to create more content.

• Wave Function Collapse (WFC):

  • Definition: A PCG algorithm developed by Maxim Gumin to create a novel output image by considering the rules and patterns of an input image.
  • Process:
    • Determines rules and patterns by analyzing small $N \times M$ subsections of the input.
    • Assesses how often each subsection appears and which subsections appear adjacent to each other.
  • Rules:
    • Local Similarity:
      • Strong requirement: Each $N \times M$ subsection in the output should occur at least once in the input.
      • Weak requirement: The frequency of subsections in the output should be similar to their frequency in the input.
    • Adjacency:
      • Strong requirement: If two subsections appear adjacent to each other in the output, they must have appeared adjacent in the input.
  • Popularity:
    • Gained traction with indie game developers and hobbyists.
    • Implemented in multiple environments.
    • Appeared in officially published indie games like Caves of Qud.
  • Application to Level Generation:
    • Inspires the focus of this thesis.
    • Algorithm may be cumbersome or limited to developers who desire more control over the process while maintaining the advantages of PCG.

• Thesis Statement

  • Goal: Apply Wave Function Collapse to generate levels for a framework based on the original Super Mario Bros. and modify it by adding user constraints to generate a usable output.
  • Observation: Observe changes in the density, linearity, and playability of WFC outputs through customized user constraints and altered native WFC parameters.

Background

• Procedural Content Generation

  • Taxonomy and Survey (Togelius et al.)

    • Breaks algorithms into five classifications based on specific properties:

      1. Online or Offline:

         • Specifies whether content generation happens during the game's runtime or development.

      2. Necessary or Optional:

         • Specifies whether content is necessary for game progression or simply background/avoidable.

      3. Random Seeds or Parameter Vectors:

         • A scale specifying the number of designer-specified parameters used to offset a random number generator.

      4. Stochastic or Deterministic:

         • Specifies the amount of randomness in generated content.

      5. Constructive or Generate-and-Test:

         • Specifies whether the algorithm tests content playability during generation or after generation based on specified criteria.

  • Search-Based PCG

    • A subset of generate-and-test algorithms.

    • Post-generation test function evaluates content with a fitness value (as opposed to simple acceptance or rejection).

    • Further generation attempts to increase this value.

  • Procedural Personas (Liapis et al.)

    • Use of procedural personas as a method of evaluating dungeons generated by PCG.

    • Procedural persona: a game-playing agent that acts out a specific style of play.

      • Examples: killing monsters, collecting treasure, reaching the exit, performing the lowest possible number of actions, and avoiding death as much as possible.

    • Performance metric given by these personas to evaluate the quality of levels that are deemed playable as a baseline, and then programmatically evolve these levels based on the metric.

    • The personas actively influenced the design patterns of the levels differently based on their architecture.

    • Exclusive use of one persona type to evolve a level resulted in more difficult levels with significant risk/reward areas.

  • Procedural Content Generation via Machine Learning (PCGML) (Summerville et al.)

    • Combines PCG with deep learning by training machine learning algorithms on large data sets.

    • Applies training to PCG so algorithms may create game content through prior training on existing game content.

    • Focuses on different ways of representing training data and applies five training methods to these representations.

      • Data representation: sequences, grids, and graphs.

      • Training methods: back propagation, evolution, frequency counting, expectation maximization, and matrix factorization.

    • Use cases of PCGML: Autonomous Generation and co-creative design blend designer intent with artificial intelligence.

    • Benefits: content repair, analysis, and data compression.

• Mario Generation

  • Design Patterns (Dahlskog and Togelius)

    • Use PCG in combination with software engineering design patterns to generate Super Mario Bros. levels.

    • Design patterns are a language originally devised for architecture and adapted to computer programming in order to solve recurring problems.

    • Mario levels tend to contain recurring patterns that fit into larger families.

    • Combining these patterns with a PCG algorithm increases the variety and control with which PCG may generate levels.

  • Grammatical Evolution (Shaker et al.)

    • Employs a subset of Genetic Programming called Grammatical Evolution to evolve Mario levels as they are created.

    • Grammatical Evolution entails the combination of an evolutionary algorithm with a context free grammar that represents the possible solutions of the algorithm.

  • Autoencoders (Jain et al.)

    • Uses autoencoders, a type of neural network that encodes input into a number of dimensions, to generate, repair, and classify level styles.

    • Able to use original and existing levels as a representation of patterns understood by the autoencoders.

    • Able to influence what kinds of levels are generated by parametrically changing how much noise goes into the autoencoder.

  • Neural Networks (Summerville et al.)

    • Uses neural networks to analyze Mario gameplay videos from YouTube and ultimately generate levels based on different play styles.

    • Feasible alternative to more traditional methods of experience-driven PCG which required in-person experiments and gameplay collection.

• Expressive Range

  • Definition: classification of a PCG algorithm’s ability to generate style and variety.

  • Metrics:

    • Smith and Whitehead:

      • Linearity:

        • r-squared best fit regression line taken from every platform midpoint in a level.

        • Describes the level’s profile.

      • Leniency:

        • Measures how difficult a level is to complete.

        • Assesses every point in a level where a player would be required to give input and giving these locations a weight based on their difficulty and possibility to lead to death.

        • These points are then averaged and normalized to produce the leniency score.

    • Horn et al. (extends Smith and Whitehead’s metrics and adds three more):

      • Leniency: same as above, normalized by level’s length and number of possible paths.

      • Linearity: same as above, only takes the endpoint of each platform instead of the midpoint. A platform endpoint is defined as any position where the player must move either up or down at least one level when advancing by one position.

      • Density: finds how packed a level is with platforms. For any given x position in the level, it counts the number of possible y positions a player could occupy and averages and normalizes that over the whole level.

      • Pattern Density: counts how many meso-patterns (or generated patterns that match patterns present in the original Mario levels) and averages and normalizes that over the level length.

      • Pattern Variation: the same as pattern density only it counts unique meso-patterns as opposed to all meso-patterns.

• Wave Function Collapse

  • Kim et al.

    • Summarizes WFC and extends its application from grid-based input images to graphs.

  • Karth and Smith

    • Simulates WFC with Answer-Set Programming to examine and critique it.

    • Concludes that WFC is very useful for a wide variety of content.

    • Concludes that the idea of no in-progress backtracking in WFC is nice, but not necessary for further iterations of the algorithm.

  • Sandhu et al.

    • Focuses on adding design-friendly constraints to WFC.

      1. Weighted choice factors the weight of WFC’s tiles into the choices it makes in the output.

      2. Separation of different types of tiles by adding non-local constraints.

      3. Allows a WFC user to reconfigure certain weights within the whole output or within local areas.

      4. Allows a “mini-wfc” to be run on certain areas of the map which eliminates certain tiles when others are placed.

Methods

• The Wave Function Collapse Algorithm

  • Constraint solving to generate an output image based on an example image or set of rules.

  • Constraint Satisfaction Problems: A number of continuous or discrete decision variables can take on any number of values. When the value of a decision variable is determined, it affects the possible values that other variables may take based on specified constraints [8].

  • Examines an input image and extracts local patterns (snapshots) and rules dictating which snapshots may appear adjacent to another.

  • Fills each section of the output space with each possible snapshot and chooses to eliminate snapshots from one section of the output.

  • Iterates through the entire output space, eliminating snapshots from adjacent stacks in accordance with the rules collected.

  • Relates to the concept of Wave Function Collapse in quantum physics where the wave function, which is a mathematical function representing the degrees of freedom to which an observable object may take on a certain state, is directly observed and collapsed into a single state.

  • Patterns from Sample

    • Only run once; involves extracting snapshots from an input image (sample) and determining adjacency rules for each of these snapshots.

    • Some implementations allow direct specification of snapshots and adjacency rules.

    • Important Parameter: Snapshot Dimensions

    • Input Image Analysis:

      • Collect snapshots from the image.

      • Iterate through the input space, starting at the top left, and store a snapshot of the image that is as large as the specified snapshot dimensions.

      • By the end of the parsing, it will generate a snapshot of every possible $x \times y$ section.

      • Collect adjacency rules to pair with every snapshot.

      • Establish which snapshots appear next to others in the input image, where adjacency is defined by positions one space removed from the snapshot, in each direction up, down, left, and right.

    • Captures Snapshot frequency, collapses any duplicate snapshots into one entry, and aggregate all of the corresponding adjacency rules into one entry to be stored together

  • Build Propagator

    • Organizes all of the information collected into a usable format.

    • Most important data collection: the wave (derived from quantum physics).

    • The wave is a multi-dimensional boolean array representing all possibilities in the output space.

    • Each position in the output image is represented in the wave, and each of these positions is initialized with an array of booleans of the same length as the number of snapshots previously collected.

    • Initialize single sections of the wave denoted as ‘stacks of snapshots’.

    • Initializes heuristic collections that aid later steps, specifically a heuristic called entropy.

      • A number that summarizes the probability distribution of snapshots in a stack based on the frequency of each snapshot.

      • Every stack begins with the same entropy, and, when a snapshot is eliminated from a stack, the stack’s entropy is updated based on that snapshot’s frequency.

  • Observe

    • Analyze the wave and select a stack to begin eliminating snapshots from to arrive at a constraint-satisfying solution.

    • Select the stack with the smallest non-zero entropy.

    • Select a snapshot out of this stack randomly and prepare to eliminate all others.

      • Weighted based on each individual remaining snapshot’s frequency.

      • Concept of taking a possibility space and reducing it to one reality.

    • Ensure snapshot adjacency using Ban function, which remove the snapshot from the relevant stack and primes adjacent snapshots for removal from the wave in a later step

    • Enforce the constraint solving principle of selection of the most constrained variable [8].

    • Update entropy and frequency-related variables for the stack for reference by the greater WFC function.

    • Handles failure by checking if any of the snapshot stacks have been completely emptied of snapshots.

      • If this is the case, choices were made elsewhere in the wave that led to a situation in which no tile could possibly exist in the given empty stack according to the adjacency rules.

      • This signifies a failure for the algorithm, and it terminates.

  • Propagate

    • Simulates the collapsing behavior of the wave.

    • Check and ban all adjacent snapshots, then recursively call the ban function for these removals.

    • Collapse non-collapsed stacks by the end of propagation, by having the cycle begin again and having the observe function identify the most constrained of the remaining stacks and collapse it.

    • Run either when all stacks in the wave are collapsed or when the observe function finds that the wave has entered an impossible state.

• Proposed WFC Modifications

  • Goal: Improve certain aspects of WFC outputs.

  • Two additions were created and added to the basic algorithm: Forced Tile Placements, and Bounded Tile Appearances.

  • Forced Tile Placements

    • Forces any specified tile in the input to appear at a specific location in the output for fine-tuned control over specific tiles in the output.

    • Requires a list of rules into the WFC function, each of which consist of a tile and a set of x, y coordinates.

      • The tile must exist in the input image, and the coordinates must reside within the space of the output image.

    • Influence tile placement in certain areas of the output by placing only a single tile somewhere directly taking into account WFC’s use of adjacency rules.

    • Run after the WFC initialization steps and before the observation-propagation loop.

    • Find the snapshot stack at the appropriate position in the wave and search through the stack for any that match the specified tile, calling the Ban() function on any snapshots that do not match.

  • Bounded Tile Appearances

    • Confines certain tile placements to certain areas of the output image while keeping them from appearing any- where else in an attempt to more strongly enforce tile locality in WFC-generated outputs.

    • The input is a tile and an x, y tuple; however, in this case, the x and y values each define a boundary in the output space past which the specified tile can not appear.

    • Positive x or y value restricts the specified tile to appearing in positions greater than that value, and a negative x or y restricts it to appearing in spaces less than.

    • Search for all stacks outside of the specified x and y range and banning any snapshots that match the specified tile from each.

• Parameterization for Generated Levels

  • Use three Levels from original Super Mario Bros: levels 1, 2, and 3.

  • Use each of these three levels as the input image for the WFC algorithm to generate 1000 output levels per trial.

  • Eight trials were performed on each level, the first being a standard run of WFC with no modifications and a standard 2x2 snapshot size. The remaining seven involved the use of one altered parameter from the modifications listed below.

  • Keep the output at a consistent size across all three levels of x = 202 and y = 16 which, out of pure choice, matches the size of level 1.

  • Forced Tile Placements

    • Three trials of WFC were run for each level using three configurations of the forced tile placement modification
    • Forced One ground ‘X’ tile in lower left corner (x=3, y=15)
    • Forced ground ‘X’ tile in lower left corner (x=3, y=15) and lower right corner (x=198, y=15)
    • Forced ground ‘X’ tile in lower left corner (x=3, y=15), lower right corner (x=198, y=15), and lower middle (x=101, y=15)

  • Bounded Tile Appearances

    • Restricted ground ‘X’ tile below y = 10
    • Restricted ground ‘X’ tile below y = 13, ‘%’ tile for Level 3 levels.

  • Snapshot Size Variations

    • Create snapshots of size 3x3 capture more information within one snapshot.
    • Create snapshots of size 2x16 to alter the shape of the snapshots into a vertical slice of the level to capture a vertical columns instead of small square snippets.

• Analysis

  • After generating 1000 levels for eight configurations on three levels, run the resulting levels through two of the expressive range heuristics previously mentioned (density and linearity) along with a game-playing agent (completeness) to assess playability.

  • Density

    • Created an analysis function as per Horn et al. [6], where the method with which to normalize the count of different possible y positions in the level with total area of the level. For all outputs, this would remain constant as all outputs were specified with a size of $202 \times 16$.

  • Linearity

    • Created an analysis function based on previously specified methods where ground tiles typically occur adjacent to each other in the input levels, so forcing one into an area typically encouraged the algorithm to place more next to it.
    • Aimed to be adequately frugal in forcing tiles so as not to take too much of the work away from WFC in its generation and, in the process, undermine the goal of generating levels with PCG.

  • Playability

    • Accessed a Java-based framework for generating and playing Super Mario Bros. levels [17] that ran an A* game-playing agent on all of the levels generated by the WFC algorithm. Each run was given a 20-second timer and returned upon completion whether the agent completed the level, died, or ran out of time.

    • Includes completion percentage, signifying the amount of the level the agent made it through regardless of the result, (with 100% signifying a completed level), in the final data aggregations with the goal of collecting stats from this agent to asses how completable levels generated by a given WFC configuration and to assess, to some extent, how difficult (or otherwise how feasible) it was to complete these levels on average.

Results

• Produced tables for each level (tables 4.1, 4.2, ??). Each row is a different heuristic, and each column is a different configuration of the modifications on WFC.

• First two statistics: average density and average linearity.

• A* agent’s total successes, failures, and time-outs when run on the 1000 levels produced.

• The success percentage.

• Average Completion Percentage is the average of the level’s completion percentage and Failure Completion Percentage is the average of the agent’s reported completion percentage only for levels that were failed or timed-out.

• Level 2, on average, tends to produce the most dense of the levels while level 3 tends to produce the least dense across most configurations. This matches the density of the original input levels when run through the density function.

• In terms of Linearity, however, The levels are much tighter in terms of average linearity.

  • For the Bounded and Forced configurations, level 2 is consistently the least linear with either level 1 or 3 being the most.

  • For playability, the number of victories almost always decreases from level 1 to level 3, with the exception of the Bounded2 configuration where level 3 sees more victories than either of the other two levels. Of note is the Column Snapshot configuration, which tends to be an exception to many of the previously stated rules and leads to heavy increases in playability statistics. For levels 1 and 2, this configuration also has a profound effect on linearity, leading to a substantial increase compared to all other trials.

  • In addition to the aggregate charts for each level are candlestick graphs to present a better understanding of the distribution of relevant values across all 1000 outputs of each WFC configuration. For each of the three levels, there is a graph showing the distributions of density, linearity, and failure completion percentage. These help to further visualize some of the trends previously discussed and to easier compare trends across configurations of the same level.

Discussion

• Standard Wave Function Collapse Generation

  • WFC, when unmodified, generates serviceable, yet rather unrealistic levels.
  • The resulting outputs show a variation in many of the heuristics used to evaluate them.
    • Level 2 produces the most dense levels on average while level 3 produces the least dense.
    • Average linearity remains approximately constant across the output of the three levels.
    • Playability decreases as the levels progress, with a significant drop for levels produced by level 3.
  • The results and observations of these standard WFC trials will serve as a baseline to compare against in following discussion of the outputs of modified WFC.

• Bounded Tile Appearances

  • Produces levels with more airspace near the top and more structures near the bottom depending on the level used as an input.

  • Level-2-produced levels also drop in average density, but the tightening of the total range of densities was not as substantial as level 1.

  • Linearity increase only in levels generated from level 3.

  • Level 1 and 2: bounding appears to have decreased the overall playability of the resulting level.

  • Level-3-produced levels, however, do experience an increase in both victories and average completion percentage.

• Forced Tile Placements

  • Ground tiles help Mario to make it further through the level when forced into the map.
  • Useful when applied to level 1 and 2 but almost useless when applied to level 3.
  • Density increase compared to standard WFC levels, most clearly in levels 1 and 2, with a greater increase as more tiles were forced in from forced1 to forced3.
  • For level 1, linearity saw a very slight increase compared to standard WFC levels, though only by a few tenths of a percent.
    • This differs from the bounded configurations which forced ground tiles lower in the level, but did not grantee that they would appear in a straight line.
  • Playability decreased overall completion percentage

• Altered Snapshots

  • Goal of these configurations: observe the behavior of WFC when it took different amounts or kinds of information out of the input image.

    • Direct affect of results. When applied appropriately the results become impressive. snapshot capture and generation becomes more natural.

  • snapshot Size 3x3:
    *Levels demonstrate more recognizable occurrences and structures.
    *Capture better resolution from level but also leave empty gaps in snapshot to fill in gaps.
    *Density Decreased. Coherent snapshot structure but created gaps

  • column-shaped 2x16 snapshot:
    *. It did not significantly affect the average density of level 1 levels, but the candlestick graph reveals an extreme tightening in the first and third quartile, along with a heavy drop in the absolute maximum density value produced.
    *Density saw mass increase in level 3
    *Playability saw substantial playablity for levels that were mass decreased. level 1 and 3 saw blank space decreasing the amount of success. levels 2 and 3 saw some benefits

Future Work

• Different Heuristics
  • Use of the leniency heuristic and comparing it with the existing playability analysis could be beneficial in learning which modifications have the most implication on difficulty.
• Use of More Competent A* algorithm to better assess level playability.
• Use of Current Modifications
  • Results from level could has much potential to add more work to allow designer to increase playability. Level the designer to ensure playability while still receiving varied results after WFC completion around said level
    *Restricting tiles by bounding powerups to adjust difficulty.
• Further Modifications
  *Force tile frequencies to match what could be missing and allow consistency and flexibility on design.
  *Remove to Screen-Wrapped Adjacency Rules to remove tiles that ruin output and can remove random pattern with WFC