# Drawing order of 2D tiles with 3D bounding volume

I'm wondering which algorithm was used to draw the sprites of the video game Commandos in the correct order. Each sprite has a 3D bounding volume (either a polygon or a cylinder), this is how the developers stored the information:

POLY "NONAME",73,987,0,54,7,1   ;Name,CenterX,CenterY,CenterZ,Height,#Vertices,#Tiles
POINT        0,-37              ;Coord. X, Coord. Y
POINT        36,-18
POINT        36,-1
POINT        28,28
POINT        -21,37
POINT        -36,1
POINT        -36,-9
TILE          37, 581,  74,  83,   0,   0, 0,"ROC10010.RLE","   "   ;PosX,PosY,Width,Height

POLY "NONAME",70,816,0,120,4,1
POINT        0,-8
POINT        8,6
POINT        0,10
POINT        -8,-3
TILE          48, 434,  50,  98,   0,  41, 0,"POST0001.RLE","   "

POLY "NONAME",1557,4094,0,44,0,1
RADIO       17
TILE        1539,2588,  37,  55,   7,   0, 0,"DEPT0000.RLE","   "

POLYRAMPA "NONAME",626,952,0,48,40,4,1  ;Name,CenterX,CenterY,CenterZ,Height,HeightOff,#Vertices,#Tiles
POINT       43,-8
POINT       2,29
POINT        -36,-7
POINT       1,-45
TILE         590, 515,  85, 111,   0,   0, 0,"CASA0003.RLE","   "


The last object named 'POLYRAMPA' is used for stairs and ramps.
Edit: All bounding volumes are convex and don't overlap each other.

And here are some in-game screenshots: The first three screenshots show the same map. Of course it's possible to fake the drawing order of this 'flat' map by sorting the sprites by their y-value.

But this approach won't work if the map is more complex, like the one at the bottom right.

So my question is: Which algorithm did the developers use?
Bonus question: Is there some source code available? (pseudocode or any object-oriented programming language would be great)

Edit: Sorting by the XYZ-coordinates of the bounding boxes center point doesn't work.
For example:

The objects on the left side have the same center points as the objects on the right. The cylinder on the left should be in the background but the one on the right in the foreground.

• I think this question would work better if phrased as "how can I do this" rather than "how specifically did this game do it", because the latter is hard to answer without emailing the developer.
– Anko
Sep 30, 2015 at 14:46

## 1 Answer

You will have to sort the sprites based on their bounding box and start drawing things from back to front. In order to be successful with this you'll have to apply a mapping from the 3D coordinates (which seem dimetric to me) to the screen coordinates. Height differences translate directly into an offset in the y-coordinate while movement along the oblique(?) axes on the ground scales with something like sqrt(2)/2.

You find a sample implementation of such sprite sorter in OpenTTD's code (mind, it's GPL, so consider that before looking at it; you don't want to commit a copyright violation by relicensing it): https://docs.openttd.org/viewport__sprite__sorter_8h.html might be a starting point exploring the code.

• Thanks for your answer. In OpenTTD they sum up the X+Y+Z coordinates of the tile's center as the sorting order which requires a grid-based map and that all tiles have the same dimensions. This won't work for the Commandos maps, see the example I just added above.
– h3k
Oct 3, 2015 at 22:12