A structured pattern for a Caterpillar

Structured patterns

Something I've been wanting to do for a while now is to produce a structured description of Gabriel Nivasch's Caterpillar.

In the context of the Game of Life, a "structured pattern" would be a description in terms of the smaller subpatterns that are repeated many times in the full pattern, such as the "shish-ke-babs" or the various rakes that make up the Caterpillar. The subpatterns in turn may be composed of smaller sub-subpatterns like pi climbers, blinkers, gliders, etc. A structured format makes a much better "blueprint" of a large pattern than a standard RLE encoding or picture-format file, and it's also very compact -- probably better compression than any standard binary-archive tool could manage.

Xlife 3.5/3.6 provides a good pattern format for describing this kind of structured pattern. Unfortunately it isn't quite versatile enough for this purpose. The big problem is that when you're dealing with periodic subpatterns, you often want to be able to include copies of them at several different phases. Xlife's approach is to define one phase of each periodic pattern as its "base" pattern; to paste multiple copies in, you paste the first base pattern, run the entire universe some number of generations to get the first pattern to the right phase relative to the second; then paste the second base pattern -- and if necessary run N more generations and paste a third base pattern, and so forth.

For stable patterns, or patterns that don't interact too closely, that's fine. But unfortunately this approach doesn't work very well for large numbers of subpatterns or higher periods -- sometimes Xlife's format doesn't support a "natural" compact definition based on subpatterns, because (for example) two of the subpatterns interfere with each other before the correct phase of the third subpattern can be placed to stabilize the whole conglomeration.

Ideas for an extension of Xlife #I format:

First, for reference, here is a summary of current Xlife syntax.

An extension of the format would fix the problem described above -- you'd have to be able to say, "run just this pattern in isolation for N generations, then paste it at (x,y)." This seems like a more natural way to compose patterns from subpatterns.

-- In fact, that's how Xlife's GUI does it! To register subpatterns in a "load script", you specify subpatterns' locations, transformations, and number of ticks forward in time from the base pattern. It's actually quite a surprise to look in an #I-format file for the first time and find out that Xlife has translated your registered subpatterns into this alternate format that is only sometimes equivalent.

I think Eugene Langvagen's PLife project has the necessary versatility to describe this kind of run-N-ticks-then-paste operation, but I haven't done enough benchmarking yet to know whether PLife can handle Caterpillar-sized structured patterns.

The main problem that I see is that a PLife script can easily become much too syntactically complex to be read directly by other Life software. You could create a structured pattern using a PLife script, but you'd have to convert it back to RLE to communicate it to anyone who doesn't have Python and PLife available. Xlife format is much more straightforward to write a parser for.

2c/3 transceiver, large size

The new 2c/3 receiver accepts diagonal signals from the track and uses a repeatable reaction to convert these signals into output gliders. (In the pattern as shown below, all the output gliders are blocked, but one or more of them could easily be allowed to escape by removing the appropriate eaters.)

This version of the receiver can process signals separated by 2175 or more generations. The incoming signal interacts with a small constellation of still lifes at the receiver end of the 2c/3 track (two blocks and an eater, shown in light green in the picture). With the assistance of a few catalysts, the constellation collapses cleanly into an R-pentomino, which is then guided onto a Herschel track.

The path of the active signal is shown in gray the image below; the direction of travel is indicated by the red arrows. Gliders from the output Herschel (short blue arrows) are used to create two more Herschels; the Herschels are then routed to various Herschel-to-glider converters, which produce five gliders in two salvos (long blue arrows). Four of these gliders collide to rebuild the original constellation. (The first glider just removes an extra block left by the conversion of the receiver's initial output R-pentomino to a Herschel.)

2c/3 signal receiver: Dave Greene, 6 February 2005

2c/3 details

2c/3 is a respectable speed in the Life universe; by comparison, a glider travels at only one-fourth of the speed of light, and it was proven many years ago that this is the fastest that any finite diagonal spaceship can travel through empty space. There is a similar limit of half of the speed of light for orthogonal spaceships.

However, disturbances in pre-existing structures can travel much faster than these limits -- there is no theoretical limit lower than lightspeed, either diagonally or orthogonally. See Gabriel Nivasch's lightspeed article for details and examples.

A signal in a 2c/3 track will quickly overtake a glider travelling in the same direction. If a sufficiently long track can be made to turn a corner, a 2c/3 signal in it will even overtake an orthogonal c/2 spaceship.