6 ms·

Generating an infinite world with the Wave Function Collapse algorithm

278 points by klaussilveira 2y ago

Footnote7341 2y ago
When did we start calling markov chains 'wave function collapse'?
- linkdd 2y ago
  The "wave function collapse" part comes from the original algorithm which inferred the constraints from a sample image : https://github.com/mxgmn/WaveFunctionCollapse 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 :)
- on_the_train 2y ago
  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
  - rererereferred 2y ago
    What would be a better name?
    - on_the_train 2y ago
      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
      - DonHopkins 2y ago
        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 https://donhopkins.com/home/wfc-notes.txt 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) [...lots more stuff...]
    - dkersten 2y ago
      Constraint-based tiling maybe?
      - erikig 2y ago
        Permutation City with a nod to Egan?
  - DonHopkins 2y ago
    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#Controversy 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 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 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/researchers-build-crab-powered.html https://www.newscientist.com/blogs/onepercent/2012/04/resear... https://www.wired.com/2012/04/soldier-crabs/ https://www.wired.com/2012/04/soldier-crabs/ http://www.complex-systems.com/abstracts/v20_i02_a02.html 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/ https://www.futilitycloset.com/2017/02/26/crab-computing/
- ben_w 2y ago
  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.
  - jampekka 2y ago
    Why would analyzing something as Markov chain be dismissing it? Perhaps its Markov chains that are being dismissed?
    - ben_w 2y ago
      The comment I am replying to looks like a dismissal, and does not look like an analysis.
  - wasabi991011 2y ago
    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.
    - zeofig 2y ago
      A Markov process is a random process where the new state only depends on the old state, not anything else. This can be stretched to include almost anything, since you can expand the definition of the state to record history or whatever you want, although you may make the process much more difficult to work with mathematically. In other words, the fact that something may be a Markov process is generally not interesting, because it is a very broad definition, and doesn't guarantee any interesting properties without further assumptions. The wavefunction in QM doesn't evolve randomly, so I would say it is not technically a Markov process. On the other hand you can create a theory of observables derived from QM that is "random" (depending on your interpretation of quantum mechanics).
- YeGoblynQueenne 2y ago
  AFAIU WFC is not a Markov chain. See here: https://escholarship.org/uc/item/1fb9k44q 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.
jerf 2y ago
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.
- linkdd 2y ago
  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
tbalsam 2y ago
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! :)
- exDM69 2y ago
  If I understood the algorithm correctly, it is using the standard WFC algorithm to generate blocks that match a constraint. Then it creates a tiling of those blocks, and substitutes parts of the tiling with new blocks generated using WFC. So it's a higher level algorithm, using WFC as its building block.
  - tbalsam 2y ago
    Yes, this is the principle that violates the WFC algorithm and makes it no longer WFC It is now just a procedural algorithm, which is faster than but loses some of the magic of what makes WFC _so good_. You can tell by looking at the renders too, the before-and-after of both methods. The difference is incomparable. That being said, it is cool as a runtime-optimized non-WFC WFC-approximating algorithm.
jebarker 2y ago
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.
atum47 2y ago
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 https://github.com/victorqribeiro/simpleWFC
- evanb 2y ago
  > People did not like it at all that it was not about quantum physics. As a physicist: You would not believe how annoying it can be to find good information about actual quantum physics. It's not just WFC, people love to name stuff after physics stuff. When the electron framework came out I braced myself, knowing that lots of regular internet searches were about to become more inconvenient.
  - _yb2s 2y ago
    In general, I hate how tech things reuse regular words. Usually it seems like no big deal at first because it’s a niche thing for a few nerds, but now that tech is “eating the world” it is actually damaging language. I heard a spoken ad on the radio the other day warning people about the dangers of phishing with absolutely zero context to clarify that they weren’t talking about fishing. I felt sad to realize that is now the dominant meaning of the word. I write a lot of open source software, and always take the time to think of a new name, usually some type of portmanteau rather than just calling it something like “java” or “python.”
  - nico 2y ago
    > people love to name stuff after physics stuff And physics love taking over natural language So many words have been co-opted by physics, that it’s almost impossible to have a good conversation about physical concepts between a lay person and someone trained in physics Any time a lay person uses any physics keyword, they get judged as ignorant and mostly dismissed
