# Several hunders of 2D objects in one screen - how to render from farer to closer one?

## Recommended Posts

L_Devil    122
Hello! I'm trying to make good particle system in 2D game. I loaded sprite for effect to directdraw surface, and I prepared that structure for particle:
struct particle
{
POINT position; //actual position on scree,
bool exist; // does this particle exist in the moment of rendering?
POINT movment; //x, y of translating
short frame; // current frame
int depth; // how far from user particle is
};


And I stored it all in one global array:
particle flame[250];


I want to blt all of them to the screen, starting from the farest and ending in the closest. Becouse array isn't sorted (To do this, actually I need to sort them in each frame - becouse some particles fading out earlier then others and it doesn't depend on order of creation) I need to make something like that in each frame:
for(int i=FARER_PARTICLE; i<CLOSER_PARTICLE; i++)
{
for(int k=0; k<250; k++)
{
if(flame[k].exist && flame[k].depth==i)
/* Here blt procedure */
}
}


And it works... BUT: If I have several hundreds of depths multiplays by several hundreds of particles objects - I need to run out about 25 thousands pass in each frames, only for particles!

##### Share on other sites
haegarr    7372
Quote:
 Original post by L_DevilBecouse array isn't sorted (To do this, actually I need to sort them in each frame - becouse some particles fading out earlier then others and it doesn't depend on order of creation)

How does fading out change the depth position of the particle?

##### Share on other sites
OrangyTang    1298
Possibly a stupid question, but if this is a 2d game do you really need to sort on a per-particle basis? I find that sorting per-system works good enough.

##### Share on other sites
pragma Fury    343
My thoughts:

1) Create the objects in the order of furthest to nearest in the first place, then there's no need for sorting at all.

or

2) Since you're working on a 2D app, there's no need to constantly re-sort the particles once they're already sorted. Just when new ones are spawned. Look into quicksort (qsort) for a fast sorting algorithm.

or

3) Game Programming Jems 5 has an article suggesting doing an incremental bubble-sort on the particles. Bubble sort is slow, but it can be stopped and resumed at a later date. The article suggests sorting as much of the array as you can within a given time-slice every frame, and then continue again on the next frame. So frame 1 you sort maybe 50 elements, frame 2 the next 50, and so on. There will be some artifacts, but they won't last long, especially with an array of only 250 elements.

##### Share on other sites
jonahrowley    300
Use direct3d instead of directdraw and use the z buffer. There are also ways to speeds up repetative draws, and you get blending, rotation and scaling for free. And it'll be a lot faster.

##### Share on other sites
Guest Anonymous Poster
You could use an STL Vector array that autosorts based on a depth value.

##### Share on other sites
L_Devil    122
Well, the difficult is here - there can be several emitters, for example one behind particles. If we have sorted particles:

1. a
2. b
3. c
4. d
5. e
itp.

and new one appeared beetwin c and d, you need to resort array to obtain this:

1. a
2. b
3. c
4. f
5. d
6. e

So it's needed to resort array in any frame that spawn particle

##### Share on other sites
haegarr    7372
You could store a pointer with the particles in a way that a deeper particle refers to the next less deep particle (say keep them in a kind of list; notice that this does not mean to drop the array stuff). For rendering you could iterate the list, simply rendering in the order given by the iteration. During this iteration you could sort in newly spawned particles into the list and remove died particles from the list.

So you have a _always_ sorted order, and no need to resort explicitely since insertion/removal is done on-the-fly. If a few particles are expected to be inserted _per frame_, then the new particles should be pre-sorted for the most efficient insertion.

##### Share on other sites
pragma Fury    343
re-sorting whenever new particles are inserted is trivial to implement, just have a dirty flag on your array.

And really, sorting an array of 250 objects using qsort is blindingly fast.

Another option would be to use a STL Set container (std::set<particle>) and implement whatever comparison operators it needs in your particle struct, it will auto-sort when inserted..

Edit:
Did a quick test, sorting an array of 250 particle objects with random depths produced an average sort time (over 10,000 tests) of 0.22487ms with qsort, so it is pretty quick.

Re-sorting an already sorted array took on average 0.073968ms.. practically nothing.

And that's a debug build. Release build reduces those times to 0.063453ms and 0.013465ms respectively.

Tests were done on a 2.2GHz AMD, times aquired using rdtsc.

[Edited by - pragma Fury on March 28, 2006 2:30:37 PM]