ConwayLife.com

This set of postings is about 1) CAs that run on various alternative grids and 2) how to emulate those CAs in Golly using the square grid. I'll focus on rules which are lifelike (two state, semi-totalistic, and don't use B0).

If you want to skip all the text below, here's what you want to download:
================================================================
Open this link:
https://drive.google.com/folderview?id= ... sp=sharing
Select "For Golly 2.4" or "For Golly 2.5", and then download ""Tiling Project Parts 1 & 2"
================================================================

As a starting point, I took a look at the 22 uniform or dual-uniform tilings listed here:
http://en.wikipedia.org/wiki/List_of_co ... rm_tilings

and the 14 pentagonal tilings enumerated here:
http://www.mathpuzzle.com/tilepent.html

First, a quick comment about two other programs:
Tiled CA (viewtopic.php?f=11&t=1025) and Ready (viewtopic.php?f=11&t=1004).
I haven't had nearly as much chance as I'd like to use Tiled CA, as it uses Windows (and I usually don't) but I'm hoping that TiledCA can handle many or even all of the tilings listed in the links above. As for Ready, I would greatly appreciate a tutorial on how to change Ready's underlying grid to the tilings listed above. Even if both programs can implement the tilings, I wanted to create Golly implementations because I wanted to take advantage of Golly's editing features, its infinite plane, its speed, and its user base. However, that's not to discount either program: aside from any intrinsic advantages either program offers, below I'll talk about why TiledCA or Ready could be very helpful when creating new tiling rules for Golly.

In the Tiling Project download, you'll find a folder for rules and icons, a folder for scripts to generate more rules, a collection of patterns, and most importantly, a folder for neighborhoods which show how a particular tiling has a topological equivalent on the square grid, or on the hexagonal grid, using the familiar trick of ignoring the square grid's northwest and southeast neighbors.

Each neighborhood shows eight square cells arranged around a central square cell. For most neighborhoods, the square cells are split into non-square tiles. Each central tile is marked with a large rectangle, and each of its designated neighbors is marked with a single pixel. It may be easiest to view the neighborhoods using a black background.

The rules can be categorized two ways: by the number of states required to emulate a two state rule, and by whether they use alternating types of square cells.

Number of states: Each script's name notes the number of states it takes to emulate its neighborhood. The number of states needed turned out to be the major issue for this project. For each tiling, I first used my own program to generate the CAs, and since my program uses transition functions very similar to those used with Golly's make-ruletree script, it was easiest for me to use Golly's ruletree approach, and create scripts which are similar to Andrew's TriLife-gen.py script distributed with Golly. The python version of Golly's make-ruletree code is rather slow to create ruletrees which use more than 5 states, and is painfully slow to create ruletrees that use more than 8 states. On my mac (with a 2.4 GHz i5 processor), ruletree files with 8 states take roughly 15 minutes to generate, ruletrees with 9 states take roughly 30 minutes, and so on.

(Late in the project, I realized that the C++ version of make-ruletree is much faster -- a 16 state rule, which would be completely out of reach with python, takes only around 4 hours, and even a 19 state rule takes roughly 24 hours, which is my limit for this sort of thing! More practically, 10 state rules take roughly 6 minutes.)

This is where TiledCA, Ready, and perhaps other programs can help. Many of the tilings in the following comments (particularly in Part 2) require a large number of states, and so it is too time-consuming to search for interesting rules. TiledCA, Ready, and my own program (which isn't ready for other users yet) are each limited to a small torus and relatively slow speeds, but they have the benefit of being able to switch to a new rule instantly once a tiling's rule family is specified. I'm hoping that TiledCA and Ready can be used to scout out interesting rules, and then the scripts I'm providing here can help create a Golly version if desired.

Alternating vs Non-Alternating: The need to keep the number of states low in Golly meant that many of the tilings use alternating types of cells, usually with a checkerboard pattern. Alternating types of cells means you can't just scribble a pattern, and you can't use Golly's built-in random-fill operation on a selection. There are work-arounds I discuss below, but regardless, rules with alternating cells are more of a pain to work with in Golly, so I divided the Patterns folder into Alternating and Non-Alternating rules.

Lets get into the particulars below with Cairo Pentagonal Tiling, a tiling which is at the intersection of both tiling lists.

Pentagonal Cairo Tiling: See http://en.wikipedia.org/wiki/Cairo_pentagonal_tiling

---- Moore Neighborhood ----

Carter Bays and his students investigated the Moore neighborhood for Cairo tiling, in which each pentagon has 7 neighbors. For rules which don't explode, Cater Bays' literature shows just one spaceship, in B346/S23. Although Bays doesn't appear to mention it, he probably noticed that the exploding rule B2/S also supports spaceships.

You can play with Carter Bays' rule using the Java applet here:

http://www.cse.sc.edu/~bays/p7p7p7/

To emulate pentagonal on the square/hexagonal grid, the most straightforward way is to divide each hexagon into four pentagons. That requires 16 states, so I gave the family of Golly ruletree files the prefix PentaCairo16.

Here's Cater Bay's spaceship: I haven't yet found any other non-exploding rules with spaceships in the 7 neighbor Moore neighborhood.


---- Von Neumann Neighborhood ----

To my surprise, the "Von Neumann neighborhood" for Cairo tiling, in which each pentagon has 5 neighbors, has also already been investigated, and to my greater surprise, a spaceship was found! While searching the web for more on Cater Bays' research, I came across David Bagley's Life project page:

http://www.tux.org/~bagleyd/life.html

David's website is terrific! There is quite a lot on his website, and I strongly recommend checking it out.

Regarding just the portion of his website relevant to Cairo Tiling, David Bagely found a spaceship in B2/S24 in the 5 neighbor Von Neumann neighborhood!

If that doesn't immediately grab you and fill you with awe and wonder, then you might want to visit the PentaWorld thread on this forum, started by forum member "137Ben", by clicking here:
viewtopic.php?f=11&t=473&start=0&hilit=pentaworld
In the PentaWorld thread, the significance of a spaceship in a five neighbor rule was discussed. (I'll get back to PentaWorld below!)

I called the von Neumann version of PentaCairo16 "PentaCairo16-VN". Here is David Bagley's spaceship: Inspired by David's find, I looked for spaceships in other rules...

The most impressive individual ship I've found in a non-exploding rule was in B24/S15 - a fairly large (but rare) p219 ship, which I called "the awesome ship": Spaceships are much more common in B2/S15: Many of the rules with B2 and S0 have spaceships. They all explode, but many of them look quite amenable to engineering. In PentaCairo-VN-B24/S05, for example, spaceships and puffers are very common, and they easily outrace the slowly expanding central blob.

Finally, I saw David Bagley's ship again in PentaCairo-VN-B2/S245.

Below, we'll look at some other, and possibly better, ways to implement Cairo Tiling in Golly.

----- Three additional Golly implementations of Cairo Tiling ------

1) PentaCairo-Basketweave

If we want to search for other interesting Cairo tiling rules, we don't want to run a C program that takes 4 hours to generate a 16 state rule! Above, I suggested using TiledCA or Ready, but as an exercise, lets see how few states we can use in a Golly implementation. The wikipedia article on Cairo tiling suggests alternating checkerboard pattern which is a topological equivalent but requires only 7 states:
http://en.wikipedia.org/wiki/Cairo_pent ... nd_tilings

For Golly, PentaCairo-Basketweave is implemented as a yellow and green checkerboard in which the green tiles are cut in half vertically and the yellow tiles are cut in half horizontally.

With alternating types of Golly cells, you can't create new patterns normally: you can't just scribble a pattern, and you can't do a control-5 random-fill operation on a selection.

Instead, to create legal patterns that respect the checkerboard, one solution is to switch to an exploding rule, like B1/S or B2/S2, draw a very small legal pattern and allow it to explode, and then switch back to a non-exploding rule to look for naturally emerging spaceships, etc. I've included PentaCairo-Basketweave-B1/S and PentaCairo-Basketweave-B2/S2 ruletrees for this purpose.

Another solution is to draw a small legal pattern, use the tile-wth-clip.py script provided with Golly to make a larger copy, and then alter it by randomly inserting background cells. (A better solution would be to create a Golly script which creates legal random patterns...)

Is this too much trouble? You can risk a shortcut. Often, using control-5 to create a random field or using the drawing tool to create a scribble will eventually result in a valid self-contained pattern such as a spaceship or oscillator, but be skeptical. Be particularly skeptical of collisions with other patterns generated this way - the two patterns may have different parities.

Here's Carter Bay's spaceship using basketweave tiling: And here's the spaceship from B2/S15 in the Von Neumann neighborhood:
2) PentaCairo5

Seven states is better than 16 cells, but we can do even better. I belatedly realized that five states is enough, and we don't have to split the Golly cells. Instead, for the Moore neighborhood, four kinds of pentagons can be neighbors with all but one of their eight neighbors, and for the Von Neumann neighborhood, four kinds of pentagons can be neighbors with all four side neighbors, and just one of their corner neighbors. The icons for these two patterns will make it clear how it works:

Here's Carter Bay's spaceship: And here's the spaceship from B2/S15 in the Von Neumann neighborhood (uses different icons from the Moore neighborhood): PentaCairo5 rules can be created very quickly, so the PentaCairo5 and PentaCairo-VN scripts should be a good tool for anyone wanting to search for interesting Cairo tiling rules.

Also five state rules can be created so quickly that we can afford a few more states. I added a Generation rule family option to the scripts, so that you can create Bnnn/Snnn/Cnnn rules, such as the Cairo Tiling version of Star Wars (and in fact, PentaCairo-B2_S345_C4 does work rather similarly to the original Star Wars rule.)


3) PentaWorld

