Randomly generated tile maps using Oskar Stålberg's wave function collapse algorithm

Go Reference Go Report Card

go-wfc

Procedurally-generated tile maps using wave function collapse.

Demos

Live demo (wasm):

Live algorithm animation (wasm):

Overview

This package uses the Wave Function Collapse algorithm as described by Oskar Stålberg.

The wave function collapse algorithm is a recursive algorithm that picks a random tile for a slot on the output image and removes impossible neighbors until only a single possibility remains. The algorithm is covered in more detail below.

If you need a generic algorithm, then please check out the golang fork of the original work.

Why?

There is already a wfc golang library so why another one? The existing one is a lot more generic and quite a bit slower as a result. Also, the tile setup for the original implementation can be very tedious. Additionally, I found it hard to follow and modify.

This variation follows Oskars work and aims to simplify the original work for easy integration into games.

Tiles

You'll need a set of tiles, also referred to as modules. These will need to be designed to fit together. The tiles should have matching colors along edges that should appear next to each other in the final output. Other than that, no manual setup or description files are needed.

You should reference the example folder when making a tile set.

sample

  • Any number of tiles can be used as input, but the recommendation is to start with a small set until you're comfortable with the constraint system.

  • You can create alternate tiles, meaning tiles with the same sets of colors along all four edges. The probability for each alternate tile is the same. If you'd like to increase/lower the probability of a particular tile, simply duplicate the image reference when calling the initialize method.

  • Unlike the original WFC implementation, no manual setup or description files are needed.

Adjacencies / Constraints

The wave function collapse algorithm requires some kind of adjacency mapping in order to remove impossible tiles and stitch together a possible output using the input set.

By default, the package uses the color values along the four edges of each tile (Up, Down, Left, Right) to build constraints. But, you can customize this behaviour if you'd like.

When designing your tiles, think about how the color values line up. They should be exactly the same on the middle 3 points for two potentially adjacent tiles. For example, the following tiles could appear as shown below because they share the same colors on the bottom of the first and the top of the second.

You can view the default adjacency constraint implementation here. It scans colors along each edge of each input tile. These colors are turned into a hash that represents that edge. Any tiles that have the same hash value in the opposite direction are considered possible adjacencies automatically.

Contradictions

It is possible that the wave can collapse into a state that has a contradiction. For example, sky beneath the ground. If a contradiction is found, the algorithm re-tries until the maximum number of attempts is reached.

When exporting an image, if you see a red tile, you've got a contradiction. If you keep seeing these, your tileset likely has an issue.

Results

Here are some example outputs for a 8 x 8 grid.

results

Quick Start

You'll need to load a set of tiles (images) into an array. A convenience function is provided by this package but you can use any method you'd like.

  // Load the input tile images (any order and count is fine)
  var input_images []image.Image
  input_images, err = wfc.LoadImageFolder(tileset_folder)
  if err != nil {
    panic(err)
  }

Next, initialize a wave function with the desired output size (in units of tiles). For example, lets say that you want your output image to be 32 x 8 tiles, you'd pass in the following.

  // Setup the initialized state. The output image will be 32 x 8 tiles.
  wave := wfc.New(input_images, 32, 8)
  wave.Initialize(42) // seed: 42

Finally, collapse the wave into a single state (if possible).

  // Collapse the wave function (make up to 100 attempts)
  err = wave.Collapse(200)
  if err != nil {
    panic(err)
  }

Optionally, you can export the collapsed wave to an image.

  // Lets generate an image
  output_image := wave.ExportImage()
  wfc.SaveImage("wave.png", output_image)

Or, you can review the results manually to do custom rendering in your game.

  for _, slot := range wave.PossibilitySpace {
    if len(slot.Superposition) == 1 {
      // successfully collapsed slot
      ...
    }
    if len(slot.Superposition) == 0 {
      // contradiction
      ...
    }
  }

Full example:

import "github.com/zfedoran/go-wfc/pkg/wfc"

func collapseWave(tileset_folder, output_image string) {
  // This is just a `[]image.Image`, you can use whatever loader function you'd like
  images, err := wfc.LoadImageFolder(tileset_folder)
  if err != nil {
    panic(err)
  }

  // The random seed to use when collapsing the wave
  // (given the same seed number, the Collapse() fn would generate the same state every time)
  seed := int(time.Now().UnixNano())

  // Setup the initialized state
  wave := wfc.New(images, 32, 8)
  wave.Initialize(seed)
  
  // Collapse the wave function (make up to 100 attempts)
  err = wave.Collapse(200)
  if err != nil {
    // don't panic here, we want to generate the image anyway
    fmt.Printf("unable to generate: %v", err)
  }

  // Lets generate an image
  output := wave.ExportImage()
  wfc.SaveImage(output_image, output)

  fmt.Printf("Image saved to: %s\n", output_image)
}

Complete source can be found here: example/main.go

Also, check out the animated version: https://github.com/zfedoran/go-wfc-example

Custom Constraints

If you'd like to customize or change this logic, you are able to pass in a custom constraint function.

You can choose a different number of lookup points (3 is the default). For example, 2 lookup points.

  wave.NewWithCustomConstraints(tiles, width, height, wfc.GetConstraintFunc(2))

Or, you can provide your own.

  wave.NewWithCustomConstraints(tiles, width, height, 
    func(img image.Image, d Direction) ConstraintId {
    ...
  })

Algorithm

The algorithm is covered in detail here: https://www.youtube.com/watch?v=0bcZb-SsnrA&t=350s

  1. A set of input image tiles (or modules) are loaded into memory.
  2. A wave function is defined with the desired output width and height (in units of tiles).
  3. The wave function is initialized such that each output tile (or slot) is in a superposition of all provided input tiles.
  4. A random slot is selected and collapsed into a random input tile.
  5. Each of the neighboring slots is now evaluated to verify if there are any input tiles that can fit next to the collapsed tile. Any impossible tiles (or modules) are removed.
  6. If the state of any of the neighboring tiles was changed in step 5), then recurse into it's neighbors to remove impossible tiles.
  7. If there are no possible tiles left at any point, a contradiction has been found and we need to go back to step 3) and try again.
  8. Once no more changes are left to propagate, go to step 4) and recurse until all slots are collapsed to a single state.

Or, you if you prefer, here is the actual implementation.

Artwork

The awesome artwork in this repository was done by @makionfire. If you need help designing a tile set, I highly recommend reaching out to her. A huge shout-out to @makionfire for letting me use this tileset.

The artwork itself does not fall under the MIT licence.

Licence

The licence for the source code in this package is MIT. Meaning, do whatever you'd like but we'd love a shoutout. The goal is to get more folks to build games with golang.

If you like this work and want to buy me or the artist a coffee or beer, you're free to do so by sending to some SOL to 🍺 💵 .sol

Owner
Zelimir Fedoran
Backend arch building something payments related on Solana. My specialties are Golang, Django, Node.js, and 3D
Zelimir Fedoran
Similar Resources

The simplest sorting algorithm that sorts in quadratic time

The simplest sorting algorithm that sorts in quadratic time

Simplest sort Showcases the simplest sorting algorithm that works in quadratic time. From here. The pseudocode for this algo can be seen below (sorts

Oct 14, 2022

Is this the simplest (and most surprising) sorting algorithm ever?

Is this the simplest sorting algorithm

May 15, 2022

Smartsort - A smart sorting algorithm for Go to sort filename containing digits that is not zero padded

smartsort A smart sorting algorithm for Go to sort filename containing digits th

Mar 26, 2022

Pipelines using goroutines

pipeline This package provides a simplistic implementation of Go pipelines as outlined in Go Concurrency Patterns: Pipelines and cancellation. Docs Go

Oct 5, 2022

A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Sep 26, 2022

High-performance minimalist queue implemented using a stripped-down lock-free ringbuffer, written in Go (golang.org)

This project is no longer maintained - feel free to fork the project! gringo A high-performance minimalist queue implemented using a stripped-down loc

Oct 24, 2022

Go framework to simplify CRUD of structured data using Graph operations

Go framework to simplify CRUD of structured data using Graph operations

gocrud Go framework to simplify creating, reading, updating, and deleting arbitrary depth structured data — to make building REST services fast and ea

Nov 28, 2022

A typed implementation of the Go sync.Map using code generation

syncmap A typed implementation of the Go sync.Map using code generation. Install go get -u github.com/a8m/[email protected] Examples: Using CLI $ syncma

Nov 24, 2022

Fast Raft framework using the Redis protocol for Go

Fast Raft framework using the Redis protocol for Go

This project has been archived. Please check out Uhaha for a fitter, happier, more productive Raft framework. Finn is a fast and simple framework for

Oct 10, 2022
estruct traverses javascript projects and maps all the dependencies and relationships to a JSON. the output can be used to build network visualizations of the project and document the architecture.
estruct traverses javascript projects and maps all the dependencies and relationships to a JSON. the output can be used to build network visualizations of the project and document the architecture.

EStruct traverses javascript projects and maps all the dependencies and relationships to a JSON. The output can be used to build network visualizations of the project and document the architecture.

Jan 27, 2022
Tutorial code for my video Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang

Learn to Use Basic Data Structures - Slices, Structs and Maps in Golang Read text from a file and split into words. Introduction to slices / lists. Co

Jan 26, 2022
Multi-String Pattern Matching Algorithm Using TrieHashNode

Multi-String Pattern Matching algorithm. This implementation is inspired from Aho-Corasick algorithm Getting Started modelA = mspm.NewModel("mspm_mode

Sep 26, 2022
Maintidx measures the maintainability index of each function

maintidx maintidx measures the maintainability index of each function. Here for

Oct 31, 2022
Data structure and algorithm library for go, designed to provide functions similar to C++ STL

GoSTL English | 简体中文 Introduction GoSTL is a data structure and algorithm library for go, designed to provide functions similar to C++ STL, but more p

Nov 24, 2022
A Go implementation of the 64-bit xxHash algorithm (XXH64)

xxhash xxhash is a Go implementation of the 64-bit xxHash algorithm, XXH64. This is a high-quality hashing algorithm that is much faster than anything

Nov 30, 2022
golang sorting algorithm and data construction.

data-structures-questions 算法和程序结构是我们学习编程的基础,但是很多的时候,我们很多都是只是在应用,而没有深入的去研究这些,所以自己也在不断的思考和探索,然后分析,学习,总结自己学习的过程,希望可以和大家一起学习和交流下算法! 目录 网络协议 数据结构 算法 数据库 Go

Nov 30, 2022
Implementation of Boyer-Moore fast string search algorithm in Go

boyermoore Implementation of Boyer-Moore fast string search algorithm in Go

Oct 7, 2022
A Go implementation of the core algorithm in paper

Boolean Expression Indexer Go library A Go implementation of the core algorithm in paper <Indexing Boolean Expression>, which already supports the fol

Nov 29, 2022
记录算法学习和LeetCode、LintCode、codewars的学习路程。A record of algorithm learning.

Problem List Leetcode、LintCode、Codewars Algorithm problem solution written by golang. LeetCode id Name(Github) Name(Gitee) 00001 TwoSum TwoSum 00003 L

Nov 3, 2021