Realizing still life constraints as a planar tiling

For general discussion about Conway's Game of Life.
User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » June 26th, 2022, 2:15 pm

In my on-going quest to make still life tiles at home using a die cutter, I realized that if I want to cut reliably at sub-millimeter detail, it's best to stick to thin material. Unfortunately, the tiles I want should be jigsaw thickness, around 1.5mm-2mm. So how do I get there?

It turns out I can cut 0.25mm cardstock very well and six layers brings me into the desired range. More about that below, but first I have a redesign of the in-between tiles to make them hold together better. I reshaped the jigsaw connections so they hold better but are still simple. More significantly, I replaced the straight empty-empty sides with rotationally symmetric curves. I think when I first did this, I forgot that I would not be flipping these pieces and could orient the sides in this way. It guards a bit against sliding and helps visually as well to make sure pieces are all facing up.
Screen Shot 2022-06-26 at 10.06.00 AM.png
Screen Shot 2022-06-26 at 10.06.00 AM.png (299.22 KiB) Viewed 1776 times
Note: I started to do something fancy by adding a 3D contour to the edges of tiles, since I have 6 layers to work with. This made it harder to fit together, so I went back to jigsaw pieces. Here are some of these pieces close up with a view of the edges
20220626_101259.jpg
20220626_101259.jpg (364.61 KiB) Viewed 1776 times
They are 1.6mm-1.7mm thick measured with calipers. The glue may add a little to the thickness.

I used the cheapest white "posterboard" I could find (uncoated and as thin as cardstock) except for the top and bottom layers of the live cell pieces. It only takes a few minutes of cutting to produce the layers for a dozen or more pieces.

The next question is how to glue them together. Initially I thought that making hand-laminated cardboard out of tiny bits of paper was a fool's errand. It is actually not that bad using forms with shaped holes to line up the pieces.

