Life, part 33

Last time in this series we learned about the fundamental (and only!) data structure in Gosper's algorithm: a complete quadtree, where every leaf is either alive or dead and every sub-tree is deduplicated by memoizing the static factory.

Suppose we want to make this 2-quad, from episode 32:

This is easy enough to construct recursively:

Quad q = Make( Make(Dead, Alive, Alive, Dead), // NW Empty(1), // NE Make(Dead, Dead, Alive, Alive), // SE Make(Dead, Alive, Alive, Dead)) // SW

Since Make is memoized, the NW and SW corners will be reference-equal.

But suppose we had this quad in hand and we wanted to change one of the cells from dead to alive - how would we do that? Since the data structure is immutable, a change produces a new object; since it is persistent, we re-use as much of the old state as possible. But because we re-use quads arbitrarily often, a quad cannot know its own location.

The solution is: every time we need to refer to a specific location within a quad, we must also say what the coordinates are in the larger world of the lower left corner cell of that quad.

Let's start with some easy stuff. Suppose we have a quad (this), the coordinate of its lower-left corner, and a point of interest (p). We wish to know: is p inside this quad or not?

(Source code for this episode is here.)

private bool Contains(LifePoint lowerLeft, LifePoint p) => lowerLeft.X <= p.X && p.X < lowerLeft.X + Width && lowerLeft.Y <= p.Y && p.Y < lowerLeft.Y + Width;

Easy peasy. This enables us to implement a getter; again, this is a method of Quad:

// Returns the 0-quad at point pprivate Quad Get(LifePoint lowerLeft, LifePoint p){

If the point is outside the quad, assume it is dead.

 if (!Contains(lowerLeft, p)) return Dead;

The point is inside the quad. Did we find the 0-quad we're after? Return it!

 if (Level == 0) return this;

We did not find it, but it is around here somewhere. It must be in one of the four children, so figure out which one and recurse. Remember, we'll need to compute the lower left corner of the quad we're recursing on.

 long w = Width / 2; if (p.X >= lowerLeft.X + w) { if (p.Y >= lowerLeft.Y + w) return NE.Get(new LifePoint(lowerLeft.X + w, lowerLeft.Y + w), p); else return SE.Get(new LifePoint(lowerLeft.X + w, lowerLeft.Y), p); } else if (p.Y >= lowerLeft.Y + w) return NW.Get(new LifePoint(lowerLeft.X, lowerLeft.Y + w), p); else return SW.Get(lowerLeft, p); }}

Once we've seen the getter, it's easier to understand the setter. The setter returns a new Quad:

private Quad Set(LifePoint lowerLeft, LifePoint p, Quad q){ Debug.Assert(q.Level == 0);

If the point is not inside the quad, the result is no change.

 if (!Contains(lowerLeft, p)) return this;

The point is inside the quad. If we are changing the value of a 0-quad, the result is the 0-quad we have in hand.

if (Level == 0) return q;

We need to recurse; you might think that the setter logic is going to be a mess right now, but actually it is very straightforward. Since setting a point that is not in range is an immediate identity, we can just recurse four times!

long w = Width / 2;return Make( NW.Set(new LifePoint(lowerLeft.X, lowerLeft.Y + w), p, q), NE.Set(new LifePoint(lowerLeft.X + w, lowerLeft.Y + w), p, q), SE.Set(new LifePoint(lowerLeft.X + w, lowerLeft.Y), p, q), SW.Set(lowerLeft, p, q)) ;}

That's the internal logic for getting and setting a 0-quad inside a larger quad. I'll also add public get and set methods that are just wrappers around these; the details are not particularly interesting.

What about drawing the screen? We haven't talked about it for a while, but remember the interface that we came up with way back in the early episodes: the UI calls the Life engine with the screen rectangle in Life grid coordinates, and a callback that is called on every live cell in that rectangle:

 void Draw(LifeRect rect, Action<LifePoint> setPixel);

