Querying a Chunk by Chunk Path

Home --> Programming Projects --> Fractal Block Engine --> Querying a Chunk by Chunk Path

The Problem

Sometimes we want to find a chunk based on its chunk path. This page describes how we do this. For example, perhaps we want to see if there exists a chunk (in memory) with the following path:
4fe_76a_c64_239_865


The actual use case for this in Fractal Block World is not for "chunks" but rather "chunk changes objects" (CC objects). The same principal applies. A CC object stores all changes that have been made to a chunk. When we load a chunk into the "active chunk tree", we first see if an associated CC object exists (in memory) for the chunk. We look for the CC object using the chunk path of the chunk. Each CC object also has an integer id, which we can use to refer to it.

The Hashcode of a Sequence of Integers

Here is the standard way that Fractal Block World assigns an integer hashcode to a sequence of integers: 
//This is C++ code.

//The first 81 primes after one million.
//We actually only use the first 80.
int prime_table[] = {
    1000003, 1000033, 1000037, 1000039, 1000081, 1000099, 1000117, 1000121, 1000133,
    1000151, 1000159, 1000171, 1000183, 1000187, 1000193, 1000199, 1000211, 1000213,
    1000231, 1000249, 1000253, 1000273, 1000289, 1000291, 1000303, 1000313, 1000333,
    1000357, 1000367, 1000381, 1000393, 1000397, 1000403, 1000409, 1000423, 1000427,
    1000429, 1000453, 1000457, 1000507, 1000537, 1000541, 1000547, 1000577, 1000579,
    1000589, 1000609, 1000619, 1000621, 1000639, 1000651, 1000667, 1000669, 1000679,
    1000691, 1000697, 1000721, 1000723, 1000763, 1000777, 1000793, 1000829, 1000847,
    1000849, 1000859, 1000861, 1000889, 1000907, 1000919, 1000921, 1000931, 1000969,
    1000973, 1000981, 1000999, 1001003, 1001017, 1001023, 1001027, 1001041, 1001069};

//Getting a prime number with wraparound.
int GetPrime(int n) {
    if( n < 0 ) n = 0; //Should not happen.
    n = n % 80;
    return prime_table[n];
}

uint32_t GetHashOfIntSequence(
    const vector<int> & sequence)
{
    int n = 0;
    long long total = 0;
    total += GetPrime(n++) * sequence.size();
    for(int i = 0; i < sequence.size(); ++i) {
        total += GetPrime(n++) * sequence[i];
    }
    return (total % 0xffffffff);
}
So, we are multiplying each integer in the sequence by a prime number and then adding them all together. The length of the sequence is also used.

Chunk Path Class

Here is pseudo code for the ChunkPath class. This represents the path of a chunk from the root of the chunk tree.

There is a method for getting an integer hashcode for the entire path. 
class ChunkPath {
public:
    //Each integer in the path vector represents an (x,y,z) triple.
    //The integer is coded as follows: (256*x) + (16*y) + z
    //We could actually use a 2 byte integer if we wanted.
    vector<int> path;
    
    bool operator==(const ChunkPath & b) const;
    
    //Returns a single 32 bit unsigned integer hashcode
    //for the entire path.
    uint32_t Hash() const {
        return GetHashOfIntSequence(path);
    }
};

A Hash Table For Querying Chunks by Path

Here is a system to store chunks by the hashcode of their paths. In Fractal Block World, this method turns out to be much faster than using an unordered_map where the key is a ChunkPath class. 
//This class stores all chunk ids for chunks that exist
//whose chunk path have the same hashcode.
class ChunkPathHashNode {
public:
    //In practice, it is extremely rare for
    //there to be more than one chunk_id stored here.
    vector<int> chunk_ids;

    void Add(int chunk_id) {
        chunk_ids.push_back(chunk_id);
    }
    
    void Remove(int chunk_id) {
        vector<int> copy = chunk_ids;
        chunk_ids.clear();
        for(int i = 0; i < copy.size(); ++i) {
            int copy_id = copy[i];
            if( copy_id == chunk_id ) continue;
            chunk_ids.push_back(copy_id);
        }
    }
    
    bool Exists(int chunk_id) const {
        for(int i = 0; i < chunk_ids.size(); ++i) {
            if( chunk_ids[i] == chunk_id ) return true; 
        }
        return false;
    }
    
    bool Empty() const {
        return (chunk_ids.size() == 0);
    }
};


//This class can be used to quickly query chunks
//based on their chunk path.
class ChunkTracker {
private:
    //Actually storing chunks based on their chunk_id.
    unordered_map<int, Chunk* > chunk_id_to_chunk;

    //The key is a path hashcode.
    //The value is the node which stores all chunk ids
    //for chunks whose path have that hashcode.
    unordered_map<uint32_t, ChunkPathHashNode* > hash_to_node;
    
public:
    //Returns -1 if no chunk exists at that location.
    int GetChunkIDFromPath(const ChunkPath & cp) {
        uint32_t hash = cp.Hash();
        //Query the hash_to_node structure...
        //If the associated node does not exist, return -1.
        //If the node exists, iterate over all
        //chunk ids stored in that node.
        //For each such chunk_id, acquire the actual chunk
        //with that chunk_id.
        //Determine if the chunk path of that chunk equals cp.
        //...
    }
    
    //Getting a chunk based on its id.
    //Returns null if no chunk exists with that id.
    Chunk * GetChunk(int chunk_id) {
        auto itr = chunk_id_to_chunk.find(chunk_id);
        if( itr == chunk_id_to_chunk.end() ) return 0;
        return itr->second;
    }
    
    //Adding a new chunk.
    //It does not yet have a chunk_id.
    void AddChunk(Chunk * chunk) {
        //We can get the ChunkPath of chunk from chunk.
        //We assign a unique integer id for its chunk_id.
        //We add to the hash_to_node data structure.
        //...
    }
    
    void RemoveChunk(int chunk_id) {
        //...
    }    
};