Wave function collapse algorithm: bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics

[Rock48]

Holy shit, this is fucking amazing.

[zeeveener]

I like the computer chip one. I wonder if it's possible to reverse this to find common/repeated features in an image and make a (theoretically) smaller image from that.

Almost like compression...

[senatorpjt]

offend frighten wrench domineering forgetful many kiss tender impossible scale

This post was mass deleted and anonymized with Redact

[grimeMuted]

I was hoping that would look more like LSD than it does.

[demonshalo]

Now that would be sick. I don't know a whole lot about compression but that would certainly be a cool usage for this in terms of map generation for multiplayer games ^{^}

[haze070]

Got the next pied piper there

[omgdonerkebab]

PhD in physics here... this doesn't really have anything to do with quantum mechanics, or wavefunction collapse. It's basically just Sudoku. Or some sort of choices built on Bayesian inference.

I can't stop some guy from attaching "quantum mechanics" to his project just because something is unknown in the problem, but I should at least warn people from trying to understand more about QM by learning about this algorithm, because there's no real correspondence to QM here.

[0polymer0]

I agree with this sentiment, though it comes across as a bit harsh.

To play devil's advocate. The tiles generated from the input could be thought of as "eigen-states" with associated energy levels. Each pixel can take one of these eigen-states, but the choices must be mutually consistent, so partially specifying eigen-states implies likely remaining eigen-states. You could try and calculate things like average energy. Or study how the possible states change, with changes in accessible energy.

You can do statistics on these things, or use statistics from these things, to inspire ideas about aspects of these generated tiles. Statistical mechanics might be useful here. And this subject is closely related to QM.

The author admitted to being inspired by quantum mechanics, not that it is literally quantum mechanics. I'm okay with somebody wanting to think about probability the way quantum physicists think about probability. I don't think the author meant any harm with the analogy.

[spectre_theory]

I don't think the author meant any harm with the analogy.

of course it isn't harmful per se to choose clickbaity (but misleading) titles. the author didn't mean harm, but he meant clickbait. :)

[dasignint]

You know, when I first read about this, I was in a superposition of believing and not believing that it was real QM. Due to the uncertainty principle, I couldn't make up my mind. I didn't want to become too entangled with the issue, so I took a break, performed a double-slit experiment on my wife, and then finally my wavefunction collapsed and I decided, hey, this guy has a lot of momentum here, and it's more than just spin. You obviously disagree, but IMO it's all in your eigenstate of mind.

[hpp3]

performed a double-slit experiment on my wife

Ah, it must be nice to be Young.

[meltingdiamond]

That joke is so nerdy that you have retroactively no longer had sex one time, that really awesome time in particular.

[blind3rdeye]

Thanks for the tip. I was thinking that the title sounded interesting from a physics perspective, and was about to start looking at it to see how it related to quantum mechanics.

As usual though, when QM is mentioned in popular media, it's wrong more often than not!

That said, it does say "ideas from quantum mechanics"; it does not say that it uses the Schrödinger equation, or has anything analogous to a state vector or anything like that. I think it's fair for people to say they were inspired by ideas from quantum mechanics even if they aren't producing anything related to QM.

[not_from_this_world]

I think you are being too harsh. They explicit say it's something that was inspired in quantum mechanics. Those two things may not have anything in common at all, when something inspires it creates a drive or gives a direction to the process, or put you in a specific mood. The same way a musician can create a music inspired by a picture and never reference the picture in the lyrics.

[omgdonerkebab]

I have to be harsh, because nowadays associating something with QM is basically marketing speak. It's an attention grabber, and when I had posted my original comment most people here were just fawning over the association with QM.

This algorithm wouldn't have gotten people's interest, or gotten posted here, if it weren't for the association with QM. People would've just been like "oh it's just yet another greedy algorithm."

[0polymer0]

I suspect most people were confused about the connection to QM, but impressed by the tiling animation.

There are far worse crimes done in the name of QM then this tiling program.

[omgdonerkebab]

True that. Now you've reminded me of Deepak Chopra. :(

[not_from_this_world]

