Life, part 27

We're continuing with our deep dive into Alan Hensel's QuickLife algorithm, rewritten in C# with an emphasis on clarity. When last we left off we had the following established:

• A Quad2 is an immutable wrapper around a ushort
• A Quad3 is an immutable struct containing four Quad2s
• A Quad4 is a mutable class containing eight Quad3's; four for the even generations and four for the odd, plus references to the Quad4s to the north, south, east, west, northwest and southeast.
• The odd generation is one cell to the southeast" of the even generation.
• We have an algorithm that efficiently steps the even generation (blue) to the odd generation (green):

How then are we going to step the odd generation back to the even generation? If stepping the even generation produces an odd generation that is one to the southeast" then stepping the odd generation in the same way will also go one to the southeast".

Long-time reader svick pointed out in a comment to the previous episode that maybe that's not so bad! If our coordinate system has to shift one to the southeast" every step then we could do things like adding new Quad4s to the north and west edges every sixteen ticks, and remove old ones from the south and east edges, and on average we would stay in the same place".

I would love to experiment with that idea, but I want to stay on target more. The QuickLife algorithm uses the fact that we alternate between one to the southeast" and one to the northwest" to attain optimizations that we will see in later episodes.

Plainly then what we must do is write the equivalent algorithm that goes one to the northwest." Let's attack the problem just on the Quad3 I've labeled this.oddSE" to start with.

Two episodes ago we made a method that takes nine Quad2s and returns a Quad3. I'm going to rename that method to Step9Quad2ToQuad3Even because it only works on evens. I won't go through the same level of exegesis that I did the first time around as we write...

static Quad3 Step9Quad2ToQuad3Odd( Quad2 nw, Quad2 n, Quad2 ne, Quad2 w, Quad2 c, Quad2 e, Quad2 sw, Quad2 s, Quad2 se){

What information do we need to get a Quad3 that is one tick ahead and one cell to the northwest?

We can get a quarter of the information we need by looking up the next generation centers of the center, east, south and southeast 2-quads; the cells for the next even generation that we can compute from the green 2-quads is show by blue 1-quads:

The blue 1-quads will be the southeast corners of the four next-generation 2-quads.

We can get another quarter by getting these mirrored" Quad2s:

 Quad2 c_e = c.HorizontalMiddleMirrored(e); Quad2 s_e = s.HorizontalMiddleMirrored(se); Quad2 c_w = w.HorizontalMiddleMirrored(c); Quad2 s_w = sw.HorizontalMiddleMirrored(s);

and then use a lookup table to get this state:

That gives us the southwest corners of the four next-generation Quad2s.

We can get these flipped" Quad2s:

 Quad2 c_s = c.VerticalMiddleFlipped(s); Quad2 e_s = e.VerticalMiddleFlipped(se); Quad2 c_n = n.VerticalMiddleFlipped(c); Quad2 e_n = ne.VerticalMiddleFlipped(e);

to get this state:

for the northeast corners.

And finally we can get these mirrored and flipped" Quad2s:

 Quad2 c_ne = c_n.HorizontalMiddleMirrored(e_n); Quad2 c_sw = c_w.VerticalMiddleFlipped(s_w); Quad2 c_se = c_s.HorizontalMiddleMirrored(e_s); Quad2 c_nw = c_w.NorthEdge | c_n.SW | nw.SE;

to get this state:

for the northwest corners of each new Quad2.

Putting it together, we can get this information:

As desired, the next step is a Quad3 one to the northwest" from the Quad3 formed by the center, east, south and southeast Quad2s.

We haven't yet written the code to actually do the lookups and generate the four Quad2s, but we can just use the same lookup tables as last time...

Wait a minute. No, we cannot!

Remember how we arranged our lookup table? We noticed the following facts for the even-to-odd cycle, which we then made use of in designing the lookup table:

• The next-tick 1-quads that go in the NW corner of a Quad2 are generated by stepping a normal" Quad2.
• The 1-quads that go in the SW corner are generated by stepping a flipped" Quad2.
• The 1-quads that go in the NE corner are generated by stepping a mirrored" Quad2.
• The 1-quads that go in the SE corner are generated by stepping a flipped and mirrored Quad2.

Are any of those conditions still met? Sadly no. If you look carefully you'll see that we are now in the opposite situation. On the odd-to-even cycle:

• The next-tick 1-quads that go in the SE corner of a Quad2 are generated by stepping a normal" Quad2.
• The 1-quads that go in the NE corner are generated by stepping a flipped" Quad2.
• The 1-quads that go in the SW corner are generated by stepping a mirrored" Quad2.
• The 1-quads that go in the NW corner are generated by stepping a flipped and mirrored Quad2.

What are we going to do about this? We could solve the problem by doing a bunch of bit shifting, but remember that the whole point of our technique of storing the next generation" 1-quads in a lookup table at the bit positions where they are going to be needed is to avoid that bit shifting by moving it back in time to the generation of the table.

I'm sure you see the obvious solution: build a second lookup table that has the properties that we want! It's only an additional 128K of memory.

Something we will see as we continue porting the QuickLife algorithm to C# is that the whole thing is based on the even and odd cycles being almost the same but different enough that you end up writing all the code twice. There will be a lot of duplicated code in my implementation, and my implementation will have quite a bit less duplication than the original.

So we'll make two lookup tables, one for even and one for odds; I'll omit the generation of the odd lookup table because it is just like the even lookup table, just with the results put in different bit positions. Our function for today then ends just as you'd expect:

 Quad2 newNW = OddLookup(c).SE | OddLookup(c_n).NE | OddLookup(c_w).SW | OddLookup(c_nw).NW; Quad2 newNE = OddLookup(e).SE | OddLookup(e_n).NE | OddLookup(c_e).SW | OddLookup(c_ne).NW; Quad2 newSW = OddLookup(s).SE | OddLookup(c_s).NE | OddLookup(s_w).SW | OddLookup(c_sw).NW; Quad2 newSE = OddLookup(se).SE | OddLookup(e_s).NE | OddLookup(s_e).SW | OddLookup(c_se).NW; return new Quad3(newNW, newNE, newSW, newSE);}

That takes care of the problem of get the next Quad3 given nine Quad2s". Last time we described how to use that helper function to step an even-to-odd Quad4, and again it should come as no surprise that odd-to-even is just the same except slightly different:

public void StepOdd(){ StepOddSE(); StepOddNW(); StepOddSW(); StepOddNE();}private void StepOddSE(){ evenSE = Step9Quad2ToQuad3Odd( oddNW.SE, oddNE.SW, oddNE.SE, oddSW.NE, oddSE.NW, oddSE.NE, oddSW.SE, oddSE.SW, oddSE.SE);}private void StepOddNW(){ evenNW = Step9Quad2ToQuad3Odd( NW == null ? AllDead : NW.oddSE.SE, N == null ? AllDead : N.oddSW.SW, N == null ? AllDead : N.oddSW.SE, W == null ? AllDead : W.oddNE.NE, oddNW.NW, oddNW.NE, W == null ? AllDead : W.oddNE.SE, oddNW.SW, oddNW.SE);}...

And so on; I won't write them all out here.

Once again I have four methods that have just one method call in them each because in future episodes we will be adding more stuff here.

Next time on FAIC: We now have enough gear that we can write a simple working proto-QuickLife" algorithm that steps a fixed set of Quad4s. We'll do that, take a look at its performance, and then think about ways to build a much faster, much more memory-efficient, and much more dynamic implementation on top of the foundation we've built so far.

For today's extra content:

We've already seen the four smallest spaceships (glider, and the three variants of light/middle/heavy spaceship). Loafer" is the fifth smallest spaceship, and moves at a relatively leisurely c/7. It's called loafer because of this slow pace and because it appears to be pushing a loaf still Life ahead of it. (Once again for reasons unknown WordPress is not serving up the animation, so see the wiki for the animation or click here.)