Storing the Blocks in a Chunk

Home --> Programming Projects --> Block Engine --> Storing the Blocks in a Chunk

Basic Idea

Once a chunk is active and players and other entities can interact with it, we want the querying of certain block information within the chunk to be fast. So, we do NOT merge adjacent blocks of the same type together. This is what we do instead:

Each chunk has a Default Block Type . We only store blocks within the chunk whose type is different from this default block type, and we store them in a hash table.

We are describing a simple system in which the only information that a block has is its type. If we want blocks to have auxillary information, then this can be stored in a separate hash table. Note that we can still be clever. If "stone" blocks have a "health" variable, then perhaps that "stone" type block has a default value for the health variable. And so we only need to store the value of the health variable for a stone block if it differs from the stone default value. Etc.

Local Block Positions

In Fractal Block World, a chunk is 16x16x16 blocks. So, it takes exactly 12 bits to represent the position of a block in a chunk. So when we want to save space, we use a 2 byte integer (a short) to refer to the position of a block within a chunk. However, normally we use the following class to refer to the position of a block in a chunk (that uses 1 byte for each x,y,z coordinate):

//This is C++ code.

class LocalBlockPos {
public:
    signed char x;
    signed char y;
    signed char z;
    
    LocalBlockPos() {
        x = -1;
        y = -1;
        z = -1;
    }
    
    LocalBlockPos(
        signed char x,
        signed char y,
        signed char z)
    {
        this->x = x;
        this->y = y;
        this->z = z;
    }

    LocalBlockPos(
        short pos_hash)
    {
        SetFromHashCode(pos_hash);
    }

    //So we can use this class as the key in a map.
    bool operator<(const LocalBlockPos & b) const {
        //...
    }
    
    bool operator==(const LocalBlockPos & b) const {
        //...
    }

    LocalBlockPos operator+(const LocalBlockPos & b) const {
        //...
    }

    bool IsValid() const {
        if(x < 0) return false;
        if(y < 0) return false;
        if(z < 0) return false;
        if(x > 15) return false;
        if(y > 15) return false;
        if(z > 15) return false;
        return true;
    }

    //It is the caller's responsibility to make sure
    //that the position is valid before calling this function.
    int ComputeHashCode() const {
        return z + (16 * y) + (256 * x);
    }
    
    void SetFromHashCode(int code) {
        z = code % 16;
        code /= 16;
        y = code % 16;
        code /= 16;
        x = code % 16;
    }
	
    //...
};

//So LocalBlockPos can be used as the key of a C++11 unordered map.
namespace std {
template <>
struct hash
{
    std::size_t operator()(const LocalBlockPos & k) const {
        return k.ComputeHashCode();
    }
};
} //End namespace std.

The reason why we used signed chars for the x,y,z coordinates is because sometimes we want to represent the position of a block that it slightly outside the chunk. This gives us some wiggle room.

We use "IsValid" to check if the LocalBlockPos really referes to the position of a block in the chunk.

Note that a local block position can be completely recovered from its hash code.

Storing All Blocks First Try

Here is simple code to store the block type of every block within a chunk. First, here is the class to store information about an individual block:

class BlockPosInfo_FirstTry {
    int block_type;
};

Notice here that we are using a 4 byte integer to represent the type of a block. We will revisit this issue later.

Here is a class with a hash table of all blocks that are not of the default type:

class BlockHolder_FirstTry {
    int default_block_type;
    
    //The key is the LocalBlockPos hash code.
    //The value is information associated to the block position.
    unordered_map<short, BlockPosInfo_FirstTry> block_data;
};

Storing All Blocks Second Try

Sometimes we want to know if a block is physically solid, and we want to know immediately. Instead of determining the type of the block and then determining if that type is solid (assuming whether or not a block is solid depends only on its type), we could instead cache whether or not the block is solid for use later. That is, we could have "flags" stored in the BlockPosInfo class. Here is what it would look like:

class BlockPosInfo_SecondTry {
    int block_type;
    
    //Can store up to 8 bool values here using bit masks:
    unsigned char flags;
};

The BlockHolder changes accordingly:

class BlockHolder_SecondTry {
    int default_block_type;
    
    unsigned char default_block_type_flags;
	
    //The key is the LocalBlockPos hash code.
    //The value is information associated to the block position.
    unordered_map<short, BlockPosInfo_SecondTry> block_data;
};

The default_block_type_flags variable caches various bools associated to the default block type.

Note that there are some block attributes that we might want to cache and access quickly that do not depend on the block type. For these, we need a convention about the value of the bool if the block is not in the hash table. Take for example Fractal Block World. Some blocks have this property of "begin a child", which means that there is a smaller chunk that occupies the same volume as the block! Whether or not a block position is a child does not depend on the block type, however we still store it in the "flags" variable in the BlockPosInfo_SecondTry class. If a block is not in the hash table, then its "is_child" variable is false. Once the block becomes a child, we need an entry for it in the BlockHolder_SecondTry::block_data hash table, even if the type of the block is the same as the default block type.

