Working on making isometric depth sorting fast and faster

I’ve been working on an isometric game with my startup for the past couple of months. And we’re just about to release it to the public. Amongst other duties, I’m currently in charge of the iso engine making it work right (sorting) and run fast (sorting and rendering).

My initial attempts at depth sorting followed the steps of others. I tried to do some calculation to determine a depth ordering based on position and size of the iso object. It wasn’t till recently did I realize this only works on square objects because it can use a center point method.

Unfortunately, our game has rectangular objects. So I was searching around and came across a lot of different methods all of which were wrong in one way or another. Read some suggestions on sorting by unit tiles or splitting up art assets. All of which are too limiting as we had already committed to rectangle objects and had some assets. Finally, I got Jobe Makar’s Actionscript for Multiplayer Games and VirtualWorlds and studied his algorithm for sorting of objects. It’s correct and works great, but it runs very slowly and relies on flash’s display renderer for sorting. In book form, it’s way too slow.

Finally, taking some ideas from different places I created an algorithm that sorts iso objects by comparing them to each other giving an answer of front, back, or side. Then I manage the sorting on my own. With this approach we’re able to sort 200+ objects on the screen every frame. This is good enough for the majority of isometric games you see on facebook. Turns out the Maxhaus project had this algorithm done years ago and Zeh gives a good explanation of it here: http://www.stimuli.com.br/works/maxhaus/ The algorithm looks correct and runs decently but it’s an O(n^2) algorithm. We weren’t be able to achieve lots of tiny objects with this algorithm, but we designed around the issue.

With this algorithm in place I could put sorting to rest and move on. I wasn’t really happy with it, but it was good enough. So I’d continue thinking about the issue a couple hours every weekend. And then one night I had a dream about iso sorting. Over the next couple of weeks I discussed with colleagues to make sure I wasn’t delusional. Now we have a prototype of a much faster sorting algorithm waiting to be integrated into the game. It’s going to enable more objects on the screen and faster rendering times, and a more engaging world for the players. I’ll eventually share the algorithm, but for now it’s a significant competitive advantage for my small company. We have other players in our space with access to significantly more resources, and this is one of our best features so sharing will have to wait till we can turn the game into a success.

The real take away lesson for me was to not give up on the problem. I had a hunch that things could be better and I kept on working at the issue from all kinds of angles and breaking it down step by step.