2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Have you looked into hash functions? These are frequently used to digest multiple pieces of data, or a large data item, down into a small, pseudo-random fingerprint that changes drastically if any particular bit in the inputs changes. They're often designed to help decorrelate correlated inputs, which is what your world seed attempts to do with the world positions. \$\endgroup\$ – DMGregory Jun 2 at 19:49
  • \$\begingroup\$ No, how could they be used in this context ?@DMGregory \$\endgroup\$ – Featherball Jun 3 at 11:00
5
+50
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.