Virtual Chunks

Home --> Programming Projects --> Fractal Block Engine --> Procedural World Generation --> Virtual Chunks

What are Virtual Chunks?

Suppose we want to generate a chunk that has some spheres of blocks intersecting it. If each sphere has radius < 16, we can find the centers of these sphere in each of the 3x3x3 surrounding chunks. Recall that a chunk is 16 blocks wide.

Here is a picture of the chunk (green) to the left of the given chunk we are procedurally generating (blue) with a sphere in it (red). The red sphere intersects the blue chunk.


We call the green chunk the virtual chunk.

So we find if the virtual chunk contains the center of a red sphere, we find the center of such a sphere in the coordinate system of the virtual chunk, and then we convert that to the coordinate system of the chunk being generated (the blue chunk). We can then iterate over all blocks in the blue chunk and see if the center of each block is inside the red sphere. We can change block types of each block accordingly.

Larger Virtual Chunks

What if we want to do the same as in the example above, but we want the sphere to have a radius between 16 and 32? Then it is not enough to look at the 3x3x3 surrounding chunks, we need to look at the 5x5x5 surrounding chunks instead. However 5^3 = 125 is kind of a large number.

What we can do instead is look at 2x2x2 regions of chunks. Temporarily call such a region a "big chunk". Then we find the big chunk that contains the blue chunk and then look at the 3x3x3 surrounding big chunks. See the following picture:

The BinPath Class

See here for a description of what a binary path (BinPath) is. See here for the BlockPath class. Here are parts of the class for BinPath: 
class BinPath {
public:
    //A LocalBlockPos has members x,y,z.
    //Each one is a signed char,
    //but we will only used the values 0 and 1
    //for these members.
    vector path;

    BinPath();

    void SetFromBlockPath(const BlockPath & block_path);

    string ToString() const;
};

//This can be faster.
void BlockPath::SetFromBlockPath(const BlockPath & block_path) {
    for(int i = 0; i < bp.path.size(); ++i) {
        LocalBlockPos lbp = block_path.path[i];
        LocalBlockPos lbp1(
            (lbp.x/8),
            (lbp.y/8),
            (lbp.z/8));
        LocalBlockPos lbp2(
            (lbp.x/4) % 2,
            (lbp.y/4) % 2,
            (lbp.z/4) % 2);
        LocalBlockPos lbp3(
            (lbp.x/2) % 2,
            (lbp.y/2) % 2,
            (lbp.z/2) % 2);
        LocalBlockPos lbp4(
            lbp.x % 2,
            lbp.y % 2,
            lbp.z % 2);
        path.push_back(lbp1);
        path.push_back(lbp2);
        path.push_back(lbp3);
        path.push_back(lbp4);
    }
}

Getting the Seed for a Virtual Chunk

