A Galaxy That Is a Pure Function

In a testbed project alongside my engine there's a starfield that can be flown through forever. It contains something like a trillion stars and stores none of them.

The whole design rests on one line:

m_RNG.Seed(m_unId);

The chunk's identifier is the seed for its own contents. The rest of the design is a consequence of that.

This continues the series taking one system at a time out of my engines.

Storage Is the Wrong Question

The instinct when asked for an enormous space is to worry about memory. A trillion stars at even a few bytes each is not a thing that fits anywhere, so the obvious approaches are to generate a large region once and save it, or to generate lazily and cache what's been visited.

Both are answering the wrong question, because both assume the stars need to exist somewhere. If the contents of a region are computed from the region's position, then the position is the storage. There's nothing to save, nothing to load, and nothing to keep consistent.

void Starfield::Chunk::SpawnStars()
{
    m_RNG.Seed(m_unId);
    m_Stars.clear();
    int nNumStars = k_nMinStars + m_RNG.Get() % (k_nMaxStars - k_nMinStars);
    ...
}

Seeding from the ID means the star count, and then every star's position and size, are a deterministic function of which chunk this is. Fly away, let the chunk be discarded, come back, and the same stars are there. Not similar stars, the same ones, because the same seed produces the same sequence.

The chunk doesn't even generate until something asks it to draw:

void Starfield::Chunk::Render(Vector3 vOffset)
{
    if (m_Stars.empty()) { SpawnStars(); }
    ...
}

Generation is deferred to first sight, which means flying past a region costs nothing for the parts that never entered view.

The ID Is the Coordinate

The identifier isn't arbitrary. The galaxy is a grid:

const unsigned int Starfield::k_unGalaxyWidth = 65535;

65535 is 0xFFFF, sixteen bits. A chunk ID is a 32-bit unsigned integer holding two 16-bit coordinates, so the ID is the position, packed. That gives 65535 squared chunks, about 4.3 billion of them, each holding between 100 and 500 stars.

Packing a coordinate pair into an integer key is an old trick, and it suits this case for a specific reason: the seed has to be stable and unique per location, and a packed coordinate is both by construction. Hashing a position would work and would need care about collisions. Using the coordinate itself can't collide, because it's a bijection.

The conversion back and forth is a pair of functions, and one detail in them is the mark of somebody who'd been burned:

double dGalaxyWidth = (double)k_unGalaxyWidth * (double)Chunk::k_fSize;
unsigned int unPosX = (unsigned int)((((double)vPosition.x + dGalaxyWidth * 0.5) / dGalaxyWidth)
                                     * (double)k_unGalaxyWidth);

Everything in that calculation is promoted to double. A galaxy 65535 chunks wide, in world units, is a number where single-precision float has gaps larger than a star. Doing the position-to-chunk mapping in float would make chunk boundaries jitter at the far edges of the space, and the resulting bug looks like stars flickering between chunks in a way that's very hard to diagnose and impossible to reproduce near the origin.

The split is the right one. Doubles for the galaxy-scale mapping, floats for positions within a chunk, because a chunk is small and local coordinates never get large. That's the standard answer to the large-world precision problem and it's here, in a testbed, in a starfield.

Seeds All the Way Down

Each star gets a seed of its own, drawn from the chunk's generator:

tmpStar.m_nSeed = m_RNG.Get();
tmpStar.m_fSize = (float)(m_RNG.Get() % (Star::k_nSizeLevels - 1) + 1) / (float)Star::k_nSizeLevels;

So there's a hierarchy: the galaxy defines chunk IDs, a chunk ID seeds a generator, that generator produces a seed per star. Any property of any star anywhere is derivable from two numbers, and neither of them is stored anywhere except as the position of the thing on screen.

This is the same idea as the two seeds per particle in my earlier engine, where variation is a function of a stored seed rather than a set of remembered rolls. Finding it again here, applied to a galaxy instead of a smoke plume, suggests it's the general answer rather than a trick that suited one system.

Sizes are quantized to sixteen discrete levels rather than being continuous. Discrete levels are what stars of the same size need if they're ever going to be drawn together, and continuous sizes would make that grouping impossible for no visible benefit, since nobody can tell a star at 7/16 from one at 0.44.

I should note the per-star seed is written and never read. It's a slot left open for something the stars would vary by later, presumably twinkle phase or color. The structure is right and one of its slots is empty, which is what a testbed looks like.

The Chunk Store Is a Sorted Vector

Loaded chunks live in a std::vector kept in ID order, searched with a hand-written binary search:

int nMin = 0;
int nMax = (int)m_Chunks.size() - 1;
while (nMin < nMax)
{
    int nMid = (nMin + nMax) / 2;
    if (m_Chunks[nMid].GetId() < unId) { nMin = nMid + 1; }
    else                               { nMax = nMid; }
}
nInsertIndex = nMin;

That's the deferred-equality form, which does one comparison per iteration instead of two and tests for a match only at the end. Written out by hand, with comments explaining why the interval always shrinks, and an assert enforcing it.

The choice of a sorted vector over a map is the interesting part. A map would be less code. The vector is contiguous, so the search walks memory the hardware likes, and the chunk objects sit next to each other rather than scattered across individual allocations. For a container that's searched constantly and modified occasionally, that's the right trade.

And the search returns its insert index through an out-parameter, so a miss immediately tells the caller where the new chunk goes. One search serves both lookup and insertion, which is the small design decision that makes a sorted vector pleasant instead of tedious.

What I'd Change

Chunks carry their own vertex buffers, which is right, but generation happens inside Render. Generating and uploading during the render pass means a frame where a new chunk appears does noticeably more work than its neighbors. Moving spawn into the update, one chunk per frame, would spread it, which is the same time-slicing idea as the asset streamer in the older engine.

I'd also make the galaxy dimensions a parameter rather than a constant. 65535 is there because it's what fits in half of a 32-bit ID, which is a reasonable default and an odd thing to hardcode when a 64-bit ID would give a galaxy nobody could cross.

And the per-star seed should either be used or removed. Only the loaded chunks are ever resident, so a few thousand stars at a time, and an unused int in them is not a memory problem. It is a question the next reader has to answer.

What Transfers

When a space is too large to store, check whether its contents can be derived from its coordinates. If they can, the size stops mattering entirely, and the interesting limits move to how fast a region can be generated rather than how much of it fits.

Use the coordinate as the seed rather than hashing it. It's stable, unique, and reversible for free.

Watch the precision at the far edge of any large coordinate space, and do the space-to-index mapping in a wider type than the one used for local positions. The bug this prevents only appears a long way from the origin, which is exactly where nobody tests.