Dependency Problem. As is usually the case around here, the actor rendering order problem has turned out to be more difficult than originally anticipated. In the old engine, the solution was easy. Every actor and tile was the same size. Create a list of every actor and tile (what I called DrawStack) and sort the list based on (gx+gy+gz)--distance from the "camera".
Last time I wrote about this problem I mentioned that this doesn't work for the walls. Walls are different sizes. But that's okay. All I had to do was figure out which walls needed to be drawn in front of the others. This was the original dependency problem that called for the topological sort. Walls are only ordered relative to their neighbors. In the screenshot below, it is impossible for Wall1 and Wall2 to overlap. So the order those two walls are drawn in doesn't matter.
On the other hand, Wall1 must be drawn over the red floor tile. So there are multiple drawing orders that solve the problem: (W2,F,W1) or (W1,F,W2).
What I want to happen is pretty clear. If Marika is standing in the red square, she should be drawn behind Wall1 and Wall2. Otherwise, she should be drawn in front of the walls. In both cases she should be drawn in front of the floor.
But because the floor never overlaps with Wall2, I can't assume that Wall2 is placed after the floor in the drawing order (DrawStack). The floor could just as easily be placed after Wall2. So if I place Marika after the floor so that she is drawn over it, then she could also be drawn over Wall2.
What I really don't want to do is call the topological sort every time any actor changes position. I think this would be way too costly.
Topological sort is achieved by defining dependency rules, so I need to identify a new rule. The floor must always be drawn before Wall1 and Wall2. Even though the floor never overlaps Wall2, its contents might.
I'm now wrestling with a couple of potential solutions. One idea I thought of was to partition each sector into subsectors. Floors define occupiable volumes, so I loop through all the floors and start building occupiable spaces for which every point is in front of the same set of walls. I can then add rules to the dependency graph that insists the floor is always rendered before every wall in front of it and after every wall behind it.
This solution has the problem of defining the spaces, which is a tricky one but can be part of the game loading sequence where speed isn't as much of an issue. Once I have the spaces defined and the walls ordered, I won't have to do any topological sorting in-game, which was one of my concerns. I don't trust the topological sort to work efficiently enough to maintain 60 FPS.