The details of zooming in" to draw the pixels as squares instead of individual pixels was entirely handled by the UI, not by the Life engine, which should make sense.

We can quickly determine whether a given quad is empty, and therefore we can optimize the drawing engine to skip over all empty quads without considering their contents further, and that's great. But there is another possibility here: because we can determine quickly if a quad is not empty, we could implement zooming out", so that every on-screen pixel represented a 1-quad or a 2-quad or whatever; we can zoom out arbitrarily far.

Let's implement it! I'm going to add a new method to Quad that takes four things:

• What is the coordinate address of the lower left corner of this quad?
• What rectangle, in Life coordinates, are we drawing?
• The callback
• What is the level of the smallest quad we're going to draw? This is the zoom factor.

private void Draw( LifePoint lowerLeft, LifeRect rect, Action<LifePoint> setPixel, int scale){ Debug.Assert(scale >= 0);

If this quad is empty then that's easy; there's nothing to draw.

 if (IsEmpty) return;

The quad is not empty. If this quad does not overlap the rectangle, there's nothing to draw. Unfortunately I chose to make the rectangle be top left corner, width, height" but we are given the bottom left corner, so I have a small amount of math to do.

 if (!rect.Overlaps(new LifeRect( lowerLeft.X, lowerLeft.Y + Width - 1, Width, Width))) return;

(Do these rectangles overlap?" is of course famously an interview problem; see the source code for my implementation.)

If we made it here we have a non-empty quad that overlaps the rectangle. Is this the lowest level we're going to look at? Then set that pixel.

 if (Level <= scale) { setPixel(lowerLeft); return; }

We are not at the lowest level yet. Simply recurse on the four children; if any of them are empty or not overlapping, they'll return immediately without doing more work.

 long w = Width / 2; NW.Draw(new LifePoint(lowerLeft.X, lowerLeft.Y + w), rect, setPixel, scale); NE.Draw(new LifePoint(lowerLeft.X + w, lowerLeft.Y + w), rect, setPixel, scale); SE.Draw(new LifePoint(lowerLeft.X + w, lowerLeft.Y), rect, setPixel, scale); SW.Draw(lowerLeft, rect, setPixel, scale);}

That's the internal logic; there is then a bunch of public wrapper methods around it that I will omit, and a new interface IDrawScale. We now have enough gear that we can start implementing our actual engine:

sealed class Gosper : ILife, IReport, IDrawScale{ private Quad cells; public Gosper() { Clear(); } public void Clear() { cells = Empty(9); } public bool this[LifePoint p] { get => cells.Get(p) != Dead;

That's all straightforward. But what about the setter? We've made a 9-quad, but what if we try to set a point outside of it? Fortunately it is very cheap to expand a 9-quad into a 10-quad, and then into an 11-quad, and so on, as we've seen.

 set { while (!cells.Contains(p)) cells = cells.Embiggen(); cells = cells.Set(p, value ? Alive : Dead); } }

The implementation of Embiggen is just what you would expect:

public Quad Embiggen(){ Debug.Assert(Level >= 1); if (Level >= MaxLevel) return this; Quad q = Empty(this.Level - 1); return Make( Make(q, q, NW, q), Make(q, q, q, NE), Make(SE, q, q, q), Make(q, SW, q, q));}

And the rest of the methods of our Gosper class are uninteresting one-liners that just call the methods we've already implemented.

I've updated the UI to support zoom out" functionality and created a Life engine that does not step, but just displays a Quad. Previously we could display a zoomed-in board:

or one pixel per cell:

But now we can display one pixel per 1-quad:

or one pixel per 2-quad, or whatever; we can zoom out arbitrarily far. If any cell in the quad is on, the pixel is on, which seems reasonable. This will let us much more easily visualize patterns that are larger than the screen.

Next time on FAIC: How do we step a quad forward one tick?