Given the BlockPath of the chunk to be procedurally generated, we can convert that path to a BinPath, chop off the last few elements of the path to get a larger chunk, then move to an adjacent chunk to the the BinPath of the virtual chunk. We can then get the seed from that path: 
int GetVirtualChunkSeedXYZ(
    int world_seed,
    int salt,
    const BlockPath & block_path,
    int chop,
    int dx, int dy, int dz)
{
    BinPath bin_path;
    bin_path.SetFromBlockPath(block_path);
    
    for(int i = 0; i < chop; ++i) {
        if( bin_path.size() == 0 ) break; 
        bin_path.path.pop_back();
    }
    
    BinPath nearby_bin_path;
    bool ComputeNearbyPath(
        bin_path, dx, dy, dz, nearby_bin_path);
    
    int seed = GenerateSeedFromPath(bin_path);
    
    return seed;
}
Here ComputeNearbyPath is like the function defined here except it works with a BinPath as input and returns a BinPath as output (instead of BlockPath's).

Here GenerateSeedFromPath is like the function defined here but with a BinPath instead of a BlockPath.

If we are ok using tail seeds (see here) then we can use the following much faster code: 
int GetVirtualChunkSeedXYZ(
    int world_seed,
    int salt,
    const BlockPath & block_path,
    int chop,
    int dx, int dy, int dz)
{
    BinPath bin_path;
    bin_path.SetFromBlockPath(block_path);
    
    for(int i = 0; i < chop; ++i) {
        if( bin_path.size() == 0 ) break; 
        bin_path.path.pop_back();
    }
    
    int seed = GetAdjTailSeedXYZ(
        world_seed, salt, bin_path, dx, dy, dz);
    
    return seed;
}
If we want the variant GetVirtualChunkSeedXY of GetVirtualChunkSeedXYZ that only uses x and y components to generate the seed, then we simply use that in the function instead of GetAdjTailSeedXYZ.

Virtual Chunk Seed + Virtual Chunk Block Type

To generate the red circle in the examples above, we use the seed for the virtual chunk. However in addition to the seed we can use one more thing: the block type of the virtual chunk. We can use this provided the virtual chunk and the chunk being generated are on the same level, because the block types of the 5x5x5 region of chunks surrounding the chunk that is being generated (the blue chunk) is given to the blue chunk.

Someone making their own engine may want to pass the blocks types of the 5x5x5 (or perhaps just 3x3x3) region of chunks surrounding not just the chunk being generated BUT THE FIRST FEW ANCESTORS OF THE CHUNK BEING GENERATED.

Converting Between the Coordinate Systems

Let C be the chunk being procedurally generated and let V be the virtual chunk. It is important that we can convert to and from the coordinate systems of these two chunks.

We need the following functions which gives the min and max positions of the chunk being generated from the coordinate system of the virtual chunk. We call these the "reverse" min (rmin) and "reverse" max (rmax). Once we know the rmin and rmax values, we can find the min and max positions of the virtual chunk within the coordinate system of the chunk being procedurally generated.

For example, if the virtual chunk is the same as the chunk being generated, then rmin = (0,0,0) and rmax = (1,1,1) will be returned. More generally, if the chunk being generated is inside the virtual chunk, then rmin and rmax will always be between (0,0,0) and (1,1,1). 
void GetOffsetsFromChop(
    const BinPath & chopped_bin,
    const BinPath & bin,
    Vector & rmin,
    Vector & rmax)
{
    rmin = Vector(0.0f, 0.0f, 0.0f); //Will add to this.
    float cur_width = 1.0f;

    for(int i = chopped_bin.path.size(); i < bin.path.size(); ++i) {
        cur_width *= 0.5f;
        rmin.x += cur_width * (float)bin.path[i].x;
        rmin.y += cur_width * (float)bin.path[i].y;
        rmin.z += cur_width * (float)bin.path[i].z;
    }
    rmax = rmin + Vector(cur_width, cur_width, cur_width);
}

void GetOffsetsFromChopNearby(
    const BinPath & chopped_bin,
    const BinPath & bin,
    int dx, int dy, int dz,
    Vector & rmin,
    Vector & rmax)
{
    GetOffsetsFromChop(
        chopped_bin, bin,
        rmin, rmax);
    Vector add(-dx, -dy, -dz)
    rmin += add;
    rmax += add;
}
So here is a function to get all relevant data about the virtual chunk: 
//min/max are the coords of the vchunk (virtual chunk)
//in the coord system of the chunk being generated.
//rmin/rmax (reverse min and max)
//are the coords of the chunk being generated
//in the coord system of the vchunk.
void GetVChunkData(
    const NodeGenInput & input, //Input to chunk generation.
    int chop,
    int dx, int dy, int dz,
    Vector & min,
    Vector & max,
    Vector & rmin,
    Vector & rmax,
    int & seed,
    string & bt)
{
    //Converting the block path to a binary path.
    BinPath bin;
    bin.SetFromBlockPath(input.full_path);
   
    //Setting the chopped_bin path to be
    //an initial segment of the bin path:
    //we remove the last chop members.
    BinPath chopped_bin = bin;
    for(int i = 0; i < chop; ++i) {
        if( bin_path.size() == 0 ) break; 
        bin_path.path.pop_back();
    }

    //Getting rmin/rmax values.
    GetOffsetsFromChopNearby(
        chopped_bin, bin,
        dx, dy, dz,
        rmin, rmax);

    //Getting min/max values.
    float width = rmax.x - rmin.x;
    float iw = 1.0f / width; //Inverse width.
    min.x = (0.0 - rmin.x) * iw;
    max.x = (1.0 - rmin.x) * iw;
    min.y = (0.0 - rmin.y) * iw;
    max.y = (1.0 - rmin.y) * iw;
    min.z = (0.0 - rmin.z) * iw;
    max.z = (1.0 - rmin.z) * iw;

    //Getting the seed.
    seed = GetNearbyTailSeed(chopped_bin, dx, dy, dz);

    //Need to get the block type from input somehow.
    //Fill in code here!!!  (Get it from the
    //procedural world generation input).
    bt = ""; //Hack!!!
}
For the block type bt, we want to set it to be the block type of the finest real chunk which contains the virtual chunks. These block types are possibly available for the input class.

The "Block Type" of a Virtual Chunk

A virtual chunk might not be an actual chunk. However sometimes we want to get the block type of the finest actual chunk which contains a given virtual chunk. This is done by accessing the adjacent block types given as input to procedural world generation (see here). That is, we access the "block types of chunks adjacent to the parent chunk".