KronisLV 2y ago
> 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 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.
- malux85 2y ago
  Yeah I was thinking parkour + zombie escape might be fun
DonHopkins 2y ago
https://news.ycombinator.com/item?id=37485705 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 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_noSplash_f68c38783c93e2a50047925fa9471286.pdf?t=qwgn02 https://escholarship.org/content/qt3rm1w0mn/qt3rm1w0mn_noSpl... Maxim Gumin's work: https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse Paul Merrell's work: https://paulmerrell.org/model-synthesis/ https://paulmerrell.org/model-synthesis/ https://paulmerrell.org/research/ https://paulmerrell.org/research/ Oskar Stålberg's work: https://twitter.com/OskSta/status/784847588893814785 https://twitter.com/OskSta/status/784847588893814785 https://oskarstalberg.com/game/wave/wave.html 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 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)%20Survey.pdf 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 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 https://news.ycombinator.com/item?id=34561910
Nihilartikel 2y ago
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.
- kelseyfrog 2y ago
  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".
tjpnz 2y ago
The universe is lazily evaluated.
- yarg 2y ago
  It's beyond that. There's information required to evaluate the current state that is currently unavailable - meaning that the current state of things will not be defined until the future.
  - Mobleysoft 2y ago
    Elaborate...
flobosg 2y ago
(2023)
A_D_E_P_T 2y ago
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."
jasonjmcghee 2y ago
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.
- feoren 2y ago
  Any game that wants a ton of content has this problem. The many caves in Skyrim start to feel the same after a while. You can often recognize the same assets over and over in very content-rich games. The total number of assets used in the article is tiny compared to what a production game would have. Procedural generation can't be used as an excuse to do less work, or it just feels same-y. A game is still a ton of work; it's just different work for different goals with procedural generation. Generating a huge world is boring if you don't have interesting objects to put in that world. Interesting objects are meaningless unless they're connected to a story. Minecraft works because it's a sandbox for you to invent your own stories, so the infinite world ends up getting filled by the player. If any element feels repetitive, the whole game will. If you wanted a fully procedural game, you need to figure out how to procedurally generate all the different aspects: story, characters, enemies, places, objects. It's more work to do that well than to make a traditional game. So people going into procedural generation thinking it'll save them work are already destined to fail.
  - dualogy 2y ago
    Agree overall, and yet, and yet.. > Procedural generation can't be used as an excuse to do less work > So people going into procedural generation thinking it'll save them work are already destined to fail Consider the possibility that nobody really picks up proc-gen in the hopes they can laze out a RDR3 or such over the weekend. Another thing is, this applies to indies and AAAs alike: while a big world has to have interesting unique things in it, by definition not every square meter can/should be chockful of another "interesting truly unique thing" because if the whole world is filled like that, it's just another kind of sameyness in that the novelty factor would wear out just as quickly once you're getting that there truly is true novelty in absolutely every little square meter, which kills the novelty sensation in a heartbeat. Novelty delights us in a backdrop of routineness, sameyness, same-old-same-old-ness. So in between interesting things, the thusly necessary slightly-"duller" in-between areas are to pace and prep and make one anticipate novelty "hopefully almost just around the corner". Ideally it's so spaced to appear just in time before the player resigns such hopes. And so if you're going to have slightly-duller "filler areas" (and let me posit that any real-world say forest (in a biome one has traversed before), without the physical air and smells and winds (or friends/pets stringing along) is quickly "proc-gen dull-ish" within minutes — even in reality — or call it "meditative"/calming) — so again, if you're going to have slightly-duller "filler areas" just to connect and space apart the unique content things to good effect, then procedural placements/scatterings/variations are going to beat manual placement not just in "effort time" but because manual would swiftly look much more repetetive (being inevitably eventually effectively copy-paste driven) given the scale of environments under discussion, even if it would not take a human months of menial clickery. Rockstar gets it right imho but their approach would also get your "many caves in Skyrim" right because they manifest little novel uniquenesses not in scattered objects or env textures/models but via lively interactive interludes, whether it's animals frolicking or chasing each other or attacking towards you or "random stranger" incidents etc. That's the right kind of "filler but not boring", nobody cares about the variety of the rocks, only noticing them if nothing seems to be happening.
RobM71 2y ago
[dead]
mrtracy 2y ago
I work with this algorithm quite a bit in a personal project. (I've changed from calling it WFC to Model Synthesis; Paul Merrell earned the naming rights, unless we discover an even earlier description.) I mentally divide it into two important components: 1. Cross-correlation (the 'wave function') 2. Label selection (choosing where the 'collapse' occurs) The "cross-correlation" is exactly what it sounds like - given an incomplete model and a set of example patterns, this data structure represents the cross-correlation of every place that any of the patterns would individually fit in the incomplete model. I think this is the most useful structure in the algorithm, and is a form of iterative 'feature detection' over the incomplete model. I think there are many interesting things which can be done with this which aren't in the basic algorithm, such as: - Having larger indivisible 'patterns' and collapsing such patterns all at once. Although example patterns are always broken down into discrete cells, larger patterns can exist where each cell gets a unique label and very limited transition set. The cross-correlation will detect where they can be placed, and if one is chosen the entire pattern could be chosen at once. - Partial seeding of labels, e.g. selecting portions of the incomplete model and artificially limiting the available labels in that area, without collapsing it. - Addition of information to labels which aren't easily expressed in an example pattern, such as rudimentary counting of distances. The 'label selection' portion (in WFC terms, this is the algorithm used to choose which space to 'collapse') is where all of the random generation comes into play. If using Model Synthesis for full world generation, this is what should be focused on for generating more interesting types of environments. However, given the common label selection algorithms I've seen and used, I think that Model Synthesis excels mostly at adding small-scale, largely self-similar patterns onto constraints provided by a larger structure. I think that other proc-gen methods better lend themselves to generating large-scale structures. A combination of the two - generating a large-scale structure to serve as a constraint, and allowing model synthesis to fill in interesting detail - seems like a good path to explore.
- mistercow 2y ago
  > Partial seeding of labels, e.g. selecting portions of the incomplete model and artificially limiting the available labels in that area, without collapsing it. It seems like you if you had this, you could do some really interesting things with multi-scale collapse. For example, you could first use collapse to lay out biomes (e.g. beach needs to border sea, desert needs to border mountains, etc.) and then use those as constraints for the next scale level, which decides the details within those biomes, and the next level for cities and towns within those environments, etc.
andsoitis 2y ago
Are these the foundations for us, one day, to procedurally generate an entire universe in which other conscious beings appear?
steveoscaro 2y ago
Someone smarter than me please tie this into the many worlds theory of the universe and collapsing wave functions.
jb_briant 2y ago
I wanted to generate a procedural dungeon for a rogue like aspect of my game using WFC. It was a misunderstanding of what this very simplistic algo can do. - it's great to fill areas with kinda non repetitive patterns which feels random-ish - it's useless to build anything structured. Eg. You can't guarantee that a path exists from the entrance of the dungeon and the exit/goal. I ended up doing it fully with traditional Procgen techniques, I'm easily at 100+ hours of work and it's still only half of it. Discussions about "the problem of proc gen" in games are missing the point. Procgen is a non-gameplay feature, and it's very time consuming to get it right and controlled. The legend that you "gain" time is hilarious when you know how complicated things become with "random generation". Proc gen is a fantastic tool to bring diversity to non-interesting zones. The game is in the point of interests, they host goals, challenges, (storyline), progression. All of that is directed by logic.
rbanffy 2y ago
> The next challenge is to come up with interesting gameplay ideas for this project Making it an open universe game would make sense. Or a screen saver inspired on Apple’s Aerials. I’ve been wanting a No Man’s Sky one for my AppleTV since ever.

278 points by klaussilveira 2y ago

Footnote7341 2y ago

When did we start calling markov chains 'wave function collapse'?

linkdd 2y ago
The "wave function collapse" part comes from the original algorithm which inferred the constraints from a sample image : https://github.com/mxgmn/WaveFunctionCollapse 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 :)
on_the_train 2y ago
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
- rererereferred 2y ago
  What would be a better name?
  - on_the_train 2y ago
    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
    - DonHopkins 2y ago
      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 https://donhopkins.com/home/wfc-notes.txt 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) [...lots more stuff...]
  - dkersten 2y ago
    Constraint-based tiling maybe?
    - erikig 2y ago
      Permutation City with a nod to Egan?
- DonHopkins 2y ago
  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#Controversy 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 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 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/researchers-build-crab-powered.html https://www.newscientist.com/blogs/onepercent/2012/04/resear... https://www.wired.com/2012/04/soldier-crabs/ https://www.wired.com/2012/04/soldier-crabs/ http://www.complex-systems.com/abstracts/v20_i02_a02.html 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/ https://www.futilitycloset.com/2017/02/26/crab-computing/
ben_w 2y ago
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.
- jampekka 2y ago
  Why would analyzing something as Markov chain be dismissing it? Perhaps its Markov chains that are being dismissed?
  - ben_w 2y ago
    The comment I am replying to looks like a dismissal, and does not look like an analysis.
- wasabi991011 2y ago
  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.
  - zeofig 2y ago
    A Markov process is a random process where the new state only depends on the old state, not anything else. This can be stretched to include almost anything, since you can expand the definition of the state to record history or whatever you want, although you may make the process much more difficult to work with mathematically. In other words, the fact that something may be a Markov process is generally not interesting, because it is a very broad definition, and doesn't guarantee any interesting properties without further assumptions. The wavefunction in QM doesn't evolve randomly, so I would say it is not technically a Markov process. On the other hand you can create a theory of observables derived from QM that is "random" (depending on your interpretation of quantum mechanics).
YeGoblynQueenne 2y ago
AFAIU WFC is not a Markov chain. See here: https://escholarship.org/uc/item/1fb9k44q 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.

jerf 2y ago

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.

linkdd 2y ago
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

tbalsam 2y ago

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! :)

