13 ms·
Infinite procedurally-generated city with the Wave Function Collapse algorithm
- mrspeaker 8y agoAmazing work! I've been excited about this technique since I first saw the original demos of it (https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse) - but can someone explain (at a very high level) how Wave Function Collapse works? I've read through some of the documentation on various repos - it starts with the nitty-gritty details, and I haven't been able to grasp the concepts.
- justinpombrio 8y agoHere's my high-level understanding. 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.
- platz 8y agoPrev https://news.ycombinator.com/item?id=18322770 https://news.ycombinator.com/item?id=18322770
- jbattle 8y agoMaybe this is a dumb comparison, but it sounds like an algorithm for solving minesweeper. The big difference is there's no "right" answer, the puzzle emerges from the outplaying of probabilities.
- c3534l 8y agoBasically.
- Qwertystop 8y agoTwo additions to this: - AFAIK, the probability distribution is based on how common any particular adjacency is in the input. If the input is just rules rather than a small sample map, they'd all be equal, but if the input is an image that shows (for example) that only one in ten roads dead-end, that would carry over to generated stuff. - It can also do an "overlapping" model, where it sets one pixel at a time but considers overlapping tiles of 2x2 or 3x3 pixels. This breaks away from the grid structure, but requires a full sample image, not just a list of tiles.
- marian42 8y agoIn my case, the probabilites for each block are supplied manually.
- vokep 8y agoOh my....perhaps this backtracking to fix past inconsistencies could allow for a game environment in which "Mandela effect" events happen naturally from time to time. Could make for an interesting game mechanic.
- marian42 8y agoYou're right. There is backtracking in the demo and when it happens it looks quite eerie. The world around you just decides it wants to look different and changes.
- yoklov 8y agoThat sounds like it could be mechanically cool. Or at least lead to a cool setting.
- minkzilla 8y agoIt seems like it would work very well in a horror game. Though random generation doesn’t lend itself too well to horror.
- sophistication 8y agoThis sounds like standard procedures for sampling from a Markov random field. https://en.wikipedia.org/wiki/Markov_random_field https://en.wikipedia.org/wiki/Markov_random_field
- teddyknox 8y agoI wonder if machine learning could be used to model the probability distributions at a greater capacity, and thus reduce backtracking. 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.
- tobr 8y agoA while back I hacked together a crossword generator that works almost exactly like this, but using a wordlist to provide probabilities.
- BorisTheBrave 8y agoHave you ever written a Sudoku solver. It works like that. 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.html https://boristhebrave.github.io/DeBroglie/articles/gallery.h...
- doubleunplussed 8y agoAs a physicist who works with quantum mechanics, I have to say, "wave function collapse", is an extremely apt name for what you're describing. Usually when quantumy things are used in names of things it's just 'cause it sounds cool, but this is spot-on.
- madhadron 8y agoAs an ex-physicist, I would say "Markov random field sampling" would be the right name.
- BorisTheBrave 8y agoIt's really not. There's no probability field (unless you count booleans as a scalar), no complex numbers, and no entanglement. 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.
- doubleunplussed 8y agoThere kind of is entanglement though! 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.
- trippypig 8y agoThis is tectonic. If it's purely WFC, I'm really amazed and excited. It's not the novelty, it's the perfection of each. They remind me of the Laurentian library by Michelangelo. https://goo.gl/images/HHQLUv https://goo.gl/images/HHQLUv https://goo.gl/images/njGNLC https://goo.gl/images/njGNLC Would love to see the output using Gothic architecture as the input.
- a1369209993 8y agoLinks are broken (without javascript?), direct links appear to be: https://s.hswstatic.com/gif/michelangelo-buildings-10.jpg https://s.hswstatic.com/gif/michelangelo-buildings-10.jpg http://www.perfectraveller.com/media/k2/items/cache/2cebfdae7a8ea5d691033c085990a9d4_XL.jpg http://www.perfectraveller.com/media/k2/items/cache/2cebfdae...
- notnot 8y agoAdmittedly without yet reading but just looking at the pictures, I'd love to see examples of where it creates patterns of patterns. Sort of like the biomes in Minecraft: one pattern to draw out where the biomes are, one to fill them in with content. Could it be made to do patterns of patterns of patterns? 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. Awesome work!
- marian42 8y agoEach block has a probability of being selected. You could make this probability location dependent, for example by sampling a noise function. That way you get something like biomes.
- yters 8y agoI imagine a counter strike scenario where the area of engagement is constantly moving throughout this infinite city, so the fight is waged over a constantly changing landscape. Hecka fun or hecka confusing?!
- Mtinie 8y agoAre the combatants channelled into the same area? If not you end up with a game of “needle in the (forever growing) haystack”.
- pavel_lishin 8y agoIt would have to work somewhat like PUBG - people caught outside a given area slowly start to bleed health. (Or for bonus fun, are catapulted towards the center of the current combat area.)
- samfriedman 8y agoCareful design of the "tiles" and some restriction to the play area could go a long way to make a "fun" map that is still hugely random.
- praptak 8y agoYou could throw in some magnets there, like a flag whose position is known and has to be captured before the other team does it.
- gmueckl 8y agoDoesn't have to be a stationart target. Just mark the position of the leader in a deathmatch scoreboard on the map and tge problem solves itself while the game can keep moving over the map.
- munificent 8y agoAs someone who already has an abysmal sense of direction (I basically never play 3D games because I'm just always lost), this is my nightmare.
- msie 8y agoThis is sufficiently advanced to be magic to me.
- msie 8y agoOk, I understand a little bit more from reading this page: https://www.grendel-games.com/procedural-generation/?lang=en https://www.grendel-games.com/procedural-generation/?lang=en
- sspencer 8y agoSomeone skin this to mimic 'Dark City'! Complete with signs to Shell Beach...
- dwd 8y agoDark City is a great film, though this had me personally thinking more of Inception.
- crazygringo 8y agoFor all those of us not running Windows, is there a video anywhere showing this off?
- adameast9000 8y agohere is a gif: https://twitter.com/marian42_/status/1061785383057440768 https://twitter.com/marian42_/status/1061785383057440768
- kowdermeister 8y agoIt's on the page: https://www.youtube.com/watch?v=VqGDxNsAkKE https://www.youtube.com/watch?v=VqGDxNsAkKE
- crazygringo 8y agoThanks! It wasn't before :)
- abetusk 8y agoHere's a collection of relevant links for the lazy: * 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
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- delinka 8y agoI’m too lazy to copypasta the links. Can you please reformat to make them clickable?
- MrStonedOne 8y agoAnimated gif https://twitter.com/marian42_/status/1061785383057440768 https://twitter.com/marian42_/status/1061785383057440768 GitHub page (demo in Unity) https://github.com/marian42/wavefunctioncollapse https://github.com/marian42/wavefunctioncollapse Original Wave Function Collapse Algorithm https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse
- dev_dull 8y agoThis is a really good example of an uncanny valley. Things like two staircases side-by-side of different sizes just looks... strange, even though there’s technically nothing wrong with it.
- mcphage 8y agoThere's a book called "Possible Palladian Villas" which gets into procedurally generated houses (in the style of Palladio), and that kind of thing came up—they'd run their algorithm to generate some houses, and then notice details in what was generated that were just... off. Not impossible, just... not quite right, either. Things you wouldn't think about unless you saw plans for a house that didn't consider it. So they'd tweak their algorithm, and re-run it, finding new details to fix. It's a cool book.
- roywiggins 8y agoI assume McMansion builders use the same design process.
- mcphage 8y agoHonestly I think that's giving them too much credit ;-)
- mrfusion 8y agoThis is great. Can you Please and thank you port it to the vive? 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.
- marian42 8y agoI don't currently have access to a Vive, but I worked with it earlier. All that needs to be done is add SteamVR to the project and hook up teleportation. That's it.
- mcphage 8y agoIf possible, I'd love to be able to run it on a Mac, too.
- marian42 8y agoIf you (or someone with a Mac) wants to create a build with the Unity Editor, I'll add it to the itch.io page.
- matuszeg 8y agoI have a vive, but I don't have a mac. I could throw the SteamVR plugin in and get it up on windows, but someone would have to test it on mac
- mrfusion 8y agoI’d love to try it on windows if you can do it.
- matuszeg 8y agoI'm at work and my Vive is at home, threw together a build that "in theory" works but I have yet to test it. If you wanna take a stab it you can download it here. https://drive.google.com/drive/folders/1uRP9uan3iViBddmQ5iZ385yy5c_khnss?usp=sharing https://drive.google.com/drive/folders/1uRP9uan3iViBddmQ5iZ3... or check out the source here https://github.com/matuszeg/wavefunctioncollapse 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.
- mrfusion 8y agoDoes this remember what’s been generated if you come back to an area you’ve been before?
- marian42 8y agoYes, it does. However the algorithm is not deterministic. If you close the game and start it again, you will see a different world.
- mrfusion 8y agoIf you want to shoot me an email I could help port it to the vive? I might just need a few detailed instructions and I can figure it out from there.
- agentultra 8y agoI can see echoes of Borges, Kafka, Euclid, Escher, Greg Egan... nice work. Some existential and strange tales to tell with an environment like this.
- ajuc 8y agoSo, does this algorithm need to remember all already decided tiles forever to be consistent? Or to recalculate everything from the start each time you teleport? 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.
- marian42 8y agoMy implementation keeps the entire world in memory, forever. This is obviously not desirable, but I didn't figure out a way around it. You can't generate a place again that you have been to because the result would be different. 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.
- ajuc 8y ago> 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. 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 ;)
- davidw 8y agoIt's very unrealistic: in a real city people would have shit bricks because of the total lack of parking, and forced the planning commission to enact big parking minimums.
- mygo 8y agoImagine creating a Tony Hawks Pro Skater course with this. Can’t learn the course ahead of time, just have to be a badass street skater.
- ryall 8y agoGreat minds: https://arcadia-clojure.itch.io/proc-skater-2016 https://arcadia-clojure.itch.io/proc-skater-2016
- BorisTheBrave 8y agoWFC collapse is an awesome algorithm, but I think this demo really illustrates that to get nice looking output with procedural generation also requires an excellent eye for design. I've played around a bit with WFC and wrote a library for using it[1], but I've never made anything as pretty as this. [1]: https://boristhebrave.github.io/DeBroglie/ https://boristhebrave.github.io/DeBroglie/
- nixpulvis 8y agoWould it be fair to call the "Wave Function" here a case of parallel constraint satisfaction?
- lsh 8y agoI'm reminded of Greg Bear's The Way. I thought it would be cool if user generated graffiti could be used as a seed for new generative graffiti so the further 'in' you go the stranger it gets
- J253 8y agoAnyone have any experience applying this to the generation of time series data? 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".
- falsedan 8y agoTime series data is one-dimensional?
- plants 8y agoIsn't that kind of just a markov chain?
- ShamelessC 8y ago"One of the dimensions can be time. In particular, d-dimensional WFC captures the behaviour of any (d-1)-dimensional cellular automata."
- rntz 8y agoIf this is based on wave-function collapse, what does it do when it hits an impossible/contradictory state? (See https://github.com/mxgmn/WaveFunctionCollapse 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.")
- marian42 8y agoIn the algorithm as it's described on that page, nothing is returned in case of a failure. I first implemented it so that single blocks would fail and a white cube would spawn at that position. Now, it uses backtracking. It keeps a history of its decisions and removes some whenever it reaches a contradiction.
- pugworthy 8y agoIt's strange, but for many, many years (40 at least?), I have had dreams that are in places like this. Endless halls, rooms, corridors, and so forth with no exit. It is really oddly triggering to run around in this thing.
- irascible 8y agoMy experience as well... like.. i'm almost convinced my brain does something similar to fill my dreamscape..
- eddy_chan 8y agoI came here to find your comment. All the vivid dreams I have are either 1) resitting an exam from 20 years ago and being completely unprepared for it or 2) running around in an endless dreamscape that is created by taking a known familiar area like a university, my local neighbourhood or a shopping centre and then scaling it up by using exactly this Wave Function Collapse algorithm. Funny thing is I can't backtrack in my dreams either.
- bryced 8y agoMinecraft has an add on that does this called “The Lost Cities” “There are highways, bridges, tunnels, a subway system, tons of dungeons with spawners and loot and so on. ” https://minecraft.curseforge.com/projects/the-lost-cities https://minecraft.curseforge.com/projects/the-lost-cities https://youtu.be/OZYZ0kV7Uw0 https://youtu.be/OZYZ0kV7Uw0
- ShamelessC 8y agoDoes it use WFC or another genration algorithm?
- ryanmarsh 8y agoThis would make so many games much more fun. Imagine if every drop in PUBG was onto an island with familiar features but not like any before it. Would definitely level the playing field too.
- chaoticmass 8y agoThis evokes a deep House of Leaves kind of horror in me when I play it. Similar to when I play No Man's Sky or Zoom in on the Mandelbrot set. Infinite sameness... forever...
- chaoticmass 8y agoThe unity game engine and everything worked really well though. It immediately used my HOTAS controllers, which I wasn't expecting. Impressive demo!
- goodmachine 8y agoPretty cool. Is everywhere reachable on foot? Are there blind interiors that are not reachable?
- mmjaa 8y agoThis is just a few ghosts and some pellets away from being awesome .. ;)
- swiftcoder 8y agoHow does the infinite part work? 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.
- scotty79 8y agoThat's why I hate being a tourist. - "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."