Как сортировать объекты в 2d игре?

На вашей диаграмме рассмотрите значение x + y для каждой ячейки

Для сортировки ячеек сверху вниз можно просто отсортировать по значению x+y.

Может быть, вы можете найти что-то полезное здесь (используйте Firefox и проверьте DEMO )

В моем случае глубина в основном pos.x + pos.y [assetHelper.js -> получить глубину () {...] в точности так, как это описывает первый ответ. Тогда сортировка будет простым сравнением [canvasRenderer -> deepSortAssets () {...]

Хорошо, давайте попробуем! Нам придется заказывать эти объекты не по расстоянию, а по препятствиям. Под этим я подразумеваю, что для двух объектов A и B A может визуально препятствовать B, B может визуально препятствовать A, или ни один не препятствует другому. Если A препятствует B, мы сначала хотим нарисовать B, и наоборот. Чтобы решить эту проблему, мы должны быть в состоянии сказать, мешает ли А В или наоборот.

Вот что я придумала. У меня была только ограниченная способность проверить это, поэтому могут быть и недостатки, но мыслительный процесс - это нормально.

Шаг 1. Сопоставьте каждый объект его границам, сохранив исходный объект для последующего использования:

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

Шаг 2. Сопоставьте каждый объект с двумя углами, которые при проведении линии между ними образуют самое большое препятствие в поле зрения камеры:

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
  };
});

Шаг 3. Сортировка объектов. Нарисуйте отрезок линии от камеры до каждой конечной точки одного объекта. Если отрезок линии между конечными точками другого объекта пересекается, другой объект находится ближе и должен быть нарисован после.

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}));
  }
});

Шаг 4. Последний шаг - вернуть исходные объекты, отсортированные по порядку от самого дальнего к ближайшему:

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

Теперь, чтобы сложить все вместе:

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);

Дайте мне знать, если это работает!