What is Wave Function Collapse?

As I said in the previous 2 blog posts (catch up on them if you haven't read them), I am intending to use the new and trendy Wave Function Collapse. I am interested in the algorithm and the results can be quite pleasing to look at especially whilst the generation is still happening. Last time I looked at a couple of ways of making random numbers, now I'm going to show how I'll use them.

An Overview

At it's core, Wave Function Collapse (WFC) is a algorithm within the field of constraint based programming. This means that the user/developer can decide to impose constraints on the algorithm/AI, then the AI creates a solution to a goal using them. The initial idea behind WFC was back when it was named Model Synthesis in a paper by Paul Merrell in 2009, since then it's been iterated upon a number of times.

The Algorithm

This is the algorithm as I have learnt to understand it, specifically for the context of the project, so it may not be the most generic version.

Steps

1. Creation of the model that the algorithm will use to create the output

2. Creation of the grid itself

3. Picking the starting tiles a good distance from each other

4. Propagate the updated constraints of the neighbours (and the neighbours of them if the constraints change)

5. Pick a tile to be confirmed based on the tiles with lowest options remaining

6. Repeat 4 and 6 until either failure or success

These are the steps in the most simplistic form, which I will try to implement first for the project. Then I will look at optimizing, things like backtracking to turn failures into successes.

This is a flow chart of the described steps, to be able to follow the logical process. The bulk of the program will be in setting up the system to work in a robust way. What is not included, is the practicality of creating the input models. Due to the goal of the project using tilesets, the input model is more complex than inputting an image. However it shouldn't take long to set it up to be functional although I'll leave editor APIs for future down the line.

This is a better visual explanation that I recorded of myself messing around with on Oskar Stålberg's site called "Wave". Here, the way that cells know what tiles they could be is based on the pixel colour of the tile parts next to them, with each edge having 3 "Sockets" that pixel colours can line up on. It's a great visualisation of the process that makes it much easier to understand than just explaining it.