# Sorting sprites

This topic is 4610 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok, I feel really stupid right now. I'm working on a 2D game and I can't figure out how to sort the sprites. I know that I'm supposed to sort them by the Y value (and that I should use qsort), but I can't figure out HOW to sort them. I was trying something like this:
int ObjFactoryCompare( const void *pArg1, const void *pArg2 )
{
CRenderable* pObj1 = (CRenderable*)pArg1;
CRenderable* pObj2 = (CRenderable*)pArg2;
return pObj1->GetPosition().y < pObj2->GetPosition().y;
}

void CObjectFactory::Render()
{
m_pDirect3D->EnableAlphaBlending(true);

qsort(m_Objects.begin(), m_Objects.size(), sizeof(CRenderable*), ObjFactoryCompare);
for(unsigned int nIndex = 0; nIndex < m_Objects.size(); ++nIndex)
{
if(m_Objects[nIndex]->GetTexture()->GetFileName() == "building.dds")
{
m_Objects[nIndex]->Move(m_Objects[nIndex]->GetPosition().x, m_Objects[nIndex]->GetPosition().y - 64);
m_Objects[nIndex]->Render();
m_Objects[nIndex]->Move(m_Objects[nIndex]->GetPosition().x, m_Objects[nIndex]->GetPosition().y + 64);

}
else
m_Objects[nIndex]->Render();
}
m_pDirect3D->EnableAlphaBlending(false);
}


And it doesn't sort the objects (the units are still drawn first). (The -64 and +64 are so that it checks by the halfway point instead of the top of the building). Any help would be appreciated! Thanks Edit: I was also wondering, is it possible to use the z-buffer to automatically do this for me?

##### Share on other sites
If the array contains pointers to objects then the comparison function will recieve pointers to pointers to objects.

Like this:
int ObjFactoryCompare( const void *pArg1, const void *pArg2 ){ CRenderable *pObj1 = *((CRenderable **) pArg1); CRenderable *pObj2 = *((CRenderable **) pArg2); return pObj1->GetPosition().y < pObj2->GetPosition().y;}
Quick sort is probably a bad choice if you intend to progressively sort the same list over multiple frames however. Consider that quick sort on a presorted array will never get below logarithmic performance while a bubble sort would have a linear running time.

##### Share on other sites
You'll probably want to sort by y + h instead of just y:
      y+h:  _____      y:    _____          |     |___       |_____|___  ____|     |   |  ____|_        ||    |     |   | |      |       ||    |     |   | |      |       ||    |     |___| |      |_______||____|     |     |______|   |         |_____|          |_____|

##### Share on other sites
You guys are the best. You're right Mushu (like always), sorting by Y + H gives me the results that I want.

Thank you very much (I've been racking my brain for 3 days over this.)

##### Share on other sites
To add to that (aswell as side-tracking alittle) it definitely seems like you are using C++ so use the standard library algorithm std::sort instead no need for void pointers & casts here:

#include <algorithm> // std::sortbool compare_renderables(const CRenderable* lhs, const CRenderable* rhs) {   return ....}....std::sort(m_Objects.begin(), m_Objects.end(), compare_renderables);

##### Share on other sites
Quote:
 Original post by doynaxQuick sort is probably a bad choice if you intend to progressively sort the same list over multiple frames however. Consider that quick sort on a presorted array will never get below logarithmic performance while a bubble sort would have a linear running time.

This is what I hate about this industry (Everybody tells you something different). I'm new to sorting so I don't really know all of the specifics, but I had read on a post here that bubble sort was a bad idea and that quick sort was the way to go. I'll try to get a bubble sort working and I'll profile them.

Thanks!

##### Share on other sites
Quote:
Original post by Programmer16
Quote:
 Original post by doynaxQuick sort is probably a bad choice if you intend to progressively sort the same list over multiple frames however. Consider that quick sort on a presorted array will never get below logarithmic performance while a bubble sort would have a linear running time.

This is what I hate about this industry (Everybody tells you something different). I'm new to sorting so I don't really know all of the specifics, but I had read on a post here that bubble sort was a bad idea and that quick sort was the way to go. I'll try to get a bubble sort working and I'll profile them.

Thanks!
Oh, bubble sort is still a bad idea in this case since it's performance will drop fast when the list starts getting out of order. It'll usually be faster than a quick sort though.

There are better algorithms for sorting pre-ordered data however. But I'll let someone suggest some examples since I'm a little rusty on the subject myself.

##### Share on other sites
Ok doynax, thanks!

Thanks guys, its working awesome now. I switched over to std::sort() (You have a typo snk_kid, you put m_Objects.begin() as the second parameter and it should be m_Objects.end()) and it works fine.

Thanks again!

##### Share on other sites
Mushu, I rated you up because you were capable of drawing those ascii overlapping boxes. I'm impressed.

-Dave

##### Share on other sites
Quote:
 Original post by ph33rMushu, I rated you up because you were capable of drawing those ascii overlapping boxes. I'm impressed.

lol. Its not a good sign of my productivity, to say the least [lol]

• 15
• 9
• 13
• 41
• 15