7 ms·
WaveFunctionCollapse: Generates bitmaps that are locally similar to the input
- WorldPeas 5y agoas someone who did game dev for a while, i sure hope this plays well with semi-hires photos(1000x1000) as it seems better than conventional algorithms for unique texturing
- user-the-name 5y agoIt does not. It is for very small-scale similarities.
- hypertele-Xii 5y agoThe smallest possible scale, in fact: a pixel and its neighbors.
- TheRealPomax 5y agoOnly "seems". It's excellent at small scales literally because it's optimized for small scale local similarity, it's useless for large scale.
- pizza 5y agoMaybe VQGAN would be good for you
- capitainenemo 5y agohttps://github.com/EmbarkStudios/texture-synthesis https://github.com/EmbarkStudios/texture-synthesis this was on HN a couple of years ago, and seems to use a similar approach for photorealistic textures.
- hesdeadjim 5y agoI played around a lot with this library: https://github.com/BorisTheBrave/DeBroglie https://github.com/BorisTheBrave/DeBroglie Fun stuff, but I struggled to get a lot of value out of using it for level gen. You get cool patterns, but levels need structure and intent to be interesting. Adding constraints to the algorithm becomes a big-oh nightmare and you end up with frequently unsolvable paths as the algorithm recurses. The game Bad North used it to good effect, so depending on the game it may be a very useful tool in the toolbelt. https://m.youtube.com/watch?v=0bcZb-SsnrA https://m.youtube.com/watch?v=0bcZb-SsnrA
- Pet_Ant 5y agoI can imagine it for textures so the cobblestone and brick don’t end up repeating.
- signa11 5y agowouldn’t you be using perlin noise based textures for that?
- leetrout 5y agoI wonder if it could be combined with a tool like Path of Exile uses. They draw very rudimentary maps (River here, N bridges, etc) and then the tooling generates the level around those constraints. https://m.youtube.com/watch?v=GcM9Ynfzll0 https://m.youtube.com/watch?v=GcM9Ynfzll0
- thom 5y agoHow slow does an algorithm have to be before it stops saving time on level design, realistically? Obviously if it straight up fails for complex sets of constraints that’s one thing but even running for a day, if it yields usable results that seems like a timesaver.
- twic 5y agoThe maps in Bad North are frequently quite weird (although never actually broken), but that's part of their charm.
- eutectic 5y agoSeems like it might be worth taking some lessons from SAT solvers. e.g. backjumping and clause learning.
- deleted 5y ago[deleted]
- Scaevolus 5y agoTownScaper is a game built around WaveFunctionCollapse. You specify which cells in a 3D grid are occupied by clicking, and it fills in the details to make a charming little town. https://store.steampowered.com/app/1291340/Townscaper/ https://store.steampowered.com/app/1291340/Townscaper/
- btown 5y agoThe creator Oskar Stålberg has a great overview talk of Wave Function Collapse and how he applied it to his previous game Bad North - it’s absolutely worth a watch! https://youtu.be/0bcZb-SsnrA https://youtu.be/0bcZb-SsnrA
- Scaevolus 5y agoAnd he has a prototype of WFC city building online! https://oskarstalberg.com/game/house/index.html https://oskarstalberg.com/game/house/index.html
- dvh 5y agohttps://oskarstalberg.com/game/house/Release/UnityLoader.js(1) https://oskarstalberg.com/game/house/Release/UnityLoader.js(...: Invoking error handler due to Uncaught RangeError: Array buffer allocation failed ERROR> blob:https://oskarstalberg.com/5b6b4a87-7358-438a-a06d-fd708250936b(1) https://oskarstalberg.com/5b6b4a87-7358-438a-a06d-fd70825093...: Uncaught RangeError: Array buffer allocation failed
- wyldfire 5y agohttps://reddit.com/r/proceduralgeneration https://reddit.com/r/proceduralgeneration has content like this come up from time to time. Useful if you are interested in similar items.
- JoeyBananas 5y agothe algorithm is much simpler than I thought it would be. It basically takes an image made of tiles (think the levels of an NES game) and it searches for a permutation of those tiles with the property that each tile is immediately surrounded by the same types of tiles as in the original image.
- mrspeaker 5y agoI've struggled with implementing my own version of this algorithm - so I know I don't understand it properly. I get lost because of the "quantum mechanics" aspect - I am kind of suspecting it's just an analogy for the actual algorithm (maybe it's not?)... but I'd love to see if this could be re-written without the "entropy" and "superposition"-type wording, just to see if I can finally make it click in my brain!
- ijk 5y agoI agree that the quantum mechanics terms are often more confusing than helpful here. To the point that I wrote a journal article to try to demystify how the algorithm works [1]. If you're familiar with constraint solving, "superposition" is just "the remaining possible choices in the domain" and "entropy" is just describing how to select the next node. [1]https://ieeexplore.ieee.org/abstract/document/9421370 https://ieeexplore.ieee.org/abstract/document/9421370
- leetrout 5y agoDo you get a commission from this? No way to read online for free?
- dailyanchovy 5y agoI wondered why you would link to magazines a while ago, as they're often behind a paywall and the author doesn't get a cut as I understand. Maybe it's for the citations? Do authors mind sharing the article for free next to the publication link?
- nightcracker 5y agoCheck out sci-hub.
- mkremins 5y agoHere's an open access link: https://escholarship.org/uc/item/3rm1w0mn https://escholarship.org/uc/item/3rm1w0mn Academics don't make any money from sales of paywalled journal articles. If you click a link to a journal article and hit a paywall, it's usually because whoever shared the link has institutional access to the journal and forgot that the paywall was there (since it effectively isn't for them.)
- murrain 5y agoThe game Caves of Qud uses this to generate maps: https://www.youtube.com/watch?v=fnFj3dOKcIQ https://www.youtube.com/watch?v=fnFj3dOKcIQ
- dwd 5y agoI would highly recommend this video as a good starter https://www.youtube.com/watch?v=2SuvO4Gi7uY https://www.youtube.com/watch?v=2SuvO4Gi7uY
- wyldfire 5y agoThis was great, I feel like I have a good understanding of how it works now. Thanks for sharing.
- nightowl_games 5y agoI used this algorithm to generate minigolf courses [1]. I used this repo [2]. The algorithm is literally just a constraint solver. I'm pretty sure it's pretty similar to the sudoku solver I wrote in prolog for a university course. It's kinda pretentiously named and described, probably because its more academic to do that. It's just a constraint solver. 1: https://twitter.com/00jknight/status/1249091532071645184 https://twitter.com/00jknight/status/1249091532071645184 2: https://github.com/math-fehr/fast-wfc https://github.com/math-fehr/fast-wfc
- purplecats 5y agowow this is awesome i would love to use this as a webapp
- MattRix 5y agoOne cool property that I haven’t seen anyone else use is that you can use time itself as another tiling dimension. I did some experiments with creating looped animations a few years ago: https://twitter.com/MattRix/status/979020989181890560 https://twitter.com/MattRix/status/979020989181890560 https://twitter.com/MattRix/status/872648369625325568 https://twitter.com/MattRix/status/872648369625325568 https://twitter.com/MattRix/status/871054734018453505 https://twitter.com/MattRix/status/871054734018453505
- 000000000000100 5y agoCan it create temporally-similar patterns as well? Something that is bounded by a similarity metric over each time period?
- MattRix 5y agoYeah seems like that should be possible, since at the end of the day WFC is a system of constraints, so you can add any other arbitrary constraints you want on top of it. With the examples I posted above, since they wrap/loop in the time dimension, there is always some similarity/consistency. For example, in the one with the rabbits, if a rabbit dies, that means there will have to also be a birth to get back to the correct number of rabbits before it loops.
- 000000000000100 5y agoInteresting, I thought there might be something built-in for randomness. Great animations!
- kebman 5y agoLove how the 3D images looks like they're taken straight out of Labyrinth, never mind M. C. Escher. Wonder what it would take to make those render more efficiently.
- amelius 5y agoReminds me of the PatchMatch algorithm. https://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/ https://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/
- fho 5y agoI assume that a lot of people have played around with this concept, it's one of those things that are not too complicated to implement. But I guess I am the only one who used the Zelda, a link to the past overworld as the training input ;-) Examples: https://imgur.com/a/R1OleXp https://imgur.com/a/R1OleXp My problem with that was that the algorithm basically always ran into unsolvable states. The WFC solution to that is to just start again, but most WFC implementations use only few (<10) tiles. The Zelda map had several hundred, you can actually see the algorithm searching for valid solutions in the videos I linked.