Chapter 9: The Alien Formation

One marching block, not forty independent aliens

Chapter 7 argued for one list and one update rule. This chapter argues for something that sounds like the opposite and is really the same idea taken one step further: sometimes the right model is not forty objects that each know how to move, but one object that knows where forty things are.

The classic invader block is the perfect example. Forty aliens march sideways in lockstep, reverse at the wall, drop a row when they reverse, and speed up as they are destroyed. Model that as forty independent entities and you immediately have a hard problem: which alien decides that the block has hit the wall? If each one tests for itself, then on a long frame the rightmost alien reverses, the one next to it does not quite reach the wall and keeps going, and the formation shears apart. You then bolt on a coordinator to fix it, and the coordinator becomes the real model while the forty entities become bookkeeping.

Start with the coordinator instead. The formation holds one offset, one direction and a grid of booleans; an alien's position is derived from its slot. One test cannot disagree with itself.

What you will learn in this chapter

• Why per-entity decisions produce shearing bugs in formations, and why one shared decision cannot.
• How to derive positions from grid indices instead of storing them, and what that buys you.
• Why a bool[,] is the right data structure here, and what it costs.
• How the classic march works: offset, direction, reverse-and-drop.
• Why the wall test must use the live edges of the block, and what changes when it does.
• How to make difficulty an emergent property of the game state rather than a separate system.
• How to hit-test against a derived grid without allocating.
• The caveats: frame-rate dependence, the Speed recomputation, and where this model stops working.

The code for this chapter

The demonstration is at github.com/nodoid/MonoGameBook/src/Chapter09. Tap an alien to destroy it and watch two things happen: the survivors speed up, and if you clear an outer column the block starts marching further before it turns.

Positions you do not store

The formation's state is remarkably small:

private readonly bool[,] alive = new bool[Columns, Rows];

public float OffsetX { get; private set; }
public float OffsetY { get; private set; }
public int Direction { get; private set; } = 1;
public int AliveCount { get; private set; }
public int DropCount { get; private set; }

Forty booleans, two floats and three integers. There is no array of positions, because a position is a function of a slot:

public Vec2 PositionOf(int column, int row) =>
    new(BaseX + column * spacingX + OffsetX,
        20f + row * spacingY + OffsetY);

BaseX centres the block in the field:

private float BaseX => (fieldWidth - (Columns - 1) * spacingX) / 2f;

This is the central trick and it is worth stating as a principle: if a value can be derived cheaply from state you already have, deriving it is usually better than storing it. Stored positions can drift out of sync with the thing that is supposed to be moving them; a derived position cannot. There is no update step that can be missed, no partially-updated frame, no ordering question.

It also makes the whole formation trivially serialisable, which Chapter 20 takes advantage of: to save a game in progress you need two floats, a direction, and forty bits.

Why a two-dimensional array

bool[Columns, Rows] is a rectangular array — one allocation, contiguous, with no per-row objects. Alternatives, and why they lose here:

• `List<Alien>` with a `Slot` field. Requires a search to answer "is (3, 2) alive?", and the list order drifts from the grid order as things are removed.
• A jagged `bool[][]`. Six allocations instead of one, and an extra pointer dereference per access, for no benefit when the grid is genuinely rectangular.
• A `ulong` bitmask. Forty slots fit in a 64-bit integer, and this is genuinely faster and smaller. It is also unreadable in a debugger and needs a helper for every access. Worth it in a game with hundreds of formations; not worth it here.

bool[,] costs one byte per slot, which for a 8 × 5 grid is forty bytes. Readability wins.

The march

The entire movement rule is nine lines:

public void Update(float seconds)
{
    if (AliveCount == 0)
        return;

    OffsetX += Direction * Speed * seconds;

    // The wall test uses the live edges, so a cleared outer column widens the march.
    float left  = BaseX + LeftmostLiveColumn  * spacingX + OffsetX;
    float right = BaseX + RightmostLiveColumn * spacingX + OffsetX;

    if (right > fieldWidth - spacingX * 0.5f && Direction > 0)
        Reverse();
    else if (left < spacingX * 0.5f && Direction < 0)
        Reverse();
}

private void Reverse()
{
    Direction = -Direction;
    OffsetY += dropDistance;
    DropCount++;
}

OffsetX moves; every alien's position moves with it, because every alien's position is computed from it. There is no loop over aliens in the update at all.

The direction guard

