I am working on custom 2D engine for a game.
I am having trouble figuring out a working system for sprite drawing-order sorting for this specific game.

Game description:

• 2D
• Top-down perspective
• Multiple floors
• Bridges

• Characters (Player characters, enemies, NPCs) move around freely. Movement is not tile based (constrained to grid).
• Characters can be positioned and move around any Floor and move between Floors.
• Objects (crates etc.) can be positioned on any Floor. (Not on Stairs.)
• Floors are traversed using Staircases.
  Staircase is a "ramp" connecting 2 Floors.
  Staircase can connect 2 Floors that can be any number of Floors apart.
• Characters and Objects cannot be positioned / move "behind" back-facing walls and behind Objects.
• Characters can be positioned / move behind other Characters and pass through each other.
• Characters and Objects can be positioned / move both on and under a Bridge.

Entities that need their sprites sorted are Characters, Objects, Bridges.
Visuals (tiles) that make rest of the game level, are rendered first (under everything else) in one pass, and don't need any kind of sorting.

What I tried so far:

V0. Sorting by Y

Obviously doesn't work because it can't solve verticality (Floors).

V1. Sorting Characters into lists by Character current Floor, than sort each list by Character current Y

Than drawing eg.
Floor 0 sorted Characters list
Floor 1 Bridges
Floor 1 sorted Characters list
...

This is practically implementation of Layers. Each Floor having one Layer.

Problem with this is approach, that Floor has to have a hard edge.
Each Character is at one point on one and only one Floor.
When two Characters are close enough together on Y axis to overlap, and each one is on a different Floor, this happens:

V2. Sorting Characters and Bridges using "Painter's Algorithm" (average distance to camera of 3D rectangle vertices)

Even though the graphic engine is 2D, I defined every Character and Bridge as 3D positioned rectangle, and defined virtual camera (view point) with 3D position.
Than calculated average 3D position of every entity and it's distance to camera. Than sorted by the distance.

Problem with this is approach is one of problems of Painter's Algorithm: the distance to camera is calculated from position of center point of the rectangle.
The bigger the rectangle, the more imprecise the calculation.

• If the rectangle is big enough, it will start wrongly overlapping surrounding rectangles.
  In my case, if the Bridge is wide enough on Y axis, it will be wrongly sorted between Characters on and under the Bridge.
• The algorithm apparently has problem sorting even same-sized rectangles of Characters between themselves right in some situations.

My implementation of the Painter's Algorithm may be wrong or buggy though.
If it maybe worked for you as solution for similar problem, please let me know.

V3. I can make the game fully 3D

and use Z-Buffer, that is made to solve the problems mentioned above.
But before I make that leap, I would like to be sure I explored all other (2D) possibilities.
---
I searched the internet high nad low for any tutorial or article on this, and surprisingly didn't find a single one that would fit my case.
I still hope somebody already figured this out.

I will be very grateful for any advice.

The problem with any sorting-based approach is that there are always edge cases where the sorting fails. This is necessarily so because it is possible to have situations where no correct sort order exists: A is in front of B and B is in front of C but C is in front of A.

https://en.wikipedia.org/wiki/Painter%27s_algorithm#/media/File:Painters_problem.svg​

(For the purpose of the description below, treat bridges as entities.)

Sorting two entities is easy enough. Take their 3D axis-aligned bounding boxes. By the separating axis theorem, there must be at least one axis separating these entities (assuming that they are not intersecting, in which case all bets are off), and it is always one of the three main axes of your 3D space: north-south, east-west, or up-down. If the separating axis is north-south, render the northern entity first. If the separating axis is up-down, render the lower entity first. If the separating axis is east-west, it doesn't matter in which order you render the entities. But even if the separating axis is up-down or north-south, the rendering order only matters if the 2D screen space bounding rectangle of the two entities overlaps. If other words, for any pair of entities, there are three possible relationships: “A is in front of B”, “B is in front of A”, and “they do not overlap”. (The fourth possibility is “A and B intersect”, but let's ignore that.)

Sorting three or more entities is harder, because “in front of” is not a transitive property. However, if your list of entities is small enough, then you can simply try all permutations. Arrange all entities in some arbitrary order. Test the correctness of the order by confirming that for any pair of entities A and B, where A is rendered before B, their relationship is either “B is in front of A” or “they do not overlap”. If the order is correct, render. If the order is not correct, try the next permutation. If you tried all permutations and none of them is correct, then there is no correct rendering order.

The algorithm described above is very slow for long lists of entities. To alleviate this, you can divide your entities into non-overlapping groups. Start with no groups. Then for each entity:

• If it does not overlap an existing group, create a new group with the (2D screen-space) bounds of that entity.
• If it overlaps one existing group, assign it to that group and expand that group's bounding box to include the entity.
• If it overlaps multiple existing groups, merge those groups, the assign it to the newly merged group and expand its bounding box to include the entity.

Then render each group individually, in any arbitrary order.

You already mentioned the Z-buffer, but perhaps you don't need to go all out and make your game fully 3d for that to work.
It's possible that you could implement one yourself. (within reason, at least) - if you don't want to set it up on the platform, or have to jump through too many hoops to get Z-buffer support on your engine.

A depth buffer would solve the cases you've mentioned per pixel, and you could put less, or even no further thought into ordering sprites, if done "right".

(By right, I mean applying the depth buffer right, not that it's a better solution overall)

Thank you very much, both of you !
I am in process of wrapping my head around your ideas, than will try and code them and see how they work in my existing system.
I'll be back with progress soon (well it actually may take some time :).

I would also go for depth buffers because it makes things a lot simpler while allowing more artistic freedom. Whole buildings can be drawn as a single multi-tile sprite to reduce the feel of grainy repeated patterns, which is probably why you used a flat color on the bridge.

You can even treat occluding walls as a static background if you begin a frame by copying both color and depth from the static scene using memcpy. Then just draw the few dynamic actors that are actually moving in the scene. Destructable walls and such can dynamically update the affected region of the background to make the game feel more interactive and fun.

Having a deferred light layer would not only add colored point lights for setting the mood, but also solve your current problem with light sources being occluded twice.

If you need existing code to look at, I have already implemented these features in my graphics API.

https://github.com/dawoodoz/dfpsr​