gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Sorting sprites

#67570 - gauauu - Thu Jan 19, 2006 2:43 am

Hey all, I'm getting ready to start an algorithm to sort my sprite list, based on screen position (on a top-down, almost isometric view, similar to secret of mana).

I had some ideas about how to implement it, but wanted to run my thoughts by some of you smart folk to see if anyone has any suggestions.

Basically, I want to sort to keep my sprites on the bottom (more "front") part of the screen drawn first, so must sort them to the front of the sprite data.

Here are the things to consider:
1. There won't be that many sprites to sort. (gba doesn't have so many sprites, and probably more likely I'll only use 30-40 at a time)
2. Because object don't move extremely fast, the array will almost always be "almost sorted"


So, my thought, which runs contrary to everything that I feel like is good and reasonable, is to do a type of bubble sort.

Each frame, I would do ONE pass of the bubble sort, swapping entries as needed. Then, I wouldn't worry about the remaining out-of-order sprites until the next frame of gameplay.

Doing this way, each frame, I am guaranteed only one pass through the list. And as most of the time, only 1 or 2 sprites will have swapped places, a simple bubble sort swap will fix them.

The nice things about using a bubble sort in this situation are:

-usually if a sprite will be out of order, it will only need to be moved to an adjacent slot, not to be inserted at some completely other position

-with other sorting methods, it's harder to isolate it down to just 1 pass through the list. With insertion, for example, it can take 2 passes just to fix one item. Or with something like quicksort, it mangles the list to pieces while the sorting is in process, so you have to do the sort all at once, instead of doing it a piece at a time. The bubble sort can sort of be in a state of perpetual "sorting", where after you do one pass, you can keep using the list, even if it is slightly out of order


For more complicated situations, this method might take multiple frames before it finally has the list properly sorted. Which means that for the worst cases, there might be a few frames where sprite priorities are wrong and the screen sprites look funny. But in all but the very nasty cases, (all sprites but one lined up on the same scanline, the one sprite passing by them all) it shouldn't be more than a small handful of frames, and be barely noticable (especially because the sprite priorities only matter when the un-sorted sprites overlap). I figure this would probably be a fair tradeoff to guarantee that my sorting doesn't end up taking a huge amount of time.

Anyway, am I missing something big? Any thoughts?

#67593 - poslundc - Thu Jan 19, 2006 6:08 am

It's worth a shot, but if I were you I'd just sort every frame. Quicksort is good, although in the last engine I wrote I just rebuilt the entire linked list from scratch and inserted the sprites in the correct order as I processed their distance-to-camera values.

If you write your code modularly, you should have no problem swapping out your sorting routine if performance becomes an issue.

Dan.

#67594 - gauauu - Thu Jan 19, 2006 7:37 am

So you think the hit of a fast sort such as the quicksort every frame is, in a general sense, small enough to not cause problems?

And good call about keeping the sorting code very modular, so I can rip it out and replace it at need. That will make it easier. I learned that lesson from the sound system....using krawall, then ripping it out and replacing it with AAS, then going back and ripping it out and moving back to krawall.

#67596 - DekuTree64 - Thu Jan 19, 2006 7:58 am

I'd probably stick with your original idea of doing a bubble sort, and just make some little optimizations knowing that it's probably mostly sorted to begin with.

Simplest would be to make a flag variable, and set it if you have to swap 2 sprites. I you finish a pass and the flag was never set, you're done.

Slightly more complicated, but avoids wasting an entire pass to find out that you're done, you could save out the first and last indices that changed during a pass. Then for the next pass, you only have to check oldFirst-1 through oldLast+1, since any outside that range are obviously not going to change. If only one sprite moved, you iterate over 3 entries for the 'finished check' pass, rather than the entire list.


Of course, optimizing bubble sort is kind of like cleaning a dump (i.e. not going to get you very far), but as Dan said, you can swap it out later if needed.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

#67597 - poslundc - Thu Jan 19, 2006 8:02 am

gauauu wrote:
So you think the hit of a fast sort such as the quicksort every frame is, in a general sense, small enough to not cause problems?


For a reasonable amount of sprites, yes. I've not done much in the way of stress-testing, but then I've always seen it as something not worth prematurely optimizing.

In the studio I work in, our games are locked to 30 Hz anyway, which is more than enough time to sort all the sprites you could want.

Dan.

#67599 - gauauu - Thu Jan 19, 2006 10:02 am

30Hz? Interesting.

I've always been of the mindset that it's hard to tell the difference once the framerate gets above 30, but there are so many people that will go on and on about how it makes a difference. (all those people who buy $300 graphics cards so they can play Quake 17 at 437 FPS)

So, do people ever notice and complain about the lower framerates, or does it seem to be a matter of "don't tell them, and they don't notice?"

Anyway, thanks for the suggestions.

#67606 - Mucca - Thu Jan 19, 2006 12:05 pm

I use insertion sort, its light and easy to understand, better than bubble sort, and for data that is nearly sorted it performs almost as well as quick sort. In my opinion, the complicated sorting algorithms such as quick, radix, bucket etc, are only worth it if a large amount of data needs to be sorted.

Code:

// Sample insertion sort algorithm processing array of pointers to objects
// to be sorted, eg sprites
// Change sort comparison to '>' for ascending

int i, j;
Object * obj;
int sort;

for (i=1; i < numObjects; i++)
{
   obj = objects[i];
   sort = obj->GetSortCode();      // e.g. y-coordinate
   j = i;
   while ((j > 0) &&
( objects[j-1]->GetSortCode() < sort ))     // descending
   {
      objects[j] = objects[j-1];
      j = j - 1;
   }
   objects[j] = vobj;
}

#67632 - poslundc - Thu Jan 19, 2006 4:55 pm

gauauu wrote:
30Hz? Interesting.

I've always been of the mindset that it's hard to tell the difference once the framerate gets above 30, but there are so many people that will go on and on about how it makes a difference. (all those people who buy $300 graphics cards so they can play Quake 17 at 437 FPS)

So, do people ever notice and complain about the lower framerates, or does it seem to be a matter of "don't tell them, and they don't notice?"


I can tell the difference usually between a game running at 60 Hz and the same game running at 30 Hz, but if you just give me a game that happens to be running at 30 Hz on a dinky platform like the GBA, I don't know if I'd be able to notice that I was missing anything.

If you're gonna do bubble sort, I'd recommend either doing full bubble sort or doing it DekuTree's way. I know I'd rather have a sort that won't be relying on some constraint of game physics that is unlikely to be enforced just to make a small optimization.

But then I would also recommend doing whatever's relatively simple to do - even insertion sort - and optimizing it when it becomes a problem.

Dan.

#67655 - YopYop - Thu Jan 19, 2006 8:10 pm

For my part when I?ve made a RPG engine I use double link list of sprite. When you enter in a new map I load the list for this map then I add the main character into this list and I keep it sort through all characters movements. I mean you slice the moving sprite up or down in the list. It work quite well if you don?t have too much moving sprites.

yopyop

#67735 - gauauu - Fri Jan 20, 2006 2:02 am

Well, I'll play with doing a full sort (Ditch bubble sort, use a real sorting algorithm) and see if I get any problems.

Thanks for the advice.

#67862 - Miked0801 - Fri Jan 20, 2006 11:18 pm

Consider shell sort - low overhead and o^1.25 performance. works great