Getting a Random Seed From A Path

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

Getting a Seed From Several Integers

Suppose we have two integers x and y and we want to generate an (integer) seed for pseudo random generation from these numbers. A natural way is to use a linear combination using prime numbers. That is, let p1 and p2 be two prime numbers. We can set the seed to be x * p1 + y * p2. In a non-fractal block game, we could use the x,y,z coordinates of a chunk to set the seed for procedural world generation of that chunk.

In Fractal Block World, life is more complex. We need a way to get a seed from the block path of the chunk being generated. That is what this page is about.

Table of Primes

//The first 81 primes after one million.
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};

int GetPrime(int n) {
    int total = 79; //Away from 81.
    while( n > total ) n -= total;
    if( n < 0 ) n = 0;
    return prime_table[n];
}

Seed from a Block Path

Here is code to get an (integer) seed from a BlockPath:

int GenerateSeedFromPathXYZ(
    const BlockPath & block_path,
{
    int total = 0;
    int n = 0;
    total += GetPrime(n++) * bp.path.size();
    for(int i = 0; i < bp.path.size(); ++i) {
        const LocalBlockPos & lbp = block_path.path[i];
        total += GetPrime(n++) * (int)lbp.x;
        total += GetPrime(n++) * (int)lbp.y;
        total += GetPrime(n++) * (int)lbp.z;
    }
    return total;
}

Fractal Block World also has an integer seed associated to each world (the player can choose a seed when they start a new game). The code in the function above can be modified to take this world_seed into account.

Seed from an adjacent Block Path

Suppose we are generating a chunk C. Sometimes we need to get the pseudo random seed for a nearby chunk. This is done by computing the nearby path and then computing the seed of that path. See here for how to compute an adjacent block path.

int GenerateSeedFromNearbyPathXYZ(
    const BlockPath & block_path,
    int dx, int dy, int dz
{
    BlockPath adj_path;
    bool valid = ComputeNearbyPath(
        block_path, dx, dy, dz adj_path);
    if( !valid ) return 0; //Edge of world!

    return GenerateSeedFromPathXYZ(adj_path);
}

XY Seed from a Block Path

Sometimes we want to generate a seed for a chunk that only depends on the x,y position of the chunk and ignores its z position. This is accomplished by the following function:

int GenerateSeedFromPathXY(
    const BlockPath & block_path,
{
    int total = 0;
    int n = 0;
    total += GetPrime(n++) * bp.path.size();
    for(int i = 0; i < bp.path.size(); ++i) {
        const LocalBlockPos & lbp = block_path.path[i];
        total += GetPrime(n++) * (int)lbp.x;
        total += GetPrime(n++) * (int)lbp.y;
        //We ignore "lbp.z".
    }
    return total;
}

There is a similar function for getting an XY seed for a chunk adjacent to a given chunk.

Too Slow

Everything in this section is all well and good but there is one problem: it is slow. If a chunk is a thousand levels deep, then it can be a little slow to compute the seed from the chunk's path.

One solution is to generate a seed using only the last few elements of the chunk's path (to get what we call the "tail path"). This is discussed here.