Two algorithms for randomly generating aperiodic tilings | Hacker News Reader

Two algorithms for randomly generating aperiodic tilings

chiark.greenend.org.uk

195 pointsfanf242 comments

This website is a refreshing breath of fresh air. There's no "sign up with your email newsletter," it's a traditional webhost (not a Medium or a Substack), there's almost no styling / images / branding, it doesn't churn and stutter due to the behind-the-scenes gyrations of the latest monstrous multi-megabyte JavaScript framework with hundreds of dependencies.

Simon Tatham (the author of this article) is the developer of PuTTY [1], an open source Windows native SSH client, and Simon Tatham's Portable Puzzle Collection [2], a bunch of simple games implemented in portable C (with OS-specific frontends, or you can play them in-browser via WebAssembly).

The website has been updated in ways that improve it (this just-written article is a huge amount of informative content, and being able to play a puzzle in-browser via WASM is very welcome), but it never jumped on any of the 21st century design bandwagons that have taken over most of the WWW (many of which, I suspect, only exist to create jobs for web developers and branding consultants).

[1] PuTTY https://www.chiark.greenend.org.uk/~sgtatham/putty/

[2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

Agreed.

Also it could benefit from a modicum of CSS.

While Firefox displays it badly, Dillo displays it quite nicely, as does my home-rolled web browser. It used to be that, if you wanted something better than black-on-white left-aligned sans-serif, you'd configure your browser to your own tastes; I wonder why it doesn't work that way any more?

Because the inconsistency carries some risk.

And 97% of web users don't know CSS.

hard. https://i.imgur.com/ZNNU95P.png

I feel like any discussion of aperiodic tiling that doesn’t mention de Bruijn is missing the mark. He showed that aperiodicity results from projecting wireframes in 4 or more dimensions onto a plane. The non-repetitive patterns appear for the same reason that irrational numbers appear in Euclidian geometry.

When I tried to give a quick explanation of what an aperiodic was to a friend recently, calling it a geometric version of irrational numbers was the easiest way to do it. Glad to hear my explanation had some substance to it, and wasn't just one of those "you can think of it like this, but that's not what it really is" explanations.

Isn’t de Bruijn’s method specific to Penrose tiles? The aperiodic monotile paper says in section 2 that it is an open question whether the cut-and-project method can construct hat tilings. So de Bruijn would have been no help to solve Simon Tatham’s problem of how to generate hat tile puzzle grids. His two algorithms are the old one his Loopy puzzle uses for Penrose grids, and the new one it uses for hat grids.

You can play Loopy on a hat tile grid here: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/loop...

yes, agree, but you’re proving my point because as you say the interesting thing about the hats is that they don’t fit into the simple geometric explanation of other aperiodic tilings.

I'd be surprised if the pinwheel tilings — which have tiles that take on an infinite number of relative angles — could be reproduced in this manner. It seems like projecting a periodic set in high dimensions should give at most a finite number of cell orientations, although I can't prove it offhand.

Near my previous job there was a park with similar tiling [0]. I'm not sure if the pattern qualifies as truly aperiodic(?) but it triggered my brain every day, I couldn't not look at it. I love these kinds of patterns, they always invoke my curiosity. Just like in music irregularity makes things interesting. Something for your brain to solve. You know there has to be logic behind a seemingly random pattern.

[0]: https://www.dutchdesignawards.nl/gallery/funenpark/

That pattern looks periodic, but it's super cool! I think the periodic unit is a flower shape consisting of 8 tiles: 2 in the middle making a hexagon, and then 6 more around the hexagon, like the petals of a flower.

There’s another method, at least for the Penrose rhombus tilings: https://archive.bridgesmathart.org/2022/bridges2022-285.html...

The author of this was one of the authors of the Hat tile paper.

I think I am obsessed with aperiodic Penrose tilings. My 21 month old son's room has an area rug with such a tiling. I want to tile a bathroom in my house with them at some point. If you want to make my day, link a photo you have of one of these IRL.

It is such a wicked combination of beauty and math, like fractals.

Photos of a Penrose pavement here https://www.maths.ox.ac.uk/outreach/oxford-mathematics-alpha... and here https://hardscape.co.uk/inspire/case-studies/maths-institute...

https://media.giphy.com/media/14vFOciTnQjnl6/giphy.gif

A company tried to put it on toilet paper but Roger Penrose claimed ownership so they had to stop http://bit-player.org/2017/sir-roger-penroses-toilet-paper

Does he have ownership over ALL aperiodic tilings or just the ones he's come up with?

Anyway, that's unfortunate. Can't he just get a cut or something?

Also, this all really begs the question as to whether this is an "invention" or just "math". Imagine if Newton's heirs had to get a cut every time Newtonian physics was used (or calculus for that matter... splitting it with Leibniz's heirs)

