Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Wave function collapse algorithm

github.com

Post reply on HN
Print view View original

71–80 of 127 posts

Re: Show HN: Wave function collapse algorithm

#71

Post by elihu »

barrkel wrote: post #41
ExUtumno wrote: post #39

Earlier quoted context omitted.

I doubt it, because music is 1-dimensional and for 1-dimensional arrays WFC is just a Markov chain.

There are three-dimensional views of music, e.g. time-frequency-amplitude. See https://en.wikipedia.org/wiki/Spectrogram

Another multi-dimensional abstraction for music that's at a bit higher level is a musical lattice. The number of dimensions is limited by the largest prime you accept in the ratios you use. (Typical western music approximated by 12-tone equal temperament uses primes of 2, 3, and 5. Powers of 2 are often ignored because notes an octave apart are perceived to be sort of equivalent for harmonic purposes.)

https://en.wikipedia.org/wiki/Lattice_(music)

Re: Show HN: Wave function collapse algorithm

#72

Post by derefr »

ExUtumno wrote: post #35
fitzwatermellow wrote: post #4

Great work! The fact that it captures "long-range order" seemingly perfectly is something not many have been able to do before! And the "collapse" visualization is great fun to watch. But is your algorithm really qualitatively all that different from previous search methods (e.g. Efros and Leung), if you are still (uniform random?) sampling over the input distribution of patches? I notice also your input textures ten…

Thanks! Efros' and Leung's method doesn't satisfy the (C1) condition. The closest previous work is Paul Merrel's model synthesis. WFC and texture synthesis serve similar purposes: they produce images similar to the input image. However, the definition of what is "similar" is different in each case. If you have a high def input with noise (like realistic rocks and clouds) then you really want to to use texture synthes…

> something like the inner rules of that image and long range correlations

I assume that if you feed WFC a large input image, it just thinks of that as a very complex set of rules that are harder to satisfy than those of a small input?

Is there a way, then, to instead train the WFC algorithm on a large corpus of small, similar samples, such that it can try to derive the rules common to all the inputs in the corpus, and produce one image that "really" fits the rules, rather than just the ephemeral quirks from an individual sample?

Would there be, for example, a way to train WFC to produce outputs matching the level-design "aesthetic" of a given game, rather than just "continuing" a particular level?

Re: Show HN: Wave function collapse algorithm

#73

Post by derefr »

ExUtumno wrote: post #52
throwaway000002 wrote: post #30

Brilliant! Don't really understand the technique, but would like your thoughts on if it's possible to give a Penrose tile set as a seed and see if aperiodic order is generated. Lovin' it!

Thanks! I'm not sure, but I think that Penrose tilesets are what I call "easy": you can't run into a situation where you can't place a new tile. It would be great if someone here could confirm or deny this. So if this is the case, then Penrose tilesets are not interesting to WFC, because you can produce arbitrary tilings with much simpler algorithms. Right now though WFC is only working with square tiles, but it's no…

Penrose tiles are "easy" on an unbounded canvas, but I'm pretty sure they're a 100%-probable "contradiction" (because they're aperiodic) on a bounded toroidal canvas.

Re: Show HN: Wave function collapse algorithm

#74

Post by ssalazar »

jmilloy wrote: post #70
ssalazar wrote: post #68

Earlier quoted context omitted.

Spectrogram is 2D (plot of amplitude given time and frequency). Its interesting to think about it for a spectrogram because "similarity" is different in each dimension (freq vs. time). Frequency is also perceived logarithmically, so you would probably want to convert to e.g. Mel scale before applying this algorithm (a 2000-2100Hz change is much subtler than a 200-300Hz change).

Isn't that 3 dimensions (amplitude, time, and frequency)? The plot of course fills 2 spatial dimensions and uses color to represent the 3rd dimension. But I don't know very much about this.

I don't have a mathematically rigorous understanding of it but the number of dimensions is basically the number of freely varying inputs to the corresponding functional representation. In a 2d image, x position and y position are mapped to a color, e.g. I(x,y) = C. In a spectrogram, freq and time are mapped to a color (amplitude) e.g. S(f,t) = A. In neither case can you just pick an arbitrary color or amplitude and in general produce a singular x/y or f/t from that.

Re: Show HN: Wave function collapse algorithm

#75

Post by derefr »

tamana wrote: post #69
ssalazar wrote: post #66

Earlier quoted context omitted.

> Or you can represent the music as instructions to performers or synthesizers (ie notation) and you've got as many dimensions as you want. These are just multiple signals in a single dimension (time).

1 physical dimension. Mathematically, each signal is a dimension.

We still call images "two-dimensional" when they're colored. There is a difference between continuous dimensions like space and time, and discrete dimensions like color channels in an image, or like instrument "tracks" of a song. The latter can have correlations, but they'll be sparse associations, rather than structural formulaic ones.

Re: Show HN: Wave function collapse algorithm

#77

Post by toxik »

ExUtumno wrote: post #38
vinchuco wrote: post #20

Can you feed it something other than bitmaps? Like its own source code?

Source code is a 1-dimensional array. For 1-dimensional arrays WFC is just a Markov chain. 2 and higher dimensional arrays are much more interesting because they have cycles, and there is no canonical way to generalize Markov chains to higher dimensions.

This will be abstract, but you seem to know your abstract algebra -- is it possible to do this kind of thing with graphs? It should be, right? And we all know code can be constructed with graphs, so… voila, you can generate code, no?

Re: Show HN: Wave function collapse algorithm

#78

Post by pfd1986 »

ExUtumno wrote: post #52
throwaway000002 wrote: post #30

Brilliant! Don't really understand the technique, but would like your thoughts on if it's possible to give a Penrose tile set as a seed and see if aperiodic order is generated. Lovin' it!

Thanks! I'm not sure, but I think that Penrose tilesets are what I call "easy": you can't run into a situation where you can't place a new tile. It would be great if someone here could confirm or deny this. So if this is the case, then Penrose tilesets are not interesting to WFC, because you can produce arbitrary tilings with much simpler algorithms. Right now though WFC is only working with square tiles, but it's no…

Agreed. The best way to find 'complexity' and perhaps aperiodicity is by using contradictory rules.

source: my own quasicrystal simulations (http://www.nature.com/nmat/journal/v14/n1/extref/nmat4152-s2...)

Re: Show HN: Wave function collapse algorithm

#79

Post by nhatbui »

natch wrote: post #55

What language is this? How can I compile / run it?

It's C#. I'm not familiar with it which is why I was surprised that after downloading Visual Studio Tools, I opened Developer Command Prompt, I did a `csc *.cs` and I was left with one nice executable, Main.exe.

Re: Show HN: Wave function collapse algorithm

#80

Post by Keyframe »

chronolitus wrote: post #33
etatoby wrote: post #11

This is great! It would be interesting to apply this concept to wavelets (instead of pixels or voxels) in order to work on real-life pictures. Also, 3 dimensions as in X, Y and time, to work on animated GIFs. Think about an infinite, never repeating Blue Ball Machine! http://m.imgur.com/5Flh68G

This is crazy, and I think it hints at the possibility of universe creation: you start from a finite pattern, which becomes the 'rules' of your created universe. Then, using this wave function collapse algorithm you expand it into an infinity where the possibilities are endless within the constraints of those generator rules

Premise of New Kind of Science, basically.
Post reply on HN