So here's a first draft of an article type thing I'm working on. Let me know what you think.
--- Cut Here --- Start ---
Basic Spaceships in the Star Wars Rule - Part One
While playing around with the Star Wars rule, I've discovered that there are two basic classes of spaceships, those with a period one front end and those with a period two front end. This discusses the structure of period one based spaceships.
The basic period one spaceship looks like this:
This basic ship also forms the head of other spaceships. These spaceships are formed by attaching a simple component to this ship. This component is merely one half of the basic ship (also known as a "signal" or "electron").
There are two basic ways in which the component can be attached to each other, and therefore the to the basic ship. They are as follows:
These components can be chained in this way to create arbitrarily large spaceships. Next, I will discuss a subset of the spaceships that can be created via this method.
If one considers only spaceships in which additional components are only attached to the outside edges of the ship, there are a limited number of locations where components may be attached. Each component may be connected to it's neighbor at one of two offsets.
By creating a list of these offsets, a spaceship of this type can be reduced to a simple string. The head of the spaceship consists of two of the components with no offset, so I will designate this connection '0'. The two possible offsets for additional components, I will designate '1' and '2' respectively.
So, given a string such as '12110221', we can construct the spaceship as follows:
Code: Select all
OO
Ooo
Oo..O
o. o
O. .O
Oo oO
o. .o
. .
Note that the number of components, and therefore the width of the ship, is one larger than the number of connections, which is also the length of the string.
Many common spaceships are of this form and so can be succinctly described using this notation. However, there are other spaceships built from this basic component which cannot, because they employ a wider set of connections.
Perhaps the simplest such spaceship is this one.
This ship consists of a head and two components attached with type '2' connections, however, as the second connection isn't towards the outside of the ship, the string '022' cannot (unambiguously) describe it.
At this point, it may seem that the notation can simply be extended to indicate which side the connection is made on, and so, the ship could be described as a string such as '02<2' or '024'. However, this notation quickly becomes inadequate when faced with constructions such as this:
This pattern isn't a spaceship proper, however, it is the grandparent of a period two spaceship which is built on the same basic structure.
As it is possible (in some cases) for a component to have connections on both sides, their configuration can no longer be represented by a simple sequence (such as string), but must rather be represented as a binary tree.
For example, the above spaceship (precursor) may be described by the following tree:
By starting with such a tree, one can then define a serialization of the tree to once again reduce the configuration of the spaceship to a string. It would be desirable if this serialization would produce the same strings as the simplified notation I defined earlier.
For example, in the simple notation '101' defines a very common spaceship. Here is that ship and it's binary tree:
By defining the output of the tree serialization as the results of a tree traversal that in the case of trees definable by the simple notation visits the nodes in the same order as the simple notation's output, a compatible serialization format can be defined.
For instance, when handling the above tree, the traversal function should visit the nodes by starting at the left node, proceed to it's parent (the root) and then down to the right node.
The type of tree traversal that visits the nodes in this order is known as in-order traversal and can be defined by the following Python code:
Code: Select all
def inorder(node):
if node.left: inorder(node.left)
print node.value
if node.right: inorder(node.right)
However, simply listing the nodes in in-order value isn't sufficient to give an unambiguous serialization of the tree, because different trees may have the same order. Therefore, one also needs to add information regarding the tree's structure to the serialization. There are various methods for doing this, but I've selected one based on the criteria of backwards compatibility with the simple notation.
To achieve this end, I only include information on the tree's structure where it differs from the simple linear list type trees. This works by defining a current direction which is maintained as follows:
- The current direction starts out left.
- When following link to a child node, change the current direction to the direction of the link.
- After traversing the root node, change the current direction to right.
The current direction is used to include tree structure information into the string, as follows:
- When following a link that doesn't point in the current direction, output an open parenthesis before following the link.
- When returning from a link that didn't point in the (then) current direction, output an close parenthesis after returning from the link.
This can be demonstrated by the following example Python code:
Code: Select all
def inorder(node, d=0):
if node.left:
if d: print '('
inorder(node.left, 0)
if d: print ')'
print node.value
if node.value == '0': d = 1
if node.right:
if not d: print '('
inorder(node.right, 1)
if not d: print ')'
This defines a single string that can be used to clearly identify a given spaceship of this type, derived directly from it's structure. For example, this moderately complex ship:
Code: Select all
OO
ooO
O..o
o .
O.O
Oo oO
o. .oO
O. .oO
o .o
.O .
o
O.
o
.
Can be represented by the following binary tree:
Code: Select all
0
/ \
2 1
/ \
2 2
/ \
1 1
/ \
2 1
\ \
2 1
/
2
Which can be reduced to '2((2)2)122(2111)01'. Not exactly the prettiest name for a spaceship, but it's something.
--- Cut Here --- End ---
So there you have it. I hope people can figure out the diagrams in the picture type format I invented. It's a pity that Golly (AFAICT) doesn't support picture formats for multi-state rules. If it did, then I'd be able to include diagrams that could be loaded up and played with.
I'm not sure if I'm explaining things well enough. This is mostly a dump of an idea I had kicking around in my head for a while, so I've thought about it quite a bit and it's hard to know if my explanations are comprehensible to others. The most basic ideas (that many spaceships are just gliders plus some electrons) are pretty easy. (And I'm sure, well known.) However, once I start getting into binary trees and traversal algorithms and what-not, am I making any sense?
At the end, it just kinda dies off. I guess I managed to get down the idea I'd been musing on and now need to think some more. There's a lot that could be discussed, but I haven't really investigated a whole lot. (Mostly this idea just came to me as I watched the various spaceships in chaotic patterns.)
Interesting ideas to cover would how some configurations become spaceships of longer periods, how such spaceships can become rakes or puffers, how some spaceships that could be described by a binary tree cannot actually be built, or are unstable and decay into something else.
Finally, there are some spaceships that are mostly built out of the standard three cell component, but cannot be encoded as a simple binary tree as discussed here. Some of these are the result of running such a description, but the components interact to create more complex behavior. These aren't really an issue, as their precursor can be described, which should suffice. However, others are more complicated. These either are a flotilla in which a sparker is perturbed by another spaceship, or a spaceship who's non-period-one components include configurations that don't arise naturally from the interaction of the period one parts.
This is labeled part one as part two is supposed to cover the spaceships with a period two front end, however I haven't really looked into them much yet (other than playing with some beam stretchers) and don't know if such a grammar exists for them.