Since it’s aperiodic, shouldn’t he only be able to claim copyright on the configurations he actually produced? Algorithms aren’t copyrightable, only concrete works fixed in a medium of expression.

Where can I get such a rug? I fixed up my home office a couple years ago and it's nice except I need a rug both to make it look nice and to absorb some sound.

I was wrong. I found something that resembled such a tiling, but was not, in fact, such a tiling. It was a fallback position. :/

If you do find any such thing, please let me know!

I searched a bit and found some on society6: https://society6.com/product/penrose-tiling6298504_rug?sku=s... https://society6.com/product/penrose-tiling-pattern_rug?sku=...

I have no idea if their rugs are any good, though, and I don't want to spend hundreds of dollars to find out.

Depending on how much free time you have, you may or may not want to dive into the rabbithole of aperiodic tilings in medieval Islamic architecture.

https://www.sciencenews.org/article/ancient-islamic-penrose-...

This is amazing. I just wish Islam was known for this still, instead of some other things.

Naively, and with general interest public forum curiousity, these tiling problems seem to be about iterating the proportions of the sides of the tiles to get symmetrical shapes, but given each tile is also necessarily a hamiltonian circuit between the angles/nodes of a shape and the tiles are aperiodic, the implied visual symmetry of the shapes doesn't seem meaningful.

It seems like there would be infinite possible aperiodic tiles (with real valued side lengths), so long as the number of angles (or nodes/vertices) for a whole tile (like a triangle) has the same evenness or oddness as the number of vertices extending from the node as the number of sides of the shape it is a part of.

So to completely tile a plane aperiodically, each node/angle of a triangle must have an odd number of "sides" from its adjacent tiles stemming from it to completely tile a plane, where each angle of a hexagon must be a node with an even number of sides connecting at its vertices. Once you are more than one "hop" away from another tile, you can have even or odd numbers of verticies.

The perimeter of any plane with a complete aperiodic tiling must still be a hamiltonian path around its edge, therefore the graph of the verticies representing the angles the aperiodic tiles must also reduce to being made of other "shapes" with hamiltonian paths. It implies to me that for every tile that is odd-sided, it requires a complementary odd-sided shape somewhere in the tiling to form a hamilonian path of "hops."

It's not a sufficient condition, but naively it looks like a necessary one. No math will get done here, but from a general interest reasoning perspective, I'd wonder if tiles and hamiltonian cycles are the same thing.

The hat is part of an infinite family of aperiodic tiles, as illustrated in the last image on this page: https://cs.uwaterloo.ca/~csk/hat/

This adjustability was a surprise, we have not seen an aperiodic tiling like this before.

I'm not a programmer, but I could use a piece of software (Python?) that could generate the "Einstein" tiles and give me the location/orientation of each to cover a large square (probably 65K tiles). I can take it from there to generate the graphics I need, but I'm stuck at this step.

How exactly was the 'hat' pattern arrived at? Was it through experiment or through an analytic process.

There's a great story here: https://www.quantamagazine.org/hobbyist-finds-maths-elusive-....

It was found by a hobbyist playing with PolyForm Puzzle Solver

This article has some of the story behind the paper https://www.theguardian.com/science/2023/apr/03/new-einstein...

Short answer to your question: David Smith discovered the hat shape by experimentation.

I don't understand what's so magical about the hat. It's a non-square shape that repeats.

it’s a non-square shape that does not and cannot repeat

Technically the shape itself repeats like a mug, infinitely tiling the plane. However, that tiling is not overly repetitive -- if it's like the Penrose tiling, it can be self-similar in a handful of rotations about a single origin, but unlike a square tiling, does not admit infinitely many self-similarities.

How can you cover infinite surface without infinite number of objects?

I mean the obvious answer is to use infinitely large objects, but I think you're just being asinine at this point.

No I really don't understand. I look at the image and clearly see the same shape repeated again and again

You’re right that the shape is used again and again, but the pattern of how it is laid does not repeat. So the new thing here is that there is a single shape that can cover the plane AND that it does this without the pattern repeating (and as an aside it cannot be made to do it with repeats)

"Aperiodic" is the opposite of "periodic"

When people talk about patterns that repeat, they usually mean one of the 17 wallpaper groups (https://en.wikipedia.org/wiki/Wallpaper_group). And people are interested in patterns that do tile the grid completely, but don't match one of those patterns. Originally it took thousands, but people had gotten it down to 2 shapes that together tiled the grid completely, but not in one of those 17 groups.

Now, people have gotten it down to a single shape that—by itself—tiles the pattern infinitely, but not in one of those 17 groups.

Bookmark

There is a „favorite“ button FYI :)

I read hackernews most of the time on a phone app that doesn't support favoriting :(

Reply on news.ycombinator.com