Sign in to follow this  

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

This topic is 4277 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

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 this post


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

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

Share this post


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


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


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

Share this post


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


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


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

Share this post


Link to post
Share on other sites

This topic is 4277 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this