1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks muchly! I assumed to try Dictionary as a first stop, but had no real idea about its performance, and whether anything else might be better suited. Sounds like it should fit the bill just fine. Also good to know how to actually implement one, cheers! \$\endgroup\$ – dw28 Oct 9 '19 at 22:01
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ One useful trick to add: if you address your local area of interest using modular arithmetic (which can be a simple bitwise AND if your area's width is a power of two), then you only ever need to update one column or row at a time as the player moves around, rather than shifting every array entry over one. You just replace the column that has left the area of interest with the one that has entered — they both have the same modulo. This can make it easier to do incremental updates if the chunks are being streamed/re-generated on the fly, since your destination slots aren't moving targets. \$\endgroup\$ – DMGregory Oct 9 '19 at 11:06
  • \$\begingroup\$ @Engineer Thanks. Good info, but there isn't really a "player" in this case - being isometric, the camera itself is the player... and can be panned around the terrain quickly. This is why I'm wondering how much utility there would actually be in unloading distant chunks... or whether using chunks is even something worth doing. \$\endgroup\$ – dw28 Oct 9 '19 at 22:06
-2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.