Procedural Generation with Wave Function Collapse (2019)

Posted3 months agoActive3 months ago

todsacerdoti

52 points

13 comments

gridbugs.orgTechstory

calmpositive

Debate

20/100

Procedural GenerationAlgorithmGame Development

Key topics

Procedural Generation

Algorithm

Game Development

The article discusses the Wave Function Collapse algorithm for procedural generation, sparking a thoughtful discussion about its origins, applications, and characteristics.

Snapshot generated from the HN discussion

Discussion Activity

Moderate engagement

First comment

Peak period

0-2h

Avg / period

1.9

Comment distribution13 data points

Loading chart...

Based on 13 loaded comments

Key moments

01Story posted
Oct 3, 2025 at 3:13 PM EDT
3 months ago
Step 01
02First comment
Oct 3, 2025 at 4:31 PM EDT
1h after posting
Step 02
03Peak activity
6 comments in 0-2h
Hottest window of the conversation
Step 03
04Latest activity
Oct 4, 2025 at 1:33 PM EDT
3 months ago
Step 04

Generating AI Summary...

Analyzing up to 500 comments to identify key contributors and discussion patterns

Discussion (13 comments)

Showing 13 comments

3 months ago

1 reply

I always found "wave function collapse" to be a terribly overcomplicated name for a pretty intuitive concept. The first paragraph does a good job explaining the term, but still I wonder how many people stray away from such things when the name alone is overwhelming.

zzyzek

3 months ago

1 reply

For many, the name is intuitive as its encapsulating the idea that a cell can hold a variety of states until it gets "collapsed".

TuringTest

3 months ago

1 reply

I prefer the name given in mathematical optimization, which is Constraints Satisfaction Problems; instead of using an imprecise physics metaphor, it gets a descriptive logical term of what's going on.

In CSPs, each cell is a 'decision variable' with a 'domain' of values, which get pruned by 'constraints' that propagate to values invalidated by the decisions made in the connected variables, until the whole 'problem' gets into either a solution which 'satisfies' all the constraints, or a contradictory state where a variable's domain is empty, causing the algorithm to backtrack.

CSPs have the advantage of having clear and efficient methods to go back to a previous state and keep exploring every alternate possibility, rather than having to restart from the beginning. The article hints at that possibility ('saving checkpoints' or'reverse the collapsing of a cell'); there's a whole field of study dedicated on the best ways to do that on a large scale for very general problems.

zzyzek

3 months ago

1 reply

Boris the brave coined the term "Constraint Based Tile Generators" (CBTG) [0], which is a specialization of the more general CSPs to this particular domain.

Personally, I find CSPs overly general and mired in esoteric, byzantine terminology. It's a large cognitive load to put on people to run through the glossary of terms just to talk about the problem set up. I don't think the quantum mechanic analogy is great but I can see it being much more intuitive than the obscure language of CSPs.

[0] https://www.boristhebrave.com/2021/10/31/constraint-based-ti...

TuringTest

3 months ago

Surely the 'solving' part of CSPs may be obscure, but the basic concept can be readily explained with the metaphor of crosswords and sudoku (both are very direct instances of CSPs); there's not much obscurity to that. In fact, the article resorts to that same metaphor to explain with precision what the 'waveform' metaphor couldn't.

Of course terminology for CSPs will get confusing when you get to represent them mathematically; but that happens to anything that you turn into math. The core concept is quite familiar and intuitive.

dejobaan

3 months ago

2 replies

There's a neat demo of this in action here: https://jaxry.github.io/wave-function-collapse/

Another, where you can set cells and then have it solve: https://oskarstalberg.com/game/wave/wave.html

And an itch.io game where you are the wave function selector: https://bolddunkley.itch.io/wfc-mixed

I thought this concept would have found more traction in the world of procgen (in games), because it's pretty neat. But I found it difficult to work with, so perhaps others also did!

seanssel

3 months ago

Caves of Qud uses it in map generation: https://youtu.be/AdCgi9E90jw

dwd

3 months ago

Oskar Stalberg has used it a bit, notably with Townscaper.

https://www.townscapergame.com/

impossiblefork

3 months ago

1 reply

I think one of the neat things with this algorithm is that it's completely local, but still creates global structures that fit together.

This is in contrast to LLMs, and I assume it comes from that it discards improbable things instead of choosing probable things.

aeve890

3 months ago

>I think one of the neat things with this algorithm is that it's completely local, but still creates global structures that fit together.

Nicely fitting for the (sort of) physical quantum wave function collapse behavior.

leetrout

3 months ago

(2019)

dustbunny

3 months ago

It's basically sudoku

zzyzek

3 months ago

This is based off of Paul Merrell's Model Synthesis work [0]. Boris The Brave had a good writeup of the core of the algorithm [1].

Max Gumin focused on just the constraint solver and added a "minimum entropy heuristic", popularized the work and coined the term "wave function collapse", as the way the solver worked was evocative of (a naive view) of how quantum mechanics solves systems [2]. Gumin's repo also has many other resources of implementations and descriptions [3].

I've published a paper on an extension that adds in a type of backtracking to both the "WFC" portion of the solver and the modify in blocks portion of the solver, which can be found in [4], for those interested.

[0] https://paulmerrell.org/model-synthesis/

[1] https://www.boristhebrave.com/2021/10/26/model-synthesis-and...

[2] https://github.com/mxgmn/WaveFunctionCollapse

[3] https://github.com/mxgmn/WaveFunctionCollapse?tab=readme-ov-...

[4] https://zzyzek.github.io/PunchOutModelSynthesisPaper/

View full discussion on Hacker News

ID: 45466655Type: storyLast synced: 11/20/2025, 2:36:48 PM

Want the full context?

Jump to the original sources

Read the primary article or dive into the live Hacker News thread when you're ready.

Open link View on HN