Data structure for expandable 3D array?

Question

I'm looking for a data structure similar to T[,,] (a 3D array) except I don't know the dimensions beforehand (nor have a reasonable upper bound) that will expand outwards as time goes on. I'd like to use negative indexes as well.

The only thing that comes to mind is a dictionary, with some kind of Point3 struct as the key. Are there any other alternatives? I'd like to lookups to be as fast as possible. The data will always be clustered around 0,0,0. It can expand in any direction, but there will never be any "gaps" between points.

---

I think I'm going to go ahead and just use a Dictionary<Point3, T> for now, and see how that performs. If it's a performance issue I'll try building a wrapper around T[,,] such that I can use negative indexes.

Answer 1

Array access is a very fast linear lookup - if speed of lookup is your priority, then it's probably the way to go, depending on how often you will need to modify your arrays.

If your goal is to maintain the chunks around a player, you might want to arrange a "current world" array structure around the player, such that it is a 3-dimensional array with the centre chunk at 9,9,9 with a size of [20,20,20]. Each time the player leaves the centre chunk for another, you re-index the array to drop the old chunks and move on.

Ultimately, you're asking for options on how to optimize your game engine, but it's nearly impossible to say which is going to be correct for you. Even though games tend to be more optimized for performance than other applications, don't get lured into micro-optimizations; optimize for readability first and then optimize for performance when you find it necessary.

If you suspect this particular data-structure is going to be a bottleneck in your engine, put some performance tracing in so it's easy to be sure one way or the other once you've got the engine running.

Answer 2

If you may need range queries, KD-Trees comes to mind. They are tree-like structures, at each level seperate the universe into two along one axis. They offer O(logN) lookup time (for constant number of dimensions) which may or may not be fast enough, but they also provide O(logN + S) time for range queries where S is the size of the items found, which usually is very good. They can handle dynamic data (insertions and deletions along with lookups) but the tree may become unbalanced as a result. Also you can do Nearest Neighboor search from a given point, (i.e. get the 10 nearest objects to point (7,8,9)) Wikipedia, as always, is a good starting point: http://en.wikipedia.org/wiki/Kd-tree

If there are huge numbers of things in the world, of if the world is very dynamic (things move, be created/destroyed all the time), kd-trees may not be good enough. If most of the time you will only ask "give me the thing at (7,8,9)" you can either use a hash as you mentioned in your question or something like a List<List<List<T>>>. I'd just implement whichever is easier within an interface and worry about the performance later.

Answer 3

Obviously you'll need to store this in a data structure resembling a sparse array, because you have no idea how large your data-set is going to be. So a Dictionary seems reasonable.

I'm going a little crazy here, but I think your indices should be in Spherical Coordinates. It makes sense to me as your data grows outwards. It will also make finding elements at a specific range from (0, 0, 0) extremely easy.

Answer 4

I am kind of assuming you need the dynamic aspect because array could be huge. In that case, what you could try is to allocate your array as a set of 3d 'tiles'. At the top level you have a 3d data structure that stores pointers to your tiles. You expand and allocate this as you go along.

Each individual tile could contain, say, 32x32x32 voxels. Or whatever amount suits your goals. Looking up you tile is done by dividing your coordinate index by 32 (by bitshifting, of course), and the index in the tile is calculated by masking away the upper bits.

A lookup like this is fairly cheap, possible on par with a .net Dictionary, but it will use less memory, which is good for performance too.

The resulting array will be chunky, though: the array boundaries are multiples of your tile size.