I think proc gen like this often falls victim to the 1000 bowls of oatmeal problem.
Unless things _feel_ different, it just feels same-y.
Some games handle this well (often through biomes with different rules and/or special areas with different rules) and others (interestingly, often those that talk about how many billions of possibilities there are) are techniquely different... But just all feel the same.
It's interesting to see how game devs continue to be creative in this area and how many games continue to have this problem.
People seem to go ga-ga over this algorithm with some frequency on HN, and I think it is only because of its in-name-only connection to quantum mechanics, because I have to say that as procedural generation algorithm I find it very lacking. It works on the cases I saw for something like a 10x10 grid decently enough but for any large-scale work it just produces endless seas of structureless repetition. Even the long-in-the-tooth "just fire Perlin noise at varying levels of detail at the problem" at least produces some overarching structure even if it is itself just random because the low-frequency, high-amplitude components you use will produce some sort of higher-level variation.
Literally anything with any hierarchy in it would be better, unless you're really leaning into that SCP-esque, liminal-space creepiness. But if that isn't your explicit goal I would definitely not recommend this for large-scale usage because in most projects that creepy liminal-space-ness is probably actively fighting your artistic goals.
It wouldn't even take that much; lay down some sort of street network with some other algorithm, a bit of "zoning" to switch some tile sets between "residential" and some other zone or even just a couple different types of "residental", perlin noise it up if you've got no better ideas, then use "wave function collapse" (I really dislike the in-name-only "quantumness" of the name, can hardly call the algorithm that with a straight face) to fill in the blocks. A straightforward implementation of that would still be pretty same-y but it would at least have some sort of structure.
I was working some time ago on a 4X with an hexagonal map (not only made of hex tiles, but the overall shape was an hexagon rather than a rectangle, no wrap-around).
Using a noise function alone does not let you choose how many landmass you want to generate.
Using "wave function collapse"/constraint solvers is too slow for large maps when the amount of constraints increase (please don't put a mountain in the middle of the ocean, or a snow tile in the middle of a desert). My implementation took almost 8h to generate a single map, and the result was not even good.
In the end, I used a combination of multiple techniques:
- voronoi to split the map into regions
- use a noise function to make the regions boundaries a bit more natural
- fill the map with water tiles, place randomly some island seeds
- grow the islands from their seeds using a cellular automata
- to create continents, simply put a lot of island seeds in the same area, to generate a bigger one
- place mountains or rifts on region boundaries to simulate "tectonic plates"
- generate a heat map (influenced by position of the north/south poles and equator of the map), a humidity map (influenced by leftover ocean tiles), a height map (which is influenced by the already placed mountains/rifts) using a noise function
- using the previous heat/humidity/height maps, generate a wind map
- using the wind map, modify the humidity map (wind carries humidity over the land)
Then, choose randomly some tiles that fit some criteria to place biomes:
- desert on hot/dry land
- forest on temperate land
- swamp on temperate/wet land
- jungle on hot/wet land
- ...
Then a bunch of different cellular automata to grow the biomes naturally.
The result was quite nice, but it still wasn't on par to the map gen in Civilization games. I still want to continue this project, but I think in my heart I gave up.
EDIT: Some formatting because i always forget HN does not support markdown lists
I first came across Amit's page in middle school 20 years ago, and studied it religiously until I built a hexagonal grid with A* in Game Maker (which taught me programming from the ground up by studying Mark Overmars' amazing manual).
Today I'm directing an indie game with a team of 10 under me.
The code is not opensource but I've written a few articles about it:
- Part 1: https://david-delassus.medium.com/procedural-map-generation-in-c-part-1-the-slow-the-bad-and-the-ugly-4445fb15e43a?sk=2ff2c19dc5fe4c706092e83c79c72f56 (perlin noise, then wfc = fail)
- Part 2: https://david-delassus.medium.com/procedural-map-generation-in-c-part-2-a-new-hope-with-cellular-automata-and-gpt4-6b3b52c6b357?sk=96ab3bb234c28d9f5dc2dca8f2f19f97 (cellular automata, and let's try to use GPT to write the code = GPT is nice, but not perfect I had to refactor the code a lot)
- My own noise function: https://david-delassus.medium.com/i-made-my-own-noise-function-9e6ce4b95a9c?sk=26c5bdd7687445016216cc0b7cb10fa7
NB: Yes it's on medium, my bad :p The `sk` token in the URL is the friend link to bypass the paywall.
I think people went gaga over it due to the sample generations on the original repository (and the simplicity of implementation for arbitrary bitmaps), not so much the name.
https://github.com/mxgmn/WaveFunctionCollapse
As for global repetition, the original repo did have this to say, that selecting tiles is important.
"Note that the unrestrained knot tileset (with all 5 tiles being allowed) is not interesting for WFC, because you can't run into a situation where you can't place a tile. We call tilesets with this property "easy". Without special heuristics easy tilesets don't produce interesting global arrangements, because correlations of tiles in easy tilesets quickly fall off with a distance. "
Speaking for myself I can't say I remember "going ga ga" as such, but I was certainly intrigued when I first discovered it because it produces cool results with a form of machine learning that is under-utilised, based on combinatorial optimisation (at least the initial version as far as I remember extracts constraints automatically from an image, so it learns a model of how parts of the image can combine).
The "wave function collapse" name is ... a little grandiloquent, to be fair.
I personally haven't used it for procedural generation and I don't expect to but it has been used in at least two games I know of: Townscaper and Bad North. Combinatorial optimisation is not cheap but if it's good enough to generate game levels for simple games then it's not that bad.
(Bad North does take a bit of time to generate a level, to be fair).
> I have to say that as procedural generation algorithm I find it very lacking.
Per-pixel 2D generation like what's used in Caves of Qud produces stranger results which I like.
> I really dislike the in-name-only "quantumness" of the name, can hardly call the algorithm that with a straight face
It caught on because it portrays an air of sophistication (read: sophistry). There are no wave functions, it's a sudoku solver. I would also argue "sudoku solver" better conveys the underlying mechanics.
> I would also argue "sudoku solver" better conveys the underlying mechanics.
It really does. I glanced over the WFC algorithm and didn't really get it, but reading your comment that it's a "sudoku solver" helped click things into place in my head.
Ha ha, great comment! You're right, WFC's name just refers to quantum mechanics because it sounds cool, not because the algorithm has anything to do with physics, waves, or collapsing functions (it's more just a constraint based Sudoko solver). But I perceive it more as a playful buzzword for a useful algorithm, and not as maliciously deceptive like Deepak Chopra, who I was just commenting on recently (Quantum was cool until Deepak Chopra ruined it for everybody):
I do think it's useful combined with other techniques like procedural programming, cellular automata, Voronoi diagrams / jump flooding, noise, etc, to steer the higher and lower level structures. Check out Maxim Gumin's work on Markov Junior!
I think the really nice property of WFC is that it's very naturally and easily artist-driven. It doesn't require programming skills to use, you just supply it with a bunch of concrete before and after examples. (Like "Programming by Example".) That makes it much easier for a wide range of people to use, which is an important feature for democratizing custom world generation. Especially when you can construct or discover the examples in-world, and have it operate kind of like a 2-d tile or 3-d cube auto-complete, that looks at the rest of the stuff you've built or seen, like Canvas does with 1-d code.
Several years before it became fashionable to dismiss everything as a Makov chain.
Given a simple history can be mapped into a higher dimensional state, Markov chains are much more common than they first seem, so it's basically* always possible to dismiss any physically implementable system as "a Markov chain" if you're so inclined.
* While I wouldn't be surprised if someone has come up with laws of physics that can't be described by a Markov chain, mere quantum mechanics can.
Quantum mechanics can be described as a Markov chain? That seems plausible but I haven't worked with MCs enough to see exactly how. Could you please elaborate? It seems interesting.
Since people started using marketing tactics to promote themselves. WFC is a $100 name for a $1 concept. Other entries in the tech hall of shame are mersenne twister and dependency injection
>There are two main complaints from academic community concerning this work, the first one is about "reinventing and ignoring previous ideas", the second one is about "improper naming and popularizing", as shown in some debates in 2008 and 2015.[33] In particular, it was pointed out in a letter[34] to the editor of IEEE Transactions on Neural Networks that the idea of using a hidden layer connected to the inputs by random untrained weights was already suggested in the original papers on RBF networks in the late 1980s; Guang-Bin Huang replied by pointing out subtle differences.[35] In a 2015 paper,[1] Huang responded to complaints about his invention of the name ELM for already-existing methods, complaining of "very negative and unhelpful comments on ELM in neither academic nor professional manner due to various reasons and intentions" and an "irresponsible anonymous attack which intends to destroy harmony research environment", arguing that his work "provides a unifying learning platform" for various types of neural nets,[1] including hierarchical structured ELM.[28] In 2015, Huang also gave a formal rebuttal to what he considered as "malign and attack."[36] Recent research replaces the random weights with constrained random weights.[6][37]
But at least it's easier to say, rolls off the tongue smoothly, and makes better click bait for awesome blog postings!
I also love how the cool buzzwords "Reservoir Computing" and "Liquid State Machines" sounds like such deep stuff.
Yukio-Pegio Gunji, Yuta Nishiyama. Department of Earth and Planetary Sciences, Kobe University, Kobe 657-8501, Japan.
Andrew Adamatzky. Unconventional Computing Centre. University of the West of England, Bristol, United Kingdom.
Abstract
Soldier crabs Mictyris guinotae exhibit pronounced swarming behavior. Swarms of the crabs are tolerant of perturbations. In computer models and laboratory experiments we demonstrate that swarms of soldier crabs can implement logical gates when placed in a geometrically constrained environment.
The difference between Deepak Chopra's abuse of Quantum Physics terminology and WFC's is that WFC actually works and is useful for something, and its coiner publishes his results for free as open source software and papers, so he deserves more poetic license than a pretentious new-age shill hawking books and promises of immortality for cash like Deepak.
Here are some notes I wrote and links I found when researching WFC (which is admittedly a catchier name than "Variable State Independent Decaying Sum (VSIDS) branching heuristics in conflict-driven clause-learning (CDCL) Boolean satisfiability (SAT) solvers"):
Here are some notes I wrote and links I found when researching Wave
Function Collapse (WFC). -Don Hopkins
Wave Function Collapse
Maxim Gumin
Paul Merrell
https://paulmerrell.org/research/
https://paulmerrell.org/model-synthesis/
Liang et al
Jia Hui Liang, Vijay Ganesh, Ed Zulkoski, Atulan Zaman, and
Krzysztof Czarnecki. 2015. Understanding VSIDS branching heuristics
in conflict-driven clauselearning SAT solvers. In Haifa Verification
Conference. Springer, 225–241.
WaveFunctionCollapse is constraint solving in the wild
https://escholarship.org/content/qt1f29235t/qt1f29235t.pdf?t=qwp94i
Constraint Satisfaction Problem (CSP)
Machine Learning (ML)
Still a misnomer in my opinion, but I noticed that this part of the algorithm was missing from all the articles that followed (mine included). People are basically implementing sudoku solvers :)
It splits an image to cells by using convolutions, derives a set of constraints of how cells can be combined and then generates combinations that satisfy the constraints. It's a form of machine learning based on combinatorial optimisation, really.
Far as I can tell it doesn't apply any Markov assumptions anywhere, but I might just not have noticed it so please prove me wrong on that one.
> The next challenge is to come up with interesting gameplay ideas for this project.
The idea of an infinite world, at least of buildings and such structures, very much reminds me of the Echo game: https://www.youtube.com/watch?v=i51x6-8GqkA or maybe the Blame! manga or the SCP fandom. It's probably work pretty well for a horror/survival game, or just something built around movement. There was also the Receiver game series, which used pre-built environment blocks that were randomly stitched together and it worked really well for that game.
First time I shared my version of the wfc algorithm I got a lot of shit also (echoing the theme of the comments). People did not like it at all that it was not about quantum physics.
I feel like diffusion algorithms are going to make headway into the procedural generation space soon.
With WFC you can have your rules for how a city is credibly composed of certain tile selections at some scales. But I'm imagining a future where a game designer can prompt a diffusion model with something like 'generate a mid size industrial city with a classy commercial district in the north and abandoned factories in the west, using the pre supplied positions of important buildings."
A diffusion model could be trained on the structure and semantics of a real city.
Great take. Wave function collapse is like a Markov chain in terms of complexity. As we know there's plenty of opportunities to apply more sophisticated techniques. The downside of course is that more complex techniques often require orders of magnitude more data. while I believe there's technical room for growth, I'm not sure there's practical room for growth or at least it's harder to imagine outside of "cool tech demo".
This is neat! However, it is now longer the WFC algorithm. The idea of the WFC algorithm is that it is limited to one-at-a-time iteration, this mathematically means that every element in the input communicates its full "state" to the output.
The parallel tiling is neat, and the resulting cross-boundary replacements are neat as well, but they are in no way WFC, and as a result will lack a lot of the positive properties of the original algorithm! This is a kind of procedural generation now that does approach the properties of WFC in the limit as the number of chunks and comparisons goes to infinity.
It is a great way to scale an approximate/approximating WFC algorithm (and I'm a huge fan of the first post on this -- sent a video of results from it to someone just a month ago or so!), so it may end up being much more practical in use day-to-day due to the speed of chunk loading.
I do maintain that WFC looked a bit nicer and more natural due to the iterative collapse bit and the constraints out on it, it felt, very "cohesive". I feel like some of that has been lost in the speedier chunk-based algorithm (i.e. the entropy of the generations is much lower), but, this doesn't mean that it's not as useful or anything like that. Just a tradeoff for parallel computation (and I'd call it something like "approximate WFC" or "pre-baked approx WFC" or the like just for clarity's sake).
In any case, good work and I appreciate the problem solving skills and especially a lot of the hard problem solves like the heightmap differences and such. Very cool stuff and I'd love to see how this (and/or adjacent techniques) get incorporated into games at some point in the future! :)
That's not "infinite." It's a strictly finite construct that can be forced to repeat itself an arbitrary number of times. The only interesting question is the size of the repeating block. (Presumably quite small.)
This is sort of analogous to the Library of Babel -- a fictional construct which contains every possible combination of Latin characters that fit in a 400-page book. The library has something like 26^1312000 books, but then inevitably must repeat. Its contents are either not infinite, or each volume it contains repeats itself infinitely many times.
Ramsey Theory describes this stuff, and it's a useful thing to know, as it wards against sloppy use of "infinite" and "finite."
This is really interesting (to me who knows nothing about procedural generation). I keep thinking that game development (being the most obvious use case for this) is the ultimate playground for polymaths.
[...stuff about SandSpielStudio and block visual programming languages like Scratch and Snap!, Long Now talk between Will Wright and Brian Eno about Cellular Automata, etc ...]
The other really cool rabbit hole to explore for generating tiles and even arbitrary graph based content (I'm sold: hexagons are the bestagons!) is "Wave Function Collapse", which doesn't actually have anything to do with quantum mechanics (it just sounds cool), but is actually a kind of constraint solver related to sudoku solvers.
There's a way to define cellular automata rules by giving examples of the before and after patterns, and WFC is kind of like a statistical constraint solving version of that.
So it's really easy for artists to define rules just by drawing! Not even requiring any visual programming, but you can layer visual programming on top of it.
That's something that Alexander Repenning's "AgentSheets" supported (among other stuff): you could define cellular automata rules by before-and-after examples, wildcards and variables, and attach additional conditions and actions with a visual programming language.
AgentSheets and other cool systems are described in this classic paper: “A Taxonomy of Simulation Software: A work in progress” from Learning Technology Review by Kurt Schmucker at Apple. It covered many of my favorite systems.
Chaim Gingold wrote a comprehensive "Gadget Background Survey" at HARC, which includes AgentSheets, Alan Kay's favorites: Rockey’s Boots and Robot Odyssey, and Chaim's amazing SimCity Reverse Diagrams and lots of great stuff I’d never seen before:
Chaim Gingold has analyzed the SimCity (classic) code and visually documented how it works, in his beautiful "SimCity Reverse Diagrams":
>SimCity reverse diagrams: Chaim Gingold (2016).
>These reverse diagrams map and translate the rules of a complex simulation program into a form that is more easily digested, embedded, disseminated, and and discussed (Latour 1986).
>The technique is inspired by the game designer Stone Librande’s one page game design documents (Librande 2010). If we merge the reverse diagram with an interactive approach—e.g. Bret Victor’s Nile Visualization (Victor 2013), such diagrams could be used generatively, to describe programs, and interactively, to allow rich introspection and manipulation of software.
>Latour, Bruno (1986). “Visualization and cognition”. In: Knowledge and Society 6 (1986), pp. 1– 40. Librande, Stone (2010). “One-Page Designs”. Game Developers Conference. 2010. Victor, Bret (2013). “Media for Thinking the Unthinkable”. MIT Media Lab, Apr. 4, 2013.
[... stuff about AgentSheets, KidSim, Lex Fridman interviews of Michael Levin and Steven Wolfram discussing Cellular Automata, CAM6 simulator, etc ...]
Oops, sorry: the best url was broken! Chaim also recently published a book on the history of SimCity which includes these diagrams and deep dive explanations of how cellular automata and SimCity work, and discussed it on HN:
I think proc gen like this often falls victim to the 1000 bowls of oatmeal problem.
Unless things _feel_ different, it just feels same-y.
Some games handle this well (often through biomes with different rules and/or special areas with different rules) and others (interestingly, often those that talk about how many billions of possibilities there are) are techniquely different... But just all feel the same.
It's interesting to see how game devs continue to be creative in this area and how many games continue to have this problem.
People seem to go ga-ga over this algorithm with some frequency on HN, and I think it is only because of its in-name-only connection to quantum mechanics, because I have to say that as procedural generation algorithm I find it very lacking. It works on the cases I saw for something like a 10x10 grid decently enough but for any large-scale work it just produces endless seas of structureless repetition. Even the long-in-the-tooth "just fire Perlin noise at varying levels of detail at the problem" at least produces some overarching structure even if it is itself just random because the low-frequency, high-amplitude components you use will produce some sort of higher-level variation.
Literally anything with any hierarchy in it would be better, unless you're really leaning into that SCP-esque, liminal-space creepiness. But if that isn't your explicit goal I would definitely not recommend this for large-scale usage because in most projects that creepy liminal-space-ness is probably actively fighting your artistic goals.
It wouldn't even take that much; lay down some sort of street network with some other algorithm, a bit of "zoning" to switch some tile sets between "residential" and some other zone or even just a couple different types of "residental", perlin noise it up if you've got no better ideas, then use "wave function collapse" (I really dislike the in-name-only "quantumness" of the name, can hardly call the algorithm that with a straight face) to fill in the blocks. A straightforward implementation of that would still be pretty same-y but it would at least have some sort of structure.
I was working some time ago on a 4X with an hexagonal map (not only made of hex tiles, but the overall shape was an hexagon rather than a rectangle, no wrap-around).
Using a noise function alone does not let you choose how many landmass you want to generate.
Using "wave function collapse"/constraint solvers is too slow for large maps when the amount of constraints increase (please don't put a mountain in the middle of the ocean, or a snow tile in the middle of a desert). My implementation took almost 8h to generate a single map, and the result was not even good.
In the end, I used a combination of multiple techniques:
Then, choose randomly some tiles that fit some criteria to place biomes: Then a bunch of different cellular automata to grow the biomes naturally.The result was quite nice, but it still wasn't on par to the map gen in Civilization games. I still want to continue this project, but I think in my heart I gave up.
EDIT: Some formatting because i always forget HN does not support markdown lists
> but it still wasn't on par to the map gen in Civilization games.
Which makes me wonder... do we know how map gen in Civilization works so well?
"You know, Hexagons are the Bestagons!"
https://www.youtube.com/watch?v=thOifuHs6eY
This is pretty cool! As someone with virtually no experience in this area I’d love to read the source code, is it open source?
A fantastic resource for this kind of generation is here:
http://www-cs-students.stanford.edu/~amitp/game-programming/...
This really brought me back.
I first came across Amit's page in middle school 20 years ago, and studied it religiously until I built a hexagonal grid with A* in Game Maker (which taught me programming from the ground up by studying Mark Overmars' amazing manual).
Today I'm directing an indie game with a team of 10 under me.
The code is not opensource but I've written a few articles about it:
NB: Yes it's on medium, my bad :p The `sk` token in the URL is the friend link to bypass the paywall.Thank you!
I think people went gaga over it due to the sample generations on the original repository (and the simplicity of implementation for arbitrary bitmaps), not so much the name. https://github.com/mxgmn/WaveFunctionCollapse
As for global repetition, the original repo did have this to say, that selecting tiles is important. "Note that the unrestrained knot tileset (with all 5 tiles being allowed) is not interesting for WFC, because you can't run into a situation where you can't place a tile. We call tilesets with this property "easy". Without special heuristics easy tilesets don't produce interesting global arrangements, because correlations of tiles in easy tilesets quickly fall off with a distance. "
Speaking for myself I can't say I remember "going ga ga" as such, but I was certainly intrigued when I first discovered it because it produces cool results with a form of machine learning that is under-utilised, based on combinatorial optimisation (at least the initial version as far as I remember extracts constraints automatically from an image, so it learns a model of how parts of the image can combine).
The "wave function collapse" name is ... a little grandiloquent, to be fair.
I personally haven't used it for procedural generation and I don't expect to but it has been used in at least two games I know of: Townscaper and Bad North. Combinatorial optimisation is not cheap but if it's good enough to generate game levels for simple games then it's not that bad.
(Bad North does take a bit of time to generate a level, to be fair).
> I have to say that as procedural generation algorithm I find it very lacking.
Per-pixel 2D generation like what's used in Caves of Qud produces stranger results which I like.
> I really dislike the in-name-only "quantumness" of the name, can hardly call the algorithm that with a straight face
It caught on because it portrays an air of sophistication (read: sophistry). There are no wave functions, it's a sudoku solver. I would also argue "sudoku solver" better conveys the underlying mechanics.
> I would also argue "sudoku solver" better conveys the underlying mechanics.
It really does. I glanced over the WFC algorithm and didn't really get it, but reading your comment that it's a "sudoku solver" helped click things into place in my head.
Ha ha, great comment! You're right, WFC's name just refers to quantum mechanics because it sounds cool, not because the algorithm has anything to do with physics, waves, or collapsing functions (it's more just a constraint based Sudoko solver). But I perceive it more as a playful buzzword for a useful algorithm, and not as maliciously deceptive like Deepak Chopra, who I was just commenting on recently (Quantum was cool until Deepak Chopra ruined it for everybody):
https://news.ycombinator.com/item?id=42714477
I do think it's useful combined with other techniques like procedural programming, cellular automata, Voronoi diagrams / jump flooding, noise, etc, to steer the higher and lower level structures. Check out Maxim Gumin's work on Markov Junior!
https://twitter.com/ExUtumno/status/1531992699997507586
Maxim Gumin @ExUtumno: I published a new project about combining rewrite rules and solving constraint problems made of rewrite rules
https://github.com/mxgmn/MarkovJunior
I think the really nice property of WFC is that it's very naturally and easily artist-driven. It doesn't require programming skills to use, you just supply it with a bunch of concrete before and after examples. (Like "Programming by Example".) That makes it much easier for a wide range of people to use, which is an important feature for democratizing custom world generation. Especially when you can construct or discover the examples in-world, and have it operate kind of like a 2-d tile or 3-d cube auto-complete, that looks at the rest of the stuff you've built or seen, like Canvas does with 1-d code.
When did we start calling markov chains 'wave function collapse'?
Several years before it became fashionable to dismiss everything as a Makov chain.
Given a simple history can be mapped into a higher dimensional state, Markov chains are much more common than they first seem, so it's basically* always possible to dismiss any physically implementable system as "a Markov chain" if you're so inclined.
* While I wouldn't be surprised if someone has come up with laws of physics that can't be described by a Markov chain, mere quantum mechanics can.
Quantum mechanics can be described as a Markov chain? That seems plausible but I haven't worked with MCs enough to see exactly how. Could you please elaborate? It seems interesting.
Why would analyzing something as Markov chain be dismissing it? Perhaps its Markov chains that are being dismissed?
The comment I am replying to looks like a dismissal, and does not look like an analysis.
Since people started using marketing tactics to promote themselves. WFC is a $100 name for a $1 concept. Other entries in the tech hall of shame are mersenne twister and dependency injection
Like calling random vector functional link networks and single-layer feed-forward networks with random hidden weight an "Extreme Learning Machine".
https://en.wikipedia.org/wiki/Extreme_learning_machine#Contr...
>Controversy
>There are two main complaints from academic community concerning this work, the first one is about "reinventing and ignoring previous ideas", the second one is about "improper naming and popularizing", as shown in some debates in 2008 and 2015.[33] In particular, it was pointed out in a letter[34] to the editor of IEEE Transactions on Neural Networks that the idea of using a hidden layer connected to the inputs by random untrained weights was already suggested in the original papers on RBF networks in the late 1980s; Guang-Bin Huang replied by pointing out subtle differences.[35] In a 2015 paper,[1] Huang responded to complaints about his invention of the name ELM for already-existing methods, complaining of "very negative and unhelpful comments on ELM in neither academic nor professional manner due to various reasons and intentions" and an "irresponsible anonymous attack which intends to destroy harmony research environment", arguing that his work "provides a unifying learning platform" for various types of neural nets,[1] including hierarchical structured ELM.[28] In 2015, Huang also gave a formal rebuttal to what he considered as "malign and attack."[36] Recent research replaces the random weights with constrained random weights.[6][37]
But at least it's easier to say, rolls off the tongue smoothly, and makes better click bait for awesome blog postings!
I also love how the cool buzzwords "Reservoir Computing" and "Liquid State Machines" sounds like such deep stuff.
https://news.ycombinator.com/item?id=40903302
>"I'll tell you why it's not a scam, in my opinion: Tide goes in, tide goes out, never a miscommunication." -Bill O'Reilly
How about rebranding WFC as "Extreme Liquid Quantum Sudoko Machines"? ;)
Then there's "Crab Computing"!
https://news.ycombinator.com/item?id=42701560
[...] If billiard balls aren't creepy enough for you, live soldier crabs of the species Mictyris guinotae can be used in place of the billiard balls.
https://www.newscientist.com/blogs/onepercent/2012/04/resear...
https://www.wired.com/2012/04/soldier-crabs/
http://www.complex-systems.com/abstracts/v20_i02_a02.html
Robust Soldier Crab Ball Gate
Yukio-Pegio Gunji, Yuta Nishiyama. Department of Earth and Planetary Sciences, Kobe University, Kobe 657-8501, Japan.
Andrew Adamatzky. Unconventional Computing Centre. University of the West of England, Bristol, United Kingdom.
Abstract
Soldier crabs Mictyris guinotae exhibit pronounced swarming behavior. Swarms of the crabs are tolerant of perturbations. In computer models and laboratory experiments we demonstrate that swarms of soldier crabs can implement logical gates when placed in a geometrically constrained environment.
https://www.futilitycloset.com/2017/02/26/crab-computing/
What would be a better name?
Constraint-based tiling maybe?
WFC in particular wasn't even new. The exact same thing was published by someone else before. I don't know if he gave it a name though
The difference between Deepak Chopra's abuse of Quantum Physics terminology and WFC's is that WFC actually works and is useful for something, and its coiner publishes his results for free as open source software and papers, so he deserves more poetic license than a pretentious new-age shill hawking books and promises of immortality for cash like Deepak.
Here are some notes I wrote and links I found when researching WFC (which is admittedly a catchier name than "Variable State Independent Decaying Sum (VSIDS) branching heuristics in conflict-driven clause-learning (CDCL) Boolean satisfiability (SAT) solvers"):
https://donhopkins.com/home/wfc-notes.txt
[...lots more stuff...]The "wave function collapse" part comes from the original algorithm which inferred the constraints from a sample image : https://github.com/mxgmn/WaveFunctionCollapse
Still a misnomer in my opinion, but I noticed that this part of the algorithm was missing from all the articles that followed (mine included). People are basically implementing sudoku solvers :)
AFAIU WFC is not a Markov chain. See here:
https://escholarship.org/uc/item/1fb9k44q
It splits an image to cells by using convolutions, derives a set of constraints of how cells can be combined and then generates combinations that satisfy the constraints. It's a form of machine learning based on combinatorial optimisation, really.
Far as I can tell it doesn't apply any Markov assumptions anywhere, but I might just not have noticed it so please prove me wrong on that one.
> The next challenge is to come up with interesting gameplay ideas for this project.
The idea of an infinite world, at least of buildings and such structures, very much reminds me of the Echo game: https://www.youtube.com/watch?v=i51x6-8GqkA or maybe the Blame! manga or the SCP fandom. It's probably work pretty well for a horror/survival game, or just something built around movement. There was also the Receiver game series, which used pre-built environment blocks that were randomly stitched together and it worked really well for that game.
Yeah I was thinking parkour + zombie escape might be fun
First time I shared my version of the wfc algorithm I got a lot of shit also (echoing the theme of the comments). People did not like it at all that it was not about quantum physics.
Here's mine if anyone is interested https://github.com/victorqribeiro/simpleWFC
I feel like diffusion algorithms are going to make headway into the procedural generation space soon.
With WFC you can have your rules for how a city is credibly composed of certain tile selections at some scales. But I'm imagining a future where a game designer can prompt a diffusion model with something like 'generate a mid size industrial city with a classy commercial district in the north and abandoned factories in the west, using the pre supplied positions of important buildings."
A diffusion model could be trained on the structure and semantics of a real city.
Great take. Wave function collapse is like a Markov chain in terms of complexity. As we know there's plenty of opportunities to apply more sophisticated techniques. The downside of course is that more complex techniques often require orders of magnitude more data. while I believe there's technical room for growth, I'm not sure there's practical room for growth or at least it's harder to imagine outside of "cool tech demo".
This is neat! However, it is now longer the WFC algorithm. The idea of the WFC algorithm is that it is limited to one-at-a-time iteration, this mathematically means that every element in the input communicates its full "state" to the output.
The parallel tiling is neat, and the resulting cross-boundary replacements are neat as well, but they are in no way WFC, and as a result will lack a lot of the positive properties of the original algorithm! This is a kind of procedural generation now that does approach the properties of WFC in the limit as the number of chunks and comparisons goes to infinity.
It is a great way to scale an approximate/approximating WFC algorithm (and I'm a huge fan of the first post on this -- sent a video of results from it to someone just a month ago or so!), so it may end up being much more practical in use day-to-day due to the speed of chunk loading.
I do maintain that WFC looked a bit nicer and more natural due to the iterative collapse bit and the constraints out on it, it felt, very "cohesive". I feel like some of that has been lost in the speedier chunk-based algorithm (i.e. the entropy of the generations is much lower), but, this doesn't mean that it's not as useful or anything like that. Just a tradeoff for parallel computation (and I'd call it something like "approximate WFC" or "pre-baked approx WFC" or the like just for clarity's sake).
In any case, good work and I appreciate the problem solving skills and especially a lot of the hard problem solves like the heightmap differences and such. Very cool stuff and I'd love to see how this (and/or adjacent techniques) get incorporated into games at some point in the future! :)
That's not "infinite." It's a strictly finite construct that can be forced to repeat itself an arbitrary number of times. The only interesting question is the size of the repeating block. (Presumably quite small.)
This is sort of analogous to the Library of Babel -- a fictional construct which contains every possible combination of Latin characters that fit in a 400-page book. The library has something like 26^1312000 books, but then inevitably must repeat. Its contents are either not infinite, or each volume it contains repeats itself infinitely many times.
Ramsey Theory describes this stuff, and it's a useful thing to know, as it wards against sloppy use of "infinite" and "finite."
This is really interesting (to me who knows nothing about procedural generation). I keep thinking that game development (being the most obvious use case for this) is the ultimate playground for polymaths.
https://news.ycombinator.com/item?id=37485705
DonHopkins on Sept 12, 2023 | parent | context | favorite | on: CityDreamer: Compositional Generative Model of Unb...
Here's some comments and links about Wave Function Collapse I wrote recently:
https://news.ycombinator.com/item?id=34561910
[...stuff about SandSpielStudio and block visual programming languages like Scratch and Snap!, Long Now talk between Will Wright and Brian Eno about Cellular Automata, etc ...]
The other really cool rabbit hole to explore for generating tiles and even arbitrary graph based content (I'm sold: hexagons are the bestagons!) is "Wave Function Collapse", which doesn't actually have anything to do with quantum mechanics (it just sounds cool), but is actually a kind of constraint solver related to sudoku solvers.
https://escholarship.org/content/qt3rm1w0mn/qt3rm1w0mn_noSpl...
Maxim Gumin's work:
https://github.com/mxgmn/WaveFunctionCollapse
Paul Merrell's work:
https://paulmerrell.org/model-synthesis/
https://paulmerrell.org/research/
Oskar Stålberg's work:
https://twitter.com/OskSta/status/784847588893814785
https://oskarstalberg.com/game/wave/wave.html
There's a way to define cellular automata rules by giving examples of the before and after patterns, and WFC is kind of like a statistical constraint solving version of that.
So it's really easy for artists to define rules just by drawing! Not even requiring any visual programming, but you can layer visual programming on top of it.
That's something that Alexander Repenning's "AgentSheets" supported (among other stuff): you could define cellular automata rules by before-and-after examples, wildcards and variables, and attach additional conditions and actions with a visual programming language.
AgentSheets and other cool systems are described in this classic paper: “A Taxonomy of Simulation Software: A work in progress” from Learning Technology Review by Kurt Schmucker at Apple. It covered many of my favorite systems.
http://donhopkins.com/home/documents/taxonomy.pdf
Chaim Gingold wrote a comprehensive "Gadget Background Survey" at HARC, which includes AgentSheets, Alan Kay's favorites: Rockey’s Boots and Robot Odyssey, and Chaim's amazing SimCity Reverse Diagrams and lots of great stuff I’d never seen before:
http://chaim.io/download/Gingold%20(2017)%20Gadget%20(1)%20S...
Chaim Gingold has analyzed the SimCity (classic) code and visually documented how it works, in his beautiful "SimCity Reverse Diagrams":
>SimCity reverse diagrams: Chaim Gingold (2016).
>These reverse diagrams map and translate the rules of a complex simulation program into a form that is more easily digested, embedded, disseminated, and and discussed (Latour 1986).
>The technique is inspired by the game designer Stone Librande’s one page game design documents (Librande 2010). If we merge the reverse diagram with an interactive approach—e.g. Bret Victor’s Nile Visualization (Victor 2013), such diagrams could be used generatively, to describe programs, and interactively, to allow rich introspection and manipulation of software.
>Latour, Bruno (1986). “Visualization and cognition”. In: Knowledge and Society 6 (1986), pp. 1– 40. Librande, Stone (2010). “One-Page Designs”. Game Developers Conference. 2010. Victor, Bret (2013). “Media for Thinking the Unthinkable”. MIT Media Lab, Apr. 4, 2013.
https://lively-web.org/users/Dan/uploads/SimCityReverseDiagr
[... stuff about AgentSheets, KidSim, Lex Fridman interviews of Michael Levin and Steven Wolfram discussing Cellular Automata, CAM6 simulator, etc ...]
More:
https://news.ycombinator.com/item?id=34561910
Oops, sorry: the best url was broken! Chaim also recently published a book on the history of SimCity which includes these diagrams and deep dive explanations of how cellular automata and SimCity work, and discussed it on HN:
SimCity Reverse Diagrams:
https://smalltalkzoo.thechm.org/users/Dan/uploads/SimCityRev...
Building SimCity discussion on HN with Chaim Gingold:
https://news.ycombinator.com/item?id=40698442
Building SimCity: How to Put the World in a Machine
https://mitpress.mit.edu/9780262547482/building-simcity/
(2023)
The universe is lazily evaluated.