____________ ____________| | || ______|______ || | x | | || | 1 | 2 | || | | | || |______|______| || | ||____________|____________|Sprites in huge world
Author
So if sprite x goes to section 2, he must be moved into section 2?
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.
Yes, your object manager can have something like this:
Mark
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
Author
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; }}
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.
So like
L11 L12 L13
L21 L22 L23
L31 L32 L33
player is in L22, you only load these levels sorrounding him.
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.
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:
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.
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 scanlinefirst_sprite = left_tile->SpriteList.First();// last visible sprite in the scanlinelast_sprite = right_tile->SpriteList.Last();// walk through the big list starting at our first visible sprite// until we draw our last visible spritewhile( 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.
Author
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?
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?
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
