Assuming that your sprites occupy sets of tiles that are rectangles (if they occupy arbitrary sets, then you cannot draw the correctly at all in the general case), the problem is that there is no total order relation between the elements, so you cannot sort them using a sort that would result in O(nlogn) comparisons.
Note that for any two objects A and B, either A should be drawn before B (A <- B), B should be drawn before A (B <- A) or they can be drawn in any order. They form a partial order. If you draw yourself a few examples with 3 overlapping objects, you may notice that the even though the 1st and the 3rd object may not overlap, thus not having a direct dependency, their drawing order depends on the 2nd object that's between them - depending how you place it, you will obtain different drawing orders. Bottomline - traditional sorts don't work here.
One solution is to use the comparison (mentioned by the Dani) and compare each object to each other object to determine their dependencies and form a dependency graph (which will be a DAG). Then do a topological sort on the graph to determine drawing order. If there aren't too many objects, this may be fast enough (it's O(n^2)
).
Another solution is to use a (for balancing - pseudo) quad tree and store the rectangles of all objects into it.
Then iterate through all the objects X, and use the quad tree to check if there are any objects Y in the stripe above the object X which starts with the leftmost and ends with the rightmost corner of object X - for all such Y, Y <- X. Like this, you will still have to form a graph and sort topologically.
But you can avoid it. You use a list of objects Q, and a table of objects T. You iterate all the visible slots from smaller to bigger values on the x-axis (one row), going row by row on the y-axis. If there is a bottom corner of an object at that slot, do the procedure above to determine dependencies. If an object X depends on some other object Y that is partly above it (Y <- X), and every such Y is already in Q, add X to Q. If there is some Y which is not in Q, add X to T and denote that Y <- X. Every time you add an object to Q, you remove dependencies of objects pending in T. If all dependencies are removed, an object from T is moved to Q.
We are assuming that object sprites don't peek out of their slots on the bottom, the left or the right (only at the top, like trees in your picture). This should improve performance for a large number of objects. This approach will again be O(n^2)
, but only in the worst case which includes weird sized objects and/or weird configurations of objects. In most cases, it's O(n * logn * sqrt(n))
. Knowing the height of your sprites can eliminate the sqrt(n)
, because you don't have to check the entire stripe above. Depending on the number of objects on the screen, you may try replacing the quad tree with an array indicating which slots are taken (makes sense if there are many objects).
Finally, feel free to inspect this source code for some ideas: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala