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.
However, 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;
}
Voilà - 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;
}
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.;
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);
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!
However, 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:
Voilà - 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.
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:
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!
