I am sorting all of my objects in my game by their Y axis and creating a sorted look up for drawing things in the correct perspective.

The way I am currently doing it is with a STD::LIST, but for over 2000 objects it takes 1400 milliseconds to do the sort, I know I am probably going about this the incorrect way, sorting algorithms are really my weak point here so I am looking for some advice!

My lookup list is a STD::LIST of this class
class LookUp
{
public:
int DataLoc;
int YLoc;
};
list <LookUp> ObjectLookUp; //my list


Here is my sorting code:

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void MyData::SortObjectsByY()
{
DWORD StartTime = GetTickCount();

ObjectLookUp.clear(); //clear our list
LookUp p;
p.DataLoc = 0;
p.YLoc = Objects.GetObjectByPosition(0)->_PositionData.LocY;

ObjectLookUp.push_front( p ); //add base player


for(int i=1;i<(int)Objects.GetObjectCount();i++) //loop through all objects
{

Object* p = Objects.GetObjectByPosition(i); //get pointer

if(p->_PositionData.LocY < ObjectLookUp.front().YLoc) //lower than our start
{
LookUp p2;
p2.YLoc = p->_PositionData.LocY;
p2.DataLoc = i;
ObjectLookUp.push_front(p2);
}
else if (p->_PositionData.LocY > ObjectLookUp.back().YLoc) //higher than our end
{
LookUp p2;
p2.YLoc = p->_PositionData.LocY;
p2.DataLoc = i;
ObjectLookUp.push_back(p2);

}
else //somewhere in middle
{
LookUp p2;
p2.YLoc = p->_PositionData.LocY;
p2.DataLoc = i;
for (list<LookUp>::const_iterator iterator = ObjectLookUp.begin(), end = ObjectLookUp.end(); iterator != end; ++iterator)
{
if (iterator->YLoc > p->_PositionData.LocY || iterator->YLoc == p->_PositionData.LocY) //if its lower or equal
{
ObjectLookUp.insert(iterator, p2);
break;
}
}
}

}
DWORD ENDTime = GetTickCount();
cout << "Objectlookup size is: " << ObjectLookUp.size() << " took " << ENDTime - StartTime << " MS" << endl;

}

If you need an explanation of what is going on:

Our first object is pushed back to our LIST to create a start point (object zero)
DataLoc is the ID number of the object to look up information about it during rendering

Then I loop through the total number of objects I have currently determine if its higher or lower than the start or end point and if it is drop it in front.
If its not, I loop through the LIST and find where to insert it and insert it. (I think this is where my bottleneck is)

As of right now this is only handling static objects so I only have to do the sort on map generation, but I need to take into account my NPC's as well and they will be able to move around in real time... So doing this type of sort everytime a NPC moves on his Y axis is horrible.

Anyway, I appreciate any thoughts, thanks!

Edit: I think much of my performance is being lost because of the number of objects added to the list, normally in a vector I would reserve() memory space, but alas I cannot do that with a list.

I am sorting all of my objects in my game by their Y axis and creating a sorted look up for drawing things in the correct perspective.

The way I am currently doing it is with a STD::LIST, but for over 2000 objects it takes 1400 milliseconds to do the sort, I know I am probably going about this the incorrect way, sorting algorithms are really my weak point here so I am looking for some advice!

My lookup list is a STD::LIST of this class
class LookUp
{
public:
int DataLoc;
int YLoc;
};
list <LookUp> ObjectLookUp; //my list


Here is my sorting code:

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void MyData::SortObjectsByY()
{
DWORD StartTime = GetTickCount();

ObjectLookUp.clear(); //clear our list
LookUp p;
p.DataLoc = 0;
p.YLoc = Objects.GetObjectByPosition(0)->_PositionData.LocY;

ObjectLookUp.push_front( p ); //add base player


for(int i=1;i<(int)Objects.GetObjectCount();i++) //loop through all players
{

Object* p = Objects.GetObjectByPosition(i); //get pointer

if(p->_PositionData.LocY < ObjectLookUp.front().YLoc) //lower than our start
{
LookUp p2;
p2.YLoc = p->_PositionData.LocY;
p2.DataLoc = i;
ObjectLookUp.push_front(p2);
}
else if (p->_PositionData.LocY > ObjectLookUp.back().YLoc) //higher than our end
{
LookUp p2;
p2.YLoc = p->_PositionData.LocY;
p2.DataLoc = i;
ObjectLookUp.push_back(p2);

}
else //somewhere in middle
{
LookUp p2;
p2.YLoc = p->_PositionData.LocY;
p2.DataLoc = i;
for (list<LookUp>::const_iterator iterator = ObjectLookUp.begin(), end = ObjectLookUp.end(); iterator != end; ++iterator)
{
if (iterator->YLoc > p->_PositionData.LocY || iterator->YLoc == p->_PositionData.LocY) //if its lower or equal
{
ObjectLookUp.insert(iterator, p2);
break;
}
}
}

}
DWORD ENDTime = GetTickCount();
cout << "Objectlookup size is: " << ObjectLookUp.size() << " took " << ENDTime - StartTime << " MS" << endl;

}

If you need an explanation of what is going on:

Our first object is pushed back to our LIST to create a start point (object zero)
DataLoc is the ID number of the object to look up information about it during rendering

Then I loop through the total number of objects I have currently determine if its higher or lower than the start or end point and if it is drop it in front.
If its not, I loop through the LIST and find where to insert it and insert it. (I think this is where my bottleneck is)

As of right now this is only handling static objects so I only have to do the sort on map generation, but I need to take into account my NPC's as well and they will be able to move around in real time... So doing this type of sort everytime a NPC moves on his Y axis is horrible.

Anyway, I appreciate any thoughts, thanks!

Quick questions without looking at your code;

Do all of those 2,000 game objects need to be layered? Are there objects that don't have height associated with them that you could omit from this list to make things more efficient and have it not effect the way everything is rendered? Not that this would matter much if it's only 1400 milliseconds and you're only calling this function once upon map generation, but if you plan on layering mobile objects in real time, this will cause your game to slow down to a halt, which is what I'm guessing you were thinking when you said it's 'horrible'.

If you have 2,000 game objects in your world and you can, for example, only see 100 of them at once but you're still drawing and layering all 2,000 of them, you're rendering/layering your world in an extremely inefficient manner. You should figure out which objects are on screen and only layer/render those. A STD::LIST can be used and you could figure out when scrolling the screen or when mobile objects move OFF the screen, which objects are supposed to be added and removed from this list in real time. That way you keep the list as small as possible while only rendering and layering things you're supposed to see.

I would rename your function SortObjectsByY to "SortObjectsByPerspective" and create a new function called SortObjectsByYCoord or something, which ONLY sorts objects which are on screen using their Y coordinate and nothing else, since hopefully the perspective is not changing via any other means than the user clicking a "rotate" button or something (upon which the other sort method should be called).

Hope this helps.

-Adam

1) If you're worrying about allocation overhead, you can use a pooled allocator like boost::pool.
2) Did you try to use std::list::sort() with an appropriate comparison function?
3) Is there any particular reason that you're using a std::list instead of the other containers?

Do all of those 2,000 game objects need to be layered?
[/quote]

Yes, I am using a slidemap style isometric view in 2d. Its very important to draw things in the correct order. Depending on the Y value a object or NPC could be in front of behind an object.

Are there objects that don't have height associated with them that you could omit from this list to make things more efficient and have it not effect the way everything is rendered?
[/quote]
Yes and those are static map features and are omited. Objects are defined as things in the world that can be changed, removed, added that was not NPC's

If you have 2,000 game objects in your world and you can, for example, only see 100 of them at once but you're still drawing and layering all 2,000 of them, you're rendering/layering your world in an extremely inefficient manner.
[/quote]
I currently loop through the whole object set everyframe and only render objects that are on screen without too much of a performance hit.

You should figure out which objects are on screen and only layer/render those. A STD::LIST can be used and you could figure out when scrolling the screen or when mobile objects move OFF the screen, which objects are supposed to be added and removed from this list in real time. That way you keep the list as small as possible while only rendering and layering things you're supposed to see.
[/quote]
I like this idea, I could get my total object/npc list down to less than one hundred. And dynamically remove and add based on a screen scroll in any axis direction.
and the sort would only need to be done in 1 frame and when we transfer to the next tile during a scroll.

Hope this helps.
-Adam[/quote]
Thanks Adam, I was hoping there would be a drop in place sort method that was faster than what I was doing that I could just call in real time when a object or npc is moved/changed.
But it looks like I might have to just figure out a better way of doing this.

You need to do a sorted insert (what you're doing in your else branch) for your stuff that you add after you do your initial sort and then you won't need to worry about sorting more than once.

Try commenting out the front and back checks individually to see if they are slowing you down or speeding you up.

You can write X <= Y instead of X < Y || X == Y like the conditional in your else branch

You can allocate memory to the list using the member function get_allocator(), which you should probably do before you start sorting since you know how much memory you will need.


You might be doing this on purpose but it looks like you should be starting i at 0 instead of 1.

1) If you're worrying about allocation overhead, you can use a pooled allocator like boost::pool.

Your going to bash me for this, but I have never used boost :/

2) Did you try to use std::list::sort() with an appropriate comparison function?
[/quote]
I will check this out, but I think maybe a combination of this and what Adam suggested will be my best bet.

3) Is there any particular reason that you're using a std::list instead of the other containers?
[/quote]
I generally use vectors for everything, I am currently only using a list because I can insert in the middle of the list as well as push to the front and back.

You might be doing this on purpose but it looks like you should be starting i at 0 instead of 1.

Object 0 is added before the loop, starting at 0 would add object zero again.

edit: Also Kobo, I added your suggestions and it cut the speed by 1/3 allocating beforehand and your other recommendations, thanks for your input!
I think I need to do a bigger rewrite on my sorting system in general to get the object count to only be whats on screen.

[quote name='Kobo' timestamp='1323454898' post='4892265']
You might be doing this on purpose but it looks like you should be starting i at 0 instead of 1.

Object 0 is added before the loop, starting at 0 would add object zero again.
[/quote]

Ah, I thought you might be doing that somewhere else but it was right there in the code you posted.

[quote name='SiCrane' timestamp='1323454645' post='4892261']
1) If you're worrying about allocation overhead, you can use a pooled allocator like boost::pool.

Your going to bash me for this, but I have never used boost :/
[/quote]
You might want to look into it sooner or later. There's a reason why boost is mentioned in at least half of the C++ threads here.

I generally use vectors for everything, I am currently only using a list because I can insert in the middle of the list as well as push to the front and back.
[/quote]
You can insert in the middle or front of a vector, it's just more expensive than pushing to the back. In any case, if the only reason you are using a list is because it supports the operations you need for sorting, then you can use std::sort() on a vector.