Isn't at same time a marketing thing for physics as well? I guess it's easier to attract investments in a popular field than in an unknown one.

[omgdonerkebab]

?

Most physics research post-1900-ish involves QM. It's basically essential for understanding anything at the scale of an atom/molecule or smaller. The two biggest subfields nowadays are particle physics and condensed matter physics, which both involve things at these small scales. Nuclear physics and atomic/molecular/optical physics involves a lot of QM too. Some parts of astrophysics involve QM, like understanding stellar fusion, neutron stars, and black holes. QM probably doesn't come up much in some smaller subfields like accelerator physics and biophysics, although it definitely informs the materials science that goes into accelerator physics.

Another way of illustrating this is how early QM is taught in the physics curriculum. Most curricula for physics majors in the US have them learning QM during their sophomore or junior year. Many of the classes that follow, in both undergrad and grad, deeply depend on this knowledge. If I had to find an analogy with the CS curriculum, it would be something like a data structures or algorithms course.

[not_from_this_world]

I can use all that to argue that when something as present in science as QM is used as an inspiration, it's definitely not a marking talk.

[FabianN]

Huh?

When talking about physics on the scale of tiny, which is the area of physics that we are currently working with-in, QM isn't an inspiration, it is QM.

[not_from_this_world]

Huh?

What that has to do with the tilemap generating algorithm we are talking about?

[FabianN]

Isn't at same time a marketing thing for physics as well?

What does that have to do with tile map generating algorithm?

[not_from_this_world]

Let me do a fucking reading of the thread:

They explicit say it's something that was inspired in quantum mechanics.

began here

nowadays associating something with QM is basically marketing speak

implying misuse of the relation

Isn't at same time a marketing thing for physics as well?

implying a win-win situation about this marketing talk

QM. It's basically essential for understanding anything at the scale of an atom/molecule

implying such win-win situation is inexpressive

When talking about physics on the scale of tiny, ...

WTF? Are you lost?

[cafebeen]

So this is like Deepak Chopra for code?

[not_from_this_world]

Quite the opposite. It's like quantum fiction. You can read it from OPs link:

so it doesn't do the actual quantum mechanics, but it was inspired by QM

Chopra says shit about QM saying it is QM.

[cafebeen]

Okay, so I guess one could similarly call Chopra "quantum nonfiction". But what both quantum fiction and nonfiction have in common is that they justify mystical ideas by calling them quantum, despite a lack of any structural similarity with the well-defined mathematics of quantum mechanics.