Storing All Blocks Third Try

We mentioned that we use 4 bytes to represent the type of a block. This is certainly enough for Fractal Block World. However Fractal Block World uses thousands of block types, and it would be great to somehow use only one byte to represent the block type of a block within a chunk.

Fortunately, my experiments show that most chunks use way less than 256 different block types (even chunks which contain thousands of blocks). Most of the time less than 20 unique block types are used. So, what we can do is assign a "key" to each block type as soon as we add a block to the BlockHolder that has that block type. For example, suppose the first block added to a chunk is of type "grass". Then the "grass" block type is assigned the key 0. Suppose 50 more grass blocks get added. Then suppose a "stone" type block gets added. Now we assign the "stone" block type to the key 1. Etc. This keeps going until we have 255 unique block types in the chunk. Then, if another unique block type is added, we do NOT associated it with a key. Instead, we require that the type of the block be stored in an auxillary hash table.

Here is code to associate these one byte keys to the first 255 unique 4 byte integers used:

#define ITOC_COMP_INVALID_KEY   255

class IntToCharCompressor {
private:
    //Key is the "int value".
    //Value is "unsigned char key".
    unordered_map<int, unsigned char> value_to_key;

    //Starts at zero.
    unsigned char next_key;

    //Index in the key.
    //Value is the value.
    svector<int> key_to_value;
public:

    IntToCharCompressor() {
        next_key = 0;
    }

    //Returns the key if it finds the key,value pair.
    //If not, will try to create a new key,value pair
    //(and will return that key).
    //If that fails, it will return ITOC_COMP_INVALID_KEY
    //showing that it could not compress the value.
    //In this case, caller has to figuer out what to do.
    unsigned char GetKey(int value) {
        auto itr = value_to_key.find(value);
        if( itr == value_to_key.end() ) {
            //The key value pair does not exist.
            if( next_key >= ITOC_COMP_INVALID_KEY ) {
                //Too many keys.
                return ITOC_COMP_INVALID_KEY;
            }
            //Adding it.
            unsigned char key = next_key; //Starts at zero.
            ++next_key;
            value_to_key[value] = key;
            key_to_value.push_back(value); //Index = key.
            return key;
        } else {
            //Already registered the key value pair.
            return itr->second;
        }
    }

    //Should be very fast.
    //Key must not be ITOC_COMP_INVALID_KEY.
    inline int GetValue(unsigned char key) {
        if( key < key_to_value.size() ) {
            return key_to_value[key];
        }
        return -1; //Should never happen.
        //Perhaps reserve -1 in every system.
    }
};

Note that in the above class, ints can be replaced with any class that has the equality operator defined.

Here is how we can modify the BlockPosInfo class. There needs to be another class called BlockTypeCompress, owned by the BlockHolder, to decode a block type key (combined with a local block position) into a block type.

//Class needed to decode a one byte "block type key"
//(and a LocalBlockPos).
class BlockTypeCompress {
public:
    IntToCharCompressor comp;

    //Only needed if we have an invalid key
    //(so the value cannot be compresse).
    //The key to this map is the pos hash.
    //The value is the block type.
    unordered_map<short, int> backup;
};

//The third version of the BlockPosInfo class.
class BlockPosInfo_ThirdTry {
public:
    //Same as "second try" class.
    unsigned char flags;

private:
    //The analogous member was public in the "Second Try" class.
    unsigned char block_type_key;

public:
    //Getting the block type.
    int GetBlockType(
        BlockTypeCompress & btc,
        short pos_hash) const
    {
        if( this->block_type_key == ITOC_COMP_INVALID_KEY ) {
            //The block type key is valid.
            auto itr = btc.backup.find(pos_hash);
            if( itr == btc.backup.end() ) {
                //Exit the program...
            }
            return itr->second;
        } else {
            //The block type key is valid and so
            //btc.comp can decode it.
            return btc.comp.GetValue(this->block_type_key);
        }
    }

    //Setting the block type.
    void SetBlockType(
        int block_type,
        BlockTypeCompress & btc,
        short pos_hash)
    {
        short new_key = btc.comp.GetKey(block_type);
        this->block_type_key = new_key;
        if( new_key == ITOC_COMP_INVALID_KEY ) {
            //Using the backup storage.
            btc.backup[pos_hash] = block_type;
        }
    }
};

Finally, here is how to modify the BlockHolder class (now, it needs to contain the BlockTypeCompress class):

class BlockHolder_ThirdTry {
    int default_block_type;
    
    unsigned char default_block_type_flags;
	
    //Need this to decode a block type key
    //(combined with a local block pos)
    //into a block type.
    BlockTypeCompress btc;
	
    //The key is the LocalBlockPos hash code.
    //The value is information associated to the block position.
    unordered_map<short, BlockPosInfo_ThirdTry> block_data;
};