[HN Gopher] WaveFunctionCollapse: Generates bitmaps that are loc...
___________________________________________________________________
WaveFunctionCollapse: Generates bitmaps that are locally similar to
the input
Author : lnyan
Score : 262 points
Date : 2021-07-16 05:57 UTC (2 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| hesdeadjim wrote:
| I played around a lot with this library:
|
| 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
| Pet_Ant wrote:
| I can imagine it for textures so the cobblestone and brick
| don't end up repeating.
| signa11 wrote:
| wouldn't you be using perlin noise based textures for that?
| eutectic wrote:
| Seems like it might be worth taking some lessons from SAT
| solvers. e.g. backjumping and clause learning.
| twic wrote:
| The maps in Bad North are frequently quite weird (although
| never actually broken), but that's part of their charm.
| leetrout wrote:
| I 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
| thom wrote:
| How 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.
| murrain wrote:
| The game Caves of Qud uses this to generate maps:
|
| https://www.youtube.com/watch?v=fnFj3dOKcIQ
| dwd wrote:
| I would highly recommend this video as a good starter
|
| https://www.youtube.com/watch?v=2SuvO4Gi7uY
| wyldfire wrote:
| This was great, I feel like I have a good understanding of how
| it works now. Thanks for sharing.
| mrspeaker wrote:
| I'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!
| stared wrote:
| I looked at the WFC recently ("Level generation and style
| enhancement - deep learning for game development overview",
| https://arxiv.org/abs/2107.07397).
|
| Yes, it is a big inspiration, and there are numerous beautiful
| examples of its results. However, the QM wording is at best an
| extremely loose analogy (one that a hacker would use). If you
| want to compare it to other methods, see "WaveFunctionCollapse
| is constraint solving in the wild"
| https://dl.acm.org/doi/10.1145/3102071.3110566.
|
| "WaveFunctionCollapse is constraint solving in the wild."
| ijk wrote:
| I 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
| leetrout wrote:
| Do you get a commission from this?
|
| No way to read online for free?
| dailyanchovy wrote:
| I 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 wrote:
| Check out sci-hub.
| wokwokwok wrote:
| It's been discussed numerous times that this is simply a
| constraint satisfaction problem with hand-wavey BS applied over
| the top.
|
| Here's a good (free) explanation:
| https://www.boristhebrave.com/2020/04/13/wave-function-colla...
|
| Specifically read the 'Least Entropy' section: It's broken down
| very simply:
|
| Pick a random tile which is the 'least random', because (due to
| already having resolved the constraints we can), this is _most
| likely_ to be a cell that won 't cause problems (ie.
| unsatisfiable constraints) later.
|
| You might also like to read this (also) free paper on
| implementing WFC using a constraint solving library:
| https://canvas.ucsc.edu/files/109152/download?download_frd=1,
| which I quote here:
|
| > The heuristic of selecting the most constrained variable or
| equivalently the variable with minimum remaining values (MRV)
| is well known in constraint solving.
|
| > Since there is more than one valid pattern for that location
| --or it would already have been set to zero entropy in the
| previous loop--one of those patterns needs to be chosen. One of
| the patterns is chosen with a random sample, weighted by the
| frequency that pattern appears in the input image.
|
| > This implements Gumin's secondary goal for local similarity:
| that patterns appear with a similar distribution in the output
| as are found in the input [12].
| amelius wrote:
| Reminds me of the PatchMatch algorithm.
|
| https://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/
| nightowl_games wrote:
| I 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
|
| 2: https://github.com/math-fehr/fast-wfc
| [deleted]
| purplecats wrote:
| wow this is awesome i would love to use this as a webapp
| MattRix wrote:
| One 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/872648369625325568
|
| https://twitter.com/MattRix/status/871054734018453505
| 000000000000100 wrote:
| Can it create temporally-similar patterns as well? Something
| that is bounded by a similarity metric over each time period?
| MattRix wrote:
| Yeah 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.
| kebman wrote:
| Love 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.
| Scaevolus wrote:
| TownScaper 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/
| btown wrote:
| The creator Oskar Stalberg 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
| Scaevolus wrote:
| And he has a prototype of WFC city building online!
| https://oskarstalberg.com/game/house/index.html
| dvh wrote:
| https://oskarstalberg.com/game/house/Release/UnityLoader.js
| (...: Invoking error handler due to Uncaught RangeError:
| Array buffer allocation failed ERROR> blob:https://oskarsta
| lberg.com/5b6b4a87-7358-438a-a06d-fd70825093...: Uncaught
| RangeError: Array buffer allocation failed
| WorldPeas wrote:
| as 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
| capitainenemo wrote:
| 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.
| pizza wrote:
| Maybe VQGAN would be good for you
| user-the-name wrote:
| It does not. It is for very small-scale similarities.
| hypertele-Xii wrote:
| The smallest possible scale, in fact: a pixel and its
| neighbors.
| TheRealPomax wrote:
| Only "seems". It's excellent at small scales literally because
| it's optimized for small scale local similarity, it's useless
| for large scale.
| wyldfire wrote:
| https://reddit.com/r/proceduralgeneration has content like this
| come up from time to time. Useful if you are interested in
| similar items.
| fho wrote:
| I 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
|
| 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.
| JoeyBananas wrote:
| the 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.
___________________________________________________________________
(page generated 2021-07-18 23:02 UTC)