# How fast or scalable is wave function collapse?

Specifically the generation part, if I wanted to use it at high resolutions.

High level descriptions make me suspect O(n²) or worse, and demos are always low res, but fast-wfc describes itself as "Wave Function Collapse with a focus on performance. It was called fast-wfc because at the time it introduced optimizations improving the execution time by an order of magnitude.", so do optimized implementations scale well? What sort of sizes are realistic?

• The best way to answer this for your use case is to download an existing implementation and run a quick test while profiling. Asking a stranger on the Internet will just get you a bunch of "fast enough for my needs" or "not fast enough for my needs" and you'll be left guessing whether your needs are more like the first person's or more like the second, or somewhere in between. Testing, profiling, and comparing to your own performance goals is the best way to evaluate whether a particular approach will meet those goals on your target hardware. Jul 17, 2022 at 21:06
• Knowing the big-O notation would help, worst cases vs. optimized cases etc., as the question is about "when can I reach for this tool", rather than learning whether a specific implementation I downloaded is a good match for a specific job. Jul 23, 2022 at 4:40
• I'd be willing to wager that in the time you spend waiting for an answer, you could benchmark an available implementation to measure the scaling behaviour empirically, using sample data representative of your application, and even profiling it on your actual target hardware. For gamedev purposes, that's way better than just a big-O formula because it tells you the size of the constants involved too. Jul 23, 2022 at 11:50
• @DMGregory The good-faith interpretation of the question is "What is the "big-oh" of WFC in a practical/optimized sense" which is something that many people might want the answer to. The difference between an O(n^2) algorithm and an O(n) algorithm are such that even throwing more hardware at a large enough problem won't help all that much and so analyzing asymptotic run-time, especially if that analysis helps in converting a O(n^2) to an O(n) algorithm, can have significant speedups. Jan 23 at 21:16

First, let's define $$\N\$$ to be the number of cells and $$\T\$$ to be the number of tiles. For example, Pac-Man has about 36 unique tiles ($$\T = 36\$$) and has about $$\28 \times 31\$$ cells ($$\N = 868\$$).

In general, the upper bound is $$\O(T^2 \cdot N^2)\$$. In practice this probably can be reduced down to $$\O(T^2 \cdot N)\$$.

We can't really do better than $$\O(T \cdot N)\$$ because just to traverse all cells and remove all non-chosen tiles, we're already at $$\T \cdot N\$$. To see why it might be $$\O(T^2 \cdot N^2)\$$, we might be required to traverse the whole grid after a single tile removal to see if any tiles need to be removed from the given constraints.

In practice, we only have pairwise neighbor tile/cell constraints and so the "impact" of a single tile removal can be localized to only cells around impacted site.

The algorithm for this approach flags neighboring cells as needing to be inspected if a tile was removed near them. After inspection, remove them from consideration, marking any neighbors as needing inspection if any further updates (tile removals) have occured.

Here's some rough pseudo-code:

function propagateConstraints(grid, accessed) {
while (still culling) {
removeFlaggedCells()
foreach cell in accessed {
foreach neighbor_cell in cell {
if tiles can be removed from neighbor_cell {
flag neighbor_cell
}
}
remove cell from accessed and unflag cell
}
}
}


In general, this only updates a kind of "wave-front" or boundary of where a tile has been removed. In the worst case this can cycle through the whole grid but this only happens if it needs to, whereas a naive version touches many cells whether it needs to or not.

I'm kind of waiving my hands here and only considering the naive way of testing whether tiles need to be updated by doing a complete pairwise comparison. In theory, if one were sufficiently motivated, there might be speedups there to try and reduce the $$\O(T^2 \cdot N)\$$ down to something closer to $$\O(T \cdot N)\$$.

I've further ignored the dimension of the grid and taken for granted that the number of neighbors is constant. There is another factor of $$\D\$$, the dimension that comes into the runtime. For fixed dimension, this obviously doesn't impact the "big-oh" but is still a relevant factor when practically considering run time.

I wrote a small article about my implementation of Wave-Function-Collapse which can be found here. The source code is also available here (though it might be a little hard to follow) and is libre/free, so feel free to inspect or use it as a reference implementation.