Getting a Random Seed From the Tail of a Path

Home --> Programming Projects --> Fractal Block Engine --> Procedural World Generation --> Getting a Random Seed From the Tail of a Path

The Problem With Using the Entire Path

The problem with using the entire block path of a chunk for a pseudo random seed (as we did here) is it can be slow (if the block path is very long). So instead, we can just use the last few elements of the block path. We call this the tail seed of the block path.

A downside of this is the world may repeat. However the player may have to try hard to find this repetition.

Getting the Tail Seed from a (Binary) Path

A BinPath is like a BlockPath except it stores the block path as a sequence of 1's and 0's. Each element of a BlockPath is a triple (x,y,z) of integers between 0 and 15 inclusive. We can convert a BlockPath to a BinPath and each (x,y,z) of the BlockPath becomes 4 triples (x_1,y_1,z_1), (x_2,y_2,z_2), (x_3,y_3,z_3), (x_4,y_4,z_4) of 0's and 1's.

We can take a BinPath and take the last 7*4 = 28 members of the sequence and convert them to integers. Specifically, the x-coordinates become one (4 byte) integer, and something similar can be said about the y and z coordinates. This gives us 4 bits of spare of the 4 byte integer.

void GetPathTailCodes(
    const BinPath & bp,
    int & code_x,
    int & code_y,
    int & code_z)
{
    code_x = 0;
    code_y = 0;
    code_z = 0;

    int place_value = 1;
    for(int i = 0; i < 7*4; ++i) {
        int index = bp.path.size() - 1 - i;
        if( index < 0 ) break;
        LocalBlockPos lbp = bp.path[index];
        code_x += lbp.x * place_value;
        code_y += lbp.y * place_value;
        code_z += lbp.z * place_value;
        place_value *= 2;
    }
}

Here is how we can generate a seed from these coord integers:

int TailCodesToSeedXYZ(
    int code_x,
    int code_y,
    int code_z)
{
    return
        GetPrime(0) * code_x +
        GetPrime(1) * code_y +
        GetPrime(2) * code_z;
}

If we only want to use the x and y coordinates, we do the following:

int TailCodesToSeedXY(
    int code_x,
    int code_y)
{
    return
        GetPrime(0) * code_x +
        GetPrime(1) * code_y;
}

Getting Tail Seeds for Adjacent Paths

To get the tail seed of a path adjacent to a given path, the following is the key function. The code integer represents either code_x or code_y or code_z.

int GetNearbyTailCode(
    int code,
    int add)
{
    code += add;
    int max = 268435456; //16^7 = 2^28.
    if( code < 0 ) return code + max;
    if( code >= max ) return code - max;
    return code;
}

For example, if code is code_x of a BinPath and we want to find the tail seed of the chunk that is 1 more in the x direction, we would call GetNearbyTailCode with add = 1 and that would return a new value for code_x. So here is a function to get the tail seed of a BinPath nearby to the given path:

int GetAdjTailSeedXYZ(
    int world_seed,
    int salt,
    const BinPath & bp,
    int dx, int dy, int dz)
{
    int code_x, code_y, code_z;
    GetPathTailCodes(
        bp, code_x, code_y, code_z);
        
    int adj_code_x = GetNearbyTailCode(code_x, dx);
    int adj_code_y = GetNearbyTailCode(code_y, dy);
    int adj_code_z = GetNearbyTailCode(code_z, dz);

    int value = TailCodesToSeedXYZ(
        adj_code_x, adj_code_y, adj_code_z);
        
    //Modifying the final seed to take salt into account,
    //using a large prime number.
    value +=
        salt * 1000537 +
        world_seed * 1000541;

    return value;
}

Similarly, we can have a GetAdjTailSeedXYZ function which uses TailCodesToSeedXY instead.