Mattie
35 posts
Why comparison sort won't work
Edited by Mattie on
Just made some diagrams to help myself understand why a basic comparison sort won't work, and I though I'd share them in case they'd help other people.

Here, we have two entities A and C being sorted, with the camera looking down from above. Since they don't intersect when projected into the screen plane (shown by the gray lines), the sort order between them doesn't matter. However, we have to pick one of them to be in front of the other, since that's how our sort algorithm works.

Let's say that we end up sorting A in front of C (A > C). Then, come across a third entity, B, which intersects both A and C in screen space. Applying our sorting rules, we place B between A and C, and all is well.

However, what if B was oriented differently? Here, we see that B should be in front of A and behind C. But because we sorted A > C before, we can't actually do this, so our sorting algorithm fails.

Hence, we need our sorting to take into account the fact that A and C don't overlap, so their global sort order is indeterminate (i.e. there are no edges connecting their nodes in the sort graph) until we get information otherwise. Once we insert B into the graph, we then have a connection between A and C, so we can then sort them properly.
Roman
9 posts
Been around ever since CPU's had 3 registers! (AtariXL800) That is a long time to stay a kid.
Why comparison sort won't work
you are right, but with limitations,
from the sample you've shown, yes a comparison sort will not work, the relationship between A & C is dependent on B.
however, in reference to HMH, early on Casey said that there will be no slopes, in which case the situation you've created will not be possible.

With flat standing or laying sprites we can define a good enough sort (with some constraints) that will generate a total sort, independent of the insertion order.
This may not be an all inclusive solution (or it may, I need to prove that), but writing a game, we do have to cheat.
So, cheat by ensuring that the level generator creates optimal maps, avoiding the pitfalls in the sort.

-Roman
Mattie
35 posts
Why comparison sort won't work
roam00010011
you are right, but with limitations,
from the sample you've shown, yes a comparison sort will not work, the relationship between A & C is dependent on B.
however, in reference to HMH, early on Casey said that there will be no slopes, in which case the situation you've created will not be possible.

With flat standing or laying sprites we can define a good enough sort (with some constraints) that will generate a total sort, independent of the insertion order.
This may not be an all inclusive solution (or it may, I need to prove that), but writing a game, we do have to cheat.
So, cheat by ensuring that the level generator creates optimal maps, avoiding the pitfalls in the sort.

-Roman

Those aren't slopes, they're either laying flat in the X-Y plane or standing up in the X-Z plane. The camera is assumed to be looking down along a τ/8 diagonal in the Y-Z plane, creating the top-down perspective. I've drawn these images rotated so that the camera is looking down from above, so it's easier to see when they overlap in screen space (which would effectively be projecting the "objects" onto the top of the image, as shown by the vertical lines).

As an aside, I've done more thinking, and found that even though we only have flat or standing sprites, we can still can run into painter's algorithm issues. Here's an example, which is basically the above two examples combined. This creates a situation where there is no order in which you could draw the sprites, without having to split the sprites up into parts.

Roman
9 posts
Been around ever since CPU's had 3 registers! (AtariXL800) That is a long time to stay a kid.
Why comparison sort won't work
Edited by Roman on Reason: edit
Please add the camera on the side view.
From the two new images it seems that from the camera view we have 4 flat rectangles, but from the side view it looks like 3 flat and one upright.

edit: assuming you are viewing at an angle, I can see your point.
But let me note that as I said before, comparison sort can't solve it all, a scene like that would have to be prevented to use comparison,
or you'll need a different method to setup the draw list to ensure a proper draw order.