To make these forms, I cut holes through the same white posterboard I use for the pieces. The holes have to be a little larger (I added 0.2mm around) so pieces slip in and out. I also simplified the holes in places. As a recent enhancement, I coated the posterboard in paraffin. This makes them water-resistant, which is useful because they get a lot of white glue (Elmer's "school glue" or generic) on them and need to be washed.

I've experimented with different approaches, including making pre-glued posterboard with dry glue and cutting that. Then the forms can be filled with slightly moist pieces. There are also ways to glue while filling. If I can make each piece in a few minutes then it's fast enough to prototype (and it's the world's most expensive jigsaw puzzle if I wanted to compensate myself monetarily for the effort).

Finally, this picture shows both the forms and a completed block still life. I plan to make enough pieces for an eater, but this is as far as I got. The complete still life holds together well and is liftable. It is tricky to get the border pieces to fit because there is a lot of tension pulling them apart. Possibly I need to make the side pieces slightly longer to compensate for expansion due to imperfect alignment.
20220626_100914.jpg
20220626_100914.jpg (169.52 KiB) Viewed 1776 times

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » July 14th, 2022, 3:08 pm

Quick update. I completed enough tiles to make an eater.
20220705_145604.jpg
20220705_145604.jpg (142.02 KiB) Viewed 1689 times
I practice, I think laser-cut acrylic works best, though you do need to cut pieces separately because 0.2mm is too big a gap. I like the new shapes better than the old ones, and layered cardstock is an effective if time-consuming prototyping method. Next thing is to get a 3D printer. Maybe next Christmas. We'll see.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 11th, 2023, 2:45 am

I wonder if anyone has a better idea for this part of the still life tiling, because I think it's an interesting puzzle and there are clearly multiple solutions. The question is specifically how to construct a set of tiles that can be reassembled with translation, rotation, and flip into all 9 ways of constructing a wheel with either 2 or 3 bumps (or spots) at multiples of 45° but cannot be assembled into one with any other number of bumps (i.e. 0, 1, 4, 5, 6, 7, 8 ). I emphasize the second constraint because there are a lot of solutions without it.

To start with, there's the set of 5 tiles I've been using in physical puzzles that I've made. This includes an "ax head" that makes it possible to combine two half wheels each with a single bump (for a total of 2) but requires that a single bump half be combined when the other has two.
Screenshot 2023-02-10 at 10.15.35 PM.png
Screenshot 2023-02-10 at 10.15.35 PM.png (39.5 KiB) Viewed 1433 times
Then there's this 4-tile solution that I all but forgot about. It's clever but counterintuitive and feels a little fragile to construct at the size I want (less than 25mm or about an inch in diameter).
Screen Shot 2016-05-25 at 11.34.02 AM.png
Screen Shot 2016-05-25 at 11.34.02 AM.png (60.75 KiB) Viewed 1433 times
I started to think about this again recently and I found the following 5-tile set (shown with spots instead of bumps) that seems more elegant to me. It would be a 4 tile set except for the complete wheel where all the spots are grouped together. That's clearly not possible because each of the sections has an empty spot on at least one side.
Screenshot 2023-02-10 at 10.10.35 PM.png
Screenshot 2023-02-10 at 10.10.35 PM.png (190.11 KiB) Viewed 1433 times
There's a lot that I like about this solution. The pieces are easy to cut (and these don't have to hold together because they'll be surrounded). It's also a very "legible" solution. Each section has either a single dot or in the case of the smaller section may not have a dot. In most cases, there is more than one subset of tiles that will achieve the same result.

Note: in practice, the problem of minimizing the total number of tiles is less important than the number of subsets of features you can construct with a given tile set. So just supplying all 9 possibilities explicitly as individual tiles has the disadvantage that you may run out of one common shape, but breaking things down makes it more likely that you can build what you need.

The tile that I can't assemble is kind of annoying. This neighborhood is limited to corners of blocks or cells attached to three consecutive live cells, so you can build lot without it. I would still prefer some way to come up with it by assembling pieces.

Note that there is no reason the pieces need to be arc segments (as the second example shows). They don't even need to span an integer number of bumps. For example, is there a split into 3, 2.5, 2.5 or three that are 2 2/3, one of which has 1/3 bumps on each side? I have tried these but haven't made any progress. The third example above is the only new result that seemed worth writing about.

At this point, I would still like a better solution and would appreciate any ideas. My usual approach would be to run some kind of exhaustive search, but I don't even have an entirely clear idea of the search space.

Update: I neglected to mention that all of the assembled wheels in the third picture use at least one size 3 section with the spot to one side. I think this could help reduce the tile set but I haven't figured out a way to take advantage of it.

Update 2: This is a minor tweak, but instead of the complete wheel for 3 spots grouped together, we can add a tile spanning five spot locations with two spots on one side (11000) that can form the full wheel by combing with 100. This has the advantage that it can be used as alternate forms of other wheels by combining with 010 or 001 (the first tile flipped). This makes the additional tile useful in more cases. However, it does not reduce the size of the tile set. I may cut out tiles like this if I can't think of anything better. It still looks like an improvement on the "ax head" approach.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 12th, 2023, 4:35 pm

Here are the three dissections (into 5, 5, and 4 pieces respectively) shown for easy comparison.
g4433.png
g4433.png (194.81 KiB) Viewed 1383 times
You can see that I've oriented the assembled wheels the same way.

The only disadvantage I see to the 4-piece solution is manufacturing fragility, and that can be mitigated by balancing out the skinny features better. One very nice property of the 4-piece solution is that once you have decided whether to make a 2 or 3 spot wheel, you can reach all arrangements simply by flipping pieces in place. This also means (as I observed when I first posted this) that you could make these preassembled with fixed rotation axes.

So in short, I'm divided on which solution I prefer. Somehow the 4-piece solution seems like the "correct" even though it's not as simple as the most recent one.

Update: Here's a discrete search space that includes all sets above above. First partition the wheel as follows into 17 regions.
Screenshot 2023-02-12 at 1.45.21 PM.png
Screenshot 2023-02-12 at 1.45.21 PM.png (34.31 KiB) Viewed 1371 times
The center circle and 8 inner regions are either present or absent in a set (2^9 possibilities). The 8 outer regions are either present or absent and if present can have one of two colored spots (3^8 possibilities) so we have (2^9)(3^8)=3359232 possible shapes, but actually far fewer because they need to be connected and must have no more than 3 dark spots.

If I were going to automate this search, I'd probably start out by constructing all reasonable tile shapes and then look at subsets. I can't think of a way to write a SAT solver problem that expresses the final condition (all 2 and 3 spots, but no others). However, it might be possible to narrow down the subsets that realize at least one of them, and then verify each by hand.

Update 2: By reducing each piece to the spans that they cover, we can rule out many combinations, though we cannot predict if they really work.

That is, for each piece above, find a 4-tuple representing <#dark spots, #outer segments, #inner segments, #center circle> The first is a value from 0 to 3, the next two from 0 to 8, and the final is either 0 or 1.
  • For the 5 pieces in the first set, there are 4 distinct tuples: <1, 3, 3, 0>, <1, 2, 2, 1>, <0, 2, 2, 1>, <2, 5, 5, 1>.
  • For the 5 pieces in second set, there are 3 distinct tuples: <1, 4, 4, 0>, <2, 4, 4, 1>, <0, 0, 0, 1>.
  • For the 4 pieces in the third set there are 4 distinct tuples: <1, 2, 4, 1>, <1, 2, 0, 0>, <1, 4, 4, 1>, <0, 2, 4, 0>.
In any valid wheel, it must hold that the sum of the tuples added elementwise is <x, 8, 8, 1> where x is either 2 or 3. For example, using the first set, we find that <1, 3, 3, 0> + <1, 3, 3, 0> + <1, 2, 2, 1> is <3, 8, 8, 1> (the wheel for a 3 cell neighborhood). It would have been <2, 8, 8, 1> if we had used <0, 2, 2, 1> instead of <1, 2, 2, 1>. To get the wheel with three dark spots together, we used <1, 3, 3, 0> + <2, 5, 5, 1>. The 8-8-1 constraint limits which pieces fit together, and it should be the case that whenever that holds, the first number in the tuple is either 2 or 3.

Note that the property imposed by the tuple is necessary but not sufficient for having pieces that fit together. Conceivably, there could be some other reason the pieces don't match up. However, it does provide a filter for identifying sets of pieces that may work. Note that there may also be dissections that are not covered by this framework.

The third set is the most complex of these (and the only reason we need a 4-tuple, not a triple). Note that every 2-dark-spot wheel must be constructed as <1, 4, 4, 1> + <1, 2, 0, 0> + <0, 2, 4, 0> = <2, 8, 8, 1> and every 3-dark-spot wheel must be constructed as <1, 2, 4, 1> + <1, 2, 0, 0> + <1, 2, 0, 0> + <0, 2, 4, 0> = <3, 8, 8, 1>.

It now seems relatively straightforward to enumerate subsets of tuples that may work, e.g. by starting with a backtracking search to create ones that add up correctly and either inspecting them directly if there aren't too many or attempting to construct subsets from them.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 15th, 2023, 3:28 pm

Here are the same pieces as in the last posting, but modified to work in the still life tiling. I gave each distinct shape a different color, and I have grouped these into arrangements that can be varied just by flipping a piece in place. Each set can realize all 9 ways of assigning 2 or 3 teeth around the wheel, usually in multiple ways though I have shown only one.
g5852.png
g5852.png (118.29 KiB) Viewed 1330 times
I don't think there is a 4-piece solution with pieces as simple as the two 5-piece alternatives.

I did a little bit of analysis using a python script to enumerate the tuples I described in the previous posting. I define simple pieces as ones in which the outer and inner segments are the same. While I didn't carry it out systematically enough to be certain, I was able to rule out the other tuple sets I checked as not being sufficient to realize all wheels. E.g., take (1, 2, 2, 0), (1, 6, 6, 1), (2, 6, 6, 1). We can realize two teeth as (1, 2, 2, 0) + (1, 6, 6, 1) and three teeth as (1, 2, 2, 0) + (2, 6, 6, 1). For a 4-piece set, we can duplicate at most one of these. There is no need to duplicate (1, 2, 2, 0), which can simply be flipped. So any arrangement has (1,2,2,0) and one of the other three pieces. Since the only way to vary this arrangement is to flip a piece, there are at most 6 possible arrangements, and we need 9. If I come up with an automated way of reaching such conclusions, I might be able to rule others out, but it is time consuming to do by hand.

For the more complex pieces like the third set, there are more possibilities to consider, and less incentive since I already have a 4-piece solution.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 25th, 2023, 1:46 am

Here's a topic that has been bugging me since I started on still life tiles. To see the problem, take this tile set. It is from an old posting and a little different from what I use now.
Screen Shot 2021-08-07 at 8.56.29 PM.png
Screen Shot 2021-08-07 at 8.56.29 PM.png (346.98 KiB) Viewed 1288 times
There are three tiles (one half and two quarter circles) that can be combined to form all empty cells with 4 or more neighbors (crowding) but for cells with 1 or 2 neighbors (0 is not represented in the bounded tiling) the simplest thing is to enumerate all 5 tiles. The problem is that
  • If I try to split them down the middle with a straight line, they could be mixed with the crowding tiles for a size 3 neighborhood.
  • If I use anything other than a straight line, I can't flip them and also fit them together.
  • I could use an internal piece like the blue circle, but that's the wrong color and it adds an extra tile if I insist on the right color.
I recently realized (though it's not very useful) that it is strictly incorrect to say that no 2D tile with other than a straight line boundary can be fit together with flips allowed. It appears to be true of any connected tile, but see how well it works if the tiles may be disconnected. The red and blue tiles below each have a boundary consisting of an elliptical hole near the edge and a matching ellipse opposite the hole.
path8971-8.png
path8971-8.png (25.71 KiB) Viewed 1288 times
The red and blue tiles fit perfectly, and will fit even if one is flipped.

I believe disconnected tiles are considered in Tilings and Patterns by Grunbaum and Shephard. These suffer from the unfortunate disadvantage that when you make physical tiles, you can't get the disconnected part to float at the precise distance as the tile is moved.

However, this may be sufficient to state that the 2D tile set "exists" and then move on to a physical analog that I can make in 3D. This is fortunately more practical, and requires going beyond a prism-shaped tile to one with a more complex boundary. In this case, there are many ways to form a non-planar boundary that stays the same when flipped. I finally made these tiles by layering 9 pieces of die-cut card stock (and maybe it's time to get a 3D printer).
pieces.jpg
pieces.jpg (941.15 KiB) Viewed 1288 times
I've combined these because of the 3-image limit. At the top left, you can see some empty cells with 1 or 2 neighbors formed by pairing up halves, of which there are 3 distinct shapes up to rotation and flips. Viewed from above, the boundary consists of a 180° rotationally symmetric curve made of circular arcs. That can't be the whole tile shape or it will not be symmetric when flipped. Instead, the boundary is such that both top and bottom have the same curved edge and it flips in the middle. The top right picture shows this boundary on a single tile. The bottom picture is an illustration of the actual layers I cut from cardstock shown in order bottom to top going left to right. There are 9 layers (for consistency with some other pieces) and the middle has a straight boundary.

You may be wondering what are the X-shaped holes in the middle of the interior layers. These are the right size and shape to arrange the layers on a Lego technics axis going through them, holding them in place while I glue them. I may write a little more about that later. I have been getting better at making very precise shapes out of layered cardstock. The top and bottom are intended to cover the holes, and they can be filled, e.g. with modeling clay for greater strength before gluing on the top and bottom layers.

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 13th, 2024, 2:51 pm

It's been almost a year since I posted to this thread, but now I have a 3D printer and I'm getting good results with the same size pieces (25mm cells). Here is an eater, using all the new pieces except the block center, with live cells all around. That one also prints well.
20240213_080616.jpg
20240213_080616.jpg (3.26 MiB) Viewed 407 times
Note that I also have some 3D prints related to Penrose tiles in this Sandbox thread. The 3D printer is a Flashforge Adventurer 3 Pro 2, and it came with the dark blue sparkly filament. I ordered the white filament separately, also from Flashforge. However I have discovered that they have slightly different material properties so I have to leave a little extra wiggle room 0.1-0.2mm when printing blue. Maybe it's more granular. With some trial and error, these pieces fit together well when printed on my printer with these materials.

I was even able split out the "loneliness" pieces into halves with 3D contours (see previous post). This required sloping the edge for acceptable overhang. I can go a bit beyond the recommended 45° from vertical. The point here is not for the contours to snap together or even match perfectly geometrically (which is impossible in a 3D print), but only to make sure that you can't mix them with the overcrowding pieces and get them into the gap. So there are now 19 pieces, and technically, 17 would suffice if you tile out infinitely instead of building a border. In that case, only the inner boundary turn is needed (four fit together into the "missing" tile representing the corner between 4 empty cells).

Usability is reasonably good, but I have been doing this so long, it is hard to compare to a novice. The loneliness cells need to be placed together before dropping into the hole, and I thought this might be too much trouble, but it's not bad. An alternative would be to leave them flat and contour the overcrowding cells. Aside from not wanting to repeat a lot of pieces (laziness) I am a little worried about contouring those 90° wedges. I should probably test them out at least.

The main thing that holds all this together are jigsaw tabs and blanks on the in-between and boundary tiles. The cell pieces are drop-ins and it's better to give them a looser fit. The jigsaws snap and hold well (again with my white filament and fine-tuned spacing). I have the jigsaw hidden under a flat layer. Maybe this is overcomplicating things, but I think it gives the surface a cleaner look, since the jigsaws are just there for mechanical reasons, not to enforce constraints. It may be easier to build upside down since the pieces are easier to distinguish visually that way. It is liftable after that.

I'm not quite ready to make this public either on Tinkercad, where I made the 3D tiles (importing complex flat shapes from Inkscape) or Thingiverse, but I may do so after I'm more confident. This is also a nice enough puzzle that I could consider trying to sell it. Anyone with a laser printer who wants to try can DM me, and I can send you an STL file or some other format. I think that some of the fine tuning can be fixed just by scaling the inner pieces by +/- a few percent. I do it by adding or subtracting line thickness in Inkscape, which is more faithful to 3D printing imprecision.

Here are the tiles viewed from above in Tinkercad.
Screenshot 2024-02-13 at 8.38.01 AM.png
Screenshot 2024-02-13 at 8.38.01 AM.png (1.44 MiB) Viewed 407 times
Here they are viewed from below, showing hidden jigsaw connections.
Screenshot 2024-02-13 at 8.39.03 AM.png
Screenshot 2024-02-13 at 8.39.03 AM.png (1.62 MiB) Viewed 407 times

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 15th, 2024, 3:28 pm

I experimented with putting contours on the overcrowding cells, and it is feasible. The main advantage I thought of at the time was to make it easier to fill in the loneliness cells, which are usually more common around the boundary, at least for small still life patterns.

However, in the process, I found some contours for the loneliness tiles that fit well enough to build them ahead of time, and it is actually more trouble to use contoured overcrowding cells at this scale. Here is a public link to Tinkercad: https://www.tinkercad.com/things/9ERIDW ... life-tiles I use it by exporting pieces as STL to Flashprint. I may put something up on Thingiverse later.

Finally, here is a screenshot of the latest tiles.
Screenshot 2024-02-15 at 11.17.30 AM.png
Screenshot 2024-02-15 at 11.17.30 AM.png (1.95 MiB) Viewed 354 times

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 17th, 2024, 3:25 am

Now that I have a 3D printer, I truly appreciate how much work I was doing gluing layers of cardstock or making pieces from polymer clay. It takes about 5 minutes a piece (roughly and dependent on size) but I can do other things while it's happening. Here is https://conwaylife.com/wiki/Cis-block_on_long_bookend realized as a tiling.
20240216_231447.jpg
20240216_231447.jpg (3.41 MiB) Viewed 309 times

User avatar
otismo
Posts: 1201
Joined: August 18th, 2010, 1:41 pm
Location: Florida
Contact:

Re: Realizing still life constraints as a planar tiling

Post by otismo » February 17th, 2024, 11:22 am

"Realizing Still Life constraints as a Planar Tiling"

I just stumbled upon this thread and the way it struck me has led to

an entire ( "instant" ) thought process which I had better write down

whilst it is still crystal-clear, so here goes :

I can imagine the entire CGoL Universe as being totally filled up by

a single Still Life ( or a grid of many; Blocks for example ).

The flip side of this is 100 % plasma or fire, The FireCloud Universe.

A simple grid of Blinkers is not what I am thinking about here,

mainly because of that single cell in the center that is always on.

Finally, where we are now at in/re oscs-guns-conduits

is that a few still lifes and catalysts can do the job

of keeping the fire alive ( the reaction ).

The next step would be to use reaction sparks to stabilise reactions.

I posted this here because this thread gets the

Official OtismO Good Stuff for NewComers Seal of Approval.
"One picture is worth 1000 words; but one thousand words, carefully crafted, can paint an infinite number of pictures."
- autonomic writing
forFUN : http://viropet.com
Art Gallery : http://cgolart.com
Video WebSite : http://conway.life

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 17th, 2024, 1:01 pm

Well, I did work out the conditions for infinite still life patterns in which each 3x3 neighborhood has exactly 4 cells (1 live surviving with 3 or 1 empty, overcrowded by 4). See viewtopic.php?f=7&t=2036&start=1700#p86918 and viewtopic.php?f=12&t=4232&p=87547#p87015

I wrote the 2nd one before I had a Cricut (let alone a 3D printer) so maybe I should come up with a craft project for it. I could probably make something out of scrap cardboard, or if I want to be fancy, printing on overhead transparencies.

Post Reply