Jump to content
  • Advertisement
Sign in to follow this  
Programmer16

Sorting sprites

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

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


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


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

Share this post


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


Link to post
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::sort

bool compare_renderables(const CRenderable* lhs, const CRenderable* rhs) {
return ....
}

....
std::sort(m_Objects.begin(), m_Objects.end(), compare_renderables);

Share this post


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


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


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


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

-Dave

Share this post


Link to post
Share on other sites
Quote:
Original post by ph33r
Mushu, 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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!