How to layer objects - geometry?

Question

I'm developing a kind of perspective based 2d/3d game.

I've got an X- and an Y-axis like I've displayed in the image below.

---

To my question: I've got a bunch of objects (marked with "1" and "2") on my map with properties like:

• positionX / positionY
• sizeX / sizeY

In the image Object "1" does get the coordinates x:3, y:2, and the Object "2" does get the coordinates x:5, y:4. SizeX and sizeY is w:1, h:1 for both objects.

What I'd like to do with this info is to sort all of the objects in ascending order (based on the objects position and size) to know in 3d which objects comes for another object.

---

Note: The Camera has to fixed position - lets say the camera has the identical X and Y value so that the camera position must not be used while calculation CameraX = CameraY.

What I've tried so far:

define objects = [
  {
    name: "objectA",
    x: 8,
    y: 12,
    w: 2,
    h: 2
  }, 
  {
    name: "objectB",
    x: 3,
    y: 5,
    w: 2,
    h: 2
  },
  {
    name: "objectC",
    x: 6,
    y: 2,
    w: 1,
    h: 3
  }
]

method sort (a, b)
  define distanceA = sqrt(a.x**2 + a.y**2)
  define distanceB = sqrt(a.x**2 + a.y**2)
  return distanceA - distanceB;

I've tried to sort the objects based on their x/y coordinate but it seems like the width and height parameter must be used also while calculation to avoid errors.

How do I have to make use of width/height? Tbh I've got no clue so any help would be really appreciated.

Answer 1

The strategy is simple: we will figure out what things are in front of what other things, and then set the order based on that. The latter is called topological sorting, and it's a powerful tool, and a simple one too.

I present two methods, each suitable for a different set of assumptions about the set of entities we are sorting.

Sparse entities

In this method, the entities do not fill the map; it is in general not true that we can travel "upward" through adjacent entities to find all entities that any particular entity is in front of.

First, for each object, we must find the left and right extents of the entity. These are, using the layout in your image, $(x-y-h, x+w-y)$. We will store these two extents, and the corresponding object, in a list.

(this code is in Python; I don't recognize your programming language so I couldn't code in it)

entity_extents = []
for e in tile_entities:
    entity_extents.append(((e.x-e.y-e.h, e.x+e.w-e.y), e))

We'll sort these by the left end.

entity_extents.sort(key=lambda x: x[0][0])

Now, we must examine each entity in turn: we have to find things that it's actually in front of or behind. Since they're already sorted by the left end, we'll check it against things further to the left that we haven't gotten past. To do this, we'll keep a list of things that are to the left of whereever we hare, sorted by the right end. As we do this we'll drop things out of the list that are no longer useful, because their right end doesn't extend past the left end of the thing we're looking at.

digraph = {}
leftward_entities = []
for e in entity_extents:
    left_h = e[0][0]
    for n,le in enumerate(leftward_entities):
        if le[0][1] > left_h: # we've found one to the right of what we have, so that one and everything further gets to live.
            del(leftward_entities[:n]) 
            break
    else:
        leftward_entities.clear() # everything's to the left.  Nothing remains.

Now we figure out, for each remaining leftward entity, whether it's in front of or behind our current entity. For this, we'll find the vertical location of the left end of our current entity, and the vertical location of the topmost portion of each leftward entity at the same horizontal location as the left end of the current entity.

    e_node = (set(), set())
    digraph[e[1]] = e_node
    left_v = e[1].x + e[1].y + e[1].h
    for le in leftward_entities:
        l_node = digraph[le]
        target_top_h = le[1].x - le[1].y
        target_left_v = le[1].x + le[1].y + abs(left_h - target_top_h) 
        if target_left_v < left_v:
            l_node[1].add(e[1])
            e_node[0].add(l[1])
        else:
            l_node[0].add(e[1])
            e_node[1].add(l[1])

And finally we need to insert the current entity into the leftwards, based on the right end:

    right_h = e[0][1]
    for n,le in enumerate(leftward_entities):
        if le[0][1] > right_h:
            leftward_entities.insert(n,e)
            break
    else:
        leftward_entities.append(e)

From here, we proceed to topological sorting.

Dense objects

The more common setup, the grid is filled with entities. if an entity can be considered behind another, they are connected by a whole path of entities behind one another that are also adjacent.

The strategy is vastly different: we'll just fill in the grid with entities...

entity_grid = {}
for e in tile_entities:
    for u in range(e.x, e.x + e.w): # not all the way though.  we don't care about the middles of buildings.
        entity_grid[(u, e.y)] = e
        entity_grid[(u, e.y + e.h - 1)] = e
    for v in range(e.y, e.y + e.h):
        entity_grid[(e.x, v)] = e
        entity_grid[(e.x + e.w - 1)] = e

...and then look around the outside of each entity for other entities.

digraph[e] = {}
for e in tile_entities:
    e_node = (set(), set())
    for u in range(e.x, e.x + e.w):
        if (u, e.y-1) in entity_grid:
            e_node[0].add(entity_grid[(u, e.y-1)])
        if (u, e.y+e.h) in entity_grid:
            e_node[1].add(entity_grid[(u, e.y+e.h)])
    for v in range(e.y, e.y + e.h):
        if (e.x-1, v) in entity_grid:
            e_node[0].add(entity_grid[(e.x-1, v)])
        if (e.x+e.w, v) in entity_grid:
            e_node[1].add(entity_grid[(e.x+e.w, v)])

And now proceed with topological sorting.

Topological sorting

Having built our digraph, we can actually sort things.

Each node in the digraph has to know two things: which things precede it, and which things follow it. In this, I've arranged so that the predecessors of an element e are in the set digraph[e][0], and its successors are in digraph[e][1].

First things first, we need to find all the entries in the digraph that have no predecessors: these are the ones that are near the very back.

itinerary = set()
for entity, (predecessors, _) in digraph.items():
    if not predecessors:
        itinerary.add(entity)

Now, we add these to our final sequence one at a time, while cutting its connections with its successors. Every time we end up with a former successor that has no still-connected predecessors, we add it to the pile to examine.

sorted_pile = []
while itinerary:
    entity = itinerary.pop()
    sorted_pile.append(entity)
    successors = digraph[entity][1]
    for succ in successors: 
        digraph[succ][0].remove(entity)
        if not digraph[succ][0]:
            itinerary.add(succ)
return sorted_pile

And ... that's it! sorted_pile now obeys the back-to-front ordering you need to draw things correctly.