Archived

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

gorgar

STL <list> sorting problem

Recommended Posts

(I've replaced the gt and lt signs with brackets in this post) How can I use the STL (list) sort functions to sort a list of pointers to objects (rather than sorting the pointers themselve, which is useless) ? I'm using (list) to store pointers to my sprite objects, and have overridden the sprite objects' (,),== and != operators, but all I can get (list).sort to do is sort the pointers. Here's the declaration I'm using for the list... list(CEntity *) m_pUnitList; If anyone could provide a small snippet to help me on my way I'd be grateful. What am I trying to do ? Basically I want to re-sort all screen objects based on their Y coordinate for a top-down style game. Thanks Edited by - gorgar on 7/24/00 10:34:29 PM Edited by - gorgar on 7/24/00 10:35:43 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

First off, sorting a list is going to be slow. You may want to define your own wrapper to force all insertions to be "in place". or consider using a set. That being said, you need to define an operator that compares pointers by dereferencing them.

struct cmpCEntity {
bool operator()(const CEntity *a,const CEntity *b) const {
return ((*a) < (*b));
}
};

This will call your overloaded comparison operator, you can now pass this as a template param.

set m_pUnitList;

Note that now inserts and deletes are now logrithmic, but you were eating O(NlogN) with each sort so we''re still ahead. Iterators still work exactly the same as in list.

For a tile based game, consider dramatically reducing the number of hights that tiles may occupy and keeping each "level" in it''s own vector with another vector of pointers to these vectors. Each level vector can have 2D coords with the usual [z*width+x] scheme. Moving a tile from one level to the next (changing it''s height) just requires coping one entity (or pointer) from one vector to the other. It all depends on how many tiles you want to be able to stack.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
oops, damm html

set(CEntity *,cmpCEntity) m_pUnitList;

replace ()''s with angle brakets.

Share this post


Link to post
Share on other sites
I was pretty sure when I started that this whole approach was inefficient and could be done better, so let me pose this question instead...

What is the best approach to sorting a maximum of 64 sprites each frame, based on the Y position of each sprite ?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I assume that by Y you mean the height of the sprite, such that
two sprites that overlap on the screen must be drawn in order of
increasing Y. If no two sprites can have the same height, or you
don''t care I would just keep a single list of all sprites in
sorted order, swapping only when a sprite changes Y value. Note
that just using set on only 64 objects means that inserts and
deletes only take 5 "ops" and you could have 128 sprites for 6
"ops" so we don''t really care that much. Giving each sprite a
pointer to the highest sprite it occludes will speed things up a
bit, and scale to large numbers of sprites much better.

The other way of doing this is rather than have a strict
Y/Height, have several "priorities" of sprites. something along
the lines of Ground,Items,Dead_Critters,Critters,Flying. Our
Hero gets drawn at the Critters Priority, and when you kill a bat
the bat gets demoted from Flying to Dead_Critters.

Share this post


Link to post
Share on other sites
That's a really interesting problem, and there are a couple of steps.

First of all, to sort the sprites at all, you'll have to have a comparison function. I assume the Sprite class has its y-coord as a non-public member. So you'll need to make a public function that specifies whether one sprite has a greater coordinate than another:

class Sprite
{
private:
int x, y; // coordinates
public:
bool yLess (const Sprite& rhs) const
{
return y < rhs.y;
}
bool xLess (const Sprite& rhs) const
{
return x < rhs.x; // allows you to sort by x as well
}
};


Now, in order to use STL's sorting functions, you need to form a predicate, which was shown by a previous poster. I'll show it here with my new class functions:

class PSpriteYLessPred
{
public:
bool operator () (const Sprite* lhs, const Sprite* rhs) const
{
return lhs.yLess (rhs);
}
};

(note: I've never used anything other than a reference to a pointer here. If you start to get weird errors, use a reference to a pointer instead of the pointer as arguments. I assume this works because this is what the previous poster submitted).

It appears from your post that you have all of your sprites in a list. They should be kept in a list if you are keeping iterators around pointing to each sprite, and intend on deleting them using the iterators later. If not, you probably want a different kind of container.

Regardless, I'll assume they're in a list. You have two choices: use list::sort, which is a sort optimized for linked lists (but still not the best sort), or you can copy the pointers to a vector and sort them there. Experimentation is probably the only way to figure out which way is better, but I'll show both:

// sort the list
spriteList.sort (PSpriteYLessPred);

// copy to a vector & sort that
vector<Sprite*> sortVec (spriteList.begin (), spriteList.end ());
// note--I've never gotten that constructor to work, but I think
// that's a Microsoft STL implementation bug. The STL spec
// says that should work. If it doesn't, do this:
vector<Sprite*> sortVec (64);
copy (spriteList.begin (), spriteList.end (), sortVec.begin ());

// now sort
sort (sortVec.begin (), sortVec.end (), PSpriteYLessPred);


Kinda fast & loose with the code there, there might be a bug or two, but that's the idea. Good luck.

Edited by - Stoffel on July 25, 2000 1:32:24 PM

Share this post


Link to post
Share on other sites
You guys are missing one of the benefits of C++. Operator Overloading, Overload the < > <= >= == != operators to compare the y members of two different objects. You can then use a basic quicksort (or any sort for that matter) without changing anything except for the types used when swapping, you might want to set it up so you have a minimum of swaps, it is better to have more comparisons than moving all that memory around.

Just wanted to add, the best sort for something like that is most likely a selection sort, it selects the lowest item in the list and places it at the beginning. It has as many swaps as there are items in the list. If you want to know how to do it, e-mail me.

Edited by - olp-fan on July 25, 2000 2:20:34 PM

Share this post


Link to post
Share on other sites
olp-fan, you have just stepped in one of the one of the big hazards of oop. Just because you can overload say [] does not mean that access will still be constant when you do list [ i ]. Of course, you shouldn't add too much magic to operators, but you cannot always trust this.

In this case gorgar has already overloaded the comparisons for
his sprites(correctly, good use of op overloading). The problem
is, he had a list of pointers to these objects. There is no way
for a class to overload pointer comparison. This is one of the
reasons that STL provides a template param for a prefix class to
act as the comparitor.

Note that I originally suggested using set instead of list, as set is always sorted(it's usually some form of balanced tree). In this case the prefix class works fine. To perform a quicksort
(and have it work well) you need random access to the data to find your pivot. STL proviedes this for any class that can get away with random_access_iterators as it's begin() and end().

thus coping a list to a vector, and then sorting that would work.
you would be better off using vectors instead of lists for the whole thing in this case though. You don't need insertion, because you are going to reorder when you sort anyway.

Plus you will want to use a Radix sort in any event, as long as your key's are ints you can blow quicksort out of the water any day of the week. However, we only have ~64 objects to sort, so anything we do is going to be fast. set works, and has a worst case of 5 pointer traversals on insert/delete.

the seprate priority lists also works, is faster, and adds some extra structure to the game that might come in usefull later. The priority lists could also be vectors as we don't care about the order of sprites in each priority so you aren't chaising pointers like you are with list. it's also more memory efficient.


Edited by - Grib on July 25, 2000 3:02:13 PM

Share this post


Link to post
Share on other sites
olp-fan:
how do you decide what < means with a Sprite? If you look at my code, I gave xLess and yLess, because they''re both valid comparisons.

One of the dangers of operator overloading is that it can obfuscate code. If I have a string class, it''s obvious what < means (alphabetically before). If I have a time class, it''s obvious what < means (chronologically before). However, if I have a sprite class, or a vector class, or an imaginary number class, it is NOT obvious what < means. Therefore you shouldn''t overload operator < in these cases.

Share this post


Link to post
Share on other sites
Well, I want to thank you all for the replies you''ve posted - I''ve got plenty to think about now, and plenty of things to try. I''m going to run some timing tests and see which approach performs better.
So much to do, so little time...

Share this post


Link to post
Share on other sites