How to sort objects in 2d game?

Question

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

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 to lateron draw all of my objects sorted into my canvas (objects in foreground/background = "layers").

---

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:

let 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
  }
]


let sortObjects = (objects) => {
  return objects.sort((a, b)=> {
    let distanceA = Math.sqrt(a.x**2 + a.y**2);
    let distanceB = Math.sqrt(b.x**2 + b.y**2);
    return distanceA - distanceB;
  });
}


let sortedObjects = sortObjects(objects);
console.log(sortedObjects);

// NOTE in 3d: first Object drawn first, second Object drawn second and so on...

Edit to the snippet above:

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

I'm not sure what you meant by:

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.

So here's a general-case solution.

You must sort the objects by their closest distance to the camera. This depends on an object's dimensions as well as its relative position.

The algorithm can be implemented in JS as follows:

// If e.g. horizontal distance > width / 2, subtract width / 2; same for vertical
let distClamp = (dim, diff) => {
    let dist = Math.abs(diff);
    return (dist > 0.5 * dim) ? (dist - 0.5 * dim) : dist;
}

// Closest distance to the camera
let closestDistance = (obj, cam) => {
    let dx = distClamp(obj.width, obj.x - cam.x);
    let dy = distClamp(obj.height, obj.y - cam.y);
    return Math.sqrt(dx * dx + dy * dy);
}

// Sort using this as the metric
let sortObject = (objects, camera) => {
    return objects.sort((a, b) => {
        return closestDistance(a, camera) - closestDistance(b, camera);
    });
}

EDIT this solution also does not work because it makes naive assumptions, will update soon or delete.

Answer 2

Alright, let's have a go at this! We'll have to order these objects not by distance, but by obstruction. By that, I mean for two objects A and B, A can visibly obstruct B, B can visibly obstruct A, or neither obstructs the other. If A obstructs B, we'll want to draw B first, and vice-versa. To solve this, we need to be able to say whether A obstructs B, or the other way around.

Here's what I've come up with. I only had a limited ability to test this, so there may still be flaws, but the thought process is sound.

Step 1. Map each object to its bounds, saving the original object for later:

let step1 = objects.map(o => ({
  original: o,
  xmin: o.x,
  xmax: o.x + o.w,
  ymin: o.y,
  ymax: o.y + o.h
}));

Step 2. Map each object to the two corners that, when a line is drawn between them, form the largest obstruction to the camera's field of view:

let step2 = step1.map(o => {
  const [closestX, farthestX] = [o.xmin, o.xmax].sort((a, b) => Math.abs(camera.x - a) - Math.abs(camera.x - b));
  const [closestY, farthestY] = [o.ymin, o.ymax].sort((a, b) => Math.abs(camera.y - a) - Math.abs(camera.y - b));

  return {
    original: o.original,
    x1: closestX,
    y1: o.xmin <= camera.x && camera.x <= o.xmax ? closestY : farthestY,
    x2: o.ymin <= camera.y && camera.y <= o.ymax ? closestX : farthestX,
    y2: closestY
  };
});

Step 3. Sort the objects. Draw a line segment from the camera to each endpoint of one object. If the line segment between the endpoints of the other object intersects, the other object is closer and must be drawn after.

let step3 = step2.sort((a, b) => {
  const camSegmentA1 = {
    x1: camera.x,
    y1: camera.y,
    x2: a.x1,
    y2: a.y1
  };
  const camSegmentA2 = {
    x1: camera.x,
    y1: camera.y,
    x2: a.x2,
    y2: a.y2
  };
  const camSegmentB1 = {
    x1: camera.x,
    y1: camera.y,
    x2: b.x1,
    y2: b.y1
  };
  const camSegmentB2 = {
    x1: camera.x,
    y1: camera.y,
    x2: b.x2,
    y2: b.y2
  };

  // Intersection function taken from here: https://stackoverflow.com/a/24392281
  function intersects(seg1, seg2) {
    const a = seg1.x1, b = seg1.y1, c = seg1.x2, d = seg1.y2,
          p = seg2.x1, q = seg2.y1, r = seg2.x2, s = seg2.y2;
    const det = (c - a) * (s - q) - (r - p) * (d - b);
    if (det === 0) {
      return false;
    } else {
      lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;
      gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;
      return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
    }
  }

  function squaredDistance(pointA, pointB) {
    return Math.pow(pointB.x - pointA.x, 2) + Math.pow(pointB.y - pointA.y, 2);
  }

  if (intersects(camSegmentA1, b) || intersects(camSegmentA2, b)) {
    return -1;
  } else if (intersects(camSegmentB1, a) || intersects(camSegmentB2, a)) {
    return 1;
  } else {
    return Math.max(squaredDistance(camera, {x: b.x1, y: b.y1}), squaredDistance(camera, {x: b.x2, y: b.y2})) - Math.max(squaredDistance(camera, {x: a.x1, y: a.y1}), squaredDistance(camera, {x: a.x2, y: a.y2}));
  }
});

