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?

From game development AttackingHobo

• 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.

  bummzack : 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)

  Ipsquiggle : Aah, thanks. :) It was from memory, so a catch like that is appreciated.
  From Ipsquiggle

• 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.

  From Iain

• 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)

  Iain : 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

  Kaj : 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.

  Ipsquiggle : 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.

  Kaj : 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.
  From Kaj

• 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.

  AttackingHobo : 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.

  munificent : 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.
  From munificent