exDM69 2y ago
If I understood the algorithm correctly, it is using the standard WFC algorithm to generate blocks that match a constraint. Then it creates a tiling of those blocks, and substitutes parts of the tiling with new blocks generated using WFC. So it's a higher level algorithm, using WFC as its building block.
- tbalsam 2y ago
  Yes, this is the principle that violates the WFC algorithm and makes it no longer WFC It is now just a procedural algorithm, which is faster than but loses some of the magic of what makes WFC _so good_. You can tell by looking at the renders too, the before-and-after of both methods. The difference is incomparable. That being said, it is cool as a runtime-optimized non-WFC WFC-approximating algorithm.

jebarker 2y ago

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.

atum47 2y ago

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 https://github.com/victorqribeiro/simpleWFC

evanb 2y ago
> People did not like it at all that it was not about quantum physics. As a physicist: You would not believe how annoying it can be to find good information about actual quantum physics. It's not just WFC, people love to name stuff after physics stuff. When the electron framework came out I braced myself, knowing that lots of regular internet searches were about to become more inconvenient.
- _yb2s 2y ago
  In general, I hate how tech things reuse regular words. Usually it seems like no big deal at first because it’s a niche thing for a few nerds, but now that tech is “eating the world” it is actually damaging language. I heard a spoken ad on the radio the other day warning people about the dangers of phishing with absolutely zero context to clarify that they weren’t talking about fishing. I felt sad to realize that is now the dominant meaning of the word. I write a lot of open source software, and always take the time to think of a new name, usually some type of portmanteau rather than just calling it something like “java” or “python.”
