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

by dw28   Last Updated October 09, 2019 08:13 AM - source

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.

Related Questions

How can I make huge terrains in Unity?

Updated October 31, 2017 10:13 AM

SRTM data represented in 3D using Unity Terrain

Updated September 27, 2018 06:13 AM

Level editing using a 2D map for a 3D game

Updated September 05, 2017 02:13 AM