Show HN: MarkovJunior, PPL based on pattern matching and constraint propagation | Hacker News Reader

Show HN: MarkovJunior, PPL based on pattern matching and constraint propagation

github.com

36 pointsExUtumno14 comments

This is phenomenal! I have been toying with similar ideas, and I am so glad you are the same person behind Wave Function Collapse [1] . The fact that you have lifted the technique into a programming language is immensely powerful. Where do you want to go with it?

What research or other projects have been impactful on this work?

From the author, 40 minutes of the algorithm running through examples. [2]

Past stories about Wave Function Collapse [3]

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

Youtube videos of WFC https://www.youtube.com/results?search_query=wave+function+c...

[2] https://www.youtube.com/watch?v=DOQTr2Xmlz0

[3] https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

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

That thesis is really fun, but it will take me a couple weeks to digest. Before it even starts I see Pat Hanrahan, who is one of the nicest most creative people I have met in CS (), I know this going to be good.

A fantasy of mine is to have a bag of arbitrary constraints and behaviors of agents that exercise the system. One could sketch a building, model the behavior of people that will use it and let the system run, doing backwards and forwards inference to evolve a structure that makes those agents satisfied across lots of criteria. The designer if they are still called that, can select designs they like and the system can use that as a seed or test oracle. Virtual cows, cow paths and evolvable structures wrt those cow paths.

What do you think of "Growing Neural Cellular Automata" [1]

Are you by chance following CadQuery? [2]

[1] https://distill.pub/2020/growing-ca/

[2] https://github.com/CadQuery/cadquery

This paper is an excellent jumping off point into the academic literature.

https://www.semanticscholar.org/paper/Combining-Markov-Rando...

Just an idea: this or something similar could be utilized to generate test vectors, for property based testing [0]. Also for model-based testing, if you consider the model to be a vector of actions [1]

Currently, AFAIK, property based testing relies on mostly random generation of input vectors. It's possible to "shape" those vectors into other data structures such as trees [2] and it's the way it's usually done, but it's difficult and error-prone for more complex inputs.

There's also the option to filter each vector before running, or, after running, by performing the shrinking algorithm to produce the minimal input vector that reproduces the problem.

When I tried using property based testing for my use-case, as a model-based testing, I had to write code to filter most of the random test vectors since they weren't relevant, they didn't make sense.

So it might be possible to guide the generation of the input vectors so they'll be less random, and save time during run.

[0] https://typeable.io/blog/2021-08-09-pbt

[1] https://fscheck.github.io/FsCheck/StatefulTesting.html

[2] https://www.stackbuilders.com/blog/a-quickcheck-tutorial-gen...

Fascinating. One of the few things posted here that got me really excited! Probably because I studied the basics of Markov algorithms, but I never imagined the idea could be developed further in such an interesting way.

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

You must've gone to a special math school or smth) I learned about them in the uni and as with 90% of material it was quite dry and formal. Pretty sure they don't talk about generative art while teaching them in 2022 (and they probably should:).

Most satisfying animations I've seen in a long time. I just can't stop staring at them, they are wonderful.

Are there any other possible use cases of this language other then image or maybe in-game world generation? Do you consider it just as an interesting academic problem or do you plan to use it somewhere?

Maybe for generating more useful input vectors for property-based testing? I wrote about this in another comment here [0]

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

An untested idea/suggestion...

In the first Open Problem, maybe the generator tweak for random Hamiltonian paths is that two grids are needed: one for the eventual H-path; and one of points that are the centroids of the first which is used to draw a random tree starting from some point, subject to some rules about distances to unconnected nearest neighbours being acceptable (hunch e.g. of length >= sqrt(2)). Then draw around that tree on the first grid to get the H-path. (Grid graph duality use.)

I'd guess this can be generalised to 3D by drawing the H-path on each 2D plane slice, and some simple rules about choosing the degree of interconnection between those planes.

It seems like all the tools for tuning the shape of the initial random trees already exist in MJ, based on the examples shown.

This would be totally cool if it had an S-expression input syntax. (I mean, it's totally cool as it is, of course...)

This is really neat, thanks for making this!

.. and incredible work, I might add. It speaks for itself, and the README.md is really in a class of its own.

There, now this is a proper series of unsubstantiative comments. :)

Reply on news.ycombinator.com