1
\$\begingroup\$

I am working on an automatically generated (theoretically) infinite 2D world. The grid would be separated in chunks made of thousands of world tiles.

We plan to use a Perlin noise function to generate the islands and biomes within a chunk, so that the chunk is completely deterministic. It means that you need no other data than the chunk seed to know exactly how the terrain look like.

But some biomes would be really rare and we don't want people to be able to predict where they are going to appear. This is why we would like to use a randomly generated chunk seed everytime a player enters a new chunk.

We however have a problem:

What if a biome ends at the border of a chunk and the other chunk has a completely different generation? How could we avoid that?

\$\endgroup\$
4
  • \$\begingroup\$ How do you select your biomes at present? But also, I'm wondering whether this prediction is a problem that's likely to arise in practice — I haven't heard of players reverse-engineering world gen systems to predict locations from their seeds. Blocking that by randomizing chunk seed on visit would just introduce a new exploit: save scumming to continue re-rolling a batch of chunks until they randomly come up as the desired biome. You can block the save scumming by saving a seed, but then you're vulnerable to prediction again. \$\endgroup\$
    – DMGregory
    Sep 5 at 14:35
  • \$\begingroup\$ For the context, we are trying to build a game on blockchain. It means this game will be multiplayer and people could really easily write a tool to be able to "pregenerate" the map. It wouldn't be possible for them to explore a chunk without going there (and waiting the travel time). \$\endgroup\$
    – Th0rgal
    Sep 6 at 13:40
  • \$\begingroup\$ Running your own private server to generate and store the chunk seeds would be much simpler, and you could insulate against that type of exploit more robustly. If clients running on hardware you don't control are minting their own new chunks onto the chain, you'd have to trust them not to modify or game the random selection logic to increase the effective probability of desirable biomes. \$\endgroup\$
    – DMGregory
    Sep 6 at 13:45
  • \$\begingroup\$ The idea is to get something completely decentralized. One server owned by an authority (me or anyone else) is not something we can accept. The idea is to use a different seed per chunk so for example use the current block hash (which can't be predicted) when a new chunk is discovered. On the chain we would only store the modifications done to the terrain by players. Because this is completely deterministic we don't need to store anything else than the block hash and the modifications to be able to render the map properly! =) \$\endgroup\$
    – Th0rgal
    Sep 6 at 14:30
1
\$\begingroup\$

For this answer, I'm going to assume that the inputs to your biome-selection process are just the elevations (or other measures like temperature/moisture) output from your Perlin noise function. If you're generating your biomes in a different way, be sure to edit your question to walk us through your current generation rules.


Perlin noise and similar functions are what's called gradient noise: they pseudo-randomly select a gradient at each lattice point, using the point's location and some seed information, and then interpolate a value between those gradients to fill the lattice cell between those corners.

So, as long as two chunks can agree on the gradients at those lattice points, then the rest will blend seamlessly. I show this in a couple of previous answers, for making a wrapping world and hexagonal tiles.

One way we can do this is to establish which chunk "owns" each lattice point. Say, a chunk owns every lattice point in its interior, and those lying exactly on its south and west edges. Its north and east edges are owned by the neighbouring chunk though - they're their south and west edges, respectively.

When we want to generate a pseudorandom gradient for a lattice point, we first check which chunk it's in, and use that chunk's seed in the pseudorandom selection. If we've never generated a seed for that chunk before, then we generate it now, on the fly, and save it. (That means you may have seeds stored for some chunks you've never visited, if they're immediately adjacent to one that you have)

And that's all - as long as the chunk you're in has access to the seeds of the neighbouring chunks, then you can generate it in a way that will be seamlessly consistent with them, even if you've never generated their interiors yet.

You may also be interested in Deterministic Procedural Wave Function Collapse for another way of approaching this chunk consistency problem, through different procedural tools, but with the same core approach: make sure they agree about the inputs to the generation function at the edges where they meet, and the output will match up seamlessly.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you so much for your answer! \$\endgroup\$
    – Th0rgal
    Sep 6 at 13:42

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.