How to store unique keys for an infinitely generated, chunked world?

Question

My game is made up of chunks which are identified in world space with and X and Y coordinate. Each chunk contains 16 tiles by 16 tiles by 4 layers. So that I don't have to loop over every single tile every time I want to access things such as hitboxes or animation frames I store that tile's value as keys in various dictionaries such as "Animations" or "Collidables". Until now I have been doing it like this:

        public string GetTileKey(int layer)
    {
        string XString = X.ToString();
        if (XString.Length < 4)
        {
            XString = XString.PadLeft(4, '0');
        }
        string YString = Y.ToString();
        if (YString.Length < 4)
        {
            YString = YString.PadLeft(4, '0');
        }
        return layer.ToString() + XString + YString;

    }

which as you can imagine, slows things down considerably!

After chatting with a few awesome people in discord I was suggested a bitwise method which would store the first few bits as the X coordinate, the second few as the Y, and the last 2 as the layer like so:

public int GetTileKeyAsInt(int layer, IInformationContainer container)
    {
        return (X << 16) | (Y << 9) | layer;
    }

(The container parameter is not currently used, I was trying things out with its X and Y coordinates. It's really just the chunk)

which works fantastic when used with X and Y values which are between 0 and 128 and which are not negative. In addition it guaranteed no duplicate keys.

I quickly realized this wouldn't work with my world, which requires both positive and negative coordinates and an "infinitely" expanding number of chunks.

What is a better way to do this? I was planning on using a float or a double and using the first bit as the sign value, and the next eight (4 and 4) to store the X and Y coordinates of local tiles within chunks and then allocating the rest of the bits to allow for a massive number of allowable chunks. I'll admit I'm not super familiar with bitwise operations or even really the specifics between int, float and double :( but from what I've gathered it doesn't actually make sense to do bitwise operations with anything larger than an Int 32!

Answer 1

Although our world may be functionally infinite, we typically need only a finite, contiguous chunk of it at a time. We can exploit that structure to make our lives easier and our code faster.

One neat way to do this is with what's called a clipmap. Here we lay down a finite grid of tiles for our scene. Let's say for simplicity it's 1024x1024 tile on each side, or 64x64 chunks' worth, letting us simulate and display over a million tiles at a time. (You can of course make this smaller or larger as needed)

When we reach the right edge of our grid, we wrap around to the left edge and just keep going, recycling parts of the map we already used now that they're safely out of view "behind" us.

Using modular arithmetic via fast bitwise AND operations, we can look at this wrap-around local grid as a sliding window that roams around our infinite world. As long as our viewport into the world is narrower than this window, we never see the edge.

Let's say the tile at the center of the player's current view is stored as two signed longs (hey, we want to roam over a huuuuuuge area, right?). In the clipmap, that tile is stored at...

// 2^10 = 1024 (powers of 2 let us use bitwise tricks)
const int CLIPMAP_POWER = 10;    
const int CLIPMAP_SIZE = 1 << CLIPMAP_POWER;
// Set all bits smaller than our clipmap size
const int CLIPMAP_MASK = CLIPMAP_SIZE - 1;

Vector2Int GetClipmapPosition(long globalX, long globalY) {
    return new Vector2Int((int)(globalX & CLIPMAP_MASK), (int)(globalY & CLIPMAP_MASK));
}

In fact, we can use this function to map any tile anywhere in the world to its designated place in the clipmap.

Yes, two tiles A & B can collide at the same clipmap position, but only if they're a multiple of 1024 tiles apart - ie. only if we've traveled so far from A that it's been clipped out of view, and our rolling window has wrapped around and recycled its place for tile B.

That illustrates a useful property of clipmaps: although the window roams around, you never need to shift a tile you've already loaded into a new place - shuffling your contents down the way you might when removing an item from the head of a list. A column of tiles that's disappeared off the left side of the screen far enough to be recycled can just be overwritten in-place with the new column of tiles, ready to enter from the right side of the screen. If you're using arrays of value types, this keeps your memory layout contiguous & predictable to get the maximum benefit of the CPU's caching features.

When iterating over the visible range of tiles to render, we just need to take the wrap-around into account:

Vector2Int start = GetClipmapPosition(centerX - range, centerY - range);
Vector2Int end = GetClipmapPosition(centerX + range, centerY + range);

for(int x = start.x, x != end.x, x = (x + 1) & CLIPMAP_MASK) {
    for(int y = start.y, y != end.y; y = (y + 1) & CLIPMAP_MASK) {
        DoSomethingWith(clipmap[x, y]);
    }
}

Now every tile that we care about (ie. those that are currently loaded at any particular moment) has a nice, simple, unchanging address, guaranteed not to collide with any other loaded tile, and it's compact enough to convert to an ID using the trick you're already familiar with:

public struct LocalTileID {
    int x;
    int y;
    byte layer;

    public int GetHashCode() {
        return  (layer << (2 * CLIPMAP_POWER))
              | ( x    <<      CLIPMAP_POWER )
              | ( y );
    }
}