Working on making isometric depth sorting fast and faster

Posted on December 26, 2009. Filed under: Uncategorized |

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.

Advertisements

Make a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

3 Responses to “Working on making isometric depth sorting fast and faster”

RSS Feed for Blazing Bytes Comments RSS Feed

Hi i use the ationscript for Multiplayer Games and VirtualWorlds to sorting the objets. it’s not really fast like you side. and then i thing maybe can use as3 ‘s own sorting function to do it. but still not right. is this possible you share some information with me? it should be really really helpful for me. thanks a lot.
my E-mail is : iamzealotwang@126.com

Are you ready to share the algo? I’d be keen to see it! I’m writing some 3d stuff for my website that could benefit from a tight depth sorting implementation for AS3. Also, what game are you talking about, and where can I see it in action?

Hey Tunied, Ivan,

The game I worked on is TinyTown. You can check it out here http://www.domisuto.com http://apps.facebook.com/tinytowngame The greater the population in your town, the more Tinys start appearing on the roads. The engine can sort lots of tiny objects quickly, and in this version performs “automatic rotation” for ease of use, so you can rotate the city and not affect the backend.

Unfortunately, I can’t share the details. My company, Domisuto LLC, is going through reorganization, and I’m not sure what is going to happen. There’s talk about selling “affordable” licenses to the engine, and we’re in talks with a sponsor to take over our game. I’ve also been thinking about the pros and cons of open sourcing the engine. And I haven’t figured out what’s the best route to take.


Where's The Comment Form?

Liked it here?
Why not try sites on the blogroll...

%d bloggers like this: