Sign in to follow this  
Charleh

2D depth sorting

Recommended Posts

Just wondering if anyone could help me optimise my depth sorting in my game... It's a Flash game but things can get a little hectic on screen - the problem is it becomes exponentially slower when quite a few objects are on the screen. I hold all my active game objects in an array - I sort this array using Flashes in built array sorting algorithm and a comparison function which is:
function order(a:BaseObject, b:BaseObject):Number {
	if (a._z < b._z) {
  		return 1;
	} else if (a._z > b._z) {
    		return -1;
	} else {
    		return 0;
   	}
}
Is there a better way of sorting this array? Is there a better way full-stop of getting the objects at the correct depths without sorting an array? Any help would be much appreciated!

Share this post


Link to post
Share on other sites
You might want to split up your drawing into multiple layers. I generally find storing all the sprites in one big list unnessisary, since certain elements are *always* going to be behind/in front of certain others. Eg. something like

- Background
- Level sprites (tiles, etc. which make up the world)
- Moving items (enemies, powerups, etc.)
- Player sprites
- Bullets and effects
- HUD

Then you can store and sort each layer individually, which will cut your sorting time down considerably. Some layers might not even need sorting as you really don't care if enemy 1 is drawn on top or underneath enemy 2, as long as they're both drawn on top of the background and level tiles.

Share this post


Link to post
Share on other sites
Well I do only have 1 real 'group' of objects I wish to sort. These are the buildings and the game objects (bad guys, good guys and stuff) and also some effects. Explosions need to be depth sorted, as do muzzleflashes etc etc as they need to appear in front/behind the bad guys.

There's nothing I can take 'out' of the sort list. Actually I've had an idea as to what might be making the sort slower - I do sort the array before I check to see which items actually need sorting - as some objects are compound and are made up of movieclips within movieclips. I can probably get some speed from weeding out the child items from the array before sorting it...though I don't know how much faster it will be!

I'll post back when I've tried this :) thanks for the suggestion though, it sparked something!

Share this post


Link to post
Share on other sites
I don't know flash but use Blitzplus/Blitz3d although the theory should be the same I would think.

When I am sorting a group of sprites in zorder a very easy and quick way - no sort required - is to do this:

Create an array that has an index that goes from 0 to max Z. Obviously make z an integer. Each element in that array contains a handle/pointer to a list of sprites with the same Z value. Clear these lists out before each frame is drawn, then populate it simply by running through your list of sprites and, using the z value as the index to the array put them into a list at the appropriate index.

Then simply run through your array from 0 to Max Z and draw each of the sprites in the lists at each element.

A little diagram to perhaps help out...

ArrayOfZs -
Index 0
1 - Contains pointer to list of all sprites at this Z Value
2
.
.
.
Max Z

then with a simple for loop that would look something like this:

For Z=0 to MaxZ
if ArrayOfZs[Z] has a non null value here then get the list of sprites at this Z and draw them now.

next

Share this post


Link to post
Share on other sites
Yeah sounds like a good idea Matt, cheers - I don't know if the number of elements (250) will be too many for any speed increase but I can only give it a shot :)

I'll post back if it clears things up!

Share this post


Link to post
Share on other sites
Well I tried that method, the chief problem being just declaring an array in Flash of say 100 elements totally kills Flash.

I tried declaring the array with zero elements and then just dynamically adding them but that seriously impacted performance also.

The quickest I've found so far is to make sure I exclude all objects that don't need to be sorted, add the ones that do to an array then use Flashes in built sort to sort it using a comparison function.

I did find a really quick bucket sort, but the only problem with that is that it only works on numerical values as it puts them into buckets and you lose information. You just know you have 10 number 1s, 5 number 2s, and so on. It only really works for numerics...

Another guy suggested a linked list - does that sound like a good idea?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this