[FRIAM] Constraint Propagation and "Wave Function Collapse" Algorithm

[glen]

FWIW, I played around with the WFC algorithm when it was brought to my attention. I don't remember when. But my interest in it is just as a particular instance of "procedural generation", "glitch", and their relation to "systemic games". As I wrote in 2020:

On 05/27/20 13:02, gepr wrote:
> And although I'm blown away by the things we (well someone, not me) can achieve with GAN, it still feels stilted to me ... a bit like the exploitation pitfalls in evolutionary computing (EC, e.g. negative altitude) or overfitted models. It brings to mind /procedural generation <e.g. https://github.com/mxgmn/WaveFunctionCollapse>/ as well. What I think EricS's idea of a multi-method constructing structure brings to the table is that collaboration can take many forms. And it maybe *must* take multiple forms in order to "round out" the composite probability distribution(s). A GAN (or EC) still seems a bit "flat" or "thin" in it's schematic guiding of a trajectory through the possible-needed space ("space" isn't the right word for such a self-constructing, dynamic thing, obviously). A minimal set of structures ... a kind of spanning basis for the collection of constructing/correcting mechanisms would be an ideal goal. And generation (the "G", what I've called Twitch) and discrimination are only 2 of them. Discrimination, in particular, seems ripe for a finer-grained, composite, implementation ... maybe that's why GANs still seem "thin" to me. But "adversarial" is also over-simplified. E.g. in the exquisite corpse (and our bad faith collaborative fiction), any one player's intention is not *entirely* adversarial, only slightly so. In the end all the players *want* some mix of cooperation, competition, syndication, and a sense of "fair play" ... as well as the ability to "game"/"cheese" it in bad faith sometimes. 

What's interesting (to me, anyway) isn't really constraints, specifically, but schema, in general ... the evolution of the "slots" and what can fit into them, the way the scheme relates the slots, the logical depth of the schematic system, etc. Clever methods for binding schema are interesting, but mostly as technical flourish on the larger background of meta-gaming.


On 10/21/23 15:23, Steve Smith wrote:
> SG> Just went down a 2-hour rabbit hole on the "wave function collapse" algorithm that emerged in graphics in 2016 but just
> SG>  came onto my radar... Has anyone else explored it already?
> SG> https://github.com/mxgmn/WaveFunctionCollapse
> 
> I think I 'get' from our myriad discussions about both dual-fields and bidirectional search why you got "rabbit holed" by this...
> 
> FWIW my "associative memory" self "squinting" from 100k ft saw some near-adjacents:
> 
>     https://en.wikipedia.org/wiki/Hashlife
> 
>          On one hand it is "memoization" up front, but it also has a possibility for a WFC style application for a *dynamic* landscape?
> 
>     https://en.wikipedia.org/wiki/Vector_quantization
> 
>          SOFMs seem like an apt near-adjacent to what you are maundering on?
> 
>     https://en.wikipedia.org/wiki/Attention_(machine_learning)
> 
>     The Text-Image transformers of DALL-E (et alia) seem to be a softer version of the constraint business?
> 
> I may be overgeneralizing or missed the focus of your fascination?
> 
> mumble,
> 
>   - Steve
> 
> 
>> Many of you have written versions of constraint propagation algorithms in one form or another. I like how this is framed by satisfying local constraints with tiles (forward) and global constraints with overlaps (backward propagation).  Of course, the name of the algorithm may be metaphorical to QM as is its use of superposition for local stacks of possible states, but I can't help wonder how Wheeler-Feynman Absorber Theory or Cramer's Transactional Interpretation might be cast as similar kinds of the same algorithm.
>>
>> more general applications:
>> https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/
>>
>> always like Dan Shiffman's Coding Train
>> https://www.youtube.com/watch?v=rI_y2GAlQFM
>>
>> https://github.com/avihuxp/WaveFunctionCollapse#demo
>>
>> A nice interactive to get the feel for it:
>> https://oskarstalberg.com/game/wave/wave.html
>>
>> A version in Julia :
>> https://github.com/roberthoenig/WaveFunctionCollapse.jl/blob/master/usage.ipynb

-- 
ꙮ Mɥǝu ǝlǝdɥɐuʇs ɟᴉƃɥʇ' ʇɥǝ ƃɹɐss snɟɟǝɹs˙ ꙮ