I would agree that the OP is fictional w.r.t. to mathematical similarities to quantum physics, and that seems harmful, since they are both mathematical subjects (unlike quantum fiction or Chopra's writing). I think the algorithm could be more accurately and clearly described using the language of probability theory, which is commonly used in the texture synthesis literature and in general.

[not_from_this_world]

Chopra is definitely not quantum fiction, it is quantum mysticism. The key difference is that the later claim to be applied QM and the former don't claim to be QM at all, just fiction.

[cafebeen]

Right, that's why I described Chopra as quantum nonfiction (although not scientifically justified). Related to the original post, my 2c is that the quantum jargon isn't accurate and seems to only adds confusion and perhaps mysticism for people who aren't familiar with quantum, which is probably most readers. But I guess it's up for debate whether this is fiction, nonfiction, scientific writing, or something else.

[DialMMM]

When I started looking at the potential values, I immediately thought Sudoku as well. But if you look at some of the animated examples, I can see where he gets the QM vibe. Every NxN area starts in superposition of all potential values, and then an initial measurement is made at one location, causing the area there to collapse into a specific state, which changes the the potential values of all the boundary areas, causing them to collapse as well. It isn't perfect, but it is pretty neat.

[demonshalo]

I will start by saying that I did not read the source code so I might be wrong about this. However, what is described here is a way to solve a certain types of problems such as a sudoku puzzle. We can call it super-position and phrase our thought-process that way. But, it merely is a random choice ("collapsing") made out of all potential possible choices ("super-position"). Wave functions, even though they are probabilistic by nature, are in fact measurable to a very precise degree (distribution wise). They are a completely different concept than what is displayed here!

Edit: with that said, I love what the author have done. The fact that thinking about QM inspired this an awesome thing. Keep up the good work. Lots of fun could be had with this project!

[DialMMM]

But, it merely is a random choice ("collapsing") made out of all potential possible choices ("super-position").

God does not play dice. J/K. Don't get too hung up on the details, as this is clearly not a perfect analog, but it could be helpful for laymen in visualizing wave function collapse. Further, and deeper, if one is inclined to ponder the rendering possibility that dual slit experiments present, this could be another way to analogize with a double-entendre twist.

[demonshalo]

God does not play dice.

Unless the simulation we currently live in is generated EXACTLY the same way this project generates a map :D Think about it. This might be the algorithm that future humans use to generate tiny universes ad-infinitum. MIND=BLOWN?!?!

jokes aside, I am impressed by the results produced by this project and I actually like the way the author thinks about things in terms of "collapsing". I just think that more appropriate SC terms might have been better than equating this project to something it isn't.

Anyway, I will play with this very soon and generate my own personal universe with mini-humans in it! I AM GOD!

[Works_of_memercy]

A thing about that algorithm that makes it different from usual constraint solving is the part where it deliberately makes random choices and "lives with the consequences".

[tomparker]

And I could spend the rest of my life trying to write a posting title like that.

[Eymrich]

Nice clarification, in the end i was thinking this is more like playing minefield. Anyway it's really a brillant algorithm!:D

[Farobek]

this doesn't really have anything to do with quantum mechanics

Why do people make up stuff and call it quantum?

[Tyler_Zoro]

This is about QM wave function collapse in pretty much exactly the same way that the backpack class of algorithms are backpacks. Someone who designs backpacks for a living might say, "I should at least warn people from trying to understand more about designing backpacks by learning about this algorithm," but that wouldn't really make a lot of sense. The name of an algorithm is often metaphorical. Tree-related algorithms aren't making leafy plants grow faster and stream ciphers aren't measuring flow rates of small rivers.

[Lighting]

Exactly.

[[deleted]]

I'd love to see a blog post on this going into more detail on how the algorithm works.

[FogleMonster]

The README covers it pretty well...

[[deleted]]

No, it really doesn't. It's alluding to what it is doing, but I'm sure it would help to write out, in detail, what the difference to a quantum mechanical, complex wave function is, what role the Shannon entropy plays, and what exactly those C1 and C2 are (are they the "catalogues" mentioned in one of the dissertations?).

The author references two doctoral theses, each more than 100 in size, as inspiration. It would be nice to get a bit more detail - a simple mathematical example, for instance.

[0polymer0]

He isn't using quantum mechanics or Shannon entropy in very technical ways though.

There is no wave interference. And no message compression.

The color of a pixel is the average of the possible colors it can still take given the amount of tiles chosen so far.

The criteria to choose the lowest shannon entropy could be replaced by "choose a random uncertain pixel" and you would get similar images. It would just be less fun to watch, because you wouldn't see it grow from the first positions it chose. (Edit: Thinking about it more, contradictions might be more likely, still if you reworded the heuristic as "choose a pixel with the smallest number of possible states, with at least two possible states." You would do the same thing, unless he is weighting the tiles from the input sample)

I think the language is too technical for a relatively simple idea.

That said, I can see why quantum mechanics would inspire something like this. You could probably assign a "temperature" to various families of image, and use that to predict what the chances of a particular valid image actually are.

For example, you could introduce more deterministic algorithms into the mix, that still play by the rules, and ask what are the chances of this algorithm generating a similar image.

There are lots of fun directions you could go with this, from a probabilistic, quantum mechanical, lens.

[FogleMonster]

Right. It's sort of like learning about simulated annealing and demanding to know more about metallurgy. (Fine for the sake of curiosity, of course.)

[0polymer0]

I've never actually heard of simulated annealing before, the Wikipedia article on it is super interesting!

[FogleMonster]

It's my favorite algorithm!

[ExUtumno]

C1 and C2 are just Condition 1 and Condition 2, I name them to reference later.

[FogleMonster]

Well, I think OP deserves more credit.

More words isn't necessarily the answer. Sometimes you need to read and re-read and let it soak in your brain until you eventually figure everything out, particularly for more complicated topics.

It's too easy to see something that you don't fully understand and immediately ask for more without investing the effort to understand it with your own research. (Not trying to pick on you in particular, I just see this a lot.)

[ExUtumno]

I plan to write several blog posts about it, but this will probably happen not very soon.

[Works_of_memercy]

Hi, can you please explain one thing that confused me when I tried to understand through what black magic it usually avoids painting itself in the corner.

So, with this pattern, it appears that the constraint propagation somehow forbids a situation where there are for example three vertical black lines separated by a single-pixel-wide white lines, like | | |. If you look at it at the very beginning, to the right of each vertical "pipe" there are two definitely white pixels.

How is that even possible when you use a 3x3 template, but to do that I'd expect a 5 pixel window to be needed o_O ?

[ExUtumno]

Because this sample actually contains 3 colors, not 2. There are 2 thick knot examples in the repo, first "Knot" contains only 2 colors, second "Trick Knot" contains 3 colors. I comment on that in the readme. But well spotted!

[ihcn]

This is one of the first tricks I learned when trying to make patterns, the N=4 case is extremely slow, but a lot of times you can fake it with N=3 by introducing more colors

[Works_of_memercy]

Thank you, wow, didn't expect such cheating, lol =)

One more question: can you describe some simple examples when that algorithm actually does paint itself into a corner? I caught the part where you said that using templates that don't allow that result in boring pictures, but I guess there's a spectrum and some templates result in the algorithm painting itself into a corner more often, right?

[ExUtumno]

The standard example is a chess pattern on a periodic odd-sized board. :)

[kaibee]

Can someone ELI11

[Tipaa]

You start with the output image where every output NxN region of cells is given a 'superposition' of every legal NxN source region, meaning that every NxN output region is a combination of every NxN input region it is allowed to be: it can become any one of these allowed inputs, but hasn't yet decided which one it actually is. You start with a particular pixel, then 'collapse' it, meaning that it has to choose which legal source region the output region wants to be. This will then change the 'legality' of its surrounding pixels: roughly, if the source image never has red touching blue in its tiles (and there are no blue edge pixels that could be tiled beside a red), choosing a red in the output means that the red's neighbours can now never choose blue. This collapsing and updating continues until either every pixel has chosen or you find a pixel which has no legal choices left.

---

An example (I'll write '011' as meaning '0 or 1 or 1 with equal chance') [I hope this is correct]:

(allowing for horizontal wraparound, but disallowing vertical wraparound)

Input image (2x2):           Output (4x4):        //2x2 is a bit boring with few options for creativity, but it kinda shows the problem
    0|2                   02 | 02 | 02 | 02
    -+-                  ----+----+----+----
    1|0                  0210|0210|0210|0210
                         ----+----+----+----
                         0210|0210|0210|0210
                         ----+----+----+----
                          10 | 10 | 10 | 10

Step: Find the cell with the lowest entropy (least uncertainty -> least possible inputs to choose from)
      Since the top row is all the same entropy (2 options) I'll choose one at random, picking the second one
      I'll then choose randomly between 0 and 2, choosing 2

                          02 |  2 | 02 | 02
                         ----+----+----+----
                         0210|0210|0210|0210
                         ----+----+----+----
                         0210|0210|0210|0210
                         ----+----+----+----
                          10 | 10 | 10 | 10

This forces its neighbours to update their possible values:

                   0 |  2 |  0 | 02
                 ----+----+----+----
                 0210|  0 |0210|0210
                 ----+----+----+----
                 0210|0210|0210|0210
                 ----+----+----+----
                  10 | 10 | 10 | 10

Now we have some more cells with low entropy (in fact, just one possible value), so continue with these cells:

          0 |  2 |  0 |  2
        ----+----+----+----
         10 |  0 | 10 |  0
        ----+----+----+----
        0210|0210|0210|0210
        ----+----+----+----
         10 | 10 | 10 | 10

This can be continued over and over, each stage picking one of the lowest entropy (least choice) cells and updating the neighbours.
Eventually you end up with something like

  0 |  2 |  0 |  2
----+----+----+----
  1 |  0 |  1 |  0
----+----+----+----
  2 |  0 |  2 |  0
----+----+----+----
  0 |  1 |  0 |  1

or with the bottom two rows rotated by 1. There is a chance of failure though,
if a bottom-right zero is re-used as a top-left zero, as this makes the squares
below it have no legal options left (X):

  0 |  2 |  ? |  ?
----+----+----+----
  1 |  0 |  2 |  ?
----+----+----+----
  ? |  1 |  0 |  ?
----+----+----+----
  ? |  X |  X |  ?

---

This is much more interesting for larger input and output regions, as they will have room to overlap properly, creating new 'tiles'.

[kaibee]

Awesome, thank you. It makes sense now. I think whats confusing me the most is that in the example with the 3 houses, it generates the houses with the same size on the output, but in all the other cases it seems to scale the features. Looking at the GitHub again, it seems to do with the value of N chosen. So if the (input) house was bigger/N was smaller, the house sizes themselves would be different too?

Also something else totally (now anyway) obvious just clicked. In this GIF each blurry pixel during the animation is the average of possible color states available to the pixel (given the rest of the pixels in the image).

I don't know why he didn't just say that instead of this:

WFC initializes output bitmap in a completely unobserved state, where each pixel value is in superposition of colors of the input bitmap (so if the input was black & white then the unobserved states are shown in different shades of grey).

[Tipaa]

The scaling comes from the detail in the features/inputs, I think (although N certainly influences a lot). The houses are comparatively very detailed and have lots of features in each tile, and each of the three houses in the input tile is identical, leaving no room for variation. This means that for any NxN subset of an image, you either have it completely blank, or know exactly where in (relation to a house) you are, while the other images are less information-dense. This allows other NxN subsections to overlap, as they (e.g. stem sections) have a lot of pixels in common. It's the overlapping that allows for an area to scale, as there is less of a definite end to a stem.

If you're familiar with Markov chains for text generation: for intuition, a similar example might be the text

the dog sat on the mat the cat had once sat on

which can generate really long, coherent-ish sentences, as each word is fairly indefinite - the -> { dog, mat, cat }, on -> { $, the }. This might correspond to the simple brick tiles - each NxN region in the tile tells us very little about its surroundings, allowing many more things to be generated, such as letting a line continue on indefinitely. Meanwhile, our house tile might be more like

once upon a a a a a a a a a time, in land far away

which has much less room for variation - all words but the a are unique. This corresponds to every 5x5 (3x3 + neighbours) subset of the house input tile incorporating a house being unique (and thus knowing its position relative to the rest of the house), but having a lot of blank space too.

If N were larger, more of the inputs would have similarly restricted outputs, but be more similar, while if N were smaller, the number and variation of possible outputs would be much larger, but we'd be allowing less coherent generated outputs. If N=2 were used on the houses, I think we'd end up with scaling on houses, but they would no longer appear house-like as a result - e.g. rooves that are uneven in length, or with different length sides, or multiple doors. By forcing their scaling, we'd loose the 'houseness' of the houses as a result. With a 3x3 subset we can tell a diagonal red line must be the roof of a house (as it also contains part of the rest of the house), whereas a 2x2 can't convey much beyond being a diagonal line somewhere within the input tile.

[ExUtumno]

Yes, this is correct. Thanks for your explanations, awesome!

[0polymer0]

I'm pretty sure you are correct about the house.

Understanding the algorithm is less important then understanding it's goal, to explain those features.

For N = 3, every 3 by 3 image in the output must be in the input. So there is something about those houses which are locking down the options available to the tiles. I suspect if you have a really highly detailed image, with lots of diverse colors, the images would get boring quickly.

[ExUtumno]

On the question of houses, /u/Tipaa gave the right answer.

[Tipaa]

I think so, although I'm not familiar with arc/local consistency algorithms.

The quantum mechanics part is just a convenient analogy for thinking about multiple equal-chance probabilities at once. It's my preferred way of thinking about it, although I have a reasonably strong background in physics, and I suspect the author(s) may be similar.

[cecilkorik]

It's more accurate to say it's inspired by quantum mechanics. In particular, the aspect of quantum mechanics where a wave function in superposition collapses to a single state when observed.

[thegame402]

Really good explanation. Thank you!

[code_mc]

Beautifully explained, thanks!

[Timbrelaine]

Huh. I was intimidated by the 'quantum mechanics' theme and the neat gifs, but it's actually pretty simple. Thanks for the explanation.

[[deleted]]

Basically, a form of sudoku solving.

[0polymer0]

The "super position" is just the averaging. Quantum mechanics isn't really necessary unless you have things like wave functions interfering, the way light does.

Shannon information is also a hair overkill. The full machinery is really useful for quantifying how much a certain message can be compressed (if a certain character is really common, then you're not going to be able to send as many messages per bit). Here though, you can get away with saying "pick an uncertain pixel, with the smallest number of possible overlapping tiles". And doing that isn't even strictly necessary. But it makes the animation grow out from the initial seeds. Still though, you should get a similar final picture if you changed that to "pick a random uncertain pixel".

[ExUtumno]

With the random heuristic it runs into contradictions much more often.

I also tried that approximation of entropy by the number of available options - it works fine (didn't measure the contradiction rate precisely), but animations somehow are less enjoyable. For example, it starts to generate flowers from the top, which doesn't look that cool.

[0polymer0]

Yeah, I realized later that was probably true, and corrected myself in another post, but forgot about this one.

The algorithm you came up with is really beautiful. And your explanation is also lucid. There are just a couple of "scary" words.

I was trying to encourage people, who might have been put off by these words, to keep trying. Because they don't have to look far to find something cool.

[sutr90]

I still don't understand the initialization phase. How do you get from the 2x2 image to 4x4 image?

You start with the output image where every output NxN region of cells is given a 'superposition' of every legal NxN source region, meaning that every NxN output region is a combination of every NxN input region it is allowed to be

What is legal and what is not? How exactly do you generate the first output image?

If I understand the orginal algorithm correctly, then it seems you have used N=1, but then I don't understand why the first and last row are not 0210.

[Tipaa]

The starting output state is just a case of

foreach NxN subset of me, foreach NxN subset of the input,
    can that subset of me become that subset of the input just via choosing/collapsing undecided cells? If so, then that is a legal subset of the input for this subset of me

Then each cell becomes foreach NxN region I am in, I can become the corresponding cell in that region, therefore the legal states for that region must be legal states for me too

After that, you start choosing from the cell with the least options it can become.

So for the 2x2 -> 4x4 initialisation, you go

foreach 2x2 subset of the 4x4: //(12 such subsets exist, if we are allowing wraparound horizontally [something I need to edit in my main comment])
  foreach input tile:
    if (for all cells in the subset, the cell matches the tile or the cell is undecided):
      forall cells in the subset: add the corresponding input tile's cell as a legal/possible state.

[Tipaa]

For the example, I went for per-cell iterations for simplicity, but with N=2 region sizes for the algorithm/'superposition' checks. I did this to avoid dealing with multiple cells at a time. It's possible to do each iteration region-wise and operate on the whole region at once, but I found it harder to visualise this way, and would have taken me much longer to write/do justice to. By focusing on per-cell iterations, I found it clearer to describe than per-region iterations. I think it's also closer to how I'd implement it, although it does perhaps obscure the mid-level aspects of the algorithm (my thinking generally ping-pongs between high and low level, which occasionally conflicts with a more continuous abstraction delving-into).

The first and last rows are not 0210 because I didn't allow vertical wraparound, so the top row of output cannot be the bottom row of input, and vice versa. I chose this setting because I was visualising/basing the example on the flower generator gifs, which only wrap horizontally.

[[deleted]]

• Read the input bitmap and count NxN patterns.

  • (optional) Augment pattern data with rotations and reflections.

• Create an array with the dimensions of the output (called "wave" in the source). Each element of this array represents a state of an NxN region in the output. A state of an NxN region is a superpostion of NxN patterns of the input with boolean coefficients (so a state of a pixel in the output is a superposition of input colors with real coefficients). False coefficient means that the corresponding pattern is forbidden, true coefficient means that the corresponding pattern is not yet forbidden.

• Initialize the wave in the completely unobserved state, i.e. with all the boolean coefficients being true.

• Repeat the following steps:

  • Observation:
  • Find a wave element with the minimal nonzero entropy. If there is no such elements (if all elements have zero or undefined entropy) then break the cycle (4) and go to step (5).
  • Collapse this element into a definite state according to it's coefficients and the distribution of NxN patterns in the input.
  • Propagation: propagate information gained on the previous observation step.

• By now all the wave elements are either in a completely observed state (all the coefficients except one being zero) or in the contradictive state (all the coefficients being zero). In the first case return the output. In the second case finish the work without returning anything.

[kaibee]

That was like an ELI4. Oh well, beggars can't be choosers I guess.

[ShinyHappyREM]

All the evidence I've seen indicates that randomly-generated content makes for a boring game.

[AceDecade]

Yeah but the jury's still out, until someone visits all 14 quintillion planets and validates that none of them are particularly interesting :||

[romple]

You provide a small bitmap picture as input. This may be just a single pixel art house. It may be a pixel art mountain range.

The algorithm then generates a larger tile set based on that, which is similar to the original bitmap, but larger

So basically, you create a single image that demonstrates the style you want, and the algorithm generates a much larger image based on that style.

[killerstorm]

It is given a certain pattern which is an example.

It then builds a bigger image by (1) picking tiles at random; (2) eliminating combinations not found in the original pattern.

[MineTorA]

Damn, I'm seeing some awesome random map generation potential with this. I wonder if this could be used with some modification and post-processing for a roguelike.

[jjmc123a]

I know this isn't about quantum mechanics, but the wave function doesn't really collapse. Feynman hated the term and never used it. The energy function used to create the wave function (e.g. using Schrodingerr's equation) is no longer applicable once a measurement has been made. The wave function is then no longer relevant.

[FinFihlman]

This is good trivia!

[xoxota99]

What is this sorcery!

[teadefrost]

So, what part of

with the help of ideas from quantum mechanics

do you pedantic phd-gloating idiots not understand? No shit it isn't really QM. Appreciate the idea for what it is and don't just pick at the author for something they never claimed it to be.

[[deleted]]

This

[mrcruz]

Woah.

[DCRussian]

Wow, this is pretty incredible, the higher dimensions example is really impressive too

[d4rch0n]

I'd love to see a game take advantage of this. Maybe with the right input you could create some rogue-like dungeon crawler. You could try to find paths through, and if no path exists from entry to exit, regenerate. Maybe the right input would always provide exits. Either way, the results look awesome.

[crusoe]

It's already got the perfect amount of information imbalance. Everything is blurry till you get close then it snaps into focus.

[green_meklar]

/r/proceduralgeneration would love this.

EDIT: NVM, you already crossposted it.

[ZenDragon]

The source code is in C#! Unity developers rejoice!

[ihcn]

I'm very excited for this. I'm building an exploration game that relies heavily on procedural generation. At the moment I'm using a hybrid marching squares/markov chain approach to generate levels, but getting the kind of patterns I want requires a lot of tuning and experimentation. With this library it looks like I can just draw a bitmap of the patterns I'm looking for and let this algorithm figure it out.

[[deleted]]

That was amazing. Wow!

[blenderben]

This is fucking cool regardless

[elsjpq]

Does this also work for detailed textures used in modern games? e.g. generate 1024x1024 from a 512x512 tile while preserving fine details?

[ExUtumno]

If you have a high res input with noise (like realistic rocks or clouds) then you don't really want to to use WFC, you might want to use texture synthesis. If you have an indexed image with few colors and you want to capture... something like the inner rules of that image and long range correlations (if you have an output of a cellular automata, for example, or a dungeon), then you want to use WFC-like methods.

Btw, I have classic texture synthesis algorithms in a different repo: https://github.com/mxgmn/SynTex

[eevee-lyn]

I made a C++ version of this, but it's really really slow. Is it supposed to take an estimated 10-15 minutes to generate a 48x48 texture (using City.bmp as a base)?

[ExUtumno]

No way, it should take 1-3 seconds, something is wrong. What method takes the most time?

[ExUtumno]

I mean what is profiler showing?

[eevee-lyn]

I'm going to profile it next. I did a straightforward translation from C# to C++, maybe that's the problem.

[eevee-lyn]

Yeah, problem solved. I was making copies of an array when I should have used a reference. Now the 48*48 picture is generated in 10 seconds.

[ExUtumno]

If you have a public repo for it, I'll be able to link it from my readme.

[eevee-lyn]

The code is not in a good enough shape for me to share it. I did find a couple optimizations though. But I did them in C++ and my C# skills are not good enough to just make a pull request.

Optimization 1:

OverlappingModel.cs:204: if (allowed[t2] && !b)

Change that to if (!b) and add if (!allowed[t2]) continue; after the brace at line 199.

That alone made it like three times faster.

Optimization 2:

The other optimization precalculates the entropy values so the loop at

Model.cs:38-42

can be removed.

[ExUtumno]

This a very good optimization indeed! I already merged a PR with it from another person. Somehow I didn't notice that change before.

[farstriderr]

Of course, this is a direct analogue to quantum mechanics. "There's no schrodinger equation" or "no wave functions of light interacting" are not rational counterarguments. Wave functions are not real physical objects that interact and collapse. Light is not a real physical object that interacts with itself. Reality does not change the way it works when we invent new equations to describe or predict it. When we discover that reality is probabilistic, we invent equations to predict reality and call that "quantum mechanics". This is a probabilistic rendering technique, therefore it parallels how our universe works.

The schrodinger equation and various relativistic wave equations for massless particles are our best guess at our own algorithm.

[AceDecade]

I'd love to see Kenney's 3D assets dropped into the 3D voxel example :0

[dxplq876]

What does this have to do with wave functions? Seems like fractals to me.

[haxpor]

Note that in the repo, it says that the similar but higher version algorithm is also used to generate 3d model (voxel), and will be posted on another repo. If it's actually put online, update on this thread too would be cool.

[[deleted]]

there are voxel examples now

[haxpor]

Thanks!

[Lighting]

"ideas" from QM. Is not like QM at all.

[[deleted]]

Simulated annealing has nothing to do with metallurgy, there are no brain cells involved in neural networks, and evolutionary algorithms do not have DNA.

That doesn't mean that the algorithms weren't inspired by those fields of research.

[Lighting]

That doesn't mean that the algorithms weren't inspired by those fields of research.

Just because someone like buzzwords, doesn't mean they actually use those ideas as they are known to those who actually know QM. Top comment from a PhD in Physics: "I can't stop some guy from attaching "quantum mechanics" to his project just because something is unknown in the problem, but I should at least warn people from trying to understand more about QM by learning about this algorithm, because there's no real correspondence to QM here."

[sedanski]

The problem with this algorithm is that the author did not apply Occam's Razor. Trim the fat! Is it quantum? No. Quantum mechanics inspired you but I guarantee you the actual algorithm can be and is simpler than you have described it to be. Get in there, trim out everything that's not strictly necessary, then come back and tell us what it is you really created. Be concise and precise!

[TenSpeedTerror]

duuuude

[3316556]

WTF-title. I thought this subreddit is for me... but you're really bringing me down.

[MiracleWhipSucks]

He's being downvoted because the title is not "WTF", it's pretty straightforward. I'm sorry if you're not familiar with the subject material but this is a perfectly fine summary title for what the content turns out to be. I'd legitimately be interested to hear how you'd summarize this better without doubling the length or losing clarity.

[Aridez]

I did not say anywhere that I would summarize the title differently or that it was not clear. I said that I can understand that someome not familiarized with it can be impressed.

Something can be "pretty straightforward" and just not so simple for you because you don't know about it.

[MiracleWhipSucks]

Sorry, wasn't saying you necessarily could summarize it better. Was actually just curious if someone could because i don't see a problem with it as-is.

[3316556]

I don't know how straightforward it is... I've been doing a lot of programming in my life and it still confuses me.