0
\$\begingroup\$

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: enter image description here

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?

\$\endgroup\$
2
\$\begingroup\$

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. :)

\$\endgroup\$
  • \$\begingroup\$ I was partitioning in my mind this problem much more than I should have (I was thinking about making chunks per-layer, and big structures on layers close to the camera where giving me all sorts of problems) Instead of using the most straightforward approach of creating fixed chunks with objects in it differing in their z position. I guess I've seen too many edge cases in my programming journey so far, thanks for your answer \$\endgroup\$ – Row Rebel Nov 14 '17 at 20:29
1
\$\begingroup\$

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.

\$\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.