7 ms·

Herringbone Wang Tiles

153 points by speednoise 12y ago

moyix 12y ago
Neat! I wrote a post [1] a while back on the isomorphism between Wang Tilings and Turing machines, which lends itself nicely to visualizations. Wang tilings have been used in other areas of computer graphics as well [2], as well as for DNA computing [3]. [1] http://moyix.wordpress.com/2012/04/06/computing-with-tiles/ http://moyix.wordpress.com/2012/04/06/computing-with-tiles/ [2] http://research.microsoft.com/en-us/um/people/cohen/WangFinal.pdf http://research.microsoft.com/en-us/um/people/cohen/WangFina... [3] http://seemanlab4.chem.nyu.edu/XOR.html http://seemanlab4.chem.nyu.edu/XOR.html
josephg 12y ago
I made a javascript implementation of one of the wang tile papers for exactly this sort of thing: https://github.com/josephg/wangjs https://github.com/josephg/wangjs Unfortunately, when you render out a large square of them the results look very repetitive. Herringbone wang tiles work much better.
taylorbuley 12y ago
I'm working on a canvas-based hexagonal grid system capable of implementing algos such as these. If you're interested in developing the idea get in touch: username at gmail.
Adaptive 12y ago
For sci-fi readers that dig aperiodic tiling, Greg Egan wrote a great short story in his book 'Diaspora' about computational wang tiles. http://www.amazon.com/Diaspora-Greg-Egan-ebook/dp/B00E83YOEI http://www.amazon.com/Diaspora-Greg-Egan-ebook/dp/B00E83YOEI (the short story is titled Wang's Carpets, available separately as well, but the whole book is worth buying or checking out from the library). I hope this is considered on topic. I find fiction, particular that which inspires interest in math/code to always be particularly relevant.
- k2enemy 12y ago
  Thanks for posting this! I just read my first Egan book (Permutation City) and was wondering which one to read next. I thought Permutation City was outstanding. I put the book down several times in awe and to think more about his ideas. It is great when a novel's story is so profound, yet plausible enough, to encourage this.
  - swayvil 12y ago
    permutation city! omg!
  - Adaptive 12y ago
    I just recently read Permutation City as well. If you liked it you'll enjoy Diaspora immensely. Permutation City is one of those books that made me feel the same way I did when first trying to understand clever recursive functions in Haskell. That is of course high praise.
Nickoladze 12y ago
This is one of those posts that makes me want to sit down and learn to make a game in my free time. Maybe I'll get around to it some time.
thisjepisje 12y ago
What would be some similar random-but-not-white noise algorithms? I only know of perlin noise and its variations.
tgb 12y ago
> It's also possible to allow tile rotation or mirroring. However, this complicates the nature of the edge constraint; with 90-degree rotation, the edge constraints on horizontals must be the same as the edge constraints on verticals. If mirroring (or 180-degree rotation) is allowed, the edge constraints must be internally symmetric. The advantage is that if rotation or mirroring are allowed, the minimum number of tiles needed decreases. (I haven't done the math to explore how far it goes down; somebody should.) Unless I'm mistaken, counting the number of tiles needed for a complete set when allowing rotations and reflections comes down to the classic necklace counting problem [1]. In particular, we have exactly 4 'beads' (i.e. edges in this case) and n colors (conveniently called colors in both theories). (Well, wikipedia's notation actually would call these 'bracelets' unless you didn't include mirroring.) Wolfram Alpha [2] gives an enumeration of these numbers for the first few, namely: 2 colors : 6 tiles, 6 w/ mirrors 3 colors: 24 tiles, 21 w/ mirrors 4 colors: 70 tiles, 55 w/ mirrors 5 colors: 165 tiles, 119 w/ mirrors (Disclaimer: I might have messed up the "with mirrors" numbers.) [1] http://en.wikipedia.org/wiki/Necklace_(combinatorics) http://en.wikipedia.org/wiki/Necklace_(combinatorics) [2] http://www.wolframalpha.com/input/?i=necklace+number http://www.wolframalpha.com/input/?i=necklace+number
joereggan190 12y ago
http://freerice.com/content-group/itv-watch-germany-vs-brazil-live-stream-world-cup-2014-semis http://freerice.com/content-group/itv-watch-germany-vs-brazi...

153 points by speednoise 12y ago

moyix 12y ago

Neat! I wrote a post [1] a while back on the isomorphism between Wang Tilings and Turing machines, which lends itself nicely to visualizations. Wang tilings have been used in other areas of computer graphics as well [2], as well as for DNA computing [3]. [1] http://moyix.wordpress.com/2012/04/06/computing-with-tiles/ http://moyix.wordpress.com/2012/04/06/computing-with-tiles/ [2] http://research.microsoft.com/en-us/um/people/cohen/WangFinal.pdf http://research.microsoft.com/en-us/um/people/cohen/WangFina... [3] http://seemanlab4.chem.nyu.edu/XOR.html http://seemanlab4.chem.nyu.edu/XOR.html

josephg 12y ago

I made a javascript implementation of one of the wang tile papers for exactly this sort of thing: https://github.com/josephg/wangjs https://github.com/josephg/wangjs Unfortunately, when you render out a large square of them the results look very repetitive. Herringbone wang tiles work much better.

taylorbuley 12y ago

I'm working on a canvas-based hexagonal grid system capable of implementing algos such as these. If you're interested in developing the idea get in touch: username at gmail.

Adaptive 12y ago

For sci-fi readers that dig aperiodic tiling, Greg Egan wrote a great short story in his book 'Diaspora' about computational wang tiles. http://www.amazon.com/Diaspora-Greg-Egan-ebook/dp/B00E83YOEI http://www.amazon.com/Diaspora-Greg-Egan-ebook/dp/B00E83YOEI (the short story is titled Wang's Carpets, available separately as well, but the whole book is worth buying or checking out from the library). I hope this is considered on topic. I find fiction, particular that which inspires interest in math/code to always be particularly relevant.

k2enemy 12y ago
Thanks for posting this! I just read my first Egan book (Permutation City) and was wondering which one to read next. I thought Permutation City was outstanding. I put the book down several times in awe and to think more about his ideas. It is great when a novel's story is so profound, yet plausible enough, to encourage this.
- swayvil 12y ago
  permutation city! omg!
- Adaptive 12y ago
  I just recently read Permutation City as well. If you liked it you'll enjoy Diaspora immensely. Permutation City is one of those books that made me feel the same way I did when first trying to understand clever recursive functions in Haskell. That is of course high praise.

Nickoladze 12y ago

This is one of those posts that makes me want to sit down and learn to make a game in my free time. Maybe I'll get around to it some time.

thisjepisje 12y ago

What would be some similar random-but-not-white noise algorithms? I only know of perlin noise and its variations.

tgb 12y ago

> It's also possible to allow tile rotation or mirroring. However, this complicates the nature of the edge constraint; with 90-degree rotation, the edge constraints on horizontals must be the same as the edge constraints on verticals. If mirroring (or 180-degree rotation) is allowed, the edge constraints must be internally symmetric. The advantage is that if rotation or mirroring are allowed, the minimum number of tiles needed decreases. (I haven't done the math to explore how far it goes down; somebody should.) Unless I'm mistaken, counting the number of tiles needed for a complete set when allowing rotations and reflections comes down to the classic necklace counting problem [1]. In particular, we have exactly 4 'beads' (i.e. edges in this case) and n colors (conveniently called colors in both theories). (Well, wikipedia's notation actually would call these 'bracelets' unless you didn't include mirroring.) Wolfram Alpha [2] gives an enumeration of these numbers for the first few, namely: 2 colors : 6 tiles, 6 w/ mirrors 3 colors: 24 tiles, 21 w/ mirrors 4 colors: 70 tiles, 55 w/ mirrors 5 colors: 165 tiles, 119 w/ mirrors (Disclaimer: I might have messed up the "with mirrors" numbers.) [1] http://en.wikipedia.org/wiki/Necklace_(combinatorics) http://en.wikipedia.org/wiki/Necklace_(combinatorics) [2] http://www.wolframalpha.com/input/?i=necklace+number http://www.wolframalpha.com/input/?i=necklace+number

joereggan190 12y ago

http://freerice.com/content-group/itv-watch-germany-vs-brazil-live-stream-world-cup-2014-semis http://freerice.com/content-group/itv-watch-germany-vs-brazi...