Getting an Adjacent Block Path

Home --> Programming Projects --> Fractal Block Engine --> Procedural World Generation --> Getting an Adjacent Block Path

The problem

Given the path of a chunk, we sometimes want to compute the paths of adjacent chunks.

Although this is used for procedural world generation, it is used in other parts of the engine as well.

Block Path Class

Here are the key parts of a class to store the position of a block within a chunk. Remember that a chunk is 16x16x16 blocks. This is called a Local Block Position. See here for more on these data types.

class LocalBlockPos {
public:
    signed char x;
    signed char y;
    signed char z;
    
    LocalBlockPos();
    
    LocalBlockPos(
        signed char x,
        signed char y,
        signed char z);

    int Hash() const {
        return z + (16 * y) + (256 * x);
    }
    
    void SetFromHash(int hash) {
        z = hash % 16;
        code /= 16;
        y = hash % 16;
        code /= 16;
        x = hash % 16;
    }
};

Note how we can encode a LocalBlockPosition as a single (4 byte) integer. We could actually store it in a 2 byte short, but the current method works well enough.

Here are the key parts of the BlockPath class:

class BlockPath {
public:
    vector<LocalBlockPos> path;

    BlockPath();

    void GetCoords(
        vector<int> & x_coords,
        vector<int> & y_coords,
        vector<int> & z_coords) const;

    void SetCoords(
        const vector<int> & x_coords,
        const vector<int> & y_coords,
        const vector<int> & z_coords);

    string ToString() const;
};

The ToString function on a BlockPath might output the following: 59a_f85_776_8c9
Note that instead of storing a path using the BlockPath class, we could store it is a vector of integers, where each integer is the hash of a LocalBlockPos. This is what the BlockHashPath class does (which the engine uses).

Long Addition

Long addition is the basic engine behind finding an adjacent block path (like we learn in grade school, along with long division).

Given a block path, we consider the x components separate from the y components separate from the z components. We take the x components and put them into a vector. We can think of this as representing a very large integer.

Here is the long addition algorithm. We only care about base = 16.

bool LongAddition(
    int base,
    const svector<int> & input,
    int change,
    svector<int> & changes,
    svector<int> & result)
{
    //Resizing the changes vector.
    changes.resize( input.size() );

    result = input; //Copying.
    //
    result[ result.size() - 1 ] += change;
    for(int i = result.size() - 1; i >= 0; i--) {
        changes[i] = result[i] - input[i];
        while( result[i] >= base ) {
            if( i == 0 ) return false;
            result[i] -= base;
            result[i-1] += 1;
        }
        while( ret[i] < 0 ) {
            if( i == 0 ) return false;
            result[i] += base
            result[i-1] -= 1;
        }
    }

    return true;
}

The function returns false if the resulting vector of coordinates would no longer be in the world.

The change value is added to the last element of the vector of coordinates.

This may cause "carrying over". The vector "changes" is returned and that shows where there was a carry over. This is needed by some parts of the engine. For example, when the player moves to an adjacent chunk, we need to know what levels need to be "shifted". A level needs to be shifted iff the chunk on that level that contains the player changes to a different chunk. However in this page we can ignore these carrying over values given by "changes". The reader can choose to make their own version of LongAddition that does not have a "changes" vector.

If the function returns true, the "result" vector is the new (shifted) vector of coordinates.

For example, suppose the "input" vector is 7 15 15 and "base" is set to 16 and "change" is set to 1. Then the LongAddition function will first add a 1 to the last coordinate, which will carry over, which will result in a second carry over. The "result" vector will be 8 0 0.

Code for Getting an Adjacent Path

We now have all the pieces for the code to get an adjacent path:

bool ComputeNearbyPath(
    const BlockPath & old_path,
    int dx, int dy, int dz,
    BlockPath & new_path)
{
    int base = 16;

    vector<int> old_x_coords;
    vector<int> old_y_coords;
    vector<int> old_z_coords;
    old_path.GetCoords(
        old_x_coords, old_y_coords, old_z_coords);
    
    //Will not use.
    vector<int> changes_x;
    vector<int> changes_y;
    vector<int> changes_z;

    vector<int> new_x_coords;
    vector<int> new_y_coords;
    vector<int> new_z_coords;

    if( !LongAddition(
        base, old_x_coords, dx, changes_x, new_x_coords) )
    {
        return false;
    }

    if( !LongAddition(
        base, old_y_coords, dy, changes_y, new_y_coords) )
    {
        return false;
    }

    if( !LongAddition(
        base, old_z_coords, dz, changes_z, new_z_coords) )
    {
        return false;
    }

    new_path.SetCoords(new_x_coords, new_y_coords, new_z_coords);
    return true;
}

This function returns false if the new path is not in the world. In this case, "new_path" is not valid.