• 14
• 15
• 10
• 10
• 9

# Sparse 2d array for excessively huge worlds.

This topic is 3519 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I wanted a huge world for a tile-based game. Excessively huge. 2^32 tiles on a side. That's 18446744073709551616 individual tiles. Assuming each tile is 1 byte (They aren't, they are almost a k!) that's 16 exabytes. To put that in perspective, an exabyte is 1024 petabytes, which is 1024 terabytes. I'm fairly certain that that's more bytes than there are atoms in the universe. At the very least, we can say with confidence that I do not have 16 exabytes of memory laying around. So how do we normally handle this sort of gigantic world? We divide it into pieces. Zones. Or chunks. But I have an additional requirment, because I hate myself - the world must be seamless. It must not just be seamless, but the world coordinates must be continuous. From the perspective of the player, the world really is 2^32 tiles on a side. So how are we going to manage this? Obviously, the world is far larger than the player will ever explore. We only need to store those chunks of the world the player actually explores. (And we can probably discard them after they leave; but that's an entirely different issue.) The solution is a sparse array. A sparse array has continuous indecies, but non-continuous storage. It's actually a tree, where each leaf corresponds to a chunk of the array. In this case, working in 2 dimensions, it looks very much like a generalized quad tree. The tree is set up by specifying the bits of the index to use at each level. Hopefully this will make sense after I explain how I traverse the tree. Each level of the tree has a specific set of bits assigned to it. I'll work with 8 bit indexes, a 256*256 world, for all the examples. Lets use a 3 level tree. Our bit ranges for the levels will be 2, 2, and 4. This means that the first level uses the first 2 bits, the second level uses the next 2 bits, etc. Each tree-node sits at one level, and stores a 2d array of it's children nodes, which sit at the next level. We can find the coordinates in this child array using simple bit operations. We take the index we are trying to find and we shift it so that the level's assigned bits are moved to the right-most position. Then we mask off all but those bits. This value is now within the range of the child array. If this node is a leaf, this value is the index into the data! We recurse into our children until we reach a leaf. Fetching a particular value from the sparse array is amortized constant time. Since the world data is loaded (or generated) on demand, no more leaf chunks are stored than the player actually visits. The world appears to be infinite - or at least excessively huge - but memory usage isn't. Now. Code.
#ifndef COMMON_SPARSE_PLANE_H
#define COMMON_SPARSE_PLANE_H

#include <vector>
#include <cassert>

namespace Common
{
template <typename INTEGER_INDEX_TYPE, typename VALUE_TYPE, typename CALLABLE_GET_CHUNK>
class SparsePlane
{
public:

typedef std::vector<VALUE_TYPE> Storage;

private:

template <typename T>
static unsigned char sum( T begin, T end )
{
unsigned char r = 0;
while (begin != end) { r += *begin; ++begin; }
return r;
}

class Node
{
union
{
std::vector<VALUE_TYPE>* storage;
std::vector<Node*>* children;
} sc;

unsigned char * bits_begin;
unsigned char * bits_end;
unsigned char shift;

bool is_leaf() { return shift == 0; }
unsigned int dim() { return 1 << (*bits_begin); }

{
INTEGER_INDEX_TYPE r = 0;
while (r < dim() - 1) ++(r <<= 1);
return r;
}

public:

Node(unsigned char * bits_begin,
unsigned char * bits_end,
CALLABLE_GET_CHUNK get_chunk,
INTEGER_INDEX_TYPE x_index,
INTEGER_INDEX_TYPE y_index)
: bits_begin(bits_begin),
bits_end(bits_end)
{
assert( bits_begin < bits_end );
assert( *bits_begin < sizeof(INTEGER_INDEX_TYPE) );

shift = sum( bits_begin + 1, bits_end );
assert( shift < sizeof(INTEGER_INDEX_TYPE) );

if (is_leaf())
{
sc.storage = new std::vector<VALUE_TYPE>();
sc.storage->resize( dim() * dim() );
//Masking off the least signifigant bits will give us the left and top extents of the chunk.
}
else
{
sc.children = new std::vector<Node*>();
sc.children->resize( dim() * dim() );
for (unsigned int i = 0; i < dim() * dim(); ++i) (*sc.children) = 0;
}
}

~Node()
{
if (is_leaf()) delete sc.storage;
else
{
for (unsigned int i = 0; i < dim() * dim(); ++i) delete (*sc.children);
delete sc.children;
}
}

VALUE_TYPE& get(const INTEGER_INDEX_TYPE x_index, const INTEGER_INDEX_TYPE y_index, CALLABLE_GET_CHUNK get_chunk)
{
INTEGER_INDEX_TYPE l_x_index = (x_index >> shift) & mask();
INTEGER_INDEX_TYPE l_y_index = (y_index >> shift) & mask();

unsigned int normalized_coord = (l_y_index * dim()) + l_x_index;

if (is_leaf())
{
return (*sc.storage)[ normalized_coord ];
}
else
{
if (!(*sc.children)[ normalized_coord ]) (*sc.children)[ normalized_coord ] =
new Node(bits_begin + 1,bits_end,get_chunk,x_index,y_index);
return (*sc.children)[ normalized_coord ]->get(x_index,y_index,get_chunk);
}
}

};

Node* root;
std::vector<unsigned char> bits;
CALLABLE_GET_CHUNK get_chunk;

public:

template <typename T>
SparsePlane(T begin, T end, CALLABLE_GET_CHUNK get_chunk) : root(0), get_chunk(get_chunk)
{
while (begin != end)
{
bits.push_back(*begin);
++begin;
}
assert(!bits.empty());
assert(sum(bits.begin(),bits.end()) == sizeof(INTEGER_INDEX_TYPE));
root = new Node(&bits[0],&bits[0]+bits.size(),get_chunk,0,0);
}

~SparsePlane() { delete root; }

VALUE_TYPE& operator()(const INTEGER_INDEX_TYPE x_index, const INTEGER_INDEX_TYPE y_index)
{
return root->get(x_index,y_index,get_chunk);
}
};
}

