Multiple Cluster Pattern Storage

[erictom333]

I've justcreated a new format to store patterns, optimised for stamp collecions. It allows for subpatterns to be labeled, commented, and moved around individually.
How it works
Each cluster is as follows:

Code: Select all

x;y;rle;name;attribution;notes

(The name, attribution and notes can be omitted)
For example, here is a glider:

Code: Select all

rule = b3/s23
1;-2;bo$o$3o!;Glider;Richard H. Guy, 1969;The first spaceship discovered in Conway's Game of Life.

which eould be equivalent to

Code: Select all

x = 1, y = -2, rule = b3/s23
#C The first spaceship discovered in Conway's Game of Life.
#C How do I do LifeViewer command thingys
bo$o$3o!

[hkoenig]

A simple format like this is nothing new, really. They've been used for lists of objects and rotors for decades.

RLE is not a particularly compact way to specify bitpatterns, which is why when I was searching for objects, I came up with my "SOF" format. The apgcode is even more compact. (In SOF, a file containing all the 30bit stable objects is 449.8 megabytes.)

If you are intending this for lists of objects to be displayed in tables or arrays as in stamp collections, then the positioning parameters are redundant and unnecessary. The script or program that creates the output bitpattern should be doing that.

If the goal is to allow the breaking of large patterns into sub-parts, then it might be better to use the suffix portion of the apgcode as a standardized object, then add and a transform (position, rotation, reflection, phase, age) to be applied to that object.

The sub-parts could be defined once, with all the metadata (name, etc.) along with an alias, and referenced with an alias.

There are eight possible transforms, which can be arbitrarily defined as "t0" to "t7". Also eight basic compass directions for most spaceships, "d0" to "d7". These specifiers should be unique and position independent, with defined defaults. Makes parsing easier.

Here's a handwaving example of how it would look.

Code: Select all

@Glider: 153           #define "Glider"
696_x-5_y-5_t2          #Beehive bitpattern offset 5,5 to Northwest and rotated
Glider_x0_y0_d7_p2	#Glider at origin, but advanced two generations

I've been thinking about coding this up and trying it out as a way to partition constructions into stages, but it's been a low priority for me, so I haven't really gotten beyond the planning stage. At a minimum, need to write the encoder and decoder and see what's missing.

[erictom333]

RLE is not a particularly compact way to specify bitpatterns, which is why when I was searching for objects, I came up with my "SOF" format. The apgcode is even more compact. (In SOF, a file containing all the 30bit stable objects is 449.8 megabytes.)

My original draft of MCPS used a base-64 apgcode instead of rle. Would that be preferable?

If you are intending this for lists of objects to be displayed in tables or arrays as in stamp collections, then the positioning parameters are redundant and unnecessary. The script or program that creates the output bitpattern should be doing that.

Something like I posted above would best serve as the raw data (.mcpr), to be fed into a script to generate cooked data (.mcps) (or done automatically). For example, the following .mcpr:

Code: Select all

%1               #category
33,Block
252,Tub
253,Boat
696,Beehive
%2
7,Blinker
7e,Toad
218c,Beacon
2a54,Clock

would compile into the following .mcps:

Code: Select all

F41=dbzdbzdb
F42=w3213kcz8o642611z32c84c
F41,x0,y0
33,x6,y0
"Block",x6,y3
252,x12,y0
"Tub",x12,y4
253,x19,y0
"Boat",x19,y4
696,x26,y0
"Beehive",x26,y5
F42,x0,y18
7,x12,y18
"Blinker",x12,y22
7e,x17,y18
"Toad",x17,y23
218c,x23,y18
"Beacon",x23,y23
2a54,x31,y18
"Clock",x31,y23

which would be equal to the following .rle (but with labels):

Code: Select all

x = 35, y = 32, rule = B3/S23
2o4b2o5bo6bo6bo$bo4b2o4bobo4bobo4bobo$o12bo5b2o5bobo$2o25bo2$2o$bo$o$
2o2$2o$bo$o$2o5$2bob2o6bo5bo6b2o5bo$2b2obo6bo4b2o7bo6b2o$6b2o4bo4b2o4b
o7b2o$7bo9bo5b2o8bo$6bo$6b2o$2bob2o$2b2obo$2o$bo$o$2o$2bob2o$2b2obo!

If the goal is to allow the breaking of large patterns into sub-parts, then it might be better to use the suffix portion of the apgcode as a standardized object, then add and a transform (position, rotation, reflection, phase, age) to be applied to that object.

The sub-parts could be defined once, with all the metadata (name, etc.) along with an alias, and referenced with an alias.

There are eight possible transforms, which can be arbitrarily defined as "t0" to "t7". Also eight basic compass directions for most spaceships, "d0" to "d7". These specifiers should be unique and position independent, with defined defaults. Makes parsing easier.

Here's a handwaving example of how it would look.

Code: Select all

@Glider: 153           #define "Glider"
696_x-5_y-5_t2          #Beehive bitpattern offset 5,5 to Northwest and rotated
Glider_x0_y0_d7_p2	#Glider at origin, but advanced two generations

I've been thinking about coding this up and trying it out as a way to partition constructions into stages, but it's been a low priority for me, so I haven't really gotten beyond the planning stage. At a minimum, need to write the encoder and decoder and see what's missing.

Here's my take (to your example), with included labels.

Code: Select all

Glider=247         #define "glider", facing N/NE by default
696,x-5,y-5,r2     #beehive at -5,-5 rotated 90° clockwise
Glider,x0,y0,r6,t2 #glider at origin, rotated 270° clockwise and advanced 2 generations
"Synthesis",x0,y-3 #label

The transformations are:
x: offset in x-axis
y: offset in y-axis
r: rotation or reflection; 0 to 7, even numbers being rotations and odd being reflections
t: advanced

[dvgrn]

Just to have a link in this thread to some prior art: there was some discussion recently about Paul Callahan's Xlife #I format from decades ago, and also the currently supported "Lua pattern script" format in Golly and the somewhat equivalent script format in LifeViewer.

Lua scripts can already support defining sub-patterns in terms of several sub-sub-patterns (and so on for more "sub"s) -- but the scripts haven't been written yet to analyze patterns and produce compact recursive definitions, and they wouldn't translate readily into LifeViewer format (though that might change, if someone wrote such a script!)

The biggest consumer of this kind of format might be a circuit editor that works on the "object" level, allowing easy grouping and ungrouping, and moving groups only along the lines by which they're connected to other groups (via glider or spaceship signals). This topic came up most recently in the "Broader Audience" thread (see the first link above).

[hkoenig]

My original draft of MCPS used a base-64 apgcode instead of rle. Would that be preferable?

How much smaller is it compared to the current apgcode? We have enough different formats as it is, and it seems that the suffix portion of the apgcode serves pretty well. I'm trying to convert what I can over to it. That it is position independent and minimal for transforms is a definite positive for lists and hierarchies. (It does make encoding/decoding a bit more involved...) A lot depends on how the sizes of the various formats compare. Maybe take some of the stampcollections and see how they'd code up, and how much space they'd use.

Of course, allowing native RLE should be allowed as an alternative or fallback.

Your translation of what I showed would work. It's mostly a matter of those who will be using such a format agreeing to what things mean, and the best way to encode the parts.

For example, I'm kinda partial to using an underscore as a separator, since the apgcode already does that. In a lot of contexts, the underscore is also considered an alphanumeric character, where the comma or semicolon isn't. (Then again, a minus isn't one, either) Those should be used in the hierarchy as separators.

I like the apgcode/wcode because it encodes an object in what feels like a unique and natural way. It doesn't depend on setting a bounding box, or having to calculate one. I once tried to use SOF more, but it had the problem of having up to eight different possible encodings, which made sorting difficult. Adding the transform as an apgcode suffix takes care of that problem.

Speaking of transforms-- I've been trying to come up with a good way to "naturally" encode the possible transforms.

LifeObject Transforms A.png (15.98 KiB) Viewed 990 times

My first attempt was to basically go try and do something where rotations and reflections would follow how the object appeared. The eight possible ways lay out nicely in a sort of cube, but the weird thing was that it seemed "natural" for the horizontal and vertical reflections to not be adjacent to the identity transform. Here it's the glide reflection which is adjacent. The only problem is that rotation on the bottom layer is reversed from that on the top, so clockwise and counter-clockwise don't seem to match. (At least the way I visualize it. Maybe it's because of a Coriolis force...)

Hamming Transforms.png (17.43 KiB) Viewed 990 times

Then I thought of trying something like a Hamming code. I actually like this one better. Movement between vertices can be logical, and the rules simple. What was surprising was that the elementary operations were "rotate counter-clockwise", "turn 180 degrees", and "glide reflect".

Operators can be combined/chained by taking the three bit code and dividing it "abb". Take the two operators and simply xor the first bit. The next two bits are almost as simple-- add them, but treat 0b11 as -1, not 3.

I finally came up with this just this weekend, so I may be missing something obvious, but it seems to work well. (Maybe someone who has studied Group Theory this century can do a better job, or point out how this problem has already been solved.)

Then there's the issue of coming up with way to specify Glider/xWSS direction and phasing. I've got some ideas, but they're kinda ugly.

[erictom333]

Here's my idea, derived independently but, on closer inspection, related to yours.

Code: Select all

x = 25, y = 29, rule = LifeHistory
8.3D4.D$10.D3.D.D$9.D4.D.D$9.D4.D.D$9.D5.D2$8.3A3.3C$8.A2B3.2BC$8.BAB
3.BCB$.2D20.D$D3.2AB11.B2A.2D$2D2.ABA11.ABA2.D$D.D.A2B11.2BA2.D$.D20.
3D2$3D19.2D$D3.A2B11.2BA3.D$2D2.ABA11.ABA2.D$2.D.2AB11.B2A.D$2D20.3D$
8.BAB3.BAB$8.A2B3.2BA$8.3A3.3A2$10.D3.2D$9.2D5.D$8.3D4.D$10.D5.D$10.D
3.2D!

The only difference mine has from yours is that a (diagonal) glide reflection is achieved by flipping the least bit, not the greatest. However, mine has the advantage of easily being able to perform a horizontal glide reflection: 1 <-> 2, 3 <-> 4, 5 <-> 6, 7 <-> 0. Rotation is also easy: add the desired rotation transformation (2, 4 or 6).

[yoleo]

Oh yeah there's group theory in this: your second encoding is related to D4 being a semi-direct product of Z mod 2 and Z mod 4, where Z2 acts via taking inverses. Let r be glide reflection, and rho rotation by 90 counter-clockwise. Then everything in D4 can be uniquely expressed as rho^n r^m where 0<=n<=3 and m=0 or 1. rho^4 = identity and r^2 = identity, so regard n as being in Z mod 4, m as being in Z mod 2. Then the above Hamming encoding corresponds to 4m+n in binary.

How encodings act when you rotate/reflect:
(1) applying r before T: this adds 4 to the encoding of T mod 8.
(2) applying r after T: negate the encoding of T mod 8, then add 4
(3) applying rho before T: subtract 1 from the encoding of T mod 8.
(4) applying rho after T: add 1 to the encoding of T mod 8.

How I got these: r rho = rho^{-1} r. Applying repeatedly, rho^j = rho^{-j} r. This sign flip is the reason why clockwise/counterclockwise flips from the top level of the cube to the bottom. For example, for (2), r (rho^n r^m) = (r rho^n) r^m = rho^{-n} r^{m+1}. So 4m+n becomes 4(m+1)-n = -(4m+n) + 4 mod 8.

Aside: here rho r = apply-r-then-apply-rho. It's the opposite of what one might think because conventionally n-by-n matrices act on R^n via left multiplication: (AB)v = A(Bv). B applies first, then A.

EDIT: correction to item (3), previously had "negate encoding then add 1."

EDIT 2: keeping track of glider/XWSS direction and phasing...hmmm...I'd think of picking some "reference instance" of the spaceship then compare all other ones to that one, in terms of space-time transformations. What spatial transformation/how generations forward do you need to apply to your "reference instance" to get the particular instance? For this, I think three pieces of info will be enough: which way it is heading (spatial rotation), the location of some cell at gen 0 (spatial translation), and which phase at gen 0 (time translation compared to reference). From this info, you should be able to find the position/phase of the spaceship any number of generations later, from the spaceship's speed and period.