Life, part 24

When last we left off we had representations for 0-quads - a single bit - 1-quads - four bits in a row - and 2-quads - a wrapper data structure around an unsigned short that could extract single cells or mask out any of the component 1-quads in place". The question in the cliffhanger was: how can we move a 2-quad - a 4*4 grid of cells - forwards one generation? Should we just pretend that there is a rectangle of empty cells around it?

No. Instead, we redefine what it means to step one tick forward. Stepping a 2-quad forward one tick results in a 1-quad; the center one-quad stepped one tick forwards.

Let me make sure that's clear. What I'm saying is that if we have this 2-quad, just to pick one at random:

And we step it forwards one tick, we assume that this 2-quad is embedded in a larger grid and we do not know the true neighbour counts of the twelve cells on the edge. But we do have enough information to step the center four cells forwards, and that gives us a 1-quad:

The implementation is straightforward; we've seen it a bunch of times. Since I don't have a custom-built data structure for a 0-quad or a 1-quad and they are just one bit or four bits, let's just put them in an integer and we'll figure out what to do with them later. (Recall that I said that bits 3, 2, 1, and 0 were the northwest, northeast, southwest and southeast cells of a 1-quad.)

private static int Rule(int cell, int count){ if (count == 2) return cell; if (count == 3) return 1; return 0;}private static int StepQuad2(Quad2 q){ int b00 = q.Get(0, 0) ? 1 : 0; int b01 = q.Get(0, 1) ? 1 : 0; int b02 = q.Get(0, 2) ? 1 : 0; int b03 = q.Get(0, 3) ? 1 : 0; int b10 = q.Get(1, 0) ? 1 : 0; int b11 = q.Get(1, 1) ? 1 : 0; int b12 = q.Get(1, 2) ? 1 : 0; int b13 = q.Get(1, 3) ? 1 : 0; int b20 = q.Get(2, 0) ? 1 : 0; int b21 = q.Get(2, 1) ? 1 : 0; int b22 = q.Get(2, 2) ? 1 : 0; int b23 = q.Get(2, 3) ? 1 : 0; int b30 = q.Get(3, 0) ? 1 : 0; int b31 = q.Get(3, 1) ? 1 : 0; int b32 = q.Get(3, 2) ? 1 : 0; int b33 = q.Get(3, 3) ? 1 : 0; int n11 = b00 + b01 + b02 + b10 + b12 + b20 + b21 + b22; int n12 = b01 + b02 + b03 + b11 + b13 + b21 + b22 + b23; int n21 = b10 + b11 + b12 + b20 + b22 + b30 + b31 + b32; int n22 = b11 + b12 + b13 + b21 + b23 + b31 + b32 + b33; int r11 = Rule(b11, n11); int r12 = Rule(b12, n12); int r21 = Rule(b21, n21); int r22 = Rule(b22, n22); return (r21 << 0) | (r11 << 1) | (r22 << 2) | (r12 << 3);}

Now I know what you're thinking; we're doing sixteen array lookups for the masks, then sixteen bit operations, then umpteen dozen additions, and then a bunch of bit shifts and bit ors, and this all seems very expensive. But remember the lesson of our first-pass optimization to Stafford's algorithm: we can do all 65536 computations for all possible 2-quads once before we start and store the resulting 1-quads in a lookup table! The cost then becomes a single lookup when it comes time to actually run a step forwards" operation.

We'll get to the details of the lookup table in a later episode; for now, let's assume that we have a fast lookup for getting the center 1-quad of a 2-quad stepped one ahead. What could we do with this?

Buckle up because this is where we really start to need some diagrams.

The next big insight that drives this algorithm is the question: given the gear we have so far, what could we do if we had a 3*3 square of 2-quads?

Let's just grab a configuration at random; this is a 12*12 fragment from the 151st generation of acorn.

I'm going to label the nine 2-quads according to their compass directions from the center 2-quad:

I want to focus your attention in particular on the 3-quad that is the upper left group of four 2-quads. What if we moved forward the NW, N, W and center 2-quads by one tick? We'd get four 1-quads.

Here is the same fragment, but this time from the 152nd generation of acorn with those four 1-quads marked:

We are making some progress here. The next insight is: what could we do if we had the same cells but we drew the 2-quad boundaries slightly differently? What if we drew them like this?

The labels here are N-W is the 2-quad that is on the western side of the northern edge, N-E is on the eastern side, and similarly for center-E and center-W.

If we moved those four 2-quads forwards one step, we'd get four more 1-quads:

I'm sure you see how this is going, but just to labour the point, let's see it through. If we draw the 2-quad boundaries like this:

Then we can move those four 2-quads forwards one tick to get these portions of the next tick:

And finally, if we can divide up the grid like this:

Then we can get the next tick at:
Put it all together and what have we got?

If we have a method that takes nine 2-quads then:

• We can generate from those nine 2-quads twelve other 2-quads that are portions of the interiors of those nine
• Of the 21 2-quads we now have in hand, move 16 of them forwards one step
• That generates these 16 1-quads:

• Which is enough information to construct a 3-quad in the next generation.

I suspect that you have two questions on your mind right about now:

• How on Earth are we going to do all those steps - slice up those nine quads into twelve more, step sixteen of them, and then somehow put those sixteen four-bit integers into some data structure that is useful to us - efficiently?
• Why is getting a particular 8*8 portion of a 12*12 grid stepped forwards one tick useful?

Next time on FAIC: We'll try to write some code to answer that first question.