Life, part 17

Code for this episode is here.

We'll take a short break from getting to our C# version of Stafford's algorithm; in this episode I want to talk about some improvements to the UI, and also talk about some more fundamental interesting Life patterns.

The basic loop for the UI is pretty simple: compute and display one tick on every timer event. We have no problem keeping up with one tick every 30 milliseconds. Let's say just to keep the numbers nice and round that we're running at 32 ticks per second.

Obviously we could go a lot faster; with the 8-quads we've been playing with thus far we can go many hundreds of times faster. We could render every other generation, or every fourth generation, or heck, every 1024th generation, 32 times a second.

I'm going to use the same logarithmic scale that I've been using for grid sizes - recall, an n-quad is a square with side 2-to-the-n - and apply it to time as well. That is, speed 0 means go forward one tick". Speed 1 means go forward two ticks". Speed 2 is four ticks, speed 3 is eight ticks, and so on.

For the UI, what we'll do is use this same convention; speed 0 is one tick per second, speed 1 is two ticks per second, and so on. As an implementation detail, for speeds 0 through 5 - one per second through 32 per second - we will instruct the algorithm to step forward a single tick, and control the update speed by changing the timer duration. Once we get above speed 5, we will set the timer to update 32 times a second, and have the algorithm loop to compute a (speed - 5) block of ticks.

If you look at the code it will probably make sense. Give it a shot and play around a bit with the speed controls, see how you like it.

If you do look at the code you might notice that the looping code has been copied into the algorithm classes a half a dozen times, rather than putting it in the UI code once. The reason why will become clear later on in this series.

On that mysterious note, let's leave speed control aside and talk about guns that shoot spaceships.

A few episodes back we were discussing patterns that grow without bound; I said that there were two questions you could ask about spaceships that would illuminate the existence of such patterns:

• Are there puffers? That is, spaceships that leave a trail of debris, stable or unstable, behind? We saw that yes, there are, and therefore there are patterns that add cells forever if allowed room to do so.
• Are there oscillators that stay in one place but regularly shoot out spaceships? If so, then the spaceship gun will lead to a continued growth of live cells as more and more spaceships fly away.

Based on our discussion so far it should come as no surprise that both the first puffers and the first guns were discovered by Bill Gosper in 1970. Here's a simple oscillator called the queen bee shuttle" - so called because the queen bee here is trying to build a hive, which is then immediately destroyed because it gets too close to the block. The queen bee does a U turn and promptly does the same thing on the other side, giving us a 30-tick oscillator:

(Images from the wiki.)

The queen bee behaviour when not captured between blocks leads to stable debris in 191 ticks. It is pleasant to watch evolve, so check that out; I've added a pattern file to the branch for this episode.

But the astonishing thing is: if you make two overlapping queen bee shuttles, you get a surprise:

Every 30 ticks we get a new glider, forever. This was the first Life pattern discovered that was known to exhibit unbounded growth. Moreover, there is a lot we can do with an infinite supply of spaceships. We'll come back to discuss a few of those things in a future episode.

Right now though I want to highlight a more recently constructed glider gun, just because I think it's neat. This is the AK-94 glider gun; it produces two gliders going opposite directions every 94 ticks, though the variant shown here eats" the northwest-bound glider rather than allowing it to escape.

(For reasons unknown, WordPress refuses to display the animated version of this graphic; see the link above to the wiki for an animated version.)

The fish hook"-like still Lifes you see all over this pattern are called, well, fish hooks by some people, but the more usual name is eater 1- so named because it was the first simple pattern discovered that survives being hit by a lot of stuff. It is therefore very useful in construction of purpose-built Life patterns because it eats cells that would otherwise grow into unwanted chaos and eats gliders that you do not want escaping for whatever reason.

Once again we have seen that there are patterns that exhibit linear growth; as the number of ticks increases, the number of cells that are changing every tick also increases as an O(n) function of time, so any O(change) algorithm is going to get slower over time. However we still have not answered the question are there patterns that have a superlinear growth of living cells over time?" Keep pondering that!

A great many more spaceship guns have been constructed, and some of them have interesting properties. However I think I will leave it there for now, and get back to our exploration of Stafford's algorithm.

Next time on FAIC: How can we use our triplet" data structure to optimize the inner loop of the first phase of the step algorithm, where we compute the next state" bits?