- nico 2y ago
  > people love to name stuff after physics stuff And physics love taking over natural language So many words have been co-opted by physics, that it’s almost impossible to have a good conversation about physical concepts between a lay person and someone trained in physics Any time a lay person uses any physics keyword, they get judged as ignorant and mostly dismissed

KronisLV 2y ago

> 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 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.

malux85 2y ago
Yeah I was thinking parkour + zombie escape might be fun

DonHopkins 2y ago

https://news.ycombinator.com/item?id=37485705 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 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_noSplash_f68c38783c93e2a50047925fa9471286.pdf?t=qwgn02 https://escholarship.org/content/qt3rm1w0mn/qt3rm1w0mn_noSpl... Maxim Gumin's work: https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse Paul Merrell's work: https://paulmerrell.org/model-synthesis/ https://paulmerrell.org/model-synthesis/ https://paulmerrell.org/research/ https://paulmerrell.org/research/ Oskar Stålberg's work: https://twitter.com/OskSta/status/784847588893814785 https://twitter.com/OskSta/status/784847588893814785 https://oskarstalberg.com/game/wave/wave.html 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 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)%20Survey.pdf 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 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 https://news.ycombinator.com/item?id=34561910

Nihilartikel 2y ago

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.

kelseyfrog 2y ago
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".

tjpnz 2y ago

The universe is lazily evaluated.

yarg 2y ago
It's beyond that. There's information required to evaluate the current state that is currently unavailable - meaning that the current state of things will not be defined until the future.
- Mobleysoft 2y ago
  Elaborate...

flobosg 2y ago

(2023)

A_D_E_P_T 2y ago

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."

jasonjmcghee 2y ago

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.

feoren 2y ago
Any game that wants a ton of content has this problem. The many caves in Skyrim start to feel the same after a while. You can often recognize the same assets over and over in very content-rich games. The total number of assets used in the article is tiny compared to what a production game would have. Procedural generation can't be used as an excuse to do less work, or it just feels same-y. A game is still a ton of work; it's just different work for different goals with procedural generation. Generating a huge world is boring if you don't have interesting objects to put in that world. Interesting objects are meaningless unless they're connected to a story. Minecraft works because it's a sandbox for you to invent your own stories, so the infinite world ends up getting filled by the player. If any element feels repetitive, the whole game will. If you wanted a fully procedural game, you need to figure out how to procedurally generate all the different aspects: story, characters, enemies, places, objects. It's more work to do that well than to make a traditional game. So people going into procedural generation thinking it'll save them work are already destined to fail.
- dualogy 2y ago
  Agree overall, and yet, and yet.. > Procedural generation can't be used as an excuse to do less work > So people going into procedural generation thinking it'll save them work are already destined to fail Consider the possibility that nobody really picks up proc-gen in the hopes they can laze out a RDR3 or such over the weekend. Another thing is, this applies to indies and AAAs alike: while a big world has to have interesting unique things in it, by definition not every square meter can/should be chockful of another "interesting truly unique thing" because if the whole world is filled like that, it's just another kind of sameyness in that the novelty factor would wear out just as quickly once you're getting that there truly is true novelty in absolutely every little square meter, which kills the novelty sensation in a heartbeat. Novelty delights us in a backdrop of routineness, sameyness, same-old-same-old-ness. So in between interesting things, the thusly necessary slightly-"duller" in-between areas are to pace and prep and make one anticipate novelty "hopefully almost just around the corner". Ideally it's so spaced to appear just in time before the player resigns such hopes. And so if you're going to have slightly-duller "filler areas" (and let me posit that any real-world say forest (in a biome one has traversed before), without the physical air and smells and winds (or friends/pets stringing along) is quickly "proc-gen dull-ish" within minutes — even in reality — or call it "meditative"/calming) — so again, if you're going to have slightly-duller "filler areas" just to connect and space apart the unique content things to good effect, then procedural placements/scatterings/variations are going to beat manual placement not just in "effort time" but because manual would swiftly look much more repetetive (being inevitably eventually effectively copy-paste driven) given the scale of environments under discussion, even if it would not take a human months of menial clickery. Rockstar gets it right imho but their approach would also get your "many caves in Skyrim" right because they manifest little novel uniquenesses not in scattered objects or env textures/models but via lively interactive interludes, whether it's animals frolicking or chasing each other or attacking towards you or "random stranger" incidents etc. That's the right kind of "filler but not boring", nobody cares about the variety of the rocks, only noticing them if nothing seems to be happening.

