ExUtumno

Author here, I'll try to answer questions/comments in this post!

Thanks for reposting, I don't mind.

Thanks! I would have probably never known about Markov algorithms if I were not taught them in 8th grade =)

Thank you!

For MarkovJunior, the recent projects that were impactful the most were Imagegram by Guilherme S. Tows [1] and Daniel Ritchie's dissertation [2] about PPLs for procgen. I took quite a different approach from Ritchie's though.

[1] https://zaratustra.itch.io/imagegram

[2] https://dritchie.github.io/pdf/thesis.pdf

At first I thought that my methods don't offer anything new to text generation besides the Markov chain, but several people already proposed ideas that sound sensible, so let me know if you make anything!

Most of the examples in the repo have those NxN all one color patches. Or, without (C2) the algorithm would have generated completely empty integrated circuits, or completely grass terrain, which is really boring.

You understood right, it's constraints + probabilities.

Btw, I have different algorithm that satisfies (C2) perfectly, but not (C1): https://github.com/mxgmn/ConvChain

There are special approaches to generating music. The best for ratio of quality/complexity that I know of are Markov constraints https://www.youtube.com/watch?v=buXqNqBFd6E and WaveNet. I don't think WFC offers something useful and new for generation of music.

In overlapping models we store probabilities for NxN blocks of colors/tiles. In non-overlapping models we store probabilities for individual colors/tiles.

Yes, (C1) is a constraint problem. But we also want to satisfy (C2) as close as possible, otherwise we could have just colored some outputs in a single color.

A very good question! The opposite of it is also important, can we follow some heuristics while creating tilesets to minimize contradiction rates, but not making tilesets easy? I don't know. If someone knows please tell me.

We need to interpret those coefficients somehow. Real coefficients can be interpreted as mixing of colors, but for complex ones I don't see a good interpretation.

I'm not experienced with the license law, but people told me that it's better to have license text in source files themselves, because I have samples in the repo that I have no idea who has rights for.

The license is MIT.

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.

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.

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

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

Thanks, I'll look into it.

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.

Thanks!

Yeah, you a right, I'll upload slower gifs. Right now youtube video has the slowest speed, in fact it has segments with no frame-skipping at all: https://youtu.be/DOQTr2Xmlz0

Well, right now it is not fast at all. :) But I plan to think about the problem of generating pixel shaders form examples in the future.

Thanks!

No, not really. ConvChain though is related to symmetry breaking, the same way as MCMC simulation of the Ising model is https://github.com/mxgmn/ConvChain

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 not hard to generalize it to arbitrary shapes. Paul F. Harrison made a tiling program that supports hex tiles: http://logarithmic.net/pfh/ghost-diagrams See also the relevant paragraph in the readme (just search the word "easy").

PatchMatch is an algorithm to quickly... match similar patches in an image, it is used in a lot of texture synthesis algos. See my answer to fitzwatermellow for the difference between texture synthesis and WFC. So yes, it's related.

Photoshop's implementation of PatchMatch handles constraints perfectly, yes.

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

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.

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 synthesis methods. 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 algos in a different repo: https://github.com/mxgmn/SynTex