Sprites draw-order sorting for top-down 2D game with floors and bridges

Question

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

More details for clarity:

• Characters (Player characters, enemies, NPCs) 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
...

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.
Characters on different heights (elevations) are often sorted wrongly.
Also if the Bridge is wide enough on Y axis, it will be wrongly sorted between Characters on and under the Bridge.

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 will be very grateful for any advice.

Answer 1

Do you have a tile layer system? You could set it up where each layer is drawn in order. The transitions could be handled by a rectangle trigger and temporarily drawing a character/movable object twice, one for the exiting layer and once for the entering layer. Since they are being drawn on top of each other it should be invisible.

class Map {
    //...
    std::vector<Layer> layers;
};

class Layer {
    //...
    std::vector<Tile> tiles;
    Map* map;
};

class Tile {
    //...
    Layer* layer;
    Map* map;
};

class Entity {
    //...
    Layer* layer;
    Map* map;
    Tile* tile;
};