RobM71 2y ago

[dead]

mrtracy 2y ago

I work with this algorithm quite a bit in a personal project. (I've changed from calling it WFC to Model Synthesis; Paul Merrell earned the naming rights, unless we discover an even earlier description.) I mentally divide it into two important components: 1. Cross-correlation (the 'wave function') 2. Label selection (choosing where the 'collapse' occurs) The "cross-correlation" is exactly what it sounds like - given an incomplete model and a set of example patterns, this data structure represents the cross-correlation of every place that any of the patterns would individually fit in the incomplete model. I think this is the most useful structure in the algorithm, and is a form of iterative 'feature detection' over the incomplete model. I think there are many interesting things which can be done with this which aren't in the basic algorithm, such as: - Having larger indivisible 'patterns' and collapsing such patterns all at once. Although example patterns are always broken down into discrete cells, larger patterns can exist where each cell gets a unique label and very limited transition set. The cross-correlation will detect where they can be placed, and if one is chosen the entire pattern could be chosen at once. - Partial seeding of labels, e.g. selecting portions of the incomplete model and artificially limiting the available labels in that area, without collapsing it. - Addition of information to labels which aren't easily expressed in an example pattern, such as rudimentary counting of distances. The 'label selection' portion (in WFC terms, this is the algorithm used to choose which space to 'collapse') is where all of the random generation comes into play. If using Model Synthesis for full world generation, this is what should be focused on for generating more interesting types of environments. However, given the common label selection algorithms I've seen and used, I think that Model Synthesis excels mostly at adding small-scale, largely self-similar patterns onto constraints provided by a larger structure. I think that other proc-gen methods better lend themselves to generating large-scale structures. A combination of the two - generating a large-scale structure to serve as a constraint, and allowing model synthesis to fill in interesting detail - seems like a good path to explore.

mistercow 2y ago
> Partial seeding of labels, e.g. selecting portions of the incomplete model and artificially limiting the available labels in that area, without collapsing it. It seems like you if you had this, you could do some really interesting things with multi-scale collapse. For example, you could first use collapse to lay out biomes (e.g. beach needs to border sea, desert needs to border mountains, etc.) and then use those as constraints for the next scale level, which decides the details within those biomes, and the next level for cities and towns within those environments, etc.

andsoitis 2y ago

Are these the foundations for us, one day, to procedurally generate an entire universe in which other conscious beings appear?

steveoscaro 2y ago

Someone smarter than me please tie this into the many worlds theory of the universe and collapsing wave functions.

jb_briant 2y ago

I wanted to generate a procedural dungeon for a rogue like aspect of my game using WFC. It was a misunderstanding of what this very simplistic algo can do. - it's great to fill areas with kinda non repetitive patterns which feels random-ish - it's useless to build anything structured. Eg. You can't guarantee that a path exists from the entrance of the dungeon and the exit/goal. I ended up doing it fully with traditional Procgen techniques, I'm easily at 100+ hours of work and it's still only half of it. Discussions about "the problem of proc gen" in games are missing the point. Procgen is a non-gameplay feature, and it's very time consuming to get it right and controlled. The legend that you "gain" time is hilarious when you know how complicated things become with "random generation". Proc gen is a fantastic tool to bring diversity to non-interesting zones. The game is in the point of interests, they host goals, challenges, (storyline), progression. All of that is directed by logic.

rbanffy 2y ago

> The next challenge is to come up with interesting gameplay ideas for this project Making it an open universe game would make sense. Or a screen saver inspired on Apple’s Aerials. I’ve been wanting a No Man’s Sky one for my AppleTV since ever.