Step 4. Final step -- get the original objects back, sorted in order of farthest to closest:

let results = step3.map(o => o.original);

Now, to put it all together:

results = objects.map(o => {
  const xmin = o.x,
        xmax = o.x + o.w,
        ymin = o.y,
        ymax = o.y + o.h;

  const [closestX, farthestX] = [xmin, xmax].sort((a, b) => Math.abs(camera.x - a) - Math.abs(camera.x - b));
  const [closestY, farthestY] = [ymin, ymax].sort((a, b) => Math.abs(camera.y - a) - Math.abs(camera.y - b));

  return {
    original: o,
    x1: closestX,
    y1: xmin <= camera.x && camera.x <= xmax ? closestY : farthestY,
    x2: ymin <= camera.y && camera.y <= ymax ? closestX : farthestX,
    y2: closestY
  };
}).sort((a, b) => {
  const camSegmentA1 = {
    x1: camera.x,
    y1: camera.y,
    x2: a.x1,
    y2: a.y1
  };
  const camSegmentA2 = {
    x1: camera.x,
    y1: camera.y,
    x2: a.x2,
    y2: a.y2
  };
  const camSegmentB1 = {
    x1: camera.x,
    y1: camera.y,
    x2: b.x1,
    y2: b.y1
  };
  const camSegmentB2 = {
    x1: camera.x,
    y1: camera.y,
    x2: b.x2,
    y2: b.y2
  };

  // Intersection function taken from here: https://stackoverflow.com/a/24392281
  function intersects(seg1, seg2) {
    const a = seg1.x1, b = seg1.y1, c = seg1.x2, d = seg1.y2,
          p = seg2.x1, q = seg2.y1, r = seg2.x2, s = seg2.y2;
    const det = (c - a) * (s - q) - (r - p) * (d - b);
    if (det === 0) {
      return false;
    } else {
      lambda = ((s - q) * (r - a) + (p - r) * (s - b)) / det;
      gamma = ((b - d) * (r - a) + (c - a) * (s - b)) / det;
      return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);
    }
  }

  function squaredDistance(pointA, pointB) {
    return Math.pow(pointB.x - pointA.x, 2) + Math.pow(pointB.y - pointA.y, 2);
  }

  if (intersects(camSegmentA1, b) || intersects(camSegmentA2, b)) {
    return -1;
  } else if (intersects(camSegmentB1, a) || intersects(camSegmentB2, a)) {
    return 1;
  }
  return Math.max(squaredDistance(camera, {x: b.x1, y: b.y1}), squaredDistance(camera, {x: b.x2, y: b.y2})) - Math.max(squaredDistance(camera, {x: a.x1, y: a.y1}), squaredDistance(camera, {x: a.x2, y: a.y2}));
}).map(o => o.original);

Let me know if that works!

Answer 3

The issue here is that you are using euclidean distance to measure how far away an object is from (0, 0), to try to measure the distance from the y = -x line. This will not work, however Manhattan distance will.

let sortObjects = (objects) => {
  return objects.sort((a, b)=> {
    let distanceA = a.x + a.y;
    let distanceB = b.x + b.y;
    return distanceA - distanceB;
  });
}

This will order your objects vertically in your rotated coordinate system.

Answer 4

In your diagram consider the value of x+y for each cell

To sort top-to-bottom the cells you can simply sort on the value of x+y.

Answer 5

Maybe you can find something useful here (use Firefox & check the DEMO)

In my case depth is basically pos.x + pos.y [assetHelper.js -> get depth() {...] exactly as the first answer describes it. Then the sorting is a simple compare [canvasRenderer -> depthSortAssets() {...]