Superpositions, Sudoku, the Wave Function Collapse algorithm.
Channel:Martin Donald · Length:14:27 · Published:2020-07-31 · Views:766805
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
- How Bankrupt American Cities Stay Alive - Debt [ST04] · Not Just Bikes · 11:01
- A NEW Trace! The FULL MH370 Story, so Far.. · Mentour Pilot · 56:06
- The medical test paradox, and redesigning Bayes' rule · 3Blue1Brown · 21:13
- The world depends on a collection of strange items. They're not cheap · Veritasium · 18:32
- Why Electronic Voting Is Still A Bad Idea · Tom Scott · 12:00
- The Beauty of Bézier Curves · Freya Holmér · 24:25
- The Continuity of Splines · Freya Holmér · 1:13:50
- elevated by Rgba & TBC | 4k intro (FullHD 1080p demoscene demo) · Demoscene High-Quality Videos (Annikras) · 3:36
- Overwatch Gameplay Architecture and Netcode · GDC Festival of Gaming · 1:04:03
- Painting a Character with Maths · Inigo Quilez · 24:46
- CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” · CppCon · 59:33
- The Real Story Behind Wayland and X - Daniel Stone (linux.conf.au 2013) · Mladen Mijatov · 45:35
- RustConf 2018 - Closing Keynote - Using Rust For Game Development by Catherine West · Rust Programming Language · 42:29
- A Deep Dive into Nanite Virtualized Geometry · SIGGRAPH Advances in Real-Time Rendering · 1:09:59
- How Crash Bandicoot Hacked The Original Playstation | War Stories | Ars Technica · Ars Technica · 31:37
- Jonathan Blow - How to program independent games - CSUA Speech · Alexandre Franco · 1:15:50