How can I create a persistent seed for each chunk of an infinite procedural world?

Question

I'm coding a chunk-based 2D game.

I generate chunks as the player explores the world. Chunks follow a procedural generation algorithm (with only one biome implemented at the minute, but I'll introduce more).

When the player leaves a chunk however and it's unloaded, that chunk is lost for good (unless they modified the chunk; if that is the case, I save it). This is because with each new chunk I generate, I generate a new random seed for it.

I introduced a world seed into my world. My chunks also have 'world coordinates', ie the first chunk you spawn in is at (0, 0) and the chunk to the right is at (1, 0), etc, in world coordinates.

I was thinking about ways I can combine the world coordinates and world seed in order to obtain a chunk seed. That way, since I always know the world seed and always know the world coordinates, I could obtain the same chunk seed in order to make sure the same chunk comes back after the player leaves it (and the chunk is unloaded) and then returns to that location in the world when it has to be reloaded.

Some of the ways I thought of were as follows:

• Use a simple equation like abs(world seed * world_coordinate_x * world_coordinate_y) where the absolute value function enforces a postive chunk seed.

This would not be an acceptable equation to use as the equation would give the same chunk seed for the world coordinates (x, y), (y, x), (-x, -y), (x, y), etc, resulting in a pretty dodgy pattern to the world.

---

I know games like Minecraft accomplish this, but I cannot find a way to obtain a chunk seed based off of the world coordinates and world seed without there being a weird symmetry in my world generation.

What seed generation method can I use to avoid these symmetries or obvious correlations?

Answer 1

As mentioned in a comment, this problem is solved by hashing.

Here's a naive C# hash function we could use to digest two signed integers into a single positive unsigned int:

static uint LocalHash(int x, int y) {
    unchecked {
        uint hash = (uint)x;
        hash ^= (uint)y << 16;
        hash ^= (uint)y >> 16;
        return hash;
    }
}

Here we've barrel-shift rotated the bits of y around 16 places, then XOR'd them together with the bits of x. So toggling the low bit of x (travelling between adjacent chunks east/west) toggles the low bit of the hash, and toggling the low bit of y (travelling between adjacent chunks north/south) toggles the 16th bit of the hash. So you have to travel 32 thousand chunks in the x direction before you start to see the same bit patterns you'd seen in nearby chunks in the y direction, and vice versa.

We can make this a seed like so:

chunkSeed = LocalHash(chunk.x, chunk.y) ^ worldSeed;

This does a good job of ensuring you have a distinct seed for all the chunks in any local area, but it doesn't decorrelate those seeds. So if you use that as a raw input to your random number generator, you might still see correlations between adjacent chunks because of this correlation in their seeds.

You can use more sophisticated hashing functions to blend-up the bits in more complicated ways that mask these correlations, like FNV hash or MurmurHash. For something like procedural generation, you usually don't need the high-end security qualities of a heavier-duty cryptographic hash.