* Animated gif: https://twitter.com/marian42_/status/1061785383057440768
* GitHub page (demo in Unity): https://github.com/marian42/wavefunctioncollapse
* Original Wave Function Collapse Algorithm: https://github.com/mxgmn/WaveFunctionCollapse
GitHub page (demo in Unity) https://github.com/marian42/wavefunctioncollapse
Original Wave Function Collapse Algorithm https://github.com/mxgmn/WaveFunctionCollapse
"Copypasta" is when you copy sections of code from one or more program's source code and paste it into another, trying to pluck specific functionality from them, and create a mess in the destination program doing it.
(I think the Navy Seal copypasta and it's variations is the most popular example: https://knowyourmeme.com/memes/navy-seal-copypasta )
Can't believe I got downvoted for having more time on the internet than some others here, learning during that time, then making a statement based on what I learned.
You start with an array where every tile is possible in every location. Then you pick a random cell and assign a tile to it. That tile implies some choices are impossible, so you set those possibilities to false. That further implies some other possibilities are false and so on. You propogate that as far as it goes, and when you are done, pick another random cell and assign a random possible tile to it.
Because you are propogating information as much as possible before making the next choice, the algorithm very rarely needs to backtrack. You can run WFC without any backtracking at all and it'll still find a solution most of the time.
Some animated examples I put together might illustrate things more: https://boristhebrave.github.io/DeBroglie/articles/gallery.h...
It's just constraint propogation, optimized for certain conditions and given a fancy name.
I guess you could call it a markov random field, but I don't think it does unbiased sampling.
You 'measure' one cell, and then all the other ones 'collapse' to values consistent with the result, because they have a hidden relationship with the cell you measured.
That's what happens in quantum mechanics. When you measure one thing, all the other things its entangled with collapse somewhat too - but not necessarily completely, it depends on the entanglement they had with the measured system.
It's a metaphor, I'm just saying it's very apt, not that it's mathematically equivalent.
1) X ? 2) X Y 3) X ? 4) X Y
? ? ? ? Z ? Z ?
The trick is that you must calculate amplitudes, not probabilities. For example, Y may contribute an amplitude of .5 to the bottom right corner , and the probability is (.5)^2=.25. And Z may contribute an amplitude of -.3 to the bottom right corner , and the probability is (-.3)^2=.09. But when both are there the amplitudes must be added and the probability is (.5-.3)^2=.04.
This is a case of destructive interference that reduces the probability of a particular tile when both are present, but if both have the same sign it can be a constructive interference and increase the probability of that tile.
This type of interference is what produce the weird interference lines in the double slit experiment (and even in the single slit experiment).
This project just add probabilities, without squaring the numbers, so it's more difficult to have quantum-like weird things.
Anyway, I like the result very much. Nice project. Nice name.
You're going to tile (say) the plane with a set of tiles you've chosen beforehand. (In this example, it looks like the tiles are 3d.) There are rules for which tiles can go next to each other---the edges must match.
As you go, there are two regions: a region in which you've settled on which tiles to use, and a boundary region in which you haven't. In the boundary region, you keep track of a probability distribution over the tiles. This distribution is influenced by the neighboring tiles (exactly how is probably the most interesting bit of the algorithm; I don't know).
The algorithm proceeds by repeatedly (i) picking a tile on the boundary that has a very skewed probability distribution, and fixing it to be the most likely tile; and (ii) updating the probability distributions of the neighboring tiles in the boundary.
It's possible that you end up making poor tile placements at the beginning that gets you stuck later, so the algorithm must sometimes backtrack to undo past decisions. You want to pick a set of tiles such that the algorithm doesn't need to backtrack too often, or it will take too long.
Note that the distribution is an ordinary probability distribution, not a sum of complex amplitudes like the name "Wave Function Collapse" would make you think.
One might also consider placing the algorithm in the context of a generative adversarial network (GAN) to adapt the tile probability modeling ML component towards a pattern that is less distinguishable from a real city.
I've played around a bit with WFC and wrote a library for using it, but I've never made anything as pretty as this.
It’s also important that players/teams can memorise the level layouts in order to form strategies.
Still a cool idea though!
In a well-designed map, every part has to play well with everything else, at least within line of sight. Even small changes to the layout result in unbalanced maps that lead to frustrating play. Randomly generated maps might be fun out of novelty, but they won't play well in the long run, at least for games like Counterstrike.
Not to say there isn't a way to make some form of satisfying gameplay out of a randomized sandbox, but it certainly won't be the same as an FPS map designed with experienced intent. That aside, it would probably produce a spot with excellent gameplay every so often out of pure serendipity, which would be fun to hunt for! I'd try it.
I'd like to see someone challenge that notion. I mean, that's certainly a known and reliable model for multiplayer play, but we see single-player games like Spelunky where familiarity means being able to recognize how common elements interact and construct your strategy on the fly, as opposed to a Super Mario where you're just memorizing the layout. Has anyone seriously attempted that in a multiplayer game? Obviously there's a lot of ways it could fail, but I feel like it could be spectacular if done well.
It is definitely a different play style this way, but im sure many people would have a preference for it.
hardly, for shooters it will become very frustrating very fast, because a lot of the time you're going to get outrandomed rather then outskilled.
I mean I don't get why everyone is focusing on shooter style games, this would be really great instead for assassination games or hide&seek games, including path findings, runners, treasure hunt etc.
If you want a more direct comparison on how map limits effects playstyles, compare Insurgency with Arma, they both have similar weapon deadliness and player types where running and gunning isn't really possible, but the overall game strategy players use and rely on is very different. You regularly see players in Insurgency using the map limits to their advantage and can just assume they won't get shot from certain directions because of it, in Arma you might try and utilize a similar area but there is no guarantee someone might not take the time to completely flank you or pop out of the sea or just take pot shots from 2km out on a hill top.
Exploration in proc gen worlds is mostly pointless anyway. Build roads to everywhere you want to go and you'll never get lost.
I also carried a lot of dirt around for those times when a bridge or stairs were needed to keep moving.
Pointless yes, but you could say that for most games.
I almost never explore caverns. I strongly prefer to dig my own systematic mines to get underground resources, even though it's more work.
On the surface, I never explore without a map. I take copious notes of the coordinates of my home and interesting features.
I tend to spend most of my time building and acquiring, and very little time exploring (even though I love the procedural generator Minecraft uses).
Would be fascinating to see if key BF maps concepts can be incorporated.
or, you don’t really care about tiles except that are directly around the players, as long as there’s a reasonable path between them. the city between them can regenerate and it wouldn’t matter; it’s not like they’d compare notes (and if they did, it’d be an odd coincidence rather than broken)
or, you can always use a map seed so the PRNG that makes it non deterministic (assuming that’s the only thing that does) generates the same numbers so that it is deterministic. the age of empires (old yes, but still relevant!) team wrote a great little piece about their multiplayer, and how they kept all their PRNGs in sync so that the games remained the same across hosts
The problem is, that the algorithm is path-dependent, deterministic PRNG is most likely already used, and doesn't help.
So if 2 players started at (x0, y0, z0) and went to (x1, y1, z1), but took different paths to get there - they would see a different tile :)
Edit: depending on how complex the world is, the server could probably just send out the world changes itself, rather than relying on each client to correctly (deterministically) apply the changes. It needs to do so anyhow for late joiners.
You can partially work around this by requiring the client to use a server-provided PRNG seed, although even then a kind of aim bot could help the player decide which path to explore to get favourable tiles.
So your best bet to avoid cheating is to do the collapse on the server using a hidden RNG.
of course tiles would need to be large enough to keep latency reasonable.
I've been working on similar (but much simpler and 2d) algorithm, and the gist of it was:
- divide infinite world into 2d chunks of constant size that easily fit in memory
- when player is nearby - deterministicaly generate edges of the visible chunks basing on perlin/simplex noise and random number generator seeded with the world coordinates of the chunk
- fill the chunks basing on 2d markov chains trained on hand-crafted map, starting with the edges going inwards
It needed a lot of training data to produce something that makes sense with even small number of possible tiles, so in the end I just generated everything with simplex/perlin noise and some heuristics.
I guess instead of markov chains I could use explicit rules to fill the chunks, like this seems to do.
But it had the advantage that it was very fast - because you didn't need to remember everything from the starting place of the player. You could teleport 1000 screens left, and then back, and everything worked fast and regenerated everything the exact same way.
If you do chunks and generate the edges first, you could run into a situation where it's impossible to fill the chunk based on it's edges.
For generating terrain, using noise functions makes a lot of sense since they are local (= don't need to know nearby values to evaluate) and deterministic.
Yes, to solve that I generated world in 2 stages - first decided which tiles are solid (using simplex noise so it was consistent), then decided "decorations" (what exact thing is in each solid tile - tree, building part, roof, stairs, etc). Most tiles were empty, tiles with nothing beneath were platforms, tiles with nothing above and something below were roofs or tree tops, etc. Where there were decisions to be made I sampled random number generator in constant order for given chunk. That, combined with seeding the generator basing on chunk coordinates meant it always generated same stuff for a given chunk, no matter which path you took to arrive to this chunk.
The problem was - there were a lot of such rules to specify, and if I only specified the few rules that were needed for consistent world - then the generated worlds were very repetative. When I added more tiles specifying rules for all combinations were too much, so I wanted it to learn rules by itself by analysing handmade maps and then tryign to use that in 2d markov chains, but I never got it to work well, and it was my master's thesis, so I just wanted to be done with it at this point ;)
If you randomly choose a point to start at (like the player avatar’s current position), then I see that you might get different tilings when regenerating the location.
It is really oddly triggering to run around in this thing.
If this were used to create level design where the local view is several iterations deep of patterns of patterns but not yet all the way to the bottom, I guess a fractal, that would be a trip.
It's easy enough to generate random time series data but this looks like a promising way to generate interesting signals with prescribed shapes or features while still being "random".
Edit: this might not be too hard. It’s open source and has instructions for loading it into unity. You might just have to add the vive camera and toolkit.
or check out the source here https://github.com/matuszeg/wavefunctioncollapse
I'll update the build (and this comment) and make sure it works later when I get back to my Vive.
Would love to see the output using Gothic architecture as the input.
(See https://github.com/mxgmn/WaveFunctionCollapse where it mentions "It may happen that during propagation all the coefficients for a certain pixel become zero. That means that the algorithm has run into a contradiction and can not continue.")
“There are highways, bridges, tunnels, a subway system, tons of dungeons with spawners and loot and so on. ”
The key problems with Wave Function Collapse tend to be that it gets exponentially slower as the area you need to collapse increases, and that it easily gets "stuck" (i.e. finds an combination of tiles that cannot be resolved, and has to backtrack arbitrarily far).
I assume the speed is solved by operating only on new chunks at the edge of the explored space, but backtracking across chunks seems... painful.
- "Look at this wonderful stairs!"
- "I see them. They are really uniquely same as any other stairs I've seen so far. And after all they are ... just staris."