1 of 16

Automatic Generation of Game Content using a Graph-based Wave Function Collapse Algorithm

Presented by Jiří Filek

2 of 16

Wave Function Collapse

Source: https://github.com/mxgmn/WaveFunctionCollapse

3 of 16

Wave Function Collapse

  • Takes an input image and produces an output image which is locally similar
    • Every NxN pattern which is in the output is also in the input
    • The probability to meet a particular pattern in the output should be close to the density of such pattern in the input

​

4 of 16

Algorithm

5 of 16

Simple Tiled Model

  • Simpler, less powerful version
  • Considers 1x2 pattern
  • Stores probabilities of tiles instead of patterns
  • Adjacency constraint propagation

​

6 of 16

Graph-based WFC

7 of 16

Graph vs Grid

  • Graph is a superset of grid
  • Tiles have variable amount of neighbors

8 of 16

Adjacency rules

  • Input as json, image doesn’t work
  • No direction relation, only connection

9 of 16

Propagator (state updates)

  • WFC: P = TDV
    • T… number of tiles
    • D… number of directions
    • V… number of connectable tiles
  • Graph-based WFC: P = TV … no directions
  • Need to know each tiles neighbors for propagation
  • Uses backtracking to resolve conflicts

10 of 16

Application

11 of 16

Sudoku

  • Each tile has 20 neighbors
  • Even closer to normal CSP

12 of 16

Four-color problem

  • Each planar graph can be colored with just four colors
  • Another standard CSP

13 of 16

Navmesh

  • Can be used to add content - empty, resource, NPC…

14 of 16

Properties

  • Controllability
    • Customs weight for connection
    • Tile preplacing - predetermination
  • Computation time increases greatly with more and complex connections

15 of 16

My take

  • Nicely explained
  • Lots of images
  • Not really that complicated topic

16 of 16

Questions?