Isometric depth sorting

Last week I decided to use an isometric perspective for rendering. The previous flat 2D style of rendering the scene was very limiting. Beyond that, I quite enjoyed isometric games like the old Age of Empires, Stronghold or Diablo. It seemed like a good compromise between my lack of 3D modeling skills and having some sort of perspective. Plus, of course the geeky style of isometric tiles is quite charming!

1 The straight forward implementation

The first implementation was pretty straight forward. I defined my isometric space so that x flows in screen coordinates left to right and top to bottom, y goes right to left top to bottom, while z just defines the floating in height. For convenience I defined that 1 unit in either x, y or z will bring you to the next tile in the iso grid.

Since I was already using the great Starling Framework for the previous 2D renderer, I simply derived an IsoSprite from the Sprite class like so. All game units will then extend from this class.

public class IsoSprite extends Sprite
{
    public var isoX:Number;
    public var isoY:Number;
    public var isoZ:Number;
}

Yes, public member variables are evil :-?, but in this case they will make up for a great boost in speed later! Note that I’m using Number here instead of int, because I wanted the Creeps to move fluently between tiles later. But step by step!

For my defined iso space, the screen coordinates for each IsoSprite could be calculated by the following code:

private function projectSprite(sprite:IsoSprite):void
{
    sprite.x = (sprite.isoX - sprite.isoY) * _halfTileWidth;
    sprite.y = (sprite.isoX + sprite.isoY - sprite.isoZ) * _halfTileHeight;
}

Where x and y are the standard screen coordinates of the Starling Sprite. The tile width and height depend on the resolution of the used tileset.

Unsorted Iso tilesHowever, when drawing the scene now, it’s not really guaranteed that the sprites are not overlapping each other in a weird order like in the image. The problem here is that we are rendering the tiles in the wrong order. Although they look kind of 3d they are still flat images rendered on top of each other. For a correct output we need to use the painter’s algorithm, drawing the tiles from back to front.

Based on the isoX and isoY coordinates of the sprites, it’s not hard to calculate a depth value for each sprite and sort them by this depth before rendering the scene:

private function calculateDepth(sprite:IsoSprite):void
{
    sprite.isoDepth = sprite.isoX + sprite.isoY;
}

And then define this comparison method to pass to the sortChildren method of Starlings DisplayObjectContainer class:

private function sortByIsoDepth(a:IsoSprite, b:IsoSprite):int
{
   if (a.isoDepth > b.isoDepth)
   {
       return 1;
   }
   else if (a.isoDepth < b.isoDepth)
   {
       return -1;
   }
   return 0;
}

Static iso tilesVoilร  – There we have a nice static isometric scene. That was not too hard! So let’s start add some creeps. Still easy? Unfortunately this is where isometry started to become quite a buzzer for me ๐Ÿ™‚

If your game units are only allowed to “jump” from tile to tile, there is no problem with the sorting approach above. You would need to extend the iso depth calculation by z, so that you can specify that creeps should be rendered above ground tiles. Notice how in the example code below z is scaled down, so that is does not interfere too much with the x/y values.

private function calculateDepth(sprite:IsoSprite):void
{
    sprite.isoDepth = sprite.isoX + sprite.isoY + 0.001 * sprite.isoZ;
}

iso-tiles-creps

Notice the rendering glitches in the image! When creeps start moving between tiles the rendering all gets messed up. My first naive idea was that the sorting was “almost” right, so I’d just need to find out where sprites are misaligned and swap indices in the display list later on. I got it to work for just the creeps on their own, but as soon as you add flying projectiles I got lost with this approach. So I did some research on the internet and was shocked that there was so less information about this topic.

I found two basic approaches to the sorting problem:

  • Forget about correct sorting and utilize the depth buffer of the GPU
  • Do a topological sort on a graph, where the nodes are the sprites and the edges are an “is behind” relationship of the nodes.

I chose option 2 because my sprite textures are full of semi-transparency and the depth buffer can’t handle semi-transparency. At the start this option sounds horribly complex for such a simple task as isometric sorting. But luckily I found some great resources which explain the theory behind it quite well:

2 The topological sort implementation

First of all I needed to extend the IsoSprite class by some additional information. The topological sort needs to compare the 3d bounds of IsoSprites with each other in order build the dependency graph. For this I decided to use axis aligned bounding boxes (AABB) which are well known from 3d rendering. They are extremely fast to compare and to update unless you are not rotating the underlying 3d model. As this rotation will never happen in the iso use case, we’re all good to use them!

public class IsoSprite extends Sprite
{
    public var isoX:Number;
    public var isoY:Number;
    public var isoZ:Number;

    // AABB in iso world space
    public var minX:Number;
    public var maxX:Number;
    public var minY:Number;
    public var maxY:Number;
    public var minZ:Number;
    public var maxZ:Number;
    
    // AABB in iso model space		
    public var minXRelative:Number;
    public var maxXRelative:Number;
    public var minYRelative:Number;
    public var maxYRelative:Number;
    public var minZRelative:Number;
    public var maxZRelative:Number;

    // Internal variables for sorting in the renderer.
    internal var isoDepth:int;
    internal var isoSpritesBehind:Vector.<IsoSprite>;
    internal var isoVisitedFlag:int;
}

Now, on each frame the bounds of each sprite needs to be updated from model space to world space.

for (i = 0; i < isoSpritesLength; ++i)
{
    sprite = _isoSprites[i];
				
    // Project sprite to screen coordinates
    sprite.x = -_viewport.x + (sprite.isoX - sprite.isoY) * _halfTileWidth;
    sprite.y = -_viewport.y + (sprite.isoX + sprite.isoY - sprite.isoZ) * _halfTileHeight;
				
    // Update bounds
    sprite.minX = sprite.isoX + sprite.minXRelative;
    sprite.maxX = sprite.isoX + sprite.maxXRelative;
    sprite.minY = sprite.isoY + sprite.minYRelative;
    sprite.maxY = sprite.isoY + sprite.maxYRelative;
    sprite.minZ = sprite.isoZ + sprite.minZRelative;
    sprite.maxZ = sprite.isoZ + sprite.maxZRelative;
}

In the next step, the dependencies between the iso sprites are determined. Currently all sprites needs to be compared to each other, which leads to a complexity of O(n^2). So for 100 sprites, 10.000 comparisons are necessary. This is where the public member variables of the sprite class become absolutely necessary for the fastest acceess possible. Also, I am re-using the behind vector and avoid function calls like push! If you are resetting the length for the behind vector to 0 and then pushing sprites on it every every frame, you get a LOT of unneccessary memory allocations in the inner loop and that will drain your framerate, especially on mobile!

// Determine dependencies for the topological graph sort
var a:IsoSprite;
var b:IsoSprite;
var i:int;
var j:int;
var behindIndex:int;
const isoSpritesLength:int = _isoSprites.length;
for (i = 0; i < isoSpritesLength; ++i)
{
    a = _isoSprites[i];
    behindIndex = 0;
				
    for (j = 0; j < isoSpritesLength; ++j)
    {
        if (i != j)
        {
            b = _isoSprites[j];
						
            if (b.minX < a.maxX && b.minY < a.maxY && b.minZ < a.maxZ)
            {
                a.isoSpritesBehind[behindIndex++] = b;
            }
        }
    }
				
    a.isoVisitedFlag = 0;
}

That was already the most expensive step in the whole process. Of course you should only process the sprites that are currently visible in the viewport, so some viewport culling should take place before. I haven’t implemented this yet, so I might add another blogpost about it, when it is done. If you have a better solution for the dependency graph creation, that processes faster then O(n^2), it would be really nice if you could drop me a short comment about it!

In the next step we do the real topological sort on the graph we just created!

// Do a topological sort on the dependency graph.
_sortDepth = 0;
for (i = 0; i < isoSpritesLength; ++i)
{
    visitNode(_isoSprites[i]);
}

Where visitNode is the following method:

private function visitNode(n:IsoSprite):void
{
    if (n.isoVisitedFlag == 0)
    {
        n.isoVisitedFlag = 1;
				
        const spritesBehindLength:int = n.isoSpritesBehind.length;
        for (var i:int = 0; i < spritesBehindLength; ++i)
        {
            if (n.isoSpritesBehind[i] == null)
            {
                break;
            }
            else
            {
                visitNode(n.isoSpritesBehind[i]);
                n.isoSpritesBehind[i] = null;
            }
        }
				
        n.isoDepth = _sortDepth++;
    }
}

That’s it basically! We now have a topological order of the nodes in our graph, specified by the “isoDepth” integer value! The only thing that is left to do is to sort the display list. This is done the same way as in the first implementation, by the sortChildren method of Starlings DisplayObjectContainer class:

// Sort
sortChildren(sortByIsoDepth);

iso-tiles-topo-sorted

And here we go. Now creeps, towers and projectiles are sorted in a nice and stable way, without rendering glitches! And on iOS the App is still running with 60fps!

Thanks for reading so far. Please drop me a note if you have improvements, suggestions or questions about the isometric depth sort!

41 thoughts on “Isometric depth sorting

      1. Zyblade

        Hey Andy,

        I’ve got a couple of questions related to isometric sorting and would be happy to email with you.
        I already tryin’ to setup a good isometric sorting algo for month’s and longer :S.

        Thanks in advance ๐Ÿ™‚

        Rob

        Reply
    1. parser

      to optimize determining dependencies you need sort object before on some axis (where most objects preferably) and than sort until you max x value is less than next object min value

      Reply
  1. Murdoch

    Awesome, thanks for this. Do you know the limitations of this approach? How many IsoSprites can be on screen at once until it slows down?

    Reply
    1. Andy Post author

      Hi Murdoch, thanks for the heads up! I think it really depends on your use case. Currently I am profiling on an iPhone 5 with about 100 to 200 Iso Sprites (depending how many creeps are running around at once), and there according to Adobe Scout 1 to 5 milliseconds are spent for the isometric sorting. So I’m still at 60fps here. But with sorting runtime of O(n^2) it probably gets worse very fast if you add more and more sprites.

      Another bottleneck I noted about sorting, was that (at least in starling) you could run into a lot of GPU draw call state changes if you use different blend modes for iso sprites, because due to the sorting, sprites with the same blend mode can’t be drawed after each other anymore. Last week I got a huge performance increase due to changing the iso blood particles back to child sprites of the dead creeps ๐Ÿ™‚

      Also, adding viewport culling to the renderer was a big performance gain as well!

      Reply
  2. Pingback: Dev Diary #17 – Chasing Zombies | Arctic Empire Dev Diary

  3. GameDev

    Very good post!

    I have thought similar idea.
    But only I have considered a x-y plane.
    When I saw your blog, this idea is became perfectly.

    Thank you for sharing. ^^

    Reply
  4. Dani

    Thanks a lot for sharing this!!!.

    After a week of trying to figure this out on my own with different approaches and many, many failures (and near misses too) I finally finished a c++ implementation based on your code. There’s some things to polish and somethings I’d like to try to speed up the process but so far I am getting good results with fixed size tiles and game actors smaller than those. Very much appreciated.

    Reply
  5. Lukasz

    I think there is no need to compare all entries to all entries. To do it you would need a correct data structure, that works somewhat like a binary tree. What I actually have in mind, is that if I was to do it for example in Java, I would put the entities in a TreeMap. provided an appropriate Comparator object (see the docs).

    It would work by clearing the map entirely at the start of rendering call and fill it with entities that fall into the rendering viewport. The map sorts itself automatically, so the next with to do would be to just render each entity from that map linearly.

    Reply
  6. TheRod

    Hi! Thanks for sharing your solutions! I’m looking for this but for cocos2dx, does anybody tried this on cocos?

    Reply
    1. Carlos Lopez

      Hi,
      After 2 (hard) months of analisys of 2.5D tile order rendering I finally determinated the correct algorithm.
      I am using it actually in a cocos2d-js tile-based game.
      Algorithm cosists in determinating and mapping “tiles back, behind and front each tile”. Once that mapping you must follow a simple “recursive” function for drawing them.

      Regards

      Reply
  7. Demi

    “which leads to a complexity of O(n^2). So for 100 sprites, 10.000 comparisons are necessary. ”

    what about spatial partitioning and only update segments that actually changed?

    Reply
  8. Stephen Hamilton

    Really interesting solution which might answer a problem I posted on StackOverflow a while ago:

    http://gamedev.stackexchange.com/questions/49226/3d-isometric-depth-sorting

    Although, I couldn’t understand where the following variables come from:

    minXRelative
    maxXRelative
    minYRelative
    maxYRelative
    minZRelative
    maxZRelative

    Do I have to statically determine these values for each object? Or can I deduce these values from the physical width/height of the sprite?

    Also, in the following code, is this meant to use the isometric point (isoX) or an absolute pixel value?

    sprite.minX = sprite.isoX + sprite.minXRelative;

    Please email me for more info

    Reply
    1. Andy Post author

      Hi thanks for the follow up.

      The min/max relative coordinates describe an axis aligned bounding box (AABB) in isometric space. So for instance if an isometric object like a character would be 0,5×0,25 iso blocks wide and 1 iso block high you need to set those values accordingly so that the sort engine can place this character correctly in the world.

      And yes you are right, the code you mentioned is in isometric space, not screen space.

      Cheers!

      Reply
      1. Art

        Hi Andy, thank you for your post!

        I’ve been stuck on depth sorting for days, but still can’t figure out how to calculate aabb to get those variables for my sprites –

        minXRelative
        maxXRelative
        minYRelative
        maxYRelative
        minZRelative
        maxZRelative

        Can you provide an examples how you did it?

        Like, for example, we have isometric tiles 64×32 and creeps 30×20 and their screen coordinates x and y. How do we translate them into min max xyz?

        Thanks

        Reply
        1. Andy Post author

          The aabb is usually calculated in model space. Think of it as your model is the center of the universe in this space. So (0, 0, 0) in this space is the pivot point of your model.

          Now it depends on where this pivot point is located, but let’s assume it is in the center of the model. For a 64×32 tile the aabb would calculate the following way:

          minXRelative = -32
          maxXRelative = 32
          minYRelative = -16
          maxYRelative = 16
          minZRelative = 0
          maxZRelative = 0

          Z assumes this tile has no height.

          Reply
          1. Vincent

            Hey great tutorial! I was a bit confused about the relative min/max as well but this cleared it up. Just a couple questions though, is it ok to set min and max z to 0 for a sprite or do I need to change it depending on the height of the sprite? Also when you say isoX and Y do you mean tile coordinates (what tile the sprite is on) or just plain isometric coordinates?

  9. Andrew

    Thanks for sharing, Andy!

    I’ve gone ahead and implemented your solution in C++ as a RenderGraph class found here (RenderGraph.hpp / RenderGraph.cpp ).

    Entity::GetMinMax() just returns a struct with two 3D vectors, `min` and `max`.

    Usage is as follows:
    std::vector renderQueue;
    RenderGraph renderGraph;

    renderGraph.SetEntities( entities_ ); // tells the render graph which entities to sort
    renderGraph.CalculateDependencies();
    renderGraph.Sort( renderQueue ); // pushes the entities from each node into `renderQueue`

    for ( unsigned int i = 0; i < renderQueue.size(); ++i ) {
    // Render( renderQueue[ i ] );
    };

    Hope this is of some help to others!

    Reply
    1. Andrew

      Just a quick edit, I’ve added in a visited flag to the RenderGraph::Node struct to prevent any stack overflows, I thought the isoDepth < 0 check would have been enough but if two entities are dependent on each other it would cause an overflow.

      New source can be found here:
      renderGraph.hpp
      renderGraph.cpp

      Reply
  10. Pingback: How do I use tiles and sprites together in an isometric scene? | Question and Answer

  11. Danny

    Hi, great tutorial, it really helped me understand some issues with depth sorting.
    I do not seem to understand how are we adding the sprites or changing the sprite index from the display list after the sorting. Will this be done in a loop after sortChildren(sortByIsoDepth)?
    Please email me if possible, I will really appreciate it.

    Reply
    1. Andy Post author

      Hi Danny,

      I’m glad the tutorial helped you!

      Yes I’m sorting the iso sprites attached to my iso renderer by a call to sortChildren. This function is provided by the starling framework’s DisplayObjectContainer:
      public function sortChildren(compareFunction:Function):void

      As parameter it takes a compareFunction, which – in my case – is sortByIsoDepth. It uses the previously computed depth. Here is the function for completeness:

      private function sortByIsoDepth(a:IsoSprite, b:IsoSprite):int
      {
      if (a.isoDepth > b.isoDepth)
      {
      return 1;
      }
      else if (a.isoDepth < b.isoDepth) { return -1; } return 0; }

      Reply
  12. Lummox JR

    I’ve been tinkering with isometric sort models on and off for some time. In the model I’ve been working with, Z position isn’t really a thing (though it probably should be), and I realized some time ago I’ll never have a perfect solution without topological sorting. The O(N^2) complexity is a problem though.

    Not too long ago I had an epiphany: The sort can be broken up into stages, calving away huge chunks of the map where there are no creeps by finding natural split lines. Divide-and-conquer should, in general cases, reduce any topological sorts to much smaller blocks. As I understand your coordinate system, lower y values are further back for the same x, and vice-versa. This is how the natural split optimization would look:

    Step 1: Sort the array of objects by minX, then by minY. Set P=item[0].maxX, and then traverse the array starting at index 1. If item[index].minX = P, then every item from 0 to index-1 is behind eery item from index onward. Recurse for those items (if more than 1 of them), starting on step 2. Then set a new P=item[index].maxX and continue.

    Step 2: Same as step 1, but switch X and Y. If recursing, start on step 1. When finished with this step, jump to step 1 if we didn’t start on that step, or if any splits were found on this step.

    Step 3: At this point a much smaller number of tiles can be sorted topologically. The topological sort can be done from the front and the back simultaneously, reducing the concern of cycles in the graph.

    The choice of sort algorithm may matter a lot. With Timsort for instance, which loves partially-sorted data, when you alternate between step 1 and step 2 the array may well be in an ideal state already. For instance, if the leftmost column can be split off, and it contains no creeps, all the minX and maxX values will match and it will already be sorted by minY. Therefore large sections with nothing but well-behaved tiles and no creeps are dealt with quickly.

    Pathological cases may be harder to crack and would want more advanced tools, like splitting along jagged lines, or checking to see if a creep straddling a line that might otherwise split can be kept with the near group instead.

    Reply
  13. bunny

    You are doing one thing – very wrong. You are polluting objects with fields that are used in sorting algorithm. This could have been avoided . For example you keep an array “isoSpritesBehind” in your IsoSprite class and you write this vector on each sorting iteration. This could cause a lot of garbage memory, when some sprites get out of screen, when they’re not sorted and dont use this field. I guess the solution would be to keep the elements in some kind of Map that maps from an IsoSprite to List of IsoSprites.

    Reply
    1. Andy Post author

      Well, the same amount of object references would then be stored in that map. Except that you have to do one extra map lookup, when you already have the iso sprite you’re interested in. Maybe I miss something here, but I don’t see any benefit in using a map.

      Reply
  14. Iman

    This algorithm just work for static sprites than donโ€™t move. if they do, then all the sprites have to be one by one tile and not bigger since the zbuffering will results wrong.
    Why didnโ€™t you set zPosition = Xtile+YTile and let the SpriteKit handle the rest? to just need to set zPosition and it will care about the rest.
    Maybe I have got the purpose of writing this aricle the wrong way.

    However my problem is that I have some sprite bigger than one by one (mostly two by two) and I have to correct the zPositions set by xtile+ytile when a one by one character is going to move throgh the big sprites at behind tiles that are zdepthed higher than they deserve because I had to assign a zPosition for a Sprite and it will be worked for all of its tiles.
    Regards,
    Iman

    Reply
  15. Lukasz

    After some work done on the issue – looking for a way to render isometric scene – I’ve found out that this is perhaps the best solution as – as you’ve said it keeps the alpha intact without glitching in comparison to rendering on the GPU and using depth buffer.

    What I’ve found though was the poor performance – as this algorithm in its pure form is O(n^2) made impossible to build something real. So I’ve researched on the topic and found out that using spatial indexing solves a big part of the issue. What I did was dividing the screen into a grid of cells and putting all the sprites into the cells which they belong. For that I used screen-projected bounds of each sprite (a rectangle) and compared it with the grid’s cells. If the cell (also a ractangle) intersected with these bounds – then I’ve put it in that cell. This resulted in a situation where I needed only to evaluate order per cell basis. As you may guess – amount of sprites per cell is much less than per whole screen (this actually depends on the resolution of the screen grid).
    So, as I needed to compare only sprites that fell into a cell – the performance grown 15 times. I can easily sort about 700 sprites in 8 miliseconds on my 8 years old Core2 DUO E8200 CPU.

    Take a look at the screenshot to see what I mean:
    http://imgur.com/hfvvMBU (dont bother the framerate on the screen – it’s limited intentionally)

    Another thing I did was moving the sorting to a different thread. Soriting doesn’t actually need to be performed each frame. I quess, that even if you do it once 100 miliseconds – it will be almost unrecognizable. So the sorting sits on it’s own thread and the main thread only asks it about if it has completed the sorting while rendering what it has from previous sort.

    If you are curious about the code (in Java) take a look at this github pages:
    https://github.com/lukasz1985/IsometricEngine/blob/master/src/game/screen/Viewport.java
    https://github.com/lukasz1985/IsometricEngine/blob/master/src/game/screen/Grid.java
    … and off course the whole repository if you want to get a better point of view.

    Also a thing to consider – as somebody mentioned – you are polluting the instances of your IsoSprite instances with the references to the sprites that are behind them. This isn’t so bad in your case, where you have only a few sprites on the scene, but doing this on a large scale scenes could eat some more memory if you didn’t take care for zeroing/nulling those references. This is also addressed in my code.

    Reply
    1. Ryan

      Thanks for the great idea.

      If you have all your sprites in a quad tree structure which is useful for viewport culling anyways then you could probably build the graph by take chunks of sprites by diving the view port into regions. It’s like the method you mentioned but works with an existing data type you probably need anyways if your game world is larger than 1 screen.

      I haven’t tried this yet but it sounds like it should work given you don’t process duplicate sprites that overlap multiple regions.

      Reply
    2. Zyblade

      @Lukasz
      Hey, would you mind, sending me your java example? The links seem to be expired :/

      Thanks a bunch =)

      Reply
  16. Ryan

    This line doesn’t make sense. If all the tiles are on the ground level (like in your screen shots) they should all have min/max z values of 0 and therefore the condition will never be met. Does your z coord not mean vertical level? In my code tiles can be on top of each other and that vertical level is “z”, which is pretty typical I thought.

    What am I missing?

    if (b.minX < a.maxX && b.minY < a.maxY && b.minZ < a.maxZ)
    {
    a.isoSpritesBehind[behindIndex++] = b;
    }

    Reply
    1. Krumelur

      My understanding: minZ and maxZ are representing the actual height of the tile (or better: of the texture) relative to the tile height. So a solid cube would occupy 100% x 100% x 100% (x, y, z) of a tile.

      Reply
  17. Krumelur

    Your array “isoSprites”: does that include everything (tiles + creeps), or just creeps?
    I was wondering if it is enough to compare each creep against each tile instead of everything against each other, because the tiles are already painted correctly because of the painters algorithm.

    Reply

Leave a Reply

Your email address will not be published.