Most efficient 3d depth sorting for isometric 3d in AS3?

I am not using the built in 3d MovieClips, and I am storing the 3d location my way.

I have read a few different articles on sorting depths, but most of them seem in efficient.

I had a really efficient way to do it in AS2, but it was really hacky, and I am guessing there are more efficient ways that do not rely on possibly unreliable hacks.

What is the most efficient way to sort display depths using AS3 with Z depths I already have?

-
Have you tested using these 'inefficient' methods and seeing if they are, in fact, a bottleneck? If they work, run with them, and change things later if you really need to optimize. – Ipsquiggle Sep 1 '10 at 21:09
Its not so much straight up inefficient, its that most of the ones I have seen are naive. – AttackingHobo Jul 5 '11 at 2:13

If you're talking a tile-based isometric game, you have a fixed number of different depths that are bounded between some known nearest and farthest depth. In that case, it's a perfect candidate for a pigeonhole sort, which has the best possible algorithmic complexity.

Just make an array where each index corresponds to a depth, and each element is a collection of entities at that depth. Sorting is just (in pseudo-code):

``````sort(entities)
buckets = new Array(MaxDistance)

for index in buckets
buckets[index] = new Array
end

// distribute to buckets
for entity in entities
distance = calculateDistance(entity)
end

// flatten
result = new Array
for bucket in buckets
for entity in bucket
end
end
end
``````

And that's from a completely unsorted collection. An even better option is to simply persist the buckets and keep the entity's bucket location updated when its depth changes.

-
Thank you! All the other examples sorted everything all the time. I never knew about bucket sort. And it seems with this I can have buckets of presorted objects that do not need to be sorted each tick. – AttackingHobo Sep 4 '10 at 0:57
Exactly right. Just keep your bucket collection around. Whenever a entity moves, have it update its position and the bucket storing it. Then you don't need to doing any sorting at all. – munificent Sep 8 '10 at 0:35
``````private function positionOrthographic():void
{
for each (var entity:Entity in entities)
{
entity.spriteView.x = entity.body.position.x;
entity.spriteView.y = entity.body.position.y + entity.body.positionZ;

var sortedEntities:Array = entities.concat();
sortedEntities.sort(sortDepths, Array.DESCENDING | Array.NUMERIC);

var numEntities:int = entities.length;

for (var i:int = 0; i < numEntities; i++)
{
world.setChildIndex(sortedEntities[i].spriteView, i);
}

}

private function sortDepths(entity1:Entity, entity2:Entity):int
{
if (entity1.layer < entity2.layer) return 1;
if (entity1.layer > entity2.layer) return -1;
if (entity1.body.position.y > entity2.body.position.y)return -1;
if (entity1.body.position.y < entity2.body.position.y)return 1;
return 0;
}
``````

Important to note I'm using the y axis as depth into the scene here (would normally be Z). This is so I can share code between top-down and side-on games. Splits sorting into a separate function. No idea how efficient it is, other than I've never noticed any slowdown from using it. Supports layers, so e.g. HUD and floating text things can always appear on top, backgrounds always below, etc.

-

Since in most isometric games most of the stuff is static it doesn't really matter how inefficient it is (within reason of course), as there's only a few objects you need to insert in the right place into an array that can be presorted already. If you are resorting everything everytime you draw, it would, but it means your algorithm is wrong to begin with.
Rule #1 in optimization: try if there's a more efficient solution on the macro level, before you optimize the micro level. (well, okay that's #2, #1 would be don't optimize before it's a measured bottleneck)

-
you have to sort every frame. The only alternative is to sort everytime something moves, which will actually mean more sorts if you have any significant number of objects – Iain Sep 3 '10 at 9:17
Nope. You have to have a sorted list at the end of each frame to hand to the renderere, there's a subtle difference. Sorting for every moving object would indeed be silly. But you know the order of static objects never changes, so resorting those would be a waste of time. If you have a presorted list of static objects and a list of dynamic objects the sorting only consists of finding the right insertion spot for the dynamic objects, which can be (depending on the number of dynamic objects vs the number of static ones) significantly cheaper. – Kaj Sep 3 '10 at 14:15
I believe the default sort for Flash is insert-sort, which is extremely efficient on a mostly-sorted array. In any case, I've previously worked with an array with 10,000 elements, sorted every frame, and it was definitely not a bottleneck. – Ipsquiggle Sep 3 '10 at 16:03
Which is what rule #1 refers to, optimization should only happen once it's needed. I only said that you shouldn't sort what you don't have to sort if you want to speed it up. A native sort routine is likely faster than any implementation in AS would be unless it's a HUGE array with very little objects that are moving. – Kaj Sep 3 '10 at 17:13

I don't know about efficiency, but this is the method I've been using for a long time:

Pretty simple method: Just add the screen-Y and the Z to get a 'distance', and then keep them in a list sorted by this property.

``````// In the 'update' of each entity
entity.distance = entity.y + entity.z;
``````

Then use:

``````allEntities:Array;
// ...

allEntities.sortOn("distance", Array.NUMERIC);
``````

Finally, rather than using Flash's rendering, I always blit things myself when I'm very concerned about depth sorting:

``````canvas:BitmapData = new BitmapData(stage.stageWidth, stage.stageHeight);
for each (var e:Entity in allEntities) {
// draw each entity in sorted order
canvas.draw(e, e.transform.matrix);
}
``````

Caveat: This opens up the can of worms which is doing your own blitting. But as I mentioned, I've always found it a road worth going down when trying to deal with depths in a precise way.

-
If you're using that technique, you should really sort using allEntities.sortOn("distance", Array.NUMERIC). Otherwise the sorting will be string based (eg. 100 < 9) – bummzack Sep 2 '10 at 5:38
Aah, thanks. :) It was from memory, so a catch like that is appreciated. – Ipsquiggle Sep 2 '10 at 17:01

I think Ollie's post is helpful however you do need to see the code in context (which he provides). I too went down this road once before for the as3isolib.v1, however I finally gave up and opted for the naive sort. It's a performance hog.

If you are blitting, (which the as3isolib.v2 is) you can do quite a bit more in terms of splitting your objects up into more easily sortable pieces, reducing the multi-dimensional sorting path. as3isolib.v2 currently reduces all sortable items in a simple linear sort.

-

You can check this blog post for a good solution for isometric z-sorting in AS3. It is derived from an approach exposed by Jobe Makar in his book ‘ActionScript for Multiplayer Games and Virtual Worlds’.

Here's the core sorting routine:

``````// Sort by cell index
_aSortableItems.sort( sortByPos );
private function sortByPos( a:SortableItem, b:SortableItem ):int {
if ( (a.uiRow * INC.WORLD_COLS + a.uiCol) < (b.uiRow * INC.WORLD_COLS + b.uiCol) ) {
return( 1 );
}
else return( -1 );
}

// Sort by row and column
for ( var i:uint = 0; i < _aSortableItems.length; i++ ) {
objItem = _aSortableItems[i];
if ( (objNewItem.uiCol <= objItem.uiEndCol) && (objNewItem.uiRow <= objItem.uiEndRow) ) {
_aSortableItems.splice( i, 0, objNewItem );