# 3D isometric depth sorting

How is it possible to depth sort tiles and objects in an isometric environments without any limitations? I've been researching this for a while now and there seems to be no publicly available answers to this question.

There are two obvious options for depth-sorting when doing isometric environments:

1. Draw all tiles from screen top to screen bottom, followed by all objects from screen top to screen bottom
2. Draw each tile and then each object on that tile from screen top to screen bottom

The limitations with number 1 is that tiles cant have different heights because objects will always appear on top of the tiles. Screenshot example:

The limitations with number 2 is that objects can't move between tiles on the x-axis without the tile below overlapping it (because it's drawn later). I've grabbed a screenshot to exemplify this:

I've read lots on bubble sorting and other algorithms, but none of them seem to take this into account, or if they do, they don't document how.

(Please not before answering, this is NOT about how to sort objects that are larger than 1 tile, I'm more than happy with slicing them up so they fit into a tile)

-
The reason no algorithm seems to handle what you are looking for is because there is no such algorithm. It's not possible to Z-sort tiles in the generic case. Even in a situation where there is a solution, it may be hard to find it (look for "topological sort"). The obvious option is to use a Z-buffer. – sam hocevar Feb 12 '13 at 17:57
Thanks for the advice Sam, can you elaborate on how a Z-buffer would differ (and not come up with the same problems) from what I've written above? – totov Feb 13 '13 at 9:14
Doesn't the #2 issue go away if you use the 'lowest' corner as the point to consider the containing tile? – Jeff Gates Feb 13 '13 at 11:52
@LaurentCouvidou Those are examples of basic isometric ordering, that's not what I'm looking for, they are only sorting in a 2D environment, this question is about when tiles and objects can have differing heights (3D!) and still be drawn correctly. – totov Feb 13 '13 at 14:44
I agree with Sam, I don't think there is a general way to solve this in 2D. Any game that needs this kind of thing that I know of is 3D. – Tetrad Feb 13 '13 at 16:37

You can do it with a topological sort (usually) but even with just straight rectangular prisms you can still get cycles, so you have to watch out for that. But you may well be able to avoid that in your level design.

Here's a great introduction (since the article has moved once, this is the code on github, which should hopefully always have a current link to the article):

https://github.com/shaunlebron/IsometricBlocks

http://en.wikipedia.org/wiki/Topological_sorting has two algorithms for doing a topological sort: I've used the depth-first one and just broken cycles by choosing the first one I encountered to be in front. So it won't crash or fail to complete if you have cycles, it will just look wonky. And you can easily report them if you're writing a map editor.

-

totov, split scene on layers (sort scene by layers) and draw it layer by layer.

For example:

• layer 1: tiles
• layer 2: object, that lays over tiles layer
• layer 3: objects, that lays over objects on layer 2
• ...
• ...

then count layers, and for each:

• draw tiles (top to bottom)
• draw objects, marked as layer 2 (top to bottom)
• draw objects, marked as layer 3 (top to bottom)
• ...
-
what about an object in the center of the map but on the height -1, when you draw the next layer, the tiles will draw over the top of the object (if it is big enough to overlap the tiles height) even if they are positioned behind it – totov Feb 13 '13 at 9:25
split object sprite on layers too =). if object positioned on z = -1, and it's height is 3 (for examp), then you must split it's sprite on 3 pieces: lowest will be rendered with (layer = -1), next with (layer = 0), and "highest" with (layer = 1). to do this, you must register that object for rendering on layers -1..2, and draw proper part of sprite on each layer – ankhzet Feb 13 '13 at 20:03
Isn't this dependant on the height of each layer always being the same? Do you have a working example? @ankhzet – totov Feb 13 '13 at 20:13
yes, the height of layer is fixed value, which is the same for each layer. each layer covers the horisontal splice of "space" on map, and layers are rendered down to up to ensure, that everything on higher layers will always be drawn over everything on lower layers. this is the way it was implemented in RTS "Stronghold", i think – ankhzet Feb 13 '13 at 23:30
what happens when an objects is transitioning between 2 layers? then the parts that were supplied to the engine sliced up would be sliced in the wrong places? – totov Feb 14 '13 at 16:46