&& Direction > 0 looks redundant — surely if the right edge is past the wall we should reverse? It is not redundant, and leaving it out produces one of the more entertaining bugs in this style of code.

Suppose a long frame moves the block far enough that its right edge is well past the wall. It reverses and starts moving left. On the next frame the right edge is still past the wall, because one frame of movement did not undo the overshoot. Without the guard it reverses again, and again, and the formation vibrates against the wall dropping a row every frame until it reaches the bottom of the screen.

The guard says: only reverse if you were moving towards the wall you just hit. It makes the reversal idempotent with respect to overshoot.

Live edges

The wall test does not use column 0 and column 7. It uses the leftmost and rightmost columns that still contain a living alien:

private int RightmostLiveColumn
{
    get
    {
        for (int column = Columns - 1; column >= 0; column--)
        for (int row = 0; row < Rows; row++)
            if (alive[column, row])
                return column;

        return Columns - 1;
    }
}

This is a rule from the original 1978 game and it is a genuinely good piece of design. Clear the right-hand column and the block can now march further right before turning, so the play area effectively widens as you clear it. The player's own progress changes the shape of the problem, without a single line of code that says "if the player has cleared a column, do something different".

It costs a scan of up to forty booleans, twice per frame, which is nothing. If it ever were something, you would maintain the two edge indices incrementally in KillNearest — but do that only when a profiler tells you to, because the scan is obviously correct and the incremental version has three edge cases.

Difficulty that is not a system

Here is the whole difficulty curve:

/// <summary>
/// Speed rises as the block thins out. That acceleration is the difficulty curve;
/// it is not a separate system.
/// </summary>
public float Speed => 26f + 150f * (1f - AliveCount / (float)(Columns * Rows));

Full block: AliveCount is 40, the fraction is 1, so speed is 26 units per second. One alien left: the fraction is 0.025, so speed is about 172 — six and a half times faster.

There is no difficulty manager, no level table, no timer that ratchets a multiplier. The pressure the player feels is a direct function of how well they are doing, computed as a property. That has three properties worth wanting:

It is self-balancing. A player who is struggling faces a slow block, because they have not killed many. A player who is winning faces a fast one.

It is legible. The player can see the cause. Every alien you kill makes the rest faster, and that is a rule you can learn in one game.

It cannot desynchronise. A stored currentSpeed field updated in KillNearest would be one more thing to get wrong on reset, on load, on a two-kills-in-one-frame edge case. A computed property is always right.

This is the game-design counterpart of the derived-position principle above, and it generalises: prefer difficulty that falls out of the state you already have over difficulty applied from outside.

Hit-testing a derived grid

Because there are no alien objects, shooting one means finding the nearest live slot:

public bool KillNearest(Vec2 point, float radius)
{
    float best = radius;
    int bestColumn = -1;
    int bestRow = -1;

    for (int column = 0; column < Columns; column++)
    for (int row = 0; row < Rows; row++)
    {
        if (!alive[column, row])
            continue;

        float distance = (PositionOf(column, row) - point).Length;
        if (distance < best)
        {
            best = distance;
            bestColumn = column;
            bestRow = row;
        }
    }

    if (bestColumn < 0)
        return false;

    alive[bestColumn, bestRow] = false;
    AliveCount--;
    return true;
}

Three things to notice.

`best` starts at `radius`, not at infinity. That single initialisation is both the "find the nearest" and the "and only if it is close enough" test. Anything further away than radius can never beat the initial value, so it can never be selected.

The method returns `bool` and does the mutation itself. Returning the slot indices and letting the caller kill it would be more "pure", and would also create a window in which a caller can forget to decrement AliveCount. Keeping the mutation next to the search makes the invariant — AliveCount equals the number of true entries — impossible to break from outside.

Nothing allocates. No LINQ, no temporary list of candidates, no Vec2[] of positions. This runs every time a shot lands, and in Chapter 22's terms it is the sort of method that must not produce garbage.

For forty slots the linear scan is the right answer. Chapter 10 discusses when a scan stops being acceptable and what to do about it.

Where this model stops working

It would be dishonest to present the formation as a general pattern. It is a very good fit for a specific shape of problem, and a bad fit outside it. The boundaries:

All members must move identically. The moment one alien breaks formation to dive at the player — as in Galaga — its position can no longer be derived from a shared offset. The usual answer is a hybrid: the formation owns the slots, and a diving alien is promoted to a real entity in Chapter 7's world, with a slot reserved for it to return to.

Membership must be a fixed grid. Aliens that spawn in arbitrary positions, or a formation that reflows when a column empties, do not fit bool[Columns, Rows].

The count must be small enough for scans. Forty is fine. Four thousand is not, and at that point you want the spatial partitioning from Chapter 10.

Caveats

Speed is recomputed on every access

Speed is a computed property with a division, and Update reads it once per frame — fine. If you find yourself reading it several times per frame, or from a draw loop, assign it to a local first. This is a general point about computed properties in game code: they are free until they are in a loop.

The march is frame-rate dependent in one respect

OffsetX += Direction * Speed * seconds is frame-rate independent, but where the reversal happens is not: a long frame overshoots the wall further before turning, so the block turns at a slightly different X. With the direction guard in place this is cosmetic rather than a bug, and running the formation inside Chapter 4's fixed-step accumulator removes it entirely.

OffsetY only ever increases

There is no reset for OffsetY short of Reset(), which is deliberate — the block descends and never climbs. It also means a long game eventually walks the formation off the bottom of the screen, which in the real game is the lose condition. If yours is not, you need an explicit floor.

Killing during iteration

KillNearest mutates alive inside its own scan, which is safe only because it mutates after the loop finishes. If you extend it to kill several aliens — a bomb, say — collect the slots first and clear them afterwards, exactly as Chapter 7 collected the dead before removing them.

The centre column is not the centre of the block

BaseX centres the full grid, not the surviving one. As the outer columns are cleared, the surviving aliens are no longer centred in the field. That is correct for an invader game — the block keeps its shape — but if you want the survivors to re-centre, that is a different model and a genuinely harder one.

Building and running this chapter

The solution is src/Chapter09/Chapter09.sln in the book's repository at github.com/nodoid/MonoGameBook/src/Chapter09. It builds and runs entirely on its own; nothing in it depends on any other chapter having been read or built.

Build either head from the chapter folder:

cd src/Chapter09
dotnet build Android/Chapter.Android.csproj
dotnet build iOS/Chapter.iOS.csproj

To deploy to a connected Android device or a running emulator:

dotnet build Android/Chapter.Android.csproj -t:Run

To run on the iOS Simulator without opening an IDE, build for the simulator runtime and install the bundle by hand:

dotnet build iOS/Chapter.iOS.csproj -p:RuntimeIdentifier=iossimulator-arm64
xcrun simctl install booted \
  iOS/bin/Debug/net10.0-ios/iossimulator-arm64/Chapter09.iOS.app
xcrun simctl launch booted com.monogamebook.chapter09

Everything the chapter demonstrates is reachable by touch on the first screen; there are no menus to navigate and nothing to load.

Try it yourself

1. Clear the entire right-hand column and watch the block march noticeably further right before turning.
2. Remove the && Direction > 0 guards and let the block reach the wall. It will drop a row every frame.
3. Change Speed to a constant 60 and play. The game is still functional and is much less interesting; difficulty curves matter more than they look.
4. Add a Vec2? DiveTarget to one slot and let that alien leave the formation, drawing it from a Chapter 7 entity while its slot stays reserved. This is the hybrid model in miniature.
5. Replace bool[,] with a ulong bitmask and IsAlive with a shift-and-test. Measure whether you can tell the difference — you will not be able to, which is the point.

Summary

Forty things that move together are better modelled as one thing that knows where forty things are. The formation holds an offset, a direction and a grid of booleans; each alien's position is derived from its slot with three multiplies. Nothing can shear apart, because there is only one decision being made.

That single decision — the wall test — needs two details to be correct. It must be guarded by the current direction, so an overshoot does not cause it to reverse every frame and drop the block to the floor. And it must be applied to the live edges of the block rather than the nominal ones, which is what makes clearing an outer column widen the march and turns the player's progress into a change in the shape of the game.

Difficulty is a computed property, not a system: speed rises as the block thins, so pressure is a direct, legible function of how well the player is doing, and it can never fall out of step with the state it is derived from.

The model has limits, and they are worth knowing before you adopt it. All members must move identically, membership must be a fixed grid, and the counts must be small enough that a linear scan is free. A diving alien is a hybrid — a formation slot plus a real entity — not an extension of this design.

Chapter 10 introduces the one thing the formation cannot do for you: deciding whether the player's shot actually hit anything, which turns out to be a much more interesting problem than "do these two rectangles overlap".