A Formal Notation for Glider Syntheses

[Gamedziner]

My proposed notation is as follows:
Begin with an imaginary reference glider G, with the following phase:

Code: Select all

bo$2bo$3o!

From there, glider phase and position will be determined based on how long it would take for each individual glider to reach G, possibly with a different direction or offset.
The notation takes the form of ([positive integer][A,B,C,D,a,b,c, or d][integer].), where the notation is repeated once per glider, but the period is replaced with an exclamation point on the final glider.

• The positive integer represents the number of generations needed to match G in phase and at least one of the x-y coordinates.
• The letter represents the direction the glider is facing as well as which coordinate the glider is offset from G by:
  A=down-right; x offset
  B=up-right; x offset
  C=up-left; x offset
  D=down-left; x offset
  a=down-right; y offset
  b=up-right; y offset
  c=up-left; y offset
  d=down-left; y offset
• The integer represents the distance, in cells, the glider is offset from G by.

A couple examples, with relevant RLEs:

The reference glider:

Code: Select all

#C 0A0!
bo$2bo$3o!

Fumarole synthesis:

Code: Select all

#C 29d5.17a3.23d1.7a-3.13d5.22b-4.24c-4!
12bobo$12b2o$13bo3$bo10bo$2b2o6b2o$b2o8b2o7$3bobo2bobo$4b2o2b2o$4bo4bo
6$3o8b3o$2bo8bo$bo10bo!

[hkoenig]

General questions--
Is the goal an encoding that is machine readable, human readable, both or neither?

Are you trying to encode existing, known constructions, or generate and survey them automatically? And if automatically, is it exhaustive enumeration, or randomly like Catalogue?

Specific to this encoding--
What about cases where there are objects that are not Gliders? Or where there are multiple target objects or pseudo-objects or intermediate steps? Or when a Spaceship (any variety) is involved?

Why two axes? Doesn't that imply that there can be multiple IDs for any particular construction? Or IDs that aren't valid? What's the procedure for choosing the proper axis?

Can you insure the first integer is always positive? Does a negative imply an improper coding? Is there a way to transform into a proper one?

Does the orientation matter? Is there a canonical form? For example, what if I turn that Fumarole construction 90deg? Will I get the same encoding?

Why upper vs. lower case? (Easy to typo by missing the shift key.) Why not A-D vs W-Z? (Why not actual compass directions, other than two characters instead of one?)

Presentation--
You might also want to make several (close to a dozen) actual images demonstrating simple collisions including the reference points and minor differences. And if necessary, why a particular encoding would be preferred when there's multiples, or when invalid.

You might want to write some code that will automatically generate your encoding from an input RLE string or list of objects. Or take the code and create the equivalent bitpattern/RLE. That's one way to understand if what you are doing is what you want. If you can't code it up, it's probably too complicated or there's something else wrong. (And create a set of test cases used for validation.)

[Gamedziner]

General questions--
Is the goal an encoding that is machine readable, human readable, both or neither?

My goal is a machine-readable encoding.

Are you trying to encode existing, known constructions, or generate and survey them automatically? And if automatically, is it exhaustive enumeration, or randomly like Catalogue?

My goal is to reduce the amount of code needed to encode larger constructions like the Demonoid.

Specific to this encoding--
What about cases where there are objects that are not Gliders? Or where there are multiple target objects or pseudo-objects or intermediate steps? Or when a Spaceship (any variety) is involved?

If the objects can be constructed with gliders, then there exists an encoding to get said objects into position before the other gliders reach their intended starting positions.

Why two axes? Doesn't that imply that there can be multiple IDs for any particular construction? Or IDs that aren't valid? What's the procedure for choosing the proper axis?

Good point. From here on out, I will treat both uppercase and lowercase as determining offset based on direction:

• A,a: -1*(x offset)
  B,b: -1*(y offset)
  C,c: x offset
  D,d: y offset

Additionally, I will now treat A,B,C, and D as gliders facing down-right, down-left, up-left, and up-right, respectively.

Can you insure the first integer is always positive? Does a negative imply an improper coding? Is there a way to transform into a proper one?

Another good point. I will now include negative integers as well.

Does the orientation matter? Is there a canonical form? For example, what if I turn that Fumarole construction 90deg? Will I get the same encoding?

With the above changes in place, rotating any construction 90 degrees clockwise will change the letter using the following mapping:

• A maps to B
  B maps to C
  C maps to D
  D maps to A

A counterclockwise rotation is equivalent to using this mapping three times.

Why upper vs. lower case? (Easy to typo by missing the shift key.) Why not A-D vs W-Z? (Why not actual compass directions, other than two characters instead of one?)

This issue is solved with the above changes.

Presentation--
You might also want to make several (close to a dozen) actual images demonstrating simple collisions including the reference points and minor differences. And if necessary, why a particular encoding would be preferred when there's multiples, or when invalid.

You might want to write some code that will automatically generate your encoding from an input RLE string or list of objects. Or take the code and create the equivalent bitpattern/RLE. That's one way to understand if what you are doing is what you want. If you can't code it up, it's probably too complicated or there's something else wrong. (And create a set of test cases used for validation.)

I plan on doing this when I have more time to make a script.

[chris_c]

I came up with something like this and used it for the 16 in 16 glider synthesis project.

There is already Python code and Javascript code that can decode my format. The Javascript version is behind the glider synthesis display on Catagolue.

I have just updated the README to talk about the canonicalisation that I do with this format and also the Python script that does the canonicalisation.

The Python script expects a bunch of RLE files containing glider syntheses in the "synths" directory. It analyses all the syntheses contained in the files. If it finds some kind of error or failure then it writes a file to the an "error" directory. If it analyses a synthesis correctly it does precisely nothing.

It appears that I don't even have code that takes the Python object representing a synthesis and output it as a string. This is because of a rather stupid backup blunder.

I also used to have code that was able to read a bunch of these glider synthesis and output only the minimum set of glider syntheses that were necessary in order to make any still life of 16 bits or less most efficiently. That code is gone too. It was basically just Djikstra's algorithm.

Anyway, for the 16 in 16 project I already thought that my Python code was a bit slow. It would be great to see a faster version written in C++ (lifelib?) but I don't have time to do it.

My format is surely not perfect but it has the advantage that Javascript code that can display syntheses in LifeViewer already exists.

[hkoenig]

I came up with something like this and used it for the 16 in 16 glider synthesis project.

I'd forgotten about your notation. And that I'd written a decoder for it and that I haven't broken that code with all the other changes I've been making to my Life utilities. (Haven't had the need to do the encoder, yet.)

Rather than trying to come up with a new encoding, it would probably be better to consider using this one, or extending it if necessary.

(Side note: do you have a name for this encoding? Also, is there a name for the transform part at the end? (My computational geometry knowledge needs refreshing, and I don't remember if such transforms have a formal name.)

If the objects can be constructed with gliders, then there exists an encoding to get said objects into position before the other gliders reach their intended starting positions.

This is not a good idea. You shouldn't include the predecessor objects as part of Glider constructions, because you don't (generally) need to care how they are created or get into position. If, in the future, a new and improved construction for that object (or better yet, a more efficient construction of multiple objects) appears, you won't need to find and update all the places that it affects.

(The only exception would be the three small orthogonal Spaceships, which are all easily constructible by three Gliders at any arbitrary distance. They do tend to over-complicate things when included on their own.)

[chris_c]

Side note: do you have a name for this encoding?

No, I don't have a name for the encoding.

Also, is there a name for the transform part at the end?

2D affine transformation with integer coefficients, maybe?

[hkoenig]

"2D affine transformation"

Thank you. That's what I was looking for.