Sprites in huge world
Hi everybody,
I'm making a game in directdraw, an rpg.
I've finished making a tile background for my game. (about 1000 x 1000 tiles)
I want another layer with sprites in it (trees, houses, walking people in different sizes), but it takes ages to loop trough thousands of sprites, sort on y values and draw them on screen in one update. Has somebody an idea about making this process faster?
By the way: I don't use game-screens, but smooth-scrolling.
And i'm workin with c++.
Gerben
Two major tips I can think of off-hand for improving performance:
> 1) Choose an appropriate sorting algorithm. Here's a good reference for starters. Note that you can usually make the assumption that on each iteration your list is already going to be mostly sorted, since I don't think you'll have sprites taking huge jumps across the map.
> 2) Only draw the sprites that are visible on the screen. Don't waste time drawing something the user is not going to see.
Maybe you already do these things, or maybe they're fairly obvious. But I thought that for starters I could mention them.
> 1) Choose an appropriate sorting algorithm. Here's a good reference for starters. Note that you can usually make the assumption that on each iteration your list is already going to be mostly sorted, since I don't think you'll have sprites taking huge jumps across the map.
> 2) Only draw the sprites that are visible on the screen. Don't waste time drawing something the user is not going to see.
Maybe you already do these things, or maybe they're fairly obvious. But I thought that for starters I could mention them.
You're going to have to break up your map into some sort of sectors, and record which sector a given object is in.
Then only consider for rendering, the sectors which are overlapping with the visible area.
Potentially similar optimisations can be used for logic handling - i.e. maintain a list of "interesting" sectors (with awake monsters, or objects which are doing "interesting" stuff), and only process objects in sectors which are either visible or have "interesting" objects in.
Mark
Then only consider for rendering, the sectors which are overlapping with the visible area.
Potentially similar optimisations can be used for logic handling - i.e. maintain a list of "interesting" sectors (with awake monsters, or objects which are doing "interesting" stuff), and only process objects in sectors which are either visible or have "interesting" objects in.
Mark
Quicksort is a fast sorting algorithm, i already use it, and i've got a check for sprites which aren't on the screen. But the main problem is that i've got to many sprites. So when the screen is updated, there is a for loop which loops trough every sprite and checks it is visible and if it is draws it. And that tages a long while. :(
I've tried that Mark, but the problem is: there are also walking sprites, so these sprites can't be in a sector. (They're walking in several sectors)
Why not split that 1000x1000 map into smaller maps that are loaded and processed independently then? You wouldn't have that problem then, unless for some reason you *had* to have all these objects together on one huge map.
markr gave a better solution, but it might be a bit harder to implement than simply breaking the map up into several component maps.
markr gave a better solution, but it might be a bit harder to implement than simply breaking the map up into several component maps.
Quote:Original post by gerbenvv
I've tried that Mark, but the problem is: there are also walking sprites, so these sprites can't be in a sector. (They're walking in several sectors)
How could a sprite be walking in more than one sector? Unless you have mirrors/clones all over the place or something. If what you meant to say was that a sprite can walk from one sector to another, then that's different. Only update the sprites in your current sector and don't bother with the others. Then when you arrive to a new sector, begin processing all the sprites/objects in that sector.
I think you're trying to do more work than is needed. Yes, the sprites *should* be moving around even when they are not on your screen, but in game programming you often have to abstract things so that your code is fast enough to prevent any noticeable slow-down. Its not like with path finding you examine every single possible path combination, right? Same principle applies here.
Yeah, but sometimes there is more than one sector on the screen. So, if a sprite is walking on the screen, can't he go to antoher sector?
Objects *can* move from one sector to another, but they will only ever be in exactly one sector.
So when an object moves, it needs to be checked if it's gone outside the current sector, and be moved to another sector.
For rendering, it's easy, simply traverse the sectors which are visible. If you make your sectors big enough (say, slightly larger than the visible area), then you will only need to check a maximum of about 4 sectors.
Objects in other sectors will simply be ignored.
For movement etc, you might want to consider an area larger than the view frustum, but you could still consider a subset of the entire universe.
Mark
So when an object moves, it needs to be checked if it's gone outside the current sector, and be moved to another sector.
For rendering, it's easy, simply traverse the sectors which are visible. If you make your sectors big enough (say, slightly larger than the visible area), then you will only need to check a maximum of about 4 sectors.
Objects in other sectors will simply be ignored.
For movement etc, you might want to consider an area larger than the view frustum, but you could still consider a subset of the entire universe.
Mark
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement