A 3D tiling for Margolus neighborhoods using flat parts

For discussion of other cellular automata.
Post Reply
User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

A 3D tiling for Margolus neighborhoods using flat parts

Post by pcallahan » August 17th, 2021, 11:19 pm

This has been on my mind since the thread on realizing CGoL as a 3D tiling. As noted there, it is pretty easy to come up with tile sets for Margolus neighborhoods (Block Cellular Automata). For a 2-state rule with rotational symmetry (such as Critters or BBM) you only need six tiles. On the previous thread I proposed a way to make tiles using legos that would be 4x4 (32mm across) and simple to construct, but still expensive to make in large quantities.

I was thinking about how to do this using laser cutting. My most ambitious goal was to use only flat laser-cut pieces that would fit together as long as thickness was kept precise. I still think this is possible, but a more practical approach may be using two flat pieces per Margolus tile and gluing them together, top and bottom, so that the bottom would fit the groove in a previous layer and the top would create new grooves offset by diagonals in between the tiles (this will be clearer with a picture).

The pieces need to be 90° rotationally symmetric relative to the rules they represent, but unambiguous so you can't flip them and get a new rule. Ideally the tile set would not permit a piece to be fitted into another with a hidden gap (this may not be mathematically necessary in a tiling, but helps to avoid human error in placement). I state all this in an attempt to explain some of the shapes below. There might be something better, but I'm content with these for now. (Enough that I may put in a laser cut order once I'm convinced it works.)

This shows the six rules up to symmetry for Critters (the form in which "vacuum" oscillates between 0 and 1). From left to right are the transitions, shown with black and white squares, the outline of the bottom tile, the outline of the top tile, and my attempt at a 3D picture of what this could look like with a semi-transparent top tile (I used some Inkscape tricks to get these and I think the results are OK but I'm sure a CAD tool could do better).

The correspondence between the black and white squares and the tiles should be clear and is left as an exercise. Black and white (0 and 1 respectively) are represented using two different tile contours.

Finally on the right is an example of how a tile would fit into a groove going layer to layer.
g14571.png
g14571.png (92.62 KiB) Viewed 1459 times
I designed the tiles to be 20mm across. The circular holes are 6mm in diameter. These features are all safely above the feature size for laser cutting on many materials. Note that each CA cell is thus 1cm across, making it possible to set up fairly large grids given enough tiles.

The 12 shapes of tiles are "universal" for symmetric Margolus CA, but to get a particular CA rule, you have to glue them the right way. I think this is a pretty fast process, though obviously it is a manual step. Alternatively, I imagine a 3D printer could handle these shapes easily (but I have no experience with that and was really interested in what I could get by cutting).

Here's run through of the 4 steps of a Critters spaceship with tiles, i.e.:

Code: Select all

x = 3, y = 5, rule = critters
$bo$2bo$2bo$bo!
For clarity, I only show one layer of tile at each step. The black and white pictures below are intended to be more readable and also indicate the color of vacuum at each step.
rect6426-7-32.png
rect6426-7-32.png (54.84 KiB) Viewed 1459 times
A nice property of how these tiles fit together is that a single laser-cut sheet will contain both the top and bottom tiles without wasted material, except around the boundaries. It occurred to me that you could probably avoid gluing entirely, just to test out how some rules look. Simply lay out the tiles and after filling in gaps, look up the appropriate piece to layer on top of it.

A "proof of concept" would be a tile set that could be handed to someone who knew nothing about CA or Margolus neighborhoods and might be quite surprised to find contours moving around. It requires only a few tiles just to get a single spaceship through a full period. I think with several hundred tiles (since each has 4 CA cells) it might be feasible to build non-trivial oscillators without finding the process too tedious.

Update: For truly flat pieces without extra gluing rules, it should suffice to make pieces that can be rotated 90° from the plane to fit in holes that match tile thickness. This is problematic, because the pieces are small (or at least skinny) relative to the main tiles, but something like the following would allow unambiguous "receptor" holes to be cut through tiles, would not fall through, and would fill gaps completely. t is the tile thickness, and w is the smallest width we allow in the material (since it becomes very fragile otherwise). The gray rectangles show how holes would be cut into the main tiles to fit these pieces.
g1071-5.png
g1071-5.png (6.37 KiB) Viewed 1415 times
I think the process of fitting together tiles like this would be more tedious. We could relax the rule that space needs to be filled and produce more usable tiles but then it becomes harder to describe a valid tiling rigorously.

Update 2: To clarify, my original intent was to use s-shaped pieces like the above to form inputs and outputs on a single tile, though I got frustrated working out the spacing. Another idea is to combine them with the tiles above as virtual glue. Simply pick out the input and output tiles for your CA rule and place matching receptor holes on them. Then each transition is realized by placing a tile to fill in a gap, placing an appropriately size s-shaped piece in its hole, and matching it with the tile for the next layer. There may be simplifications, but in its most straightforward implementation, you would just need to add 6 new s-shaped pieces. So instead of any gluing instructions, the tile set itself would determine the rule.

Update 3: Here's a better 3D view of the tiles in tinkercad: https://www.tinkercad.com/things/ff8gb1ONEfb-margolus

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

Re: A 3D tiling for Margolus neighborhoods using flat parts

Post by pcallahan » August 20th, 2021, 12:50 pm

Pinging my thread after pricing laser cutting for these. I'm planning to use a material called "taskboard" because I got good results in another project. With a little trial and error, I found a way to lay out both kinds of tiles in all 6 configurations in the same cut.
Screen Shot 2021-08-20 at 9.36.11 AM.png
Screen Shot 2021-08-20 at 9.36.11 AM.png (202.6 KiB) Viewed 1382 times
The tan dots show "area engraving" which just means that the laser burns a mark instead of cutting. The dots are redundant based on the shape, but I think they would improve the experience of simulating a CA by hand. It also costs extra to add them, so I'm a little unsure it's worth it.

Ordering through Ponoko, the above costs $10.69 for one sheet, goes under $6.89 per sheet in quantities of 8 and is just a little over $4 ($4.03) for 100 sheets, though that's way more than I have any reason to order (without the dots, the price per sheet is $8.43, $5.65 and $3.22 respectively).

If this keeps up, maybe I will buy my own laser cutter. As I noted in an update to the previous thread, you can see what the Critters pieces look like glued together at this link https://www.tinkercad.com/things/ff8gb1ONEfb-margolus

I am not even sure if these are easy to 3D print because of the overhang. Maybe someone else knows.

Another thought: Suppose instead of glue, you made pieces that snap together like legos (just top tile to bottom tile). Then you'd have a toy for setting up any Margolus rule CA you like. This is beyond my fabrication abilities, but might even have a niche market, such as in an educational setting.

Update: For 3D printing, it is probably best to have two halves that snap together. I am not sure if this https://www.tinkercad.com/things/9Qck4a ... snap-tiles works in real plastic but something similar should. (I would also have to adjust tile sizes so pieces fit into gaps.)

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

Re: A 3D tiling for Margolus neighborhoods using flat parts

Post by pcallahan » September 4th, 2021, 4:07 pm

I ordered these as a laser cut from Ponoko. I used coasterboard (cardboard designed for drink coasters) instead of taskboard (a wood pulp board for prototyping) because it was slightly less expensive and had the same thickness. It seems good enough. Here is the sheet I received of cut pieces, each 2cm on a side. It's enough to make 96 Margolus 2x2 window transitions by gluing them together.
20210902_122432.jpg
20210902_122432.jpg (550.3 KiB) Viewed 1262 times
Gluing took some time, but not much skill. You just need a single dot of white glue (like Elmer's). Get the alignment right before it dries, and then they hold together very well (so far).

This is the sequence of transitions needed to move a Margolus "critter" (spaceship) 2 cells right. As in the original formulation of the rule, the vacuum oscillates between 0 and 1. Each step shows the piece that would be applied for all cells not shown explicitly, assumed to be vacuum. I applied some explicit vacuum transitions if they were neighboring the pattern. (Since it's missing vacuum, I had to prop up some pieces underneath, but with a lot of tiles it could be done more simply.)
sequence.png
sequence.png (1.63 MiB) Viewed 1262 times
You can verify in this picture that step 5 has the same state and next transition as step 1, but shifted 2 cells right. Two notes: the dots show the previous generation, so to read the state, you should really look at the shape of the dents, though it's a bit painful. Also, since most of the vacuum is omitted, you may see some dots from past states at each generation. However, the number of non-vacuum cells is conserved at 4, as expected.

Addendum: With regard to gluing, I first put a lot of pieces together freehand, checking alignment visually. The gaps can be off by a fractional millimeter and still usable. However, I eventually got dissatisfied with my imprecision and realized I had what I needed to build a frame to align the tiles properly. One side of the cut material aligns with the lower pieces, and these can be fit back into the cut-out in different ways (not necessarily the original way). After measuring the distance to the edge of the upper piece, I taped on another piece of cardboard to align these at the top. Fitting them together, they align horizontally, assuming the first is aligned. If I do this again, I will build a better frame before gluing any tiles. It was less frustrating and produced better results than freehand gluing.
20210904_091750.jpg
20210904_091750.jpg (68.42 KiB) Viewed 1248 times

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

Re: A 3D tiling for Margolus neighborhoods using flat parts

Post by pcallahan » September 5th, 2021, 2:37 pm

I was thinking of how to store these tiles compactly after making 96 of them, and I realized that the CA transition rule itself provides the answer. The 0-cell block neighborhoods alternate with 4-cell block neighborhoods (vacuum) and these can be packed together like this:

Code: Select all

x = 8, y = 8, rule = critters:T8
!
It is just shown as empty because LiveViewer adjusts for alternating vacuum.

Similarly, 2-cell block neighborhoods can be handled with the two kinds of 2-cell transitions:

Code: Select all

x = 8, y = 8, rule = critters:T8
o2b2o2bo$b2o2b2o$o2b2o2bo$b2o2b2o$o2b2o2bo$b2o2b2o$o2b2o2bo$b2o2b2o!
This appears to alternate in LifeViewer, but would be a static pattern in the rule with alternating vacuum.

Finally, the 1- and 3-cell block neighborhoods also fit together:

Code: Select all

x = 8, y = 8, rule = critters:T8
$bobobobo2$bobobobo2$bobobobo2$bobobobo!
Again, because of the vacuum-adjusted rule, we see only 1-cell neighborhoods, but the odd generations (starting with 0) are 3 cells in the original rule.

To pack these, pick one kind of transition and place 4 tiles in a 2x2 pattern. Next take its complementary transition and snap it into place in the middle, adding 4 more left and right, above and below, hanging over the original layer. Continue with 4 until you have layers of 4, 5, 4, 5, 4, 5, and 4 tiles. There's now 1 tile left out of 16 of the second type. Snap that in place in the middle. It's a surprisingly stable structure even on glued cardboard. I bet it would work even better with high-precision injection-molded plastic like legos:
20210905_110025.jpg
20210905_110025.jpg (85.91 KiB) Viewed 1209 times
Crazy thought: Could you synthesize 6 different molecules that have these packing characteristics? If so, would they spontaneously form quasicrystals that followed Margolus CA rules? (one for the nanotech enthusiasts, if we have any, also perhaps fans of Greg Egan's Diaspora with its Wang Carpets, though I will forgo asking whether consciousness could emerge in these quasicrystals).

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

Re: A 3D tiling for Margolus neighborhoods using flat parts

Post by pcallahan » October 20th, 2021, 6:37 pm

Update: Never mind. I'm not sure what I was thinking here. There is still nothing to prevent removing a sheet from the assembled clip. (Shows the limits of my visualization ability.) If the clip can extend beyond the sheet, then it works, but my goal is to keep the surfaces flush. A small gap would be acceptable, but not a bump. I suppose it is impossible, because the holes go through both sides of the sheet identically and the sheet can slip off no matter which way a connecting piece entered.

Another thought: the pieces could be tapered so friction gradually increased to where the piece can be pushed flush with the slot but would require a lot of force to push through. I prefer geometry to friction, but maybe that could be make to worth with some experimentation.

The following is mostly true, but the pieces would still have to extend beyond the acrylic slot on the outer surface, once snapped into place, and would leave a bump:

I have started to wonder if there is a way to laser cut Margolus tiles out of plastic and snap them together. A 3D printer could do it, but I was puzzled over how to do it with flat parts. I think this geometry works, though it may not be practical. The clips are intended to be 1.5mm thick and the sheets (shown only as sections around the clip holes) are 3.5mm thick. I am thinking of delrin for the clips and acrylic for the sheets. You would keep pushing the clips until the knobbed ends bend apart and then snap in the gap on the other side.

The holes in the acrylic are crosses with one dimension longer than the other, but turned 90° so you can't slip the entire assembly through.
Screen Shot 2021-10-20 at 3.14.02 PM.png
Screen Shot 2021-10-20 at 3.14.02 PM.png (1.88 MiB) Viewed 1001 times
There are a lot of plans for clipping together laser-cut acrylic at angles, but I could not find anything for sandwiching together two tiles as I would like to do. For a little while I thought it might be impossible or the best I could manage was a friction fitting (which honestly still might be preferable for this application: just size an acrylic rectangle (about 3mmx6mm and ~3mm thickness), taking kerf into account, and force into place during assembly.

Update: 32 can be packed like this for laser cut. One sheet on 1.5mm black or white delrin is $5.93 for Ponoko, but it comes down in quantity. Note that two pins would needed to attach a pair of Margolus tiles. It's probably worth doing a small proof of concept order, maybe with different sizes and different plastic. I don't see why it wouldn't work unless the plastic can't bend enough on that 1mm thick section.
Screen Shot 2021-10-20 at 5.56.08 PM.png
Screen Shot 2021-10-20 at 5.56.08 PM.png (387.78 KiB) Viewed 955 times
Update 2: As designed, I think it would fail to attach the acrylic tiles, because the shorter slot does not leave any room for the clip to bend open. It might still work if the slot is made long enough to accommodate the clip opening, but too short for the long part to fit.

Update 3: This idea looks a little more practical. Only one side needs to be flexible. The other simply catches it. Now the flexible arms have a lot more play, and an added advantage is that one side has a single slot that at least in theory can be completely flush with the tile. I have some other applications for clipping together acrylic tiles and this should improve the appearance.
Screen Shot 2021-10-20 at 9.40.49 PM.png
Screen Shot 2021-10-20 at 9.40.49 PM.png (3.07 MiB) Viewed 939 times

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

Re: A 3D tiling for Margolus neighborhoods using flat parts

Post by pcallahan » October 26th, 2021, 3:16 pm

Here is yet another flat-part Critters tiling. I don't think I will bother trying to make this because it looks really tedious to assemble. In fact, I was trying to come up with this in August but I missed the obvious somehow. What it does is to represent bits using rectangular slots that can be filled with small perpendicular tiles (shown in red). The slots have two orientations, either parallel to the square diagonal (representing 1) or perpendicular (representing 0).
Screen Shot 2021-10-26 at 11.59.18 AM.png
Screen Shot 2021-10-26 at 11.59.18 AM.png (1.1 MiB) Viewed 870 times
Assume you start with one layer that is built by placing the small red tiles in the outside (output) slots and ignoring the inside (input) slots (which may be thought to be filled in below going out to infinity). Now you need to place another layer of tiles to fill up slots with the protruding red tiles. You do this by centering the tile at a place where 4 corners meet at the previous layer. This leaves alternate slots open, and you fill them with the red tiles and continue.

As designed, this does not prevent placing a new tile directly on top of the previous layer instead of at the corners. This is fixable by tapering the red tiles and maybe some other way I haven't thought of. A single placement determines how the whole layer is placed. I believe that it would be possible to use this as a feature to carry out the steps in reverse, but I might think a little harder about eliminating it.

Finally, if we're not limited to flat tiles, the basic idea of holes in the middle and bumps on the outside would be a way to design Margolus tiles for 3D printing. In this case, the bits could be made more visually obvious (my head spins a little trying to keep track of 0s and 1s by orientation alone).

Update: If you drop the "flat parts" condition, I think you get a more intuitive set of tiles. The example shows the first transition of a Critters glider. It would be clear to any observer that 4 of the bumps are always different from background and propagate in one direction. (Update 2: I doubled the vertical dimension for clarity.)
Screen Shot 2021-10-27 at 8.18.50 AM.png
Screen Shot 2021-10-27 at 8.18.50 AM.png (2.98 MiB) Viewed 814 times

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

Re: A 3D tiling for Margolus neighborhoods using flat parts

Post by pcallahan » June 8th, 2022, 5:58 pm

I planned to write a longer update about this, but I don't think I'll take this technique any further, though I like the idea. I am using a Cricut die cutter to cut pieces of Cheerios box cardboard into two layers that can be glued to emulate a Margolus transition rule, in this case Critters. It's the same idea I used for the laser cut, but I had to modify the shapes a little and increase the size to cut them reliably with a die cutter. I made enough pieces to get the four phases of a Critters spaceship and also show some background.
20220608_143534.jpg
20220608_143534.jpg (176.21 KiB) Viewed 409 times
I was even able to get two colors, because there is enough blank yellow space on a box of Cheerios that you can cut them out of just that part. (But yeah, it's kind of tedious.)

The other improvement is that I cut out a starting generation sheet that accepts either shape. This is sort of usable (you have to fidget and smooth out pieces) and almost fun, but the big problem is it's not readable, or at least I find it really hard to see patterns in the yellow shapes. I still have the goal of prototyping Margolus blocks. If these were produced as well as Legos, I think there would be some interest, not necessarily because many people care about reversible CA, but because simply starting with any initial layer of blocks would produce endless and fairly unpredictable patterns, while other arrangements such as periodic layouts would continue with symmetry. It would help to add more color.

Post Reply