Superpositions, Sudoku, the Wave Function Collapse algorithm.

Channel:Martin Donald · Length:14:27 · Published:2020-07-31 · Views:766805

Watch on YouTube

Summary

Martin Donald explains the Wave Function Collapse algorithm using Sudoku-like constraint solving and shows how he implemented it with Blender and Godot. It links demos and reference articles.

Why HN recommends it

Commenters recommend it as the clearest way to understand WFC, especially in threads about Townscaper and tiled content generation.

I found them hard to understand until I found this video by Martin Donald — HN, 2022

Algorithms & data structures · Computer graphics & rendering · Game programming & engines

Subtitles (excerpt)

sudoku is a solitaire game played on a 9x9 grid where the 81 cells are further grouped into nine three by three boxes the goal is to fill each space of the grid with one number between one and nine while adhering to certain rules or constraints which are as follows every row column and box must contain all numbers 1 through 9 and no number may ever appear twice within the same row column or box when observing a blank sudoku puzzle every square on the grid has the potential to be any of the nine possible numbers we could also say that they are in a superposition occupying all nine possible states at once but usually a sudoku puzzle doesn't start off blank instead there are already a few numbers filled in their superpositions collapsed to a single possibility these collapsed cells will of course affect the possibility space of surrounding cells we know for example that since there's a five in this row that none of the other cells in the same row column or box may contain a five so we can propagate that knowledge to those affected cells removing five from their superpositions after propagating all of the constraints imposed by our initial conditions the next logical thing to do is to look for the cell with the lowest

On Hacker News

I didn't know about wave collapse functions before stumbling about Townscaper. Still, I found them hard to understand until I found this video by Martin Donald: [VIDEO] Now, I'm just looking for a use-case to implement them myself sometime. — V__, 2022-06
Not OP, but I happened to see a good video on this recently: [VIDEO] In short, it’s an algorithm for procedural generation of tiled content, like 2d/3d game maps. — orls, 2022-05
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 genera… — t8y, 2021-12
I was inspired by Nicky Case[0], but independently recently reached the same conclusion as you have here. In March of 2020 when the pandemic was first hitting the US, before there was an official lock-down, and before any company wide announcement, and without any communication, my entire team had come in on a Friday, and my entire team had stayed home on the Monday. In essence, there was enough … — ItsMonkk, 2022-01

Related videos