Category Archives: Rendering

Getting new creeps into the game

Yesterday I added new creeps to Mazebert TD: Rats!

As I do not have the 3D skills to create, animate and render 3D models myself, I am using existing resources from the internet. My one and only source by now is the isometric sprites section of Reiner’s Tilesets. For each character, various animations like walking, running, fighting, tipping over, etc. are available. Also each animation is rendered in 8 isometric directions! Reiner, thank you so much for sharing your great work! Without your site, there would be no creeps to kill in Mazebert TD. Well, there might be creeps, but killing them would really be a lot of less fun.

Been Hit NE 0000

After downloading the ZIP file from Reiner’s website, I end up with a lot of images like the one shown above. First thing I do is to remove the animation sequences I don’t need. Right now I only use three animations: Running, Stunned, Dying. In the next step I remove all rendered directions I do not need. Currently creeps can only move diagonal, so I end up with: North-east, North-west, South-east, South-west.

Now it’s time to prepare the remaining sprites. The desired information for my isometric rendering engine is:

  • A diffuse light pass
  • A shadow pass

For that, I wrote a little batch script, that extracts this information from the remaining bitmaps. It uses the mogrify command from the great image processing library Image Magick.

@echo off
echo Preparing sprites.

echo Diffuse aspect...
rd diffuse /s /q
mkdir diffuse
mogrify 
  -path diffuse 
  -transparent "#5e4229" 
  -transparent "#0c0905" 
  -format png *.bmp

echo Shadow aspect...
rd shadow /s /q
mkdir shadow
mogrify 
  -path shadow 
  +transparent "#0c0905" 
  -channel RGB 
  -evaluate set 0 +channel -channel A -blur 2x2 
  -evaluate multiply 0.5 +channel 
  -format png *.bmp

cd shadow
for %%j in (*) do (
rename "%%j" "shadow_%%j"
)

echo Done.
pause

The first mogrify statement in the script extracts the diffuse information from the images. The brown background color is turned transparent as well as the color of the casted shadow on the ground (in this example #5e4229 and #0c0905).
In the second mogrify statement the shadow color is extracted from the input images, the rest is turned transparent. Plus, a little blur is applied to the shadow so that the resulting shadows in the game are not that hard.

With the help of Texture Packer I bundled the output of the script in two texture atlases. I can really, really recommand Texture Packer if you are creating sprite based games. It costs just a few bucks and it works very, very well and saves you lots of troubles holding your assets together. Plus, it works out of the box with Starling.

Diffuse texture atlas

Diffuse texture atlas

Shadow texture atlas.

Shadow texture atlas.

After Postprocessing the diffuse part.

After postprocessing.

For the diffuse part I used the cool “inner padding” feature of Texture Packer, so that a few pixels are added to the sprite region of each diffuse creep image. In a little postprocessing step I add an comic-like outline stroke and some light overlay to the images. With the stroke each image gets a few pixels bigger, but that’s okay as we added those pixels up front with the inner padding!

And there are rats :-)

And there are rats 🙂

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!