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.
> 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.
> Partial seeding of labels, e.g. selecting portions of the incomplete model and artificially limiting the available labels in that area, without collapsing it.
I've done that in my toy WFC to let it generate an output which matches[0] the colours and transparency of a supplied PNG. Handy for generating text / shaped output. Does a pre-pass which only keeps the best N match options for the colour in that cell.
[0] As best it can - my input tileset only really has green, light green, slightly less green, a bit reddy-green, fractionally blue-green, ...
> I've changed from calling it WFC to Model Synthesis; Paul Merrell earned the naming rights, unless we discover an even earlier description.
Wang Tiles, 1961. The WFC algorithm is just one way to generate a tiling. I haven't done a literature search but I'd be surprised if there isn't a materially identical paper with decades of priority.
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.
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.
I think Path of Exile does this kind of procedural generation of areas very well. Generated maps of a specific area will feel similar with some landmarks and the direction you're traveling in, but this is a good thing, because they can be used as guide posts where to go if you're an experienced player.
PoE2 on the other hand is some of the worst map generation iv'e ever seen. Like a copy and paste of the same exact thing hundreds of times to give you a large lifeless drudge of a map.
> 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.
The interesting part comes with building a simulation on top of this. For example with simulated citizens that go about their day fulfilling needs, going to work etc.
That's not a game though, and if the citizens all do permutations of the same n-things it's the exact problem that the poster you're replying to is talking about.
Games are interesting because designers have figured out what to present to the player, how to frame it in ways that are engaging/stimulating/challenging/intriguing/etc. That still needs to be authored in some way.
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. "
> 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.
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).
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.
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.
> 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.
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.”
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
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.
If you want to study a quantum mechanical system in equilibrium at inverse temperature β, the interesting quantity is the partition function Z = tr exp[-β H]. This can be converted into a path integral Z = ∫ dφ exp[-S[φ]] which can be importance-sampled via the Metropolis-Hastings algorithm [mh] via Markov-chain Monte Carlo.
This approach is commonly used in lattice field theory [lft], where the Hamiltonian H is that of a discretized spacetime (or the problem is formulated in terms of the action S to begin with).
Real-time problems in quantum mechanics involve exp[i t H] which brings a horrible complication called the sign problem [sign]. The one-sentence summary is that exp[-β H] is positive-definite but exp[i t H] is not and it's not clear how to incorporate a complex Boltzmann weight as a probability for MCMC.
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).
You will have a hard time constructing Markov Chain that correctly models the real-time evolution of physical quantum-mechanical observables. The problem is that the transition matrix that governs quantum-mechanical evolution is exp[i t H], which is not a well-formed probability distribution.
I would have said something very close to zeofig's answer, with the one significant change being to say that a deterministic system is itself a very boring kind of Markov chain where all states' transition probabilities are exactly 0 or 1.
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 :)
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)
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.
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".
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 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! :)
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.
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.
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.
[...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 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.
> 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.
> Partial seeding of labels, e.g. selecting portions of the incomplete model and artificially limiting the available labels in that area, without collapsing it.
I've done that in my toy WFC to let it generate an output which matches[0] the colours and transparency of a supplied PNG. Handy for generating text / shaped output. Does a pre-pass which only keeps the best N match options for the colour in that cell.
[0] As best it can - my input tileset only really has green, light green, slightly less green, a bit reddy-green, fractionally blue-green, ...
> I've changed from calling it WFC to Model Synthesis; Paul Merrell earned the naming rights, unless we discover an even earlier description.
Wang Tiles, 1961. The WFC algorithm is just one way to generate a tiling. I haven't done a literature search but I'd be surprised if there isn't a materially identical paper with decades of priority.
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.
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.
I think Path of Exile does this kind of procedural generation of areas very well. Generated maps of a specific area will feel similar with some landmarks and the direction you're traveling in, but this is a good thing, because they can be used as guide posts where to go if you're an experienced player.
PoE2 on the other hand is some of the worst map generation iv'e ever seen. Like a copy and paste of the same exact thing hundreds of times to give you a large lifeless drudge of a map.
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.
> It's more work to do that well than to make a traditional game.
hah, think dwarf fortress! That game is still incomplete to this day...
The interesting part comes with building a simulation on top of this. For example with simulated citizens that go about their day fulfilling needs, going to work etc.
That's not a game though, and if the citizens all do permutations of the same n-things it's the exact problem that the poster you're replying to is talking about.
Games are interesting because designers have figured out what to present to the player, how to frame it in ways that are engaging/stimulating/challenging/intriguing/etc. That still needs to be authored in some way.
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?
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!
"You know, Hexagons are the Bestagons!"
https://www.youtube.com/watch?v=thOifuHs6eY
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. "
> 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.
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).
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.
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
> 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.
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.”
> 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
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.
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.
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.
If you want to study a quantum mechanical system in equilibrium at inverse temperature β, the interesting quantity is the partition function Z = tr exp[-β H]. This can be converted into a path integral Z = ∫ dφ exp[-S[φ]] which can be importance-sampled via the Metropolis-Hastings algorithm [mh] via Markov-chain Monte Carlo.
This approach is commonly used in lattice field theory [lft], where the Hamiltonian H is that of a discretized spacetime (or the problem is formulated in terms of the action S to begin with).
Real-time problems in quantum mechanics involve exp[i t H] which brings a horrible complication called the sign problem [sign]. The one-sentence summary is that exp[-β H] is positive-definite but exp[i t H] is not and it's not clear how to incorporate a complex Boltzmann weight as a probability for MCMC.
mh: https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_al...
lft: https://en.wikipedia.org/wiki/Lattice_field_theory
sign: https://en.wikipedia.org/wiki/Numerical_sign_problem
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).
You will have a hard time constructing Markov Chain that correctly models the real-time evolution of physical quantum-mechanical observables. The problem is that the transition matrix that governs quantum-mechanical evolution is exp[i t H], which is not a well-formed probability distribution.
I would have said something very close to zeofig's answer, with the one significant change being to say that a deterministic system is itself a very boring kind of Markov chain where all states' transition probabilities are exactly 0 or 1.
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 :)
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?
Permutation City with a nod to Egan?
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...]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
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".
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 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! :)
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.
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.
> 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.
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.
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.
Are these the foundations for us, one day, to procedurally generate an entire universe in which other conscious beings appear?
Someone smarter than me please tie this into the many worlds theory of the universe and collapsing wave functions.
The universe is lazily evaluated.
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.
Elaborate...
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)
[dead]