• Advertisement
Sign in to follow this  

Sprites in huge world

This topic is 4549 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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. :(

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
So if sprite x goes to section 2, he must be moved into section 2?


____________ ____________
| | |
| ______|______ |
| | x | | |
| | 1 | 2 | |
| | | | |
| |______|______| |
| | |
|____________|____________|

Share this post


Link to post
Share on other sites
Quote:
Original post by gerbenvv
Quicksort is a fast sorting algorithm, i already use it

No it's not. Not always, anyway.
If you're working on data that is almost sorted to begin with, it is horribly slow. (And I'd assume that is the case for your game).
Since only a few values are going to change every frame, you should be able to use a sorting algorithm that takes advantage of that.

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

Well, sounds like your check works by checking every sprite, which kinda defeats the point. You should already know which sprites are used where, so you can simply look up what is used in the visible area. For example, each tile could just contains pointers to the sprites it uses. Then you don't need to loop through all your sprites, you only need to check the handful of tiles that are on screen, and read the pointers from there.

Share this post


Link to post
Share on other sites
Yes, your object manager can have something like this:


For each object we are currently interested in {
call object movement function;
if (object has moved) {
check if object still within its previous sector;
if (object is in a new sector) {
Remove object from its previous sector's object list;
Add object to its new sector's object list;
}
}
}


Mark

Share this post


Link to post
Share on other sites
It's ok, i found this one:


void insert_sort(int data[], int length) {
int i, j, value;

for (i = 1; i < length; i++) {
value = data;

for (j = i - 1; (j >= 0) && (data[j] > value); j--) {
data[j + 1] = data[j];
}

data[j + 1] = value;
}
}

Share this post


Link to post
Share on other sites
Seperate your world into seperate levels, and only load what is in levels sorrounding the player.

So like

L11 L12 L13
L21 L22 L23
L31 L32 L33

player is in L22, you only load these levels sorrounding him.

Share this post


Link to post
Share on other sites
Quote:
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


Your basic problem is that you're considering every sprite on every frame. Why consider the same off-screen sprite many times every second when you've already performed the same calculation recently?

Just create a list that holds the identification (depending on how your program is structured. Can be array indexs, hashtable keys, pointers etc) of all 'visible sprites'. This list should be updated only when A)The camera view moves, and B)When a sprite's world location changes.

Your draw function should only consider the sprites on that visible sprite list, because you've already calculated what is seen and what is not seen. The Draw function should always remain as minimal as possible because it can easily become a bottleneck if you're trying to do too much in it.

Other people have made good suggestions here as well that could easily be mixed with this solution.

Share this post


Link to post
Share on other sites
I have tried most of the suggestions already posted and tried many different variations and combinations. The solution I use involves having sprites belong to a series of different lists. For clarity, the term sprite is being used as "any non-background image and any non always-on-top image: read 'tiles'". This could be a player, npc, tree, or any item.

The big list:
Durring a sprite's lifetime it belongs to a large managed list of all non-tile sprites. Each sprite is sorted by it's y then x position. When a sprite moves it is removed from the list then re-inserted via a binary search from it's last position in the list (obviously takes longer if the sprite is new and had no previous location). The sorting here will come in handy later.

The tile list:
Each tile keeps an internal list of pointers/references to sprites sorted first by y then x position. The same type of insertion sort as on the big list is used here when a sprite moves.

The fun part comes next. Since the sprites are sorted in the order they are in the big list and then again on the tiles, I can use a row of tiles to form a scanline of sprites. A scanline consists of the first sprite on the leftmost visible tile and ends with the last sprite on the rightmost visible tile. Since the sprites are sorted in their correct drawing order in the big list, drawing a scanline looks something like:


// pseudo code, please don't try to use it literally.

// first visible sprite in the scanline
first_sprite = left_tile->SpriteList.First();
// last visible sprite in the scanline
last_sprite = right_tile->SpriteList.Last();

// walk through the big list starting at our first visible sprite
// until we draw our last visible sprite
while( first_sprite && first_sprite != last_sprite )
{
// draw the sprite
first_sprite->Draw();
// walk through the list
first_sprite = first_sprite->NextInBigList();
};




The thing I like about this approach is that I can choose the size of the area I want to work with. I use the grid-like architecture of a tilemap to get array lookup speed out of a linked list without having to iterate over unnecessary parts while at the same time I get the speedy expansion/insertion/removal that comes with a linked list.

The biggest drawback to this I feel is having to manipulate the sprite accross 2 lists whenever it's position changes. This is a tradeoff I am willing to live with at the moment since it is only affected when something changes it's position.

I hope that gives you an idea at least.

Share this post


Link to post
Share on other sites
Thanks for replies!

I've now got this idea:

[ main ]