If you read the PentaWorld thread, the description of PentaCairo5-VN should sound familiar. (Here is the PentaWorld thread again: viewtopic.php?f=11&t=473&start=0&hilit=pentaworld ) Forum member 137Ben suggested a neighborhood with four rectangles, each with five orthogonal neighbors, and Forum member Calcyman pointed out that this was equivalent to four kinds of squares, each with four orthogonal neighbors and one kind of corner neighbor. So, it sounds like PentaWorld is topologically equivalent to the von Neumann PentaCairo neighborhood! Just to be sure, I modified my Cairo16 code and made new icons, to create PentaWorld16.

Sure enough, here's the spaceship from PentaCairo16-VN-B2/S15 in PentaWorld16:
--- Which of the four implementations is best? ----

For creating and scouting out new rules, PentaCairo5 is clearly the fastest.

But once you have a rule you like, PentaCairo16 is usually the easiest to work with, because it has non-alternating cells.

But not always: PentaCairo-Basketweave is turned 45 degrees, and so it offers the advantage of orthogonal ships, which are easier to nudge around. You just have to remember to move all patterns two cells over, to respect the checkerboard.

As for PentaWorld16, I don't know that we have any further use for it, except to note the similarity between state 15 and Kok's Galaxy, which is the icon for Golly.
Thanks to Ben's PentaWorld, whenever we run Golly, we can think of Cairo Pentagonal Tiling!

I've also been working on the other types of pentagonal tilings listed here:
http://www.mathpuzzle.com/tilepent.html

Here's a rundown of each type:

Types 1, 2, and 3 are topologically equivalent to hexagonal tiling.

Type 4 is equivalent to Cairo Tiling.

Type 5 is on the Dual-Uniform tiling list - it is called Floret Pentagonal Tiling. Each tile has eight neighbors. I have not been able to find any lifelike rules with spaceships in this tiling. It can be straightforwardly emulated on the square grid by splitting a hexagon into six pieces, so that lifelike rules are emulated with 64 states. But there is another way, shown in the neighborhoods folder, which requires only 10 states. I included C code for creating ruletrees using the 10 state emulation for the moore and von Neumann neighborhoods. I'd love to see a spaceship in this tiling, but I haven't seen one yet.

Type 6 is another Dual-Uniform tiling, called Prismatic Pentagonal Tiling. Like Cairo tiling, there is a 7 neighbor Moore neighborhood and a 5 neighbor von Neumann neighborhood. Spaceships and puffers can easily be found for lifelike rules, but all such rules that I've found explode, and moreover, all spaceships travel along a single axis. Since it takes only 4 states to emulate this tiling, you can easily create new rules to play around with using the project folder's python scripts.

Type 7 is another variant which has a 7 neighbor Moore neighborhood and a 5 neighbor von Neumam neighborhood. I was more interested in the von Neumann neighborhood - 5 neighbors! - and I found two non-exploding rules with spaceships. However, each rule has a preferred direction for spaceships -- in one rule, spaceships only travel vertically, and in the other, spaceships only travel horizontally. It would be interesting to find a rule in which has both kinds of spaceships. In the Moore neighborhood, I could only find spaceships in B2 rules, which explode, just like they do with Cairo tiling. Unfortunately, it takes 9 states to emulate this tiling. Note: In the Patterns and Neighborhoods folders, see "Penta-Type9" and "Penta-Type9-VN" rather than "Type7".

Type 8 is topologically equivalent to Cairo tiling.

Type 9 is topologically equivalent to Type 7.

Type 10 has tiles which have either 6 or 7 neighbors. I included a neighborhood in the neighborhoods folder, but I haven't yet created a CA for this type of tiling.

Type 11 has tiles which have either 5 or 7 neighbors. There are many ways to emulate this tiling on the square grid - I used a way that has two kinds of hexagons and a third hexagon split into two pentagons. It is a bit counter-intuitive, but it requires only 5 states, so generating new Golly rules is very fast with a python script. I could only find spaceships in B2/S1, which is an exploding rule.

Type 12 is topologically equivalent to hexagonal tiling.

Type 13 is another way to arrange tiles with 6 or 7 neighbors. I included a neighborhood in the neighborhood folder, but I haven't yet created a CA for this type of tiling.

Type 14 has tiles with 5, 6, or 7 neighbors. I implemented this tiling as a CA on my own system, and haven't found any rules with spaceships yet. I included a neighborhood in the neighborhood folder, but I haven't yet converted the code for golly.

--- Additional Pentagonal Tilings ---

The 14 types of pentagons have geometrical significance (are there only 14?), but there are many additional topological arrangements of pentagons which tile the plane.

For example, Type 3 tiling looks like peace signs. If you alternate peace signs with upside down peace signs, the tiles all fit together, but now you have a tiles with either 6 or 8 neighbors. To see this, open Penta-AltPeace-6-6-8 in the neighborhoods folder. I implemented this tiling as a CA on my own system. B2/S does not explode, and has spaceships, puffers, and rakes -- some kinds travel along one axis, some kinds travel along another axis, and none travel along the third hexagonal axis. I haven't yet converted my code for a Golly version, but I'll post it here when I do.

There are many other pentagonal tilings as well. Since you get pentagons if you divide a hexagon into two, three, or four parts, there are plenty of tilings just from mixing different types of divided hexagons. I'm still working on finding interesting combinations.

--- PentaHex ---

You could also extend the idea by mixing split hexagons with undivided hexagons, such as the PentaHex-5-12 neighborhood in the neighborhoods folder, in which 12 pentagons with five neighbors each surround a hexagon with 12 neighbors. (This neighborhood is mentioned in "Tilings & Patterns" by Branko Grunbaum and G. C. Shephard). This one is on my to-do list, and I'll post a Golly implementation here.

--- HexStar ---

Finally, I stumbled onto a way to use Type 3 pentagons to do something useful! They can make it easier to implement George Maydwell's HexStar neighborhood!
(See http://cell-auto.com/neighbourhood/hexstar/ )
The HexStar neighborhood is too large for Golly's Moore neighborhood, but since Type 3 pentagons are equivalent to really small hexagons, the Hexstar neighborhood fits into an emulation of Type 3 tiling. It might take 16 states to straightforwardly represent a radius 2 neighborhood in Golly [ Link to Radius 2 Weighted Life posting goes here ] but we can do it in just 8 states using Type 3 pentagons. George Maydwell used his neighborhood for a variety of rules, such as George's Brain, a variant of Brian's Brain, and various alternating and non-totalistic rules, but I think he didn't mention any 2 state semi-totalistic rules. (I apologize to George if he did and I missed them; See http://www.collidoscope.com/modernca/hexagonal.html).

In any case, there *are* interesting lifelike rules in the HexStar neighborhood: as you can see in the Patterns folder, B3/S37 is a rule with ships, puffers, rakes, and complex oscillators. There are other interesting B3 rules -- B3/S3 is a milder version of B3/S37, and so forth. I also noticed a spaceship in B4/s234 - it is otherwise a boring rule, but maybe there are interesting B4 rules as well.

HexStar rules can be tried out with Brian's square cell program, or Maydwell's own program:
http://www.collidoscope.com/modernca/he ... cklab.html

--- Triumphant ---

No, wait, one more that I overlooked this until just now! Here is another way to use Type 3 pentagons:
http://cell-auto.com/neighbourhood/triu ... index.html
and you can see the neighborhood in a java CA here:
http://hex.alife.co.uk/diffusion/
This one is also now on my to-do list, and I'll post a Golly implementation here.