Procedural sidescroller world gen algorithm by seed

Question

I'm trying to recreate a procedural side-scroller world gen algorithm by using a seed and I find my self stuck trying to solve a particular problem.

Seed generation applies very well with voxel-like games, but it seems slightly less suitable to generate randomly placed sprites with differing widths for sidescrollers

Here's a picture explaining the problem:

Assuming I load the game at screen-2, I'd be e.g. between coordinates 100 and 0, and the seed function would tell me that between coordinates 100 and 0 there's the sprite of a big block of mountains to render, whose center lies in the coordinate interval [0, 100] ( the center of the sprite is the pink dot in the picture)

assuming I'm loading the game from coordinate 300, as is the case in screen-1, a seed function wouldn't be able to recognize the presence of a mountain sprite there, even though part of it is still visible in the interval between e.g. [250, 350]

A straightforward solution would be to sample from the seed function the interval including the biggest-sized object in the game, which is of course highly inefficient given many objects only cover a fraction of the screen.

How is this type of problem generally solved? Are algorithms based on seeds unsuitable for this particular project? If this is the case, what could be a reasonable alternative?

Answer 1

You'd solve this the same way as you do in 3D.

In 3D games with procedurally generated landscapes, you can often see a distant mountain that's located in a different generation site than the one you're in. So, just as you said, you need to sample the procedural generator function for adjacent areas.

This doesn't become problematically inefficent, because we don't need to sample every adjacent millimetre.

Instead, the world is divided into buckets or chunks of fixed size. Given a position in the world, we can determine which chunk it's in by dividing & flooring the position. Then find the immediately adjacent chunks by adding or subtracting 1.

Each chunk spawns content only inside its bounds. If your maximum object size is smaller than the chunk size, then you only need to check one chunk outside your visible bounds in each direction to ensure you've spawned all content that will be visible to the player.

For a case like you showed, that might be as few as 2-3 chunk evaluations to ensure you can show everything that's visible in a given screen. Not too inefficient at all. :)

Answer 2

If you know your maximum width of sprite -- then you can check for the presence of any sprite between your screen.X - maxSpriteWidth to screen.x + screen.width.

If the scale of your objects is truly gigantic (like, it includes mountains that are miles wide as well as small things less than a meter in size), then you could use a multi-level data structure that separates objects by size: "Find all big things within X miles", "find all medium things within X meters of the screen boundaries", "find all small things within X centimeters of the screen boundaries".

Regarding the actual question of using seeds for the generation part -- generally seeded iterated functions like your usual random function work better when you're generating everything up front -- if you're on-the-fly generating "what is the position of item X" or "is there an item in this region R" then it tends to be easier to use a hash of the relevant data.