• Advertisement
Sign in to follow this  

Sorting sprites

This topic is 4521 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
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
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
Assuming you have a reasonably large number of sprites (at least 1000), try radix sort. See here for how to do it with floats. It runs in O(n+m) time, where n is the number of elements and m is dependent on the algorithm itself (which is why you don't use it for sorting small lists).

Share this post


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


This is a cool tool for drawing diagrams in your code.
I dunno if it works under .NET though..

Share this post


Link to post
Share on other sites
You guys have really helped me out a lot. Here's the results of what I have so far (do you like my programmer art?) The sprites jump (instead of moving smoothly) because I'm using a trial version.

RTS Stage 1 (12kb)
RTS Stage 1 (7KB WMV)

[Edited by - Programmer16 on October 9, 2005 2:14:46 PM]

Share this post


Link to post
Share on other sites
The point is moot since you have abandoned qsort, but there is a problem with the comparison function.

qsort expects the comparison function to return a negative number if the first < second, 0 if they are equal, and a positive number if the first > second.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
As I've understood, insertion sort and especially shell sort is good for sorting sprites as they're almost always nearly sorted.

Share this post


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

  • Advertisement