WaveFunctionCollapse VS MarkovJunior

Thank you! And yes, I agree. I was looking at uh https://github.com/mxgmn/WaveFunctionCollapse and wondering if that were applicable here :)

Have a good day!

Intuitively, it measures the difference between two probability distributions. It's not symmetric, so it's not quite that, but in my opinion, it's good intuition.

As motivation, say you're an internet provider, providing internet service to a business. You naturally want to save money, so you perhaps want to compress packets before they go over the wire. Let's say the business you're providing service to also compresses their data, but they've made a mistake and do it inefficiently.

Let's say the business has, incorrectly, determined the probability distribution for their data to be $q(x)$. That is, they assign probability of seeing symbol $x$ to be $q(x)$. Let's say you've determined the "true" distribution to be $p(x)$. The entropy, or number of bits, they expect to transmit per packet/symbol will be $-\sum p(x) lg(q(x))$. Meaning, they'll compress their stream under the assumption that the distribution is $q(x)$ but the actually probability of seeing a packet, $x$, is $p(x)$, which is why the term $p(x) lg(q(x))$ shows up.

The number of bits you're transmitting is just $-\sum p(x) lg(p(x))$. Now we ask, how many bits, per packet, is the savings of your method over the businesses? This is $-\sum p(x) lg(q(x)/p(x))$, which is exactly the Kullback-Leibler divergence (maybe up to a sign difference).

In other words, given a "guess" at a distribution and the "true" distribution, how bad is it between them? This is the Kullback-Leibler distribution and why it shows up (I believe) in machine learning and fitness functions.

As a more concrete example, I just ran across a paper talking [0] about using WFC [1] to asses how well it, and other algorithms, do when trying to create generative "super mario brothers" like levels. Take a 2x2 or 3x3 grid, make a library of tiles, use that to generate a random level, then use the K-L divergence to determine how well your generative algorithm has done compared to the observed distribution from an example image.

[0] https://arxiv.org/pdf/1905.05077.pdf

[1] https://github.com/mxgmn/WaveFunctionCollapse

Reminds me of wave function collapse - a programmatic way to generate mazes.

I am using WFC to generate the terrain, with pretty much a copy-paste implementation of the original WFC implemented into Unity.

If you still want to go the WFC route, the original WFC repository is a great place to start. There's also a (relatively barebones looking) Godot plugin you could take a look at.

wave function collapse studies - this is done with the https://github.com/mxgmn/WaveFunctionCollapse algorithm after I saw https://github.com/CodingTrain/Wave-Function-Collapse mention it. done in P5! IG https://www.instagram.com/ronivonu/

There’s an interesting approach similar to this called [Wave Function Collapse](https://github.com/mxgmn/WaveFunctionCollapse) (no relation to wfc in physics idea besides inspiration). It can infer the probabilistic constraints from one input example, and it seems to generalize quite well. Here’s a [little demo](https://oskarstalberg.com/game/wave/wave.html)

Our of curiosity, have you seen MarkovJunior, from the same developer? It's a generalization of WFC into a far more powerful probabilistic programming language capable of not only assembling random maps, but even generating solveable Sokoban levels?

It's not WFC but I'll be working on this soon too. For now I rewrote MarkovJunior in Rust, and made it into a library that is both faster and easly extensible.

Github source by the mxgmn

Have https://cragl.cs.gmu.edu/pixelate/ be used to preserve features of your input image and keep the resolution input low for WFC, then randomly select features (shapes) from the input image to be used for procedural creation, like in the Dungeon Growth example from: https://github.com/mxgmn/MarkovJunior

I've done a similar thing myself when trying to test operations on a hierarchical database for my internal product.

Biggest difficulty for me was that some combinations of operations were illegal and I had to think about all the edge cases and filter them out, and this took a long time.

My SO works in hardware, and she says they always use a constraint solver to generate test cases / test vectors, and she never understood why this wasn't popular in software. I googled it a bit and found lots of academic papers but no concrete implementation.

I've also thought about generating test vectors using a generator based on Markov chains, I wrote about that here [0], based on this [1] submission.

I'm not familiar enough with either using constraint solvers to generate test cases, or Markov chains, to know if I'm talking nonsense here or is it just something that nobody thought to develop properly.

[0] https://news.ycombinator.com/item?id=31704791

[1] https://github.com/mxgmn/MarkovJunior

Have you played with MarkovJunior? You can write game rules in 2 or 3 dimensions (or any other dimension) using colors.

I implemented my own take on MarkovJunior (https://github.com/mxgmn/MarkovJunior), which is fancy pattern replacement (from the same mind who gave us WaveFunctionCollapse). Here is some dungeon creation algorithm.