Generating an infinite world with the Wave Function Collapse algorithm

278 点作者 klaussilveira4 个月前

17 条评论

mrtracy4 个月前

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.

评论 #42755430 未加载

评论 #42755578 未加载

评论 #42756781 未加载

jasonjmcghee4 个月前

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.

评论 #42751856 未加载

评论 #42752313 未加载

jerf4 个月前

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.

评论 #42749213 未加载

评论 #42749605 未加载

评论 #42749575 未加载

评论 #42750013 未加载

评论 #42749675 未加载

评论 #42749892 未加载

atum474 个月前

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

评论 #42752698 未加载

Footnote73414 个月前

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

评论 #42749271 未加载

评论 #42749111 未加载

评论 #42749132 未加载

评论 #42749987 未加载

KronisLV4 个月前

> 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: <a href="https://www.youtube.com/watch?v=i51x6-8GqkA" rel="nofollow">https://www.youtube.com/watch?v=i51x6-8GqkA</a> 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.

评论 #42749507 未加载

Nihilartikel4 个月前

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.

评论 #42749995 未加载

A_D_E_P_T4 个月前

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

tbalsam4 个月前

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

评论 #42756572 未加载

rbanffy4 个月前

> The next challenge is to come up with interesting gameplay ideas for this projectMaking 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.

jebarker4 个月前

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.

jb_briant4 个月前

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.

andsoitis4 个月前

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

steveoscaro4 个月前

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

tjpnz4 个月前

The universe is lazily evaluated.

评论 #42752534 未加载

DonHopkins4 个月前

<a href="https://news.ycombinator.com/item?id=37485705">https://news.ycombinator.com/item?id=37485705</a>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:<a href="https://news.ycombinator.com/item?id=34561910">https://news.ycombinator.com/item?id=34561910</a>[...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.<a href="https://escholarship.org/content/qt3rm1w0mn/qt3rm1w0mn_noSplash_f68c38783c93e2a50047925fa9471286.pdf?t=qwgn02" rel="nofollow">https://escholarship.org/content/qt3rm1w0mn/qt3rm1w0mn_noSpl...</a>Maxim Gumin's work:<a href="https://github.com/mxgmn/WaveFunctionCollapse">https://github.com/mxgmn/WaveFunctionCollapse</a>Paul Merrell's work:<a href="https://paulmerrell.org/model-synthesis/" rel="nofollow">https://paulmerrell.org/model-synthesis/</a><a href="https://paulmerrell.org/research/" rel="nofollow">https://paulmerrell.org/research/</a>Oskar Stålberg's work:<a href="https://twitter.com/OskSta/status/784847588893814785" rel="nofollow">https://twitter.com/OskSta/status/784847588893814785</a><a href="https://oskarstalberg.com/game/wave/wave.html" rel="nofollow">https://oskarstalberg.com/game/wave/wave.html</a>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.<a href="http://donhopkins.com/home/documents/taxonomy.pdf" rel="nofollow">http://donhopkins.com/home/documents/taxonomy.pdf</a>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:<a href="http://chaim.io/download/Gingold%20(2017)%20Gadget%20(1)%20Survey.pdf" rel="nofollow">http://chaim.io/download/Gingold%20(2017)%20Gadget%20(1)%20S...</a>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.<a href="https://lively-web.org/users/Dan/uploads/SimCityReverseDiagr" rel="nofollow">https://lively-web.org/users/Dan/uploads/SimCityReverseDiagr</a>[... stuff about AgentSheets, KidSim, Lex Fridman interviews of Michael Levin and Steven Wolfram discussing Cellular Automata, CAM6 simulator, etc ...]More:<a href="https://news.ycombinator.com/item?id=34561910">https://news.ycombinator.com/item?id=34561910</a>

评论 #42750987 未加载

flobosg4 个月前

(2023)