Show HN: Wave function collapse algorithm • Hacker News Board

Re: Show HN: Wave function collapse algorithm

#81

Post by ExUtumno » Fri, Sep 30, 2016, 8:22 PM UTC

derefr wrote: post #72

ExUtumno wrote: post #35

Earlier quoted context omitted.

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, a…

About harder and easier to satisfy, the question of how the rate at which the algorithm runs into contradictions depends on the input is not easy at all. There is no simple correlations between the contradiction rate and the size of the input.

But the first thing you'll notice if you feed it an image with a lot of patterns, is that it will work very slowly.

Yeah, the corpus thing can be done if we cut out rare patterns and leave only frequent ones. I haven't tried it though.

Re: Show HN: Wave function collapse algorithm

#82

Post by ExUtumno » Fri, Sep 30, 2016, 8:24 PM UTC

spot wrote: post #45

ExUtumno wrote: post #35

Earlier quoted context omitted.

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…

predating Efros & Leung by many years: http://draves.org/fuse/

Thanks, I'll look into it.

Re: Show HN: Wave function collapse algorithm

#83

Post by BHSPitMonkey » Fri, Sep 30, 2016, 8:28 PM UTC

elevensies wrote: post #43

JonnieCache wrote: post #42

Earlier quoted context omitted.

How is music 1-dimensional?

A microphone records amplitude of sound waves over time, i.e. the air pressure -- that's the dimension.

You're describing audio, not music. Music as data isn't quantified in the same way as audio (see the various forms of musical notation that exist), and in fact music displayed in a sequencer or tracker looks pretty similar to the 2D bitmaps in the article.

Re: Show HN: Wave function collapse algorithm

#84

Post by brianpgordon » Fri, Sep 30, 2016, 8:31 PM UTC

borgel wrote: post #62

chronolitus wrote: post #33

Earlier quoted context omitted.

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

If you enjoy pondering on that, you may enjoy reading Permutation City [1] by Greg Egan. [1] http://www.goodreads.com/book/show/156784.Permutation_City

One of my absolute favorite sci-fi novels, and it changed my thoughts on philosophy of mind more than any other book.

Re: Show HN: Wave function collapse algorithm

#85

Post by ExUtumno » Fri, Sep 30, 2016, 8:35 PM UTC

DennisP wrote: post #54

ExUtumno wrote: post #52

Earlier quoted context omitted.

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…

Maybe it could be interesting to place Penrose tiles with the simple algorithm, but color them with your algorithm just like you're currently coloring squares.

So basically make a not-easy tileset with the shapes of Penrose tiles. Yes, this could be interesting.

Re: Show HN: Wave function collapse algorithm

#86

Post by ExUtumno » Fri, Sep 30, 2016, 8:41 PM UTC

toxik wrote: post #77

ExUtumno wrote: post #38

Earlier quoted context omitted.

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?

What do you mean by "code can be constructed with graphs"?

Re: Show HN: Wave function collapse algorithm

#87

Post by sushisource » Fri, Sep 30, 2016, 8:44 PM UTC

bduerst wrote: post #14

I don't have much to contribute to the conversation on this other than that it's incredibly cool.

My thoughts exactly. I will definitely read through this to understand it by my first impression was "This is so fucking neat!"

Re: Show HN: Wave function collapse algorithm

#88

Post by bronz » Fri, Sep 30, 2016, 8:44 PM UTC

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…

how did you come to understand all of this? are you an academic?

Re: Show HN: Wave function collapse algorithm

#89

Post by ExUtumno » Fri, Sep 30, 2016, 8:46 PM UTC

wyager wrote: post #61

ExUtumno wrote: post #38

Earlier quoted context omitted.

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.

Just to make sure I understand, if I were to use 1D WFC with 1xN tiles, would it be the same as an (N-1)th order Markov chain? Or would it be a 1st-order Markov chain with (N-1) simultaneous outputs?

If you use overlapping model (there are 2 models in the repo) with 1xN patterns, it would be a the same as (N-1)th order Markov chain.

Re: Show HN: Wave function collapse algorithm

#90

Post by ExUtumno » Fri, Sep 30, 2016, 8:53 PM UTC

chrischen wrote: post #2

Cool. I wonder what the results are on a high resolution image.

I wonder too =). But it'll run like forever on a high res image. For high res image you want to use something like texture synthesis, see my reply to fitzwatermellow for more.