Comment by t8y | Hacker News Reader

Comment by t8y | Hacker News Reader

This uses the "wave function collapse" algorithm. Oskar Stalberg also made a great demo of how it works[0], but it might not make sense just from that. Martin Donald made a really nice youtube video on how it works[1]. The name "wave function collapse" can be off putting but it's pretty straightforward, and an algorithm that can come in handy for many uses both in game development and just general software development.

I'm actually procrastinating on HN from working on a GPU parallelised version that can generate millions of positions every frame. In Townscaper you can actually see that the algorithm runs quite slow and lags behind the players input, there's just a bunch of animation to hide it. I'm hoping to eventually get a version that can run in log2(mapsize) time.

[0]http://oskarstalberg.com/game/wave/wave.html [1]https://www.youtube.com/watch?v=2SuvO4Gi7uY

What's the difference between "wave function collapse" and constraint propagation? As described in the youtube link, it looks like it's the same.

I didn't know that constraint propagation existed. Having a quick look it does look the same.

In the in the original WFC(wave function collapse)[0] versions it always used an example of a completed output and generated all valid tile combinations from that. For a game this means that the developer can use hand made maps as examples for it to create new plausible maps. In the common vernacular WFC doesn't use this step and just directly either generates what combinations work or the devs manually decide what tiles can be next to others. Perhaps only the combination of both steps should be considered WFC.

Just to guess I think this is probably a case of it being developed independently in different fields. It's good to have another name for it as I always hated it being called "wave function collapse" when that is a physics thing.

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

The readme there refers to WFC as "constraint propagation with a saved stationary distribution" which makes sense; the goal is to have distributions of tiles similar to the sample image.

Reply on news.ycombinator.com