Archived

This topic is now archived and is closed to further replies.

red_sodium

Best method of sorting sprites

Recommended Posts

Hey, I''m looking for a fast, easy way to sort sprites in drawing order. I''m using a (std:vector at the moment, but if I want to be able to bring sprites in front and behind each other regularly, I would have to re-order the vector every frame. Is there an easier/(CPU) cheaper way of doing this?

Share this post


Link to post
Share on other sites
If you start with alot of sprites: sort them before you go in the gameloop.

Everytime you add a sprite: insert it into the correct spot.
Everytime you move a sprite: move it to the correct spot.


Would this help?

--
You''re Welcome,
Rick Wong

- sitting in his chair doing the most time-consuming thing..

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hi there, I''ve just implemented a technique for rendering scenes from front to back using a MergeSort algorithm based on objects'' depths into the screen. Mergesort scales well for large numbers of objects ( O(n*log(n)) vs O(n^2) for simpler selection sort etc), and can easily be implemented as a template class --- your sprites would simply need to overload the <= and = operators.

I found this very useful:
http://www.halcy0n.com/docs/mergesort.html

Cheers

Share this post


Link to post
Share on other sites
If you''re using a 3D API the easiest way would just be to set the Z-Values and let the graphics card sort it out.

Otherwise, my main advice would be to not use a vector if you''re going to be rearranging a lot of objects each frame. An STL list would probably be a more logical choice.

----------------------------------------
"Before criticizing someone, walk a mile in their shoes.
Then, when you do criticize them, you will be a mile away and have their shoes." -- Deep Thoughts
"If you have any trouble sounding condescending, find a Unix user to show you how it''s done." - Scott Adams
FaceHat Software -- Wear the hat.

Share this post


Link to post
Share on other sites
We currently sort about 100-200 objects (sprites) per frame using std::sort on a std::vector and it isn''t a bottleneck. Perhaps with a lot more objects you''ll run into problems, hard to tell without some idea of how many objects you''re sorting and what other things are going on.

We cull those objects out of a larger list of all the visual objects based on bounding boxes and stick them into the vector, then sort that.

As always - profile your solutions.

Share this post


Link to post
Share on other sites