Help us shape the future of Go! Take the 2026 Go Developer Survey

wfc

package module
v0.0.0-...-38a8756 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 28, 2019 License: MIT Imports: 5 Imported by: 0

README

Wave Function Collapse

Go port of the Wave Function Collapse algorithm originally created by ExUtumno https://github.com/mxgmn/WaveFunctionCollapse

Introduction

The Wave Function Collapse algorithm is a random pattern generator based on methods found in quantum physics. A sample input of constraints is fed in along with desired output criteria, i.e. width, height, periodic. The algorithm begins by analyzing the input constraints and building a list of rules about how the patterns can fit together. The output is then created in a "superposed" state, in which each slot of the output contains all possible patterns. During the first iteration, a slot is selected semi-randomly and "observed", i.e. narrowed down to one randomly chosen pattern. The implications of this selection are then propagated to the slot's neighbors recursively, eliminating patterns that cannot exist in those slots given the constraints. This cycle of observe and propagate is then repeated until all slots have one patten chosen, or there is a contradiction in which a slot has zero possible patterns.

Input Image Output Image

Input Images Input Images Input Images Output Image

Installation

The project can be fetched via Go's CLI with the following command.

go get github.com/shawnridgeway/wfc

Otherwise, the project can be imported with the following line.

import "github.com/shawnridgeway/wfc"

Usage

There are two models included in this project:

  • Overlapping Model: this algorithm takes a sample image as input and uses its patterns to create a randomized texture as output.

  • Simple Tiled Model: this algorithm takes in a list of tiles and constraints and produces a randomized permutation.

Each of the models has its own constructor, but all other methods are common to the two models.

NewOverlappingModel

Constructor for a new OverlappingModel.

NewOverlappingModel(inputImage image.Image, n, width, height int, periodicInput, periodicOutput bool, symmetry int, ground bool) *OverlappingModel

Accepts:

  • inputImage image.Image: the sample image which will be used to extract patterns for the output.
  • n int: the size of the patterns that the algorithm should extract. The algorithm will extract n by n square patterns from the input image to be used in constructing the output. Larger values will enable the algorithm to capture larger features in the input image, at a cost to the performance.
  • width int: width in pixels of the output image
  • height int: height in pixels of the output image
  • periodicInput bool: true if the algorithm should consider the input to be repeating. This enables pattern detection to connect top-bottom and left-right pixels to form additional patterns.
  • periodicOutput bool: true if the output should be repeatable. This means that continuity is preserved across top-bottom and left-right borders and that the image will appear seamless when tiled.
  • symmetry int: the number of axies of symetry to consider when constructing the output. A larger value implies more reflections and rotations of the extracted patterns. Acceptable values are integers from 1 throught 8.
  • ground bool: true if the algorithm should look for a repeating ground pattern. This has the effect of making the bottom tiles appear only on the bottom of the output image.

Returns:

  • *OverlappingModel: a pointer to the newly constructed model
NewSimpleTiledModel

Constructor for a new SimpleTiledModel.

NewSimpleTiledModel(data SimpleTiledData, width, height int, periodic bool) *SimpleTiledModel

Accepts:

  • data SimpleTiledData: data structure of tiles and constraints to be used.
    • Unique bool: true if the tile set contains variations of each tile.
    • TileSize int: the width and height in pixels of each tile.
    • Tiles []Tile: list of tiles to be used in the generation.
      • Name string: identifying name of the tile.
      • Symetry string: axies of symetry. Acceptable values are "L", "T", "I", "\\" or "X".
      • Weight float64: the desired frequency of this tile in the output. Values less than 1 will appear less often while those above 1 will appear more often. Note that 0 is not acceptable and will be converted to 1. If you wish to turn a tile off, please remove it from the list.
      • Variants []image.Image: list of images that can be used when rendering this tile.
    • Neighbors []Neighbor: list of tile neighbor constraints. Defines which tiles can apper next to eachother.
      • Left string: name of the first tile in the pair
      • LeftNum int: variation number of the first tile in the pair
      • Right string: name of the second tile in the pair
      • RightNum int: variation number of the second tile in the pair
  • width int: width in tiles of the output image
  • height int: height in tiles of the output image
  • periodic bool: true if the output should be repeatable. This means that continuity is preserved across top-bottom and left-right borders and that the image will appear seamless when tiled.

Returns:

  • *SimpleTiledModel: a pointer to the newly constructed model.
Generate

Run the algorithm until success or contradiction.

(model *Model) Generate() (image.Image, bool)

Returns:

  • image.Image: the output image.
  • bool: true if the generation was successful, false if a contradiction was encountered.
Iterate

Run the algorithm through iterations number of generations, stopping at success or contradiction.

(model *Model) Iterate(iterations int) (image.Image, bool, bool)

Accepts:

  • iterations int: the number of generations to iterate over.

Returns:

  • image.Image: the output image
  • bool: true if the algorithm finished and cannot iterate further.
  • bool: true if the generation was successful, false if a contradiction was encountered or is not finished.
Render

Returns an image.Image of the output at its current state. This is often not necessary since both Generate and Iterate return the output image as well.

(model *Model) Render() image.Image

Returns:

  • image.Image: the output image at its current state.
IsGenerationSuccessful

Returns true if the generation is finished and successful, i.e. has no contradiction.

(baseModel *Model) IsGenerationSuccessful() bool

Returns:

  • bool: true if the generation is finished and successful, i.e. has no contradiction.
Clear

Clear the internal state of the algorithm for a new generation. Only necessary to call when using Iterate and the algorithm has not finished.

(model *Model) Clear()
SetSeed

Sets a stable seed for the random number generator. Unless this method is called, the model will use a seed based on the current time each time the model is reset. This method is mostly useful for creating a reproducable tests.

(baseModel *Model) SetSeed(seed int64)

Accepts:

  • seed int64: seed value to feed to the random number generator.

Examples

More example can be found in the test files included in the project.

Overlapping Model
// Create a new model
model := wfc.NewOverlappingModel(inputImg, 3, 48, 48, true, true, 2, true)

// Run the algorithm until success or contradiction
outputImg, success := model.Generate() 

// Run the algorithm 10 times, stopping at success or contradiction
outputImg, finished, success := model.Iterate(10)
Simple Tiled Model
// Create a new model
model := wfc.NewSimpleTiledModel(data, 20, 20, false)

// Run the algorithm until success or contradiction
outputImg, success := model.Generate() 

// Run the algorithm 10 times, stopping at success or contradiction
outputImg, finished, success := model.Iterate(10)

Credits

This project was based off the JavaScript version by kchapelier (https://github.com/kchapelier/wavefunctioncollapse) and the original version by ExUtumno (https://github.com/mxgmn/WaveFunctionCollapse)

All images are borrowed from the above two repositories, please refer to those repositories for limitations on usage and distribution.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type AppliedAlgorithm 

type AppliedAlgorithm interface {
	Iterator
	Generator
	OnBoundary(x, y int) bool
	Propagate() bool
	Clear()
}

type BaseModel 

type BaseModel struct {
	InitiliazedField     bool           // Generation Initialized
	RngSet               bool           // Random number generator set by user
	GenerationSuccessful bool           // Generation has run into a contradiction
	Wave                 [][][]bool     // All possible patterns (t) that could fit coordinates (x, y)
	Changes              [][]bool       // Changes made in interation of propagation
	Stationary           []float64      // Array of weights (by frequency) for each pattern (matches index in patterns field)
	T                    int            // Count of patterns
	Periodic             bool           // Output is periodic (ie tessellates)
	Fmx, Fmy             int            // Width and height of output
	Rng                  func() float64 // Random number generator supplied at generation time
}

func (*BaseModel) ClearBase 

func (baseModel *BaseModel) ClearBase(specificModel AppliedAlgorithm)

*

  • Clear the internal state to start a new generation

func (*BaseModel) Generate 

func (baseModel *BaseModel) Generate(specificModel AppliedAlgorithm)

*

  • Execute a complete new generation until success or failure.

func (*BaseModel) IsGenerationSuccessful 

func (baseModel *BaseModel) IsGenerationSuccessful() bool

*

  • Check whether the generation completed successfully

func (*BaseModel) Iterate 

func (baseModel *BaseModel) Iterate(specificModel AppliedAlgorithm, iterations int) bool

*

  • Execute a fixed number of iterations. Stop when the generation succeedes or fails.

func (*BaseModel) Observe 

func (baseModel *BaseModel) Observe(specificModel AppliedAlgorithm) bool

*

  • Observe
  • returns: finished (bool)

func (*BaseModel) SetSeed 

func (baseModel *BaseModel) SetSeed(seed int64)

*

  • Set the seed for the random number generator. Useful for a stable testing environment.

func (*BaseModel) SingleIteration 

func (baseModel *BaseModel) SingleIteration(specificModel AppliedAlgorithm) bool

*

  • Execute a single iteration
  • returns: finished (bool)

type GeneratedImage 

type GeneratedImage struct {
	// contains filtered or unexported fields
}

General struct for common functionality between CompleteImage and IncompleteImage

func (GeneratedImage) At 

func (gi GeneratedImage) At(x, y int) color.Color

func (GeneratedImage) Bounds 

func (gi GeneratedImage) Bounds() image.Rectangle

func (GeneratedImage) ColorModel 

func (gi GeneratedImage) ColorModel() color.Model

type Generator 

type Generator interface {
	Generate() (image.Image, bool)
}

type Inversion 

type Inversion func(int) int

Tile inversion function type

type Iterator 

type Iterator interface {
	Iterate(iterations int) (image.Image, bool, bool)
}

type Neighbor 

type Neighbor struct {
	Left     string // Mathces Tile.Name
	LeftNum  int    // Default to 0
	Right    string // Mathces Tile.Name
	RightNum int    // Default to 0
}

Information on which tiles can be neighbors

type OverlappingModel 

type OverlappingModel struct {
	*BaseModel                 // Underlying model of generic Wave Function Collapse algorithm
	N            int           // Size of patterns (ie pixel distance of influencing pixels)
	Colors       []color.Color // Array of unique colors in input
	Ground       int           // Id of the specific pattern to use as the bottom of the generation. A value of -1 means that this is unset
	Patterns     []Pattern     // Array of unique patterns in input
	Propagator   [][][][]int   // Table of which patterns (t2) mathch a given pattern (t1) at offset (dx, dy) [t1][dx][dy][t2]
	Fmxmn, Fmymn int           // Width and height of output, minus n
}

*

  • OverlappingModel Type

func NewOverlappingModel 

func NewOverlappingModel(img image.Image, n, width, height int, periodicInput, periodicOutput bool, symmetry int, ground bool) *OverlappingModel

*

  • NewOverlappingModel
  • @param {image.Image} img The source image
  • @param {int} N Size of the patterns
  • @param {int} width The width of the generated image
  • @param {int} height The height of the generated image
  • @param {bool} periodicInput Whether the source image is to be considered as periodic / as a repeatable texture
  • @param {bool} periodicOutput Whether the generation should be periodic / a repeatable texture
  • @param {int} symmetry Allowed symmetries from 1 (no symmetry) to 8 (all mirrored / rotated variations)
  • @param {int} [ground=0] Id of the specific pattern to use as the bottom of the generation ( see https://github.com/mxgmn/WaveFunctionCollapse/issues/3#issuecomment-250995366 )
  • @return *OverlappingModel A pointer to a new copy of the model

func (*OverlappingModel) Clear 

func (model *OverlappingModel) Clear()

*

  • Clear the internal state, then set ground pattern

func (*OverlappingModel) Generate 

func (model *OverlappingModel) Generate() (image.Image, bool)

*

  • Retrieve the RGBA data
  • returns: Image, successful

func (*OverlappingModel) Iterate 

func (model *OverlappingModel) Iterate(iterations int) (image.Image, bool, bool)

*

  • Retrieve the RGBA data
  • returns: Image, finished, successful

func (*OverlappingModel) OnBoundary 

func (model *OverlappingModel) OnBoundary(x, y int) bool

*

  • OnBoundary

func (*OverlappingModel) Propagate 

func (model *OverlappingModel) Propagate() bool

*

  • Propagate
  • return: bool, change occured in this iteration

func (*OverlappingModel) Render 

func (model *OverlappingModel) Render() image.Image

*

  • Retrieve the RGBA data
  • returns: Image

func (*OverlappingModel) RenderCompleteImage 

func (model *OverlappingModel) RenderCompleteImage() image.Image

*

  • Create a image.Image holding the data for a complete image

func (*OverlappingModel) RenderIncompleteImage 

func (model *OverlappingModel) RenderIncompleteImage() image.Image

*

  • Create a image.Image holding the data for an incomplete image

type Pattern 

type Pattern []int

*

  • Pattern Type. Flattened array of color codes.

type SimpleTiledData 

type SimpleTiledData struct {
	Unique    bool       // False if each tile can have variants. (Default to false?)
	TileSize  int        // Default to 16
	Tiles     []Tile     // List of all possible tiles, not including inversions
	Neighbors []Neighbor // List of possible connections between tiles
}

Parsed data supplied by user

type SimpleTiledModel 

type SimpleTiledModel struct {
	*BaseModel               // Underlying model of generic Wave Function Collapse algorithm
	TileSize   int           // The size in pixels of the length and height of each tile
	Tiles      []TilePattern // List of all possible tiles as images, including inversions
	Propagator [][][]bool    // All possible connections between tiles
}

*

  • SimpleTiledModel Type

func NewSimpleTiledModel 

func NewSimpleTiledModel(data SimpleTiledData, width, height int, periodic bool) *SimpleTiledModel

*

  • NewSimpleTiledModel
  • @param {object} data Tiles and constraints definitions
  • @param {int} width The width of the generation, in terms of tiles (not pixels)
  • @param {int} height The height of the generation, in terms of tiles (not pixels)
  • @param {bool} periodic Whether the source image is to be considered as periodic / as a repeatable texture
  • @return *SimpleTiledModel A pointer to a new copy of the model

func (*SimpleTiledModel) Clear 

func (model *SimpleTiledModel) Clear()

*

  • Clear the internal state, then set ground pattern

func (*SimpleTiledModel) Generate 

func (model *SimpleTiledModel) Generate() (image.Image, bool)

*

  • Retrieve the RGBA data
  • returns: Image, successful

func (*SimpleTiledModel) Iterate 

func (model *SimpleTiledModel) Iterate(iterations int) (image.Image, bool, bool)

*

  • Retrieve the RGBA data
  • returns: Image, finished, successful

func (*SimpleTiledModel) OnBoundary 

func (model *SimpleTiledModel) OnBoundary(x, y int) bool

*

  • OnBoundary

func (*SimpleTiledModel) Propagate 

func (model *SimpleTiledModel) Propagate() bool

*

  • Propagate
  • return: bool, change occured in this iteration

func (*SimpleTiledModel) Render 

func (model *SimpleTiledModel) Render() image.Image

*

  • Retrieve the RGBA data
  • returns: Image

func (*SimpleTiledModel) RenderCompleteImage 

func (model *SimpleTiledModel) RenderCompleteImage() image.Image

*

  • Create a image.Image holding the data for a complete image

func (*SimpleTiledModel) RenderIncompleteImage 

func (model *SimpleTiledModel) RenderIncompleteImage() image.Image

*

  • Create a image.Image holding the data for an incomplete image

type Tile 

type Tile struct {
	Name     string        // Name used to identify the tile
	Symmetry string        // Default to ""
	Weight   float64       // Default to 1
	Variants []image.Image // Preloaded image for the tile
}

Raw information on a tile

type TilePattern 

type TilePattern []color.Color

Flat array of colors in a tile

Source Files

View all Source files

Directories

Path Synopsis
internal
testutils

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.