Recommended data structure for storage and fast access of infinite chunk-based heightmap terrain

Question

I'm aiming to create a chunk based heightmap terrain in Unity. I already have a basic multifractal simplex noise set up and working, able to generate heightfields and meshes at runtime... but only individually for the moment.

I'm attempting to work out how best to store and access each chunk. I already have a couple of methods worked out to convert global positions to chunk coordinates and chunk-local barycentric triangle coordinates, so I can interpolate heights. I've used that to build a method to march a camera-space-to-world-space ray across the mesh and iterate through x/z-plane intersections until it finds the height-intersection - for a fast way to look up mouse-position on the terrain without having to attach physics collision meshes for each chunk and use Unity's raycasting. That's all working nicely.

I'm just a bit stumped now on how to implement the main infinite-grid storage that I'll generate chunk meshes from.

This is planned to be in service of a game with an isometric perspective, revealing the world as units explore fog-of-war over time... with the ability to move the camera around the uncovered terrain fairly quickly, so I'm guessing there might be limited scope for unloading previously generated chunks... it'll be an ever-expanding dataset (so I'll presumably have to be looking for ways to keep it light on memory)

I figure I can either:

1. Create a 2-dimensional array of float (or perhaps short - 64k height levels should probably be plenty) for the entire terrain, and dynamically resize the array as each x/z boundary is pushed back. Generate just the terrain mesh in chunks, to keep each mesh chunk under the Unity 64k-vertex limit.
2. Create a grid manager class, which has some kind of dynamic data structure that stores map-chunk objects, and instantiates them/retains references to them as they're demanded, each of which would contain its own (res*res)-sized heightmap array.
3. Something else?

I'm assuming option 2 will have the most mileage, but what I'm most unsure about is what kind of dynamic data structure to use. I'd guess some kind of key/object pair structure, where the key is built from the chunk coordinates?

Assuming I'll want to access height-values quickly and constantly, across chunk-boundaries, for things like my mouse-ray-intersection method, and for pathfinding code, etc... I presume I'll need a way to access chunks that is nearly as fast as looking up arrays by indices, and O(1) complexity. Or perhaps some way of caching recently-accessed chunks or chunks that the camera is near? Or pointers to them, or something?

As you can probably tell I'm fairly new to the gamedev side of things, but I have a VFX background, and so know my way around 3D geometry math and basic scripting. In terms of designing/structuring/implementing a game, I'm a total novice though, so any pointers to relevant tutorials and such would be much appreciated.

Answer 1

You could use the class Dictionary to store chunks. A C# Dictionary is an association between keys and values with O(1) performance on retrieving values by key. A Dictionary is also a sparse data-structure, which means that it is not necessary for the whole address-space to be filled.

First, create a struct ChunkAddress which represents the unique identifier of a chunk. In your case, a chunk could be identified by its x and z coordinate in the world grid. The address structure should also have a custom implementation of GetHashCode, because that method is used internally by Dictionary to convert keys into hashtable entries. I've stolen the implementation from this stackoverflow post. And when you override GetHashCode, you also have to override Equals.

So this struct could look like this:

public struct ChunkAddress {
     public int x;
     public int z;

     public ChunkAddress(int x, int z) {
         this.x = x;
         this.z = z;
    }

    public override int GetHashCode() {
        unchecked { 
            int hash = 17;
            hash = hash * 23 + x;
            hash = hash * 23 + z;
            return hash;
        }
    }
    public override bool Equals(Object obj) {
        if ((obj == null) || ! this.GetType().Equals(obj.GetType())) {
            return false;
        } else { 
            ChunkAddress other = (ChunkAddress) obj; 
            return (x == other.x) && (z == other.z);
        }   
    }
}

Now you can declare a dictionary for your chunks like this:

Dictionary<ChunkAddress, Chunk> chunks;

You can then try to retrieve a chunk with chunks.TryGetValue(key, out value). The boolean return value tells you if that chunk already exists in the dictionary. If it does, it can be found in the second argument you passed to that method. If it doesn't, you have to create that chunk and store it.

If you need the chunk at a grid location, you would use a method like this (untested!):

public Chunk GetOrCreateChunkAtGridLocation(int x, int z) {
    Chunk chunk;
    ChunkAddress address = new ChunkAddress(x, z);
    if (chunks.TryGetValue(address, out chunk) {
          // chunk exists in the dictionary
          // the variable "chunk" now references it
    } else {
          // chunk doesn't exist yet, so we have to create it
         chunk = new Chunk();
         /* initialize the chunk */

         // store chunk in the chunks collection so we can 
         // retrieve it from memory the next time we need it
         chunks.Add(address, chunk);
   }
   return chunk;
}

Answer 2

You will have a limited area of interest around your player, no matter if the world space is infinite, so you should never need more than that number of chunks in memory. (For other matters, see below.)

Let's say you had 5x5 chunks, with the player in the middle. For this range=5, the offsets from player would be:

-2 -1 0 +1 +2

For 2 dimensions this would be a 2D array of 5x5=25 chunks; for 3 dimensions this would be a 3D array of 5x5x5=125 chunks. 0 is always the middle (e.g. [0,0,0]) where your player is at. Multiple players with their own (overlapping) areas of interest, is something I'll leave to you.

An array accessed by offset like this, is O(1) read access, and is ideal. Obviously, you cannot index an array by negative numbers, so you will need to convert to array index space back (and forth) by adding (or subtracting) (range - 1) / 2 to offset.

A hashmap is amortised O(1) to read - still great. Make a 2D or 3D hashmap from a normal long, int or even string keyed hashmap by splitting the long, int, or string into multiple parts. For example, a unsigned long of 64 bits could be used as 21 bits x 3 (for x, y and z) = 63 bits total.

This is local space keying. If you want to retrieve chunks by world space, the approach to hashmap use is the same, only you'll probably need to serialise and deserialise to and from disk (or, from a large portion of memory - but ultimately that will run out if you don't limit your world size).

If you want to store what has happened in other, previously visited chunks... disk? LocalStorage? a large but finite section of main memory? - your call. But the coordinates system can work the same, while the area of interest array restricts the consumption of main memory to some fixed bound.

Most such applications have the low fat form of the chunk which sits on disk or on the server, and is decompressed once it reaches cache / registers; and the full fat form which can sit in memory (or possibly cache L3), decompressed and ready for instant use.

Answer 3

There is this awesome repo https://github.com/jacksondunstan/NativeCollections which has multiple collection implementations all of which you can find on his blog (there are links in the repo's README, as well as his blog https://jacksondunstan.com/ where he describes all of them and what they are best for). There are more of them (which are not in the readme) so be sure to check out his blog.

I think you could use some of these for your use cases. I did a simular system once and used a 3d array of structs, which was a simple and a valid solution for the scope of the project. It boils down to the scope and what you will be doing the most to the collection.