Back to For Beginners

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

For Beginners

Started by L_Devil March 28, 2006 08:42 AM

7 comments, last by pragma Fury 18 years ago

L_Devil

122

Author

March 28, 2006 08:42 AM

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!

haegarr

7,408

March 28, 2006 09:02 AM

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?

OrangyTang

1,298

March 28, 2006 09:24 AM

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.

[size="1"][[size="1"]TriangularPixels.com[size="1"]] [[size="1"]Rescue Squad[size="1"]] [[size="1"]Snowman Village[size="1"]] [[size="1"]Growth Spurt[size="1"]]

pragma Fury

343

March 28, 2006 10:02 AM

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.

jonahrowley

300

March 28, 2006 10:21 AM

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.

Anonymous

March 28, 2006 11:17 AM

You could use an STL Vector array that autosorts based on a depth value.

L_Devil

122

Author

March 28, 2006 11:19 AM

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

haegarr

7,408

March 28, 2006 12:07 PM

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.

pragma Fury

343

March 28, 2006 01:30 PM

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]

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

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

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

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines