Archive for July 2017

 
 

“Triangular Life”

Recently I looked through a bunch of triangular cellular automata in which each (1) uses two states, (2) uses the simple alive cell count type of rule, and (3) uses the neighborhood around a cell c that is all the triangles that share a vertex with c; that is, the 12 shaded triangles below are the neighborhood around the yellow triangle:
12-cell triangular neighborhood
These cellular automata have state tables that can be thought of as 13 rows of 2 columns: there are 12 possible non-zero alive cell counts plus thee zero count and each of these counts can map to either alive or dead in the next generation depending on whether the cell in the current generation is alive or dead (column 1 or column 2). I looked at each of the 4096 cellular automata you get by filling the third through eighth rows of these state tables with each possible allocations of 0s and 1s and letting all other rows contain zeros.

A handful of these 4096 feature the spontaneous generation of gliders but one rule is clearly the triangular analog of Conway’s Life. I have no idea if this rule has been described before in the literature but it is the following:

On a triangular grid

  • If a cell is dead and it has exactly four or six vertex-adjacent alive neighbors then it alive in the next generation.
  • If a cell is alive and it has four to six vertex-adjacent alive neighbors, inclusive, then it remains alive in the next generation.
  • Otherwise it is dead in the next generation.

The above has a glider shown below that is often randomly generated and exhibits bounded growth.
Here it running in Jack Kutilek’s web-based CA player:

Tri Life gliders are slightly rarer than in Conway life because they are bigger in terms of number of alive cells in each glider “frame”. If you don’t see a glider in the above, stir it up by dragging in the window.

frames of the glider in cannonical triangular life

Rhombo

Over the past couple of weeks I wrote some code in C# to generate dissections of the rhombic triacontahedron into golden rhombohedrons. George Hart discusses these types of dissections here  and also talks about the problem of enumerating them in an appendix here — briefly, all this material by Hart and others is about how the fact that the rhombic triacontahedron and the rhombic enneacontahedron are zonohedra lead to both having interesting combinatoric properties which can be explored by coloring their dissections.

I was, however, more interested in how such dissections could be turned into an interlocking puzzle, akin to a traditional burr puzzle. amd as such needed code to generate 3D models of the dissections. My generation code is a dumb, constructive, brute force approach in which I just traverse the search space adding rhombohedrons to a candidate dissection in progress and backtracking when reaching a state in which it is impossible to add a rhombohedron without intersecting the one that was already added or the containing triacontahedron, keeping track of configurations that have already been explored.

Dissections of the rhombic triacontahedron into golden rhombohedrons (hereafter “blocks”) turns out to always need 10 and 10 of the two types of blocks that Hart refers to in the above as the “pointy” and “flat” varieties (and which I refer to as yellow and blue). Further it turns out that in all of these dissections there are four blocks that are completely internal, i.e. sharing no face with the triacontahedron; I also believe that the four internal blocks are always three blue and one yellow, but I’m not sure about that.

My strategy for finding an interlocking puzzle was the following:

  • Generate a bunch of raw dissections into blocks
  • For each dissection, search the adjacency graph for four pieces, the union of sets of five blocks, such that
    • Each piece forms a simple path in the dissection; that is, each block in the piece
      • is either an end block that is face adjacent to a next or previous block in the piece or is a non-end block that is face adjacent to a next block and a previous block.
      • and does not share any edges with other blocks in the piece except for the edges of the face adjacencies.
    • Each piece contains at least one fully internal block.
    • Each piece is “single axis disentangle-able” from each other piece, where we mean by that that there exists some edge e in the complete construction such that if given piece p1 and piece p2, if you offset p1 in the direction of  e by a small amount p1 does not intersect p2.
    • Each piece is not single axis disentangle-able from the union of the other three pieces.

I never managed to succeed in doing a complete enumeration, generating all of the dissections for reasons that I don’t feel like going into. (As I said above, I did not do anything fancy and it would be easier to just be smarter about how I do the generation than to make what I have more efficient; i.e. could have done the George Hart algorithm if I had known abouyt that or there are ways of transforming one dissection into another that I don’t do — I do an exhaustive search, period — but I never did the smarter stuff because I found what I was looking for, see below)

But from about 10 dissections I found one set of pieces that uniquely satisfies all of the above:

Here’s some video. (The individual blocks were 3D printed and super glued together)

I’m calling the above “rhombo”. Those pieces are rough because I only 3D printed the individual rhombohedrons and then superglued them together into the pieces, which is imprecise. I had to sand them heavily to get them to behave  nicely. I’ll eventually put full piece models up on Shapeways.

In the course of doing this work, it became apparent that there is no good computational geometry library for C# to use for something like this. There is one called Math.Net Numerics along with Math.Net Spatial that will get you vectors and matrices but not with all the convenience routines you’d expect to treat vectors like 3D points and so forth. What I ended up doing was extracting the vectors and matrices out of monogame and search-and-replacing “float” to “double” to get double precision. Here is that code on github. I also included in there 3D line segment/line segment intersection code and 3D triangle/triangle intersection code which I transliterated to C#. The line segment intersection code came from Paul Bourke’s web site. And the triangle intersection code came from running Tomas Moller’s C code through just a C preprocessor to resolve all the macros and then transliterating the result to C#.