4 ms·

The most interesting part of this is how it works, which this article is kinda light on. It uses the "wave function collapse" procedural generation technique (

The most interesting part of this is how it works, which this article is kinda light on. It uses the "wave function collapse" procedural generation technique (has been on the frontpage before if I recall correctly) to select fitting tiles when the player clicks on the map to build something. https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse In the section about notable forks, ports and spin-offs there are some links to Oskar Stalsberg's twitter showing various points along the development of this digital toy. https://github.com/mxgmn/WaveFunctionCollapse#notable-ports-forks-and-spinoffs https://github.com/mxgmn/WaveFunctionCollapse#notable-ports-... I've been following this for years and it is really inspiring to see this be so successful. I have the feeling that digital toys will become more common when gamedevs get access to things like GTP-3 seens like a really natural fit to me, supporting the creativity of the player by filling in blanks in a sufficiently advanced way.

Kinrany 6y ago
"Wave function collapse", aka constraint satisfaction
bschne 6y ago
Not sure what of this was actually used in townscaper, but someone in another discussion of the game (can't remember where unfortunately) referred to these two sources: - Oskar Stålberg's 2018 Talk "Wave Function Collapse in Bad North" (https://www.youtube.com/watch?v=0bcZb-SsnrA https://www.youtube.com/watch?v=0bcZb-SsnrA) - Müller et al, 2006 - "Procedural Modeling of Buildings" (https://doi.org/10.1145/1141911.1141931 https://doi.org/10.1145/1141911.1141931)
OneGuy123 6y ago
The name "wave function collapse" is such a overcomplicated academic term. In reality this algorith is very simple: 1) try to randomly place a part at X if it fits 2) try to pick the random part in such a way that once it will be placed we will maximize that probability that we will be able to build further on (so you just pick the part that reduces the chance of blocking the build in the next step in case nothing can fit anymore). Then you just have to provide all combination of possible connection in terms of 2d/3d graphics.
- jmiskovic 6y ago
  "Everything should be made as simple as possible, but no simpler." I think your version would run into dead ends very soon. You need to keep track for all grid positions what are remaining possible blocks (this is 'superposition') and eliminate them as you place blocks ('collapsing'). You also need a good strategy in which order to place blocks, and also how to backtrack if you run out of options. The Townscaper seems to be using non-rectangular grid, so it's maybe more like a 2D graph of distributed nodes, with perhaps Voronoi algorithm to assign 2D geometry to each node. You make it sound trivial, it's a lot of work to make it work (and probably quite a few discarded prototypes along the way).
  - 91edec 6y ago
    Oskar gave a technical talk about how he implements the grid and other interesting bits in this video: https://www.youtube.com/watch?v=1hqt8JkYRdI https://www.youtube.com/watch?v=1hqt8JkYRdI
    - jmiskovic 6y ago
      Thanks for the link. The grid generation is so much more complicated than I assumed.
- darkerside 6y ago
  I just read the wiki on wave function collapse https://en.m.wikipedia.org/wiki/Wave_function_collapse https://en.m.wikipedia.org/wiki/Wave_function_collapse I actually found it a simpler and more elegant algorithm than what you describe and not hard to understand at all.
  - BrandoElFollito 6y ago
    As someone who did a PhD in particle physics, this is very hard to understand (and not just apply math) This is actually just one of the interpretations, there are more and some are gaining traction (see for instance https://youtu.be/5hVmeOCJjOU https://youtu.be/5hVmeOCJjOU, S Caroll is a great speaker but you need to stay concentrated :)
Orochikaku 6y ago
I first came across this concept here on HN[1][2], I recall thinking at the time that it’d be incredible implemented in a full game. [1]: https://news.ycombinator.com/item?id=18443311 https://news.ycombinator.com/item?id=18443311 [2]: https://marian42.itch.io/wfc https://marian42.itch.io/wfc

Kinrany 6y ago

"Wave function collapse", aka constraint satisfaction

bschne 6y ago

Not sure what of this was actually used in townscaper, but someone in another discussion of the game (can't remember where unfortunately) referred to these two sources: - Oskar Stålberg's 2018 Talk "Wave Function Collapse in Bad North" (https://www.youtube.com/watch?v=0bcZb-SsnrA https://www.youtube.com/watch?v=0bcZb-SsnrA) - Müller et al, 2006 - "Procedural Modeling of Buildings" (https://doi.org/10.1145/1141911.1141931 https://doi.org/10.1145/1141911.1141931)

OneGuy123 6y ago

The name "wave function collapse" is such a overcomplicated academic term. In reality this algorith is very simple: 1) try to randomly place a part at X if it fits 2) try to pick the random part in such a way that once it will be placed we will maximize that probability that we will be able to build further on (so you just pick the part that reduces the chance of blocking the build in the next step in case nothing can fit anymore). Then you just have to provide all combination of possible connection in terms of 2d/3d graphics.

jmiskovic 6y ago
"Everything should be made as simple as possible, but no simpler." I think your version would run into dead ends very soon. You need to keep track for all grid positions what are remaining possible blocks (this is 'superposition') and eliminate them as you place blocks ('collapsing'). You also need a good strategy in which order to place blocks, and also how to backtrack if you run out of options. The Townscaper seems to be using non-rectangular grid, so it's maybe more like a 2D graph of distributed nodes, with perhaps Voronoi algorithm to assign 2D geometry to each node. You make it sound trivial, it's a lot of work to make it work (and probably quite a few discarded prototypes along the way).
- 91edec 6y ago
  Oskar gave a technical talk about how he implements the grid and other interesting bits in this video: https://www.youtube.com/watch?v=1hqt8JkYRdI https://www.youtube.com/watch?v=1hqt8JkYRdI
  - jmiskovic 6y ago
    Thanks for the link. The grid generation is so much more complicated than I assumed.
darkerside 6y ago
I just read the wiki on wave function collapse https://en.m.wikipedia.org/wiki/Wave_function_collapse https://en.m.wikipedia.org/wiki/Wave_function_collapse I actually found it a simpler and more elegant algorithm than what you describe and not hard to understand at all.
- BrandoElFollito 6y ago
  As someone who did a PhD in particle physics, this is very hard to understand (and not just apply math) This is actually just one of the interpretations, there are more and some are gaining traction (see for instance https://youtu.be/5hVmeOCJjOU https://youtu.be/5hVmeOCJjOU, S Caroll is a great speaker but you need to stay concentrated :)

Orochikaku 6y ago

I first came across this concept here on HN[1][2], I recall thinking at the time that it’d be incredible implemented in a full game. [1]: https://news.ycombinator.com/item?id=18443311 https://news.ycombinator.com/item?id=18443311 [2]: https://marian42.itch.io/wfc https://marian42.itch.io/wfc