In a semi-infinite procedural (chunk based) map, how do you handle objects larger than a single chunk?

Question

I'll use an example to try and be more specific. Assume this is for a 2D top-down game. Chunks in this are made up of 32x32 tiles.

If procedural buildings were to be generated based on some kind of noise algorithm and a building was typically 3x3 chunks in size, how do you ensure the seed for this map will always produce the same buildings?

Given two adjacent chunks: chunk A and chunk B, what if they both meet the noise algorithm's requirement for being a spawn point for a building?

If they are both far from the player's current view range, it could depend on how the player approaches these chunks as far as which one gets generated first.

My first thought was to only check for buildings every so many chunks, however, I'd also like to have some objects that may span tens of chunks. I don't think this is a proper solution.

Should I simply be using a different type of algorithm to identify where buildings should be able to be spawned at, an ever expanding Voronoi diagram as an example, or is there something else I'm just not considering with how I'm already trying to attempt this? Perhaps I should be handling cross chunk objects on a grander scale (like a collection of 32x32 chunks)?

Thanks!

Answer 1

First, your generator(s) should definitely be working at the global, world scale and then applied at the chunk scale. You saw that already and it was a great observation. Here are some notes on working with procedurally generated content that will hopefully make sense. I think that you're confusing "Random World" with "Procedural World," and they're related but not the same. What you want is a Procedural World that can be always be the same if you want, or different each time you run.

Noise is not random. Noise output is always the same from the same input parameters. The great thing about noise is that it is 100% repeatable.

You control the input parameters, this is how you come up with different noise fields and the only place randomness occurs!

It's very common for one, single seed to change the base set of numbers and then everything else is based on those. In an example case, the input parameters to the noise would be based on chunk location in global space modified by that global base set. It doesn't matter which chunk gets created first since the chunk is always in the same place and parameters are always the same for the same seed.

Noise does not have to stand alone. You can have one noise controlling your chunks, another noise controlling your building placement, and so on. This allows you to tweak buildings without messing with your terrain. Each of these noise fields can be at different scales, etc...

You can use more than one random number generator. You can seed multiple generators and use each one independently. Random numbers come in a variety of styles depending on what you want from them, it's a deep subject with lots of statistics involved, but something to consider in the future.

In general the idea is that everything your algorithms based on noise create should be 100% repeatable and independent of anything else. Your choice of seed guarantees not that each run will be different, but that each run will be the same until a different seed is chosen.

It is this repeatable behavior combined with working globally and applying locally that will solve your buildings problem.

Answer 2

Keep in mind that chunks are only a strategy for storing data. All your world generation, including building placement, should be done at the world level.

That type of generation can be relative to the player or some other strategy that works for your game. For very large buildings you might want to go a little higher level. If your generation range is smaller than the half extents of your largest buildings, you either need to extend the range of your generation range or you need to test conditions for more than just the center of the building. Have conditions that can allow the building to be placed by the edge or corner.

Answer 3

When dealing with your buildings that are bigger than a single chunk simply mark the chunk as not building-checked. When you try to address a chunk that's not checked and far enough from the outer limit to ensure that all relevant chunks have been generated then you do your building check.

Answer 4

I am thinking about this same problem. Like mentioned in another answer I am thinking about having different noise sources at different scales control different parts of generation. Even with that guidance there is still the question of how to implement generation?

Let's imagine you have a "Structures Coordinate System" (SCS) defined with a granularity suitable for the structures you generate. In the same way as chunk addressing collapses all contained cells into a single coordinate the SCS would collapse larger areas into a single coordinate. From there, given any world coordinate, you could sample a noise source with the SCS coordinate to determine if there is a structure "near by".

You could also use the SCS coordinate to sample another noise source to determine what kind of structure to build. As an optimization you could also use the SCS coordinate as the key into a structures map Dictionary<Vector, IBuilding>. A quick structures check could be done using the chunk index (chunk -> global -> SCS) to determine if this chunk needs to check for structures. If so the structure instance could be pulled from the cached factory, and chunk cells would then be checked against the structure and contained cell generation delegated to the structure generator.

I'll probably be implementing something like the sketch above in my current project. Check out my ongoing series of blog posts for more rambling interspersed with code.