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

61–70 of 127 posts

Re: Show HN: Wave function collapse algorithm

#61

Post by wyager »

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.

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?

Re: Show HN: Wave function collapse algorithm

#62

Post by borgel »

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

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

Re: Show HN: Wave function collapse algorithm

#63

Post by matthewwiese »

Excellent! I especially like the example third from the top (black/white "rooms"). This would be a great tool to generate maps for roguelikes in a more "organic" fashion. Not only that, but the bitmap source you use for input would provide wildly different results.

Given that and the simplicity of just providing a bitmap as input, this could be adapted well to provide customization to the player as well.

Re: Show HN: Wave function collapse algorithm

#64

Post by Sire »

khalilravanna wrote: post #51
wodencafe wrote: post #37

That's incredible! This could be great for generating maps in a sprite based strategy game!

As a person currently rewriting the mapgen algorithm for their Dwarf-Fortress-like game, I'm very excited to experiment with this this weekend =D

Cool, got anything to show? :)

Re: Show HN: Wave function collapse algorithm

#65

Post by ssalazar »

barrkel wrote: post #49
elevensies wrote: post #43

Earlier quoted context omitted.

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

You can also view digital images as 1-dimensional arrays of bits. (This is roughly how fax machines work.) That doesn't mean they can't also be 2-dimensional images, or representations of 3-dimensional images, or indeed an encoding of a 3D scene directly. Similarly, you can unpack a linear sequence of sound samples into a two-dimensional plot of frequency and amplitude with a fourier transform.

> Similarly, you can unpack a linear sequence of sound samples into a two-dimensional plot of frequency and amplitude with a fourier transform.

Fourier transform by itself is still 1D (amplitude vs. frequency); to get to 2 dimensions you can plot it over time i.e. a spectrogram.

Re: Show HN: Wave function collapse algorithm

#66

Post by ssalazar »

JonnieCache wrote: post #50
barrkel wrote: post #49

Earlier quoted context omitted.

You can also view digital images as 1-dimensional arrays of bits. (This is roughly how fax machines work.) That doesn't mean they can't also be 2-dimensional images, or representations of 3-dimensional images, or indeed an encoding of a 3D scene directly. Similarly, you can unpack a linear sequence of sound samples into a two-dimensional plot of frequency and amplitude with a fourier transform.

Or you can represent the music as instructions to performers or synthesizers (ie notation) and you've got as many dimensions as you want. Music is not sound, it's made of sounds. The fact that it gets mixed down to a single waveform when you consume it, either in the studio or when it hits your ear, isnt particularly relevant to how its made. I suppose the same is true of images though. Markov chains applied to midi…

> 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).

Re: Show HN: Wave function collapse algorithm

#68

Post by ssalazar »

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

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).

Re: Show HN: Wave function collapse algorithm

#69

Post by tamana »

ssalazar wrote: post #66
JonnieCache wrote: post #50

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. Music is not sound, it's made of sounds. The fact that it gets mixed down to a single waveform when you consume it, either in the studio or when it hits your ear, isnt particularly relevant to how its made. I suppose the same is true of images though. Markov chains applied to midi…

> 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.

Re: Show HN: Wave function collapse algorithm

#70

Post by jmilloy »

ssalazar wrote: post #68
barrkel wrote: post #41

Earlier quoted context omitted.

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

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.
Post reply on HN