sprites : array with sprite types (tree, house, npc, etc.) (struct sprite)
sprites coords : array with sprite coords (struct sprite_coord)

[ sprite struct ]

width, height : sprite its width and height
surface : surface with sprite on it (ddsurface)

[ sprite coord struct ]

x, y : sprite its position on map (long)
sprite : pointer to sprite type (struct sprite *)
next : pointer to next sprite of the tile (struct sprite_coord *)

[ tile struct ]

... some shit of the tile

sprites : total sprites on tile(int)
sprite : pointer to first sprite of the tile (struct sprite_coord *)

[ update function ]

* show tiles
* put every sprite from every tile in an array
* sort array on y and x
* walk trough sprites and draw them

What about this, is there a way to do it faster?

Share this post


Link to post
Share on other sites
Hi,
When programming my tile engine I used to have an array lists the same 'height' of the map, say if your map is 1000*1000 then the array had 1000 entries. Name it:
ENTITYLIST EntityList[1000];
Each list responds to a Y coordinate. Then an object locates at y=10.5 and another located at y=10.8 both will be set into the list EntityList[10]. If one of those objects move to another coordinate, like Y=11.1, then it should be located at the EntityList[11].

When rendering the background, I know exactly the limits I should consider for rendering. Say I render the background tiles, columns 200 to 240, rows 100 to 130. Then I exactly know my extents in rows and columns. Then in this case, I know I should process from EntityList[100] to EntityList[130]. But if you have large objects you may want to render (like a tree or a castle), then consider extending the limits a little and consider rows from 90 to 130.

Now, what to do with X? Keep the lists sorted. Don't just add objects in front or back, you should keep them sorted. Notice that when you render the background, you also know the columns in your map. In the previous example we renderes columns from 200 to 230. If your lists are sorted, then you can iterate the list and discard objects until you reach the coordinate 200 up to coordinate 230, when you pass this limits stop and continue with the next List.

Of course you can optimize this. There is no reason to have only one of these list arrays. You can have as many as you wish foming layers. I recall having one for ground objects (rubble, rocks, flowers and dead units), one for treasure (coins, weapons, chests), one for inmobile objects (walls, trees, fountains, big rocks, houses), one for characters and monsters (they keep moving from one place to other, changing from list to list), and one for flying objects. Its good to keep moving units in a different list, that way the lists gets smaller and the changes are quick.

Hope this helps.
Luck!
Guimo



Share this post


Link to post
Share on other sites
That's gonna need to much memory. i can't have an array of 1000 x 1000, but one of 50.000 x 50.0000.

What do i have to do if a sprite is 100px width? Take the center as THE point? But what if only 40px are visible?

[Edited by - gerbenvv on September 8, 2005 1:15:10 PM]

Share this post


Link to post
Share on other sites
Hi,
No problem.
Each object list is basically a pointer to objects with little extra info. Maybe one int to count objects in each list. Thats about 8 bytes.
8 bytes*1000 = 8kb... not much mem at all...

8*50000=400kb... average PC has way larger memory. Consider in this case your 50000*50000 map will consume at least 1 byte/entry... thats about 2.5gb memory...

Now, if you have that size of maps, dont try to load all the map in one time. Brek it into 256x256 chunks and keep 9 chunks (central and the 8 around) loaded at a time.

Now, each sprite HAS a central point. Its exactly where the sprite is located in the world. Say a tree is located in your world at position (32.3f, 24.5f). You place it in the list number 24. When you process the list, you must consider an additonal extent. If you have to process rows from 100 to 120, then consider processing rows from 90 to 130 so objects may be processed.

Consider that you are rendering 40 rows. But you are saving 960.

There are some other considerations when this is useful, particularly when processing lights and blockers for real time shadow.

My old game engine:
http://www.spritekin.com/kengine/screenshots.htm

Luck!
Guimo

Share this post


Link to post
Share on other sites
I programmed my idea and it is very fast! (75 fps) So there is no need to chunk the world.

World map = 4.95Mb
1000 x 1000 tiles (tiles are 50 x 50)
10000 sprites

Now, i'm gonna do the graphics.

Share this post


Link to post
Share on other sites
Why waste memory on a tile struct? You can just have a 2D array w/ an int value to represent tile and base tile type by where it the tile is on the tileset, so you group the blocking tiles, non blocking, water, etc.

Edit: Wait, did you actually like draw the background of the map or did you work off a tileset? If you just drew it, you still don't need a tile struct, just need to store each tiles value whether its swimming blocking nonblocking etc......

Share this post


Link to post
Share on other sites
I've now got an array with tile types (named tiles) and an array with the tile struct.

In the tile struct is information about its row, cell, sprites on it, pointer to first sprite, etc.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement