Realizing still life constraints as a planar tiling

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

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » January 14th, 2020, 2:57 am

Another idea is to forget about the octagons entirely and use these 6 domino-like tiles, assuming the user is able to count.
Screen Shot 2020-01-13 at 10.39.15 PM.png
Screen Shot 2020-01-13 at 10.39.15 PM.png (23.57 KiB) Viewed 1731 times
These must be placed so colors of squares and red boundaries meet. Each corner square contains a number of dots equal to the number of black corner squares in the next two corners going clockwise. So when the tiles are placed, the dots give a quick visual indication of the number of neighbors.

This shows a block, a ship, a beehive, and and eater. It is easy to see that every black square contains two or three dots, and no white square contains exactly three dots. The tile without any dots is not really needed here but it can be placed around the boundaries.
Screen Shot 2020-01-13 at 10.39.47 PM.png
Screen Shot 2020-01-13 at 10.39.47 PM.png (111.28 KiB) Viewed 1731 times
The tiles can be contoured to force the squares to line up by color, but the user is responsible for enforcing the cell counts.

I think if these were made with heavy enough material, like dominoes or mahjongg tiles, they might actually be fun to work with. I can only guess since I had to do it in Google draw. Another point is that they don't enforce any totalistic rule or the still-life property, so they could be used to set up and visualize the next step of any totalistic rule including life.

The disadvantage, of course, is that there is a brain involved in the process, if minimally. You would not be able to get a still life by some process of shaking the tiles together or translate it into a molecular computer. I wonder if these could be the basis of an actual game, e.g. pick some tiles randomly and build a still-life for points.

Update: we can make the counting automatic (e.g.) by clipping the corners off the above tiles and turning them into octagons. Then we can fill in the gaps with tiles that enforce the count. I am not sure if this results in a smaller tiling than the original one in this thread. At some point, the question is just whether the tiles vary too much in size to be usable.

Update 2: The same tile set with interlocking boundaries to force colors.
Screen Shot 2020-01-14 at 10.00.31 AM.png
Screen Shot 2020-01-14 at 10.00.31 AM.png (47.35 KiB) Viewed 1704 times
Note that this tile set can be used for assembling non-stable Life patterns too. I think I've hit my attachment limit on this post, but by assembling three blocks in a row, you can see that two white squares above and below have a count of three (birth) and two black squares on the ends each have only one neighbor and will die.

pcallahan
Posts: 487
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » January 15th, 2020, 11:48 pm

Note that we can turn this into an automatic still life tiling by moving slightly into 3D. The idea is sketched below (and I emphasize it's just the idea, not a complete construction).
Screen Shot 2020-01-15 at 7.30.57 PM.png
Screen Shot 2020-01-15 at 7.30.57 PM.png (89.88 KiB) Viewed 1660 times
The dots can be placed so that they have octagonal symmetry. "Color" the dots in a quadrant in clockwise order according to the two following quadrants, also in clockwise order. But instead of using colors, use bumps and dents. Now when the tiles are placed, the four quadrants incident to the same corner will form a symmetric octagon of bumps and dents representing neighbor counts. The semi-transparent blue octagons would have complementary bumps and dents so they can only be placed on a matching neighborhood, but may be rotated.

We could support flips I guess by having bumps and dents on both sides, but if one side is flat any we're limited to rotations, we have:

For live cells, counts 2 and 3, for 4+7 = 11 octagons total.
For dead cells, counts 0, 1, 2, 4, 5, 6 for 1+1+4+10+7+3 = 26 octagons total.

Note that there are only 3 neighborhoods of 6 cells, because one of them causes internal overcrowding and doesn't work for a still life.

So that gives us 37 octagons and 6 squares for 43 distinct pieces, ignoring the previous ways of splitting up octagon neighborhoods. This is not conceptually any better than the pure 2D tiling, but it could be easier to work with because the pieces are all about the same size.

The above is mainly for completeness, because I think that inspecting the dots visually may be adequate for using this as a puzzle and it really reduces the tile count by a lot, besides being more generalizable.

Update: A visual approach with octagonal symmetry, using "flower petals."
Screen Shot 2020-01-16 at 12.06.09 AM.png
Screen Shot 2020-01-16 at 12.06.09 AM.png (112.91 KiB) Viewed 1642 times
Update 2: A mildly amusing aside (at least I find it so). After making these 6 tiles in Google draw, I decided to construct all rotations ahead of time to aid in making patterns out of them. 24 rotations I thought? Wait, no, some are symmetric and have duplicates. I went through the process of eliminating duplicates and was surprised that the result was a nice number like 16. It took me about a day to realize that obviously there are 16 2x2 bitmap patches before you start reducing the set with rotational symmetry. I completely forgot since I had been treating them as geometric objects so long.

Here's a link to the a drawing document with the tiles if anyone wants to copy it and try it out. https://docs.google.com/drawings/d/18aF ... lLdJs/view

Update 3 An alternative to matching dots to two chosen neighbors would be to match all three neighbors in each 2x2 grid by splitting the dots across boundaries. So one dot counts the diagonal, and each half dot counts the horizontal or vertical neighbor. This could be used to replicate the actual neighbors with correct spacing inside each assembled tile, sometimes talking a half dot each from adjoining quadrants. I might try to make some tiles like that, but I'm a little reluctant to split something that is already small. I think the petal design makes the neighbor connections very clear.

Update 4 Here's the split-dot solution if my comments above weren't clear. I did not try to add jigsaw contours, but this shows the idea. Now the dots in each compound cell form an exact image of the live neighbors around it. I think that's an interesting property and could help for non-totalistic rules, but I still prefer the flower petals.
Screen Shot 2020-01-16 at 9.22.50 PM.png
Screen Shot 2020-01-16 at 9.22.50 PM.png (41.55 KiB) Viewed 1604 times

pcallahan
Posts: 487
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » January 28th, 2020, 3:24 pm

Revisiting the tiles (e.g. here) I noticed that there is another way to get symmetry besides octagons, which increases symmetry and I think results in more intuitive tiles as well, since the Moore neighborhood is not really an octagon.

If we continue to treat cells as squares and count neighbors by quadrant, the quadrants with one neighbor can be treated identically (unlike with octagons). Specifically, take this cell neighborhood:

Code: Select all

a b c
d e f
g h i
Arbitrarily grouping neighboring cells (there are two choices) we count the neighbors in quadrants clockwise around the center e as b+c, f+i, h+g, d+a. By doing this, a given neighborhood is represented as a cycle of values in {0, 1, 2}. E.g. (0, 1, 2, 0) is a neighborhood in which b+c=0, f+i=1, h+g=2, and d+a=0. The total count is 3 so birth or survival occurs in cell e.

If we represent these neighbors as tiles with boundaries, allowing flips and rotations, we can reduce the number of neighborhoods by a lot. In fact, treating 0+1 and 1+0 the same in each quadrant results in more reduction than maintaining 0-1, 1-0 order around an octagon.

For still lifes, we can also rule out tiles with 7 or 8 neighbors total, since they are internally overcrowded, as well as 6 neighbors grouped as (0, 2, 2, 2) for the same reason.

Here is the complete set of 27 tiles. Black tiles are live. White tiles are dead. Light blue tiles go in-between.
tiles.png
tiles.png (43.13 KiB) Viewed 1544 times
This is kind of a lot but not crazy (note that the game Blokus uses 21 distinct pieces for each player for a total of 84). No doubt we could reduce the number with some splitting rules, but I think that harms the usability of physical tiles.

(Assume for now you can't link black and white tiles directly. I can fix that by tweaking contours. It may not matter anyway. You can chain together 2-neighbor black and white tiles but you can't tile the plane with them.)

Like the previous construction, the in-between tile represent 2x2 windows. These tiles have a zig-zag where they join so they cannot be flipped relative to each other (which would reverse the count of cells around the quadrants and change the meaning). For handling, it's preferable if the tiles are about the same size, though admittedly the in-between ones are bigger than the cells (in the very first from 2016, they were smaller, and this is adjustable).

Here's the eater done with these tiles:
eater.png
eater.png (54.15 KiB) Viewed 1544 times
And here's the block on table:
b_on_t.png
b_on_t.png (67.32 KiB) Viewed 1544 times
I'm still working on the best contours. I just used polygon points that I found by trial and error, and then rotated them around a square. If I get ambitious, I can use bezier curves for more of a jigsaw puzzle effect.

Note: this opens up the possibility of making stackable tiles for computing Life generations. These would require some additional surface features (and get a little tricky if you wanted to make them flippable). I am skeptical that this would be a fun activity for human beings, but still life construction is essentially a jigsaw puzzle, so it has more potential.

A link to 27 transparent PNGs of tiles on Google drive: https://drive.google.com/drive/folders/ ... sp=sharing

Finally, here's a python script that creates the PNGs in imagemagick.

Code: Select all

import math

WIDTH = 50
HEIGHT = 200 / math.sqrt(2) - WIDTH

def rotation(theta):
  cosv = math.cos(math.radians(theta))
  sinv = math.sin(math.radians(theta))

  def rotate(pair):
    x, y = pair
    return (round(cosv * x - sinv * y, 12),
            round(sinv * x + cosv * y, 12))

  return rotate

def scaling(r):
  def scale(pair):
    x, y, = pair
    return x * r, y * r
  
  return scale

W2 = WIDTH-25
H2 = HEIGHT-25

def flip(pair):
  x, y = pair
  return x, -2 * H2 - y

def to_svg(origpath, r = 1.0):
  path = list(map(scaling(r), origpath))
  return " ".join(["M %5.3f, %5.3f" % path[0]] +
                  ["L %5.3f, %5.3f" % pair for pair in path[1:]] +
                  ["Z"])

PATH1 = [(-W2, -H2), (-8, -H2), (-12, -H2 - 20), (12, -H2 - 20), (8, -H2), (W2, -H2)]
PATH2 = [(-W2, -H2), (-15, -H2), (-25, -H2 - 25), 
         (-8, -H2 - 30), (-8, -H2 - 18), (8, -H2 - 18), (8, -H2 - 30),
         (25, -H2 - 25), (15, -H2), (W2, -H2)]
PATH1F = list(map(flip, PATH1))
PATH2F = list(map(flip, PATH2))
EMPTY = [(-W2, -H2), (W2, -H2)]

PATHS = [[EMPTY, PATH1, PATH2],
         [EMPTY, PATH1F, PATH2F]]

COLOR = ["white", "black"]

def tile_path(quadrants):
  result = []
  for i in range(4):
    count = quadrants[(i + 1) % 4] + quadrants[(i + 2) % 4]
    tooth = ([(-WIDTH, -HEIGHT)] + PATHS[quadrants[i]][count] + 
             [(WIDTH, -HEIGHT), (WIDTH + 16, -HEIGHT + 9), (HEIGHT - 16, -WIDTH - 9)])
    result.extend(map(rotation(90 * i - 45), tooth))
  return result

def cell_path(state, quadrants):
  result = []
  for i in range(4):
    path = [(x, -HEIGHT - WIDTH - y) for x, y in PATHS[state][quadrants[i]]]
    tooth = [(-WIDTH, -WIDTH)] + path + [(WIDTH, -WIDTH)]
    result.extend(map(rotation(90 * i - 45), tooth))
  return result

def pattern(x, y, grid, scale, size):
  lines = []
  lines.append("-stroke none")
  for i in range(len(grid)): 
    for j in range(len(grid[i])): 
      color = COLOR[grid[i][j]]
      lines.append("-fill %s -draw 'rectangle %s %s %s %s'" % (color, 
                                                               x + j * size - size, y + i * size - size,
                                                               x + j * size, y + i * size))
  lines.append("-fill lightblue -stroke gray")
  for i in range(len(grid) - 1): 
    for j in range(len(grid[i]) - 1): 
      quadrants = (grid[i][j], grid[i][j + 1], grid[i + 1][j + 1], grid[i + 1][j])
      lines.append("-draw 'translate %d, %d path \"%s\"'" %
                   (x + j * size, y + i * size, to_svg(tile_path(quadrants), scale)))
  return lines

def all_cells():
  result = {}
  
  for a in range(3):
    for b in range(3):
      for c in range(3):
        for d in range(3):
          forward = (a, b, c, d)
          reverse = forward[::-1]
          canonical = min(
            min(forward[-i:] + forward[:-i] for i in range(4)),
            min(reverse[-i:] + reverse[:-i] for i in range(4)))
          if forward == canonical and sum(forward) <= 6:
            result.setdefault(sum(forward), []).append(forward)

  return result

lines = ["magick -size 700x600 canvas:none -fill lightblue -stroke gray"]

x = 70
y = 70
for a in range(2):
  for b in range(2):
    for c in range(2):
      for d in range(2):
        quadrants = (a, b, c, d)
        if quadrants == min([quadrants[-i:] + quadrants[:-i] for i in range(4)]):
          lines.append("-draw 'translate %d, %d path \"%s\"'" % (x, y, to_svg(tile_path(quadrants), 0.5)))
          x += 110

by_count = all_cells()

x = 70
y = 200
state = 1
for count in [2, 3]:
  for quadrants in by_count[count]:
    lines.append("-fill %s -draw 'translate %d, %d path \"%s\"'" % (COLOR[state], x, y, to_svg(cell_path(state, quadrants), 0.5)))
    x += 110

x = 70
y += 110
state = 0
for count in [0, 1, 2]:
  for quadrants in by_count[count]:
    lines.append("-fill %s -draw 'translate %d, %d path \"%s\"'" % (COLOR[state], x, y, to_svg(cell_path(state, quadrants), 0.5)))
    x += 110

x = 70
y += 110
state = 0
for count in [4]:
  for quadrants in by_count[count]:
    lines.append("-fill %s -draw 'translate %d, %d path \"%s\"'" % (COLOR[state], x, y, to_svg(cell_path(state, quadrants), 0.5)))
    x += 110

x = 70
y += 110
state = 0
for count in [5, 6]:
  for quadrants in by_count[count]:
    if quadrants != (0, 2, 2, 2):
      lines.append("-fill %s -draw 'translate %d, %d path \"%s\"'" % (COLOR[state], x, y, to_svg(cell_path(state, quadrants), 0.5)))
      x += 110
lines.append("tiles.png")
print(" \\\n").join(lines)

lines = ["magick -size 600x600 canvas:none -fill lightblue -stroke gray"]
eater = [
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 0],
  [0, 0, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 0],
  [0, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0]]

lines.extend(pattern(100, 100, eater, 0.5, 100))
lines.append("eater.png")
print(" \\\n").join(lines)

lines = ["magick -size 600x700 canvas:none -fill lightblue -stroke gray"]
block_on_table = [
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 0],
  [0, 0, 0, 1, 1, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 0],
  [0, 1, 0, 0, 1, 0],
  [0, 0, 0, 0, 0, 0]]

lines.extend(pattern(100, 100, block_on_table, 0.5, 100))
lines.append("b_on_t.png")
print(" \\\n").join(lines)

Last edited by pcallahan on February 12th, 2020, 2:42 pm, edited 2 times in total.

hkoenig
Posts: 125
Joined: June 20th, 2009, 11:40 am

Re: Realizing still life constraints as a planar tiling

Post by hkoenig » January 28th, 2020, 6:04 pm

(skipping over the recent posting)

I like the split dots better. With the petals, it isn't entirely obvious which quadrants are contributing. The split dots show that orthogonally, it takes two tiles to contribute, but only one diagonally.

pcallahan
Posts: 487
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » January 28th, 2020, 6:29 pm

hkoenig wrote:
January 28th, 2020, 6:04 pm
(skipping over the recent posting)

I like the split dots better. With the petals, it isn't entirely obvious which quadrants are contributing. The split dots show that orthogonally, it takes two tiles to contribute, but only one diagonally.
I agree that it's a more faithful rendering of the neighborhood, and in that sense is a better visualization. I still like the petals but that's purely a matter of personal preference.

pcallahan
Posts: 487
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » January 30th, 2020, 12:05 pm

hkoenig wrote:
January 28th, 2020, 6:04 pm
(skipping over the recent posting)

I like the split dots better. With the petals, it isn't entirely obvious which quadrants are contributing. The split dots show that orthogonally, it takes two tiles to contribute, but only one diagonally.
Here's another variation, and maybe it's the right one for purists. All it does is duplicate the 2x2 neighborhood in each quadrant, but with an appropriate rectangle on boundaries so everything adds up to squares when placed. Each cell bounded by grid lines is a complete representation of the neighborhood. Shown here with block and eater.
Screen Shot 2020-01-30 at 7.51.58 AM.png
Screen Shot 2020-01-30 at 7.51.58 AM.png (39.93 KiB) Viewed 1494 times
This is starting to look way too much like the way I've actually implemented neighborhoods in some programs. I wonder if anyone else has presented the tiles in this form before. I'm surprised I got side-tracked with octagons before doing this.

As a visualization, it might satisfy those reasonably familiar with Life. I think it is a lot for a novice to absorb at once. Also, I think I'd get a headache if I tiled my floor this way.

There should be enough room for jigsaw contours as long as they only go 1/8 of the way into each tile.

Update: I like this variation better, shrinking the quadrants into corners and leaving space to show the original pattern cells.
Screen Shot 2020-01-30 at 10.20.03 AM.png
Screen Shot 2020-01-30 at 10.20.03 AM.png (37.5 KiB) Viewed 1484 times
Update 2: The more I look at the above, the more I like it. It seems to function as training wheels to learn how to just run these patterns on paper or in your head (which I believe some of the "gods of old" are able to do). It does not make it quite as easy as counting dots or petals. E.g., it threw me for an instant when that white "glider" showed up in the eater before I realized it represents the 5 dead cells in the neighborhood. There is a little more memorization to do in order to verify still lifes visually, but in the process, you actually get a better sense of how to see the neighborhoods without any annotations.

The second set also leaves a lot of space for jigsaw contours. I am still thinking in terms of a game. Possibly the all-blank tile should just be omitted. Is there a way you could score or compare patterns like poker hands?

Update 3: (and seconds later) Scrabble! The tiles can have the overall feel of Scrabble pieces, except larger and perfectly square. The jigsaw edges might be unnecessary. Unlike Scrabble, the determination of valid patterns would not be dictionary dependent. We don't necessarily need to limit it to still lifes as long as there is some way to score neighborhoods.

mniemiec
Posts: 1106
Joined: June 1st, 2013, 12:00 am

Re: Realizing still life constraints as a planar tiling

Post by mniemiec » January 30th, 2020, 6:48 pm

pcallahan wrote:
January 30th, 2020, 12:05 pm
Update: I like this variation better, shrinking the quadrants into corners and leaving space to show the original pattern cells.Screen Shot 2020-01-30 at 10.20.03 AM.png

Update 2: The more I look at the above, the more I like it. It seems to function as training wheels to learn how to just run these patterns on paper or in your head (which I believe some of the "gods of old" are able to do). It does not make it quite as easy as counting dots or petals. E.g., it threw me for an instant when that white "glider" showed up in the eater before I realized it represents the 5 dead cells in the neighborhood. There is a little more memorization to do in order to verify still lifes visually, but in the process, you actually get a better sense of how to see the neighborhoods without any annotations.

The second set also leaves a lot of space for jigsaw contours. I am still thinking in terms of a game. Possibly the all-blank tile should just be omitted. Is there a way you could score or compare patterns like poker hands?
I like these tiles; it only took me a few seconds to see how they fit together (with the 3x3 neighborhoods being shown in miniature in the center of each square). Jigsaw contours on the cell boundaries could be used to enforce creating only valid combinations of adjacent tiles (e.g. putting 2 next to 3 would be syntactically correct, rather than merely semantically incorrect), but aren't strictly necessary if you trust the user to enforce this rule by eye. On the other hand, I though the whole point of this exercise was to produce a set of files that can produce all valid Life still-lifes, and no patterns that aren't still?

I can see how this will produce all valid patterns and only valid patterns, but as it appears to be rules-agnostic, it won't exclude non-still-lifes. It is pretty, though. On the other hand, if you only want to show valid patterns, you could just use the first two tiles, and the we're back to how Life has been represented on square grids from the beginning.

pcallahan
Posts: 487
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » January 30th, 2020, 7:26 pm

mniemiec wrote:
January 30th, 2020, 6:48 pm
I can see how this will produce all valid patterns and only valid patterns, but as it appears to be rules-agnostic, it won't exclude non-still-lifes. It is pretty, though. On the other hand, if you only want to show valid patterns, you could just use the first two tiles, and the we're back to how Life has been represented on square grids from the beginning.
You're right that this is a detour from actually enforcing still life rules. I was thinking about hkoenig's preference for the split dots and trying to take that to its logical conclusion. But these could be turned into 3D still life tiles by having bumps and dents in the mini-neighborhoods and providing a limited set of caps that fit over only the ones consistent with still life patterns. (But you can't do it until you pull them into neighborhoods, or the caps would overlap, unless I'm missing something) There isn't enough symmetry to create a small set of caps, but it would be a valid construction.

What I actually see in this case is a way to enhance human pattern-matching. I do see more when the neighborhoods are collected than when the patterns are presented the normal way with two colored tiles. If I have to, I can force myself to see neighborhoods, but there's some effort involved. The set of neighborhoods consistent with still lifes is also small enough to memorize pretty easily as a short-cut to counting (i.e. there would be a lot of injected-molded caps to make, but I think they fit into the brain very well: there are a lot fewer than Chinese characters for instance).

But aside from practical importance or direct relevance to the original thread, I thought this made a very striking visualization of neighborhoods.

Update: Instead of having a custom cap for every neighborhood, I wonder how far you could make it with some very simple lego-like pieces to snap on top in layers and reduce the number of possibilities. I know simsim314 worked on something like this, so my idea might not be new. What if you had four pieces that could be snapped over any two adjacent bumps/dents. If they're both the same, it keeps them unchanged. Otherwise, you can take adjacent (0,1) depending on the piece, either keep them order (0, 1) or swap to (1, 0). Over enough applications, the neighborhood can be put in canonical form and tested with just a few tiles. It's a bit tedious, but the tile count might be very small. So far, it's 10.

Update 2: I wonder if we can get by with just (0, 0) -> (0, 0), (1, 1) -> (1, 1), and (0, 1) -> (1, 0). That is, find a "domino" covering of bits for which bits always swap if two adjacent domino are different. If we're limited to just the 8 neighbors around the center, we're limited by the fact that an alternating 0-1 pattern with count 4 would alternate each layer. But maybe we could add some bits in the neighborhood that are initially zero. This is getting far from practicality, but it's a puzzle.
Last edited by pcallahan on January 30th, 2020, 9:43 pm, edited 2 times in total.

hkoenig
Posts: 125
Joined: June 20th, 2009, 11:40 am

Re: Realizing still life constraints as a planar tiling

Post by hkoenig » January 30th, 2020, 9:01 pm

pcallahan wrote:learn how to just run these patterns on paper or in your head (which I believe some of the "gods of old" are able to do)
Back before computers, I did use up lots of graph paper (and erasers were cheaper than new paper). Still have some of that around here somewhere. At some point it did become unnecessary to count neighbors, just recognize the patterns.

And the smaller bits looks better to me. A thin frame of a third color around them would help offset the neighbor pattern from the center of the bit.

pcallahan
Posts: 487
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » January 31st, 2020, 7:18 pm

hkoenig wrote:
January 30th, 2020, 9:01 pm
Back before computers, I did use up lots of graph paper (and erasers were cheaper than new paper). Still have some of that around here somewhere. At some point it did become unnecessary to count neighbors, just recognize the patterns.
I had an early TRS-80 computer before I ever heard of Life, so I never had to use graph paper. I am not sure I would have had the patience for it. I probably have more patience now and sometimes like working things out on paper but often go with "virtual paper" like Google draw. But having manipulatives like tiles is also fun (maybe I need to open up a new kind of Montessori school and find parents willing to test these things out on their kids).

I also wanted to get back to this.
mniemiec wrote:
January 30th, 2020, 6:48 pm
I can see how this will produce all valid patterns and only valid patterns, but as it appears to be rules-agnostic, it won't exclude non-still-lifes.
As I said, the concentrated neighborhoods could be made into bumps and dents. True, we are no longer talking about a planar tiling. You get a lot of different patterns of bumps and dents that have the same count, and that's a problem. I noticed a general way to put them in canonical form with just two new pieces. Let's say the dent is one unit deep and the bump is one unit high. They are squares and adjacent around the neighborhood (the middle has a different shape to match a cap piece). Use these two pieces:
  • A square of thickness w+2 that fits into a dent (w is arbitrary but chosen to avoid coincidences in stacking).
  • A domino of two joined squares, one of thickness w and the other of thickness w+4, aligned at their central planes.
The picture below shows the idea in cross-section. Given a series of adjacent dents and bumps (linear here but they could be around a ring) You use the square to move a value up unchanged, and use the domino to swap two adjacent values and move a bump. In this case, the original blue pattern is canonicalized to two bumps at the right through successive operations (and maybe this could be used to reduce a planar tiling too, but I'm not sure how to go outside to inside).
Screen Shot 2020-01-31 at 2.32.09 PM.png
Screen Shot 2020-01-31 at 2.32.09 PM.png (77.65 KiB) Viewed 1425 times
(Open: does this admit unwanted tilings? If so, I believe it's fixable.)

In practice, this would result in a tedious process of dropping in tiny bits of plastic with tweezers. :wink: But I am now convinced that you can get a canonical totalistic Moore neighborhood with just 8 tiles in 3D and that's a surprise. You would want to move the bumps to a place starting at a corner, for instance, but it would not have to be the same corner with rotations, so there might not be all that much movement needed. Then you just add caps to recognize 2 or 3 around live, or 0, 1, 2, 4, 5, 6 around dead (so 16, but we can probably reduce it further).
hkoenig wrote: And the smaller bits looks better to me. A thin frame of a third color around them would help offset the neighbor pattern from the center of the bit.
blocktiles.png
blocktiles.png (12.13 KiB) Viewed 1425 times
I did this in imagemagick so I can generate larger patterns than I can make in Google draw. I am not sure about lines. They may clarify things, but I was going for a minimal aesthetic, and it seems like the black/white contrast is already enough to remove ambiguity.

I feel as if still life violations would jump out at me, but I should probably test that with real non-still-life patterns. Update: here's a section of the infinite houndstooth p2 oscillator (which conveniently uses all tiles at all orientations. Do the births and deaths jump right out?
ht.png
ht.png (11.72 KiB) Viewed 1418 times
Here's a python script to generate the imagemagick command for eater and block on table:

Code: Select all

import math

COLORS = ["white", "black"]

def tile(quadrants, x, y, side, scale):
  lines = []
  length = side * scale
  inner = side * (scale - 3) + 1
  for i in range(4):
    rotate = 90 * i - 180
    lines.append("-stroke none")
    (a, b, c, d) = quadrants[i:] + quadrants[:i]
    lines.append("-fill %s -draw 'translate %d %d rotate %d translate 1 1 rectangle 0 0 %d %d'" %
                 (COLORS[a], x, y, rotate, length - 1, length - 1))
    lines.append("-fill %s -draw 'translate %d %d rotate %d translate %d %d rectangle 0 %d %d %d'" %
                 (COLORS[b], x, y, rotate, inner, inner, side * 2, side * 2 - 1, side * 3 - 1))
    lines.append("-fill %s -draw 'translate %d %d rotate %d translate %d %d rectangle 0 0 %d %d'" %
                 (COLORS[c], x, y, rotate, inner, inner, side * 2 - 1, side * 2 - 1))
    lines.append("-fill %s -draw 'translate %d %d rotate %d translate %d %d rectangle %d 0 %d %d'" %
                 (COLORS[d], x, y, rotate, inner, inner, side * 2, side * 3 - 1, side * 2 - 1))
    lines.append("-fill none -stroke red -draw 'translate %d %d rotate %d translate 0 0 "
                 "path \"M %d %d L %d %d L %d  %d\"'" %
                 (x, y, rotate, length, inner, inner, inner, inner, length))
  lines.append("-stroke lightgray -draw 'translate %d %d path \"M 0 %d L 0 %d\" path \"M %d 0 %d 0\"'" %
               (x, y, -length + 1, length -1, -length + 1, length - 1))
  return lines


def pattern(x, y, grid, side, scale):
  size = side * scale * 2 + 1
  lines = []
  for i in range(len(grid) - 1): 
    for j in range(len(grid[i]) - 1): 
      quadrants = (grid[i][j], grid[i][j + 1], grid[i + 1][j + 1], grid[i + 1][j])
      lines.extend(tile(quadrants, x + j * size, y + i * size, side, scale))  
  return lines


lines = ["magick -size 900x700 canvas:skyblue"]
x = 100
y = 100
for a in range(2):
  for b in range(2):
    for c in range(2):
      for d in range(2):
        quadrants = (a, b, c, d)
        if quadrants == min(quadrants[i:] + quadrants[:i] for i in range(4)):
          lines.extend(tile(quadrants, x, y, 7, 5))
          x += 120

eater = [
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 0],
  [0, 0, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 0],
  [0, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0]]
lines.extend(pattern(100, 250, eater, 7, 5))

block_on_table = [
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 0],
  [0, 0, 0, 1, 1, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 0],
  [0, 1, 0, 0, 1, 0],
  [0, 0, 0, 0, 0, 0]]
lines.extend(pattern(500, 250, block_on_table, 7, 5))

lines.append("blocktiles.png")
print(" \\\n").join(lines)

pcallahan
Posts: 487
Joined: April 26th, 2013, 1:04 pm

Re: Realizing still life constraints as a planar tiling

Post by pcallahan » February 1st, 2020, 3:00 am

pcallahan wrote:
January 31st, 2020, 7:18 pm
I feel as if still life violations would jump out at me, but I should probably test that with real non-still-life patterns.
For some additional comparisons, here's a glider and blinker. I think the violations mostly jump out, but I might have missed the cell birth on the glider if I wasn't looking for it. This is like learning any other kind of pattern recognition. There aren't that many possible neighborhoods to begin with, taking symmetry into account, and if you're unsure, you can just count the cells.
glbl.png
glbl.png (6.21 KiB) Viewed 1401 times
Here's a more complicated still life.
99a.png
99a.png (13.34 KiB) Viewed 1401 times
It may be worth trying this on completely random patterns to see if I miss any births or deaths. If I just want a totalistic rule, the dominos or petals might be better.

Another gamification idea would be to have manual still life in an interactive program, where you need to click on only the cells that change in order to move to the next generation.

Update:
Here are the neighborhoods up to symmetry grouped by CGOL transition. To identify a still life, it is probably easiest to memorize the all the survival windows for black cells (required) and all the birth windows for white cells (forbidden). (I replaced the first image I posted with one that shows context and is ordered by neighbor count.)
windows.png
windows.png (12.7 KiB) Viewed 1374 times

Post Reply