Tweet

Élie Michel 🍪

Follow @exppad

30 Jul, 7 tweets, 5 min read

@ExUtumno

The #WaveFunctionCollapse algorithm by @ExUtumno has got really trendy in #ProcGen and game dev communities, but it wasn't the first of its kind!
It was highly based on Paul Merrell's work published almost 10 years earlier.⬇️
1/7

First of all, Gumin's #WFC and Merrell's #ModelSynthesis give very similar results when they use the same tile set.
2/7

But WFC is more often "stuck" and forced to restart, so it takes much longer on large grids. Merrell's approach is more naive but in the end it does not make a visible difference.
3/7

@ExUtumno

@ExUtumno's main contribution over existing work was actually the overlap mode (see

https://twitter.com/exppad/status/1267045322116734977

)
But so when @OskSta uses WFC, w/o overlap, it's actually closer to #ModelSynthesis!
4/n

Nota Bene: afaik OskSta added a #backtracking method to the original WFC, in order to avoid restarting from sratch when WFC gets stuck, mitigating the performance issue.
5/7

A part of Merrell's algorithm that got lost in the story is a per-block generation, to minimize further the risk of deadlocks. A similar approach is used by [Bian18] hal.inria.fr/hal-01811874/d…
6/7

📚More info on Merrell's comparison page! code, video, etc: paulmerrell.org/model-synthesi… (I bet he got a bit furstrated to see his PhD rebranded under another name😬)
7/7

• • •

Missing some Tweet in this thread? You can try to force a refresh

This Thread may be Removed Anytime!

Twitter may remove this content at anytime! Save it as PDF for later use!

More from @exppad

Élie Michel 🍪

@exppad

31 May 20

@ExUtumno

The #WaveFunctionCollapse algorithm has been introduced by @ExUtumno as a texture synthesis method and nicely used by @OskSta for procedural generation of 3D buildings. Wait, what, how do those relate? Sounds like totaly different applications!
⬇️ Answers in the thread! 1/18

Discrete pixel values: WFC is different from many other texture synthesis algorithms because it never blends pixel colors. It does not need to know that a little bit of blue and some red creates purple. Others do require this, e.g. hal.inria.fr/hal-01824773/f…
2/18

This is a strength because it makes WFC more general. Pixels don't even need to contain colors. They just contain "stuff" or, more properly said, "abstract symbols". Can be an integer, a letter, a shape, whatever.
3/18

Read 18 tweets

Élie Michel 🍪

@exppad

17 May 20

@OskSta

Having a lot of fun reproducing @OskSta 's #Townscaper in #unity3d, very instructive exercise!
⬇️ Details in the thread bellow 1/10

Townscapper is based on #MarchingCubes, the traditional algorithm for converting voxel data to polygonal mesh (see also #DualContouring) 🧊
⬇️ We will apply it on a less usual grid though 2/10

Non regular grid generation based on hexagonal tiles with randomly removed edges.
Subdividing ensures that faces are all squares
➡️required to apply marching cubes! 3/10