Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
6  
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
add comment

6 Answers

up vote 10 down vote accepted

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)
        buckets[distance].add(entity)
    end

    // flatten
    result = new Array
    for bucket in buckets
        for entity in bucket
            result.add(entity)
        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.

share|improve this answer
1  
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
add comment

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 );
      bAdded = true;
      break;
   }
}
if ( !bAdded ) _aSortableItems.push( objNewItem );
share|improve this answer
1  
-1 for a link with no additional information. –  AttackingHobo Jul 5 '11 at 2:14
    
@AttackingHobo You may have noticed that Ollie is new here, isn't downvoting kind of a harsh treatment? Even so, editing his post might be appropriate to enhance this Q&A. –  Nick Weaver Feb 21 '12 at 14:15
    
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  Jonathan Hobbs Aug 22 '12 at 7:16
add comment

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.

share|improve this answer
add comment
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.

share|improve this answer
add comment

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)

share|improve this answer
    
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
add comment

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.