#endif


Some assumptions I made. First, no one will ever use an INTEGER_INDEX_TYPE of more than 256 bits. I don't think that's going to be an issue. Second, INTEGER_INDEX_TYPE is unsigned. I don't expect this code will work with negative indicies, and I'm not going to test it either. Third, you'll never have less than 2 levels. One level is just an array. Use an array. Some usage code.
void load_chunk(unsigned char x_start, unsigned char y_start, unsigned int dim, std::vector<int> * vector)
{
assert(vector);
for (int i = 0; i < vector->size(); ++i)
{
(*vector) = i;
}
}

int main( int argc, char* argv[] )
{
std::vector<unsigned char> sparse_bits;
sparse_bits.push_back(2);
sparse_bits.push_back(2);
sparse_bits.push_back(4);
Common::SparsePlane<unsigned char,int,void (*)(unsigned char,unsigned char,unsigned int,std::vector<int>*)>
}


Here I used just 8 bits for the index, and 3 levels. The interface is a bit clunky, but it gets the job done. Now, what I need you for. Ask questions, so I can answer them, and turn this into a proper article! [Edited by - Deyja on August 2, 2008 11:22:11 PM]

##### Share on other sites
Quote:
 Original post by DeyjaThe tree is set up by specifying the bits of the index to use at each level.

Ah. That's a clever implementation of a sparse array, and it's probably quite effective in your situation where you have one section of the array active and the rest blank. Have you actually benchmarked it against a simple std::map or std::tr1::unordered_map implementation?

[Edited by - drakostar on August 3, 2008 5:47:23 AM]

##### Share on other sites
Nope, but the design goal isn't speed in this case, it's memory. In my specific problem domain, it's not even about ram. It's about disc storage (I don't have 16 exabytes of that either!) I also don't have a situation where I can test them, yes, in any but a trivial case. When ever I have a huge player database, out there eating up my ram, I'll certainly be looking to do this as fast as possible.

Clients and shards both store straight-up 2d arrays. This sits between them and the database.

A sparse array like this could be implemented using an std::map. You could just mask off the least-significant bits and use a two-part key. The memory usage for the tree would probably be slightly better in some cases, and worse in others. It also would not offer constant-time access.

IIRC, the unordered_map implements a single-dimension sparse array. You'd need an unordered_map of unordered_maps. It would work. You index one coordinate at a time. I'm not familiar with the look-up times of unordered_map to make a comparison. I'd expect them to use some sort of tree of index ranges, if it supports non-integer indicies like it's name implies.

This implementation really shines when you have many players radiating in all directions from a central location, such that the number of active higher level blocks over the number of active blocks is as low as possible.

Also, I'm only going to use 16-bit indicies. That's merely 2^32 unique tiles; about 65k on a side.

##### Share on other sites
It looks like you aren't asking for design help. So ignore me. Use a deterministic algorithm based on rand() to generate sections, store the seed only.

"A typical star weighs about 2x10^33 Grams, which is about 1x10^57 atoms of hydrogen per star... That is a 1 followed by 57 zeros."

my point was you could make clever use of a chaotic fractal and deterministically generate an infinite, thoroughly unique world with no data storage at all.