Как сортировать объекты в 2d игре? - PullRequest
Новая
       13

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

0 голосов
/ 19 января 2019

Я разрабатываю своего рода перспективную 2d / 3d игру в javascript.

У меня есть оси X и Y, как показано на рисунке ниже.

На мой вопрос: У меня есть набор объектов (помеченных "1" и "2") на моей карте со свойствами, такими как:

  • позицияX / позицияY
  • размер X / размер Y

На изображении объект "1" получает координаты x:3, y:2, а объект "2" получает координаты x:5, y:4. SizeX и sizeY равны w:1, h:1 для обоих объектов.

Что я хотел бы сделать с этой информацией, так это отсортировать все объекты в порядке возрастания (на основе положения и размера объектов), чтобы узнать в 3d, какие объекты поступают для другого объекта, чтобы затем нарисовать все мои отсортированные объекты в мой холст (объекты на переднем плане / background = "layer").

img

Примечание. Камера находится в фиксированном положении - допустим, камера имеет идентичные значения X и Y, поэтому положение камеры не должно использоваться при расчете CameraX = CameraY.

Что я пробовал до сих пор: 

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...

Изменить на фрагмент выше:

Я пытался отсортировать объекты по их координатам x / y, но кажется, что параметр ширины и высоты необходимо использовать также во время вычислений, чтобы избежать ошибок.

Как использовать ширину / высоту? Я понятия не имею, поэтому любая помощь будет очень признательна.

Ответы [ 5 ]

0 голосов
/ 02 февраля 2019

Хорошо, давайте попробуем! Нам придется заказывать эти объекты не по расстоянию, а по препятствиям. Под этим я подразумеваю, что для двух объектов A и B A может визуально препятствовать B, B может визуально препятствовать A, или ни один не препятствует другому. Если A препятствует B, мы сначала хотим нарисовать B, и наоборот. Чтобы решить эту проблему, мы должны быть в состоянии сказать, мешает ли A 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);

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

0 голосов
/ 31 января 2019

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

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

0 голосов
/ 19 января 2019

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

diagram with X+Y for each cell

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

0 голосов
/ 20 января 2019

Я не уверен, что вы имели в виду:

Примечание. Камера находится в фиксированном положении - допустим, камера имеет идентичные значения X и Y, поэтому положение камеры не должно использоваться при расчете CameraX = CameraY.

Итак, вот общее решение.

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

Алгоритм может быть реализован в JS следующим образом: 

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

РЕДАКТИРОВАТЬ это решение также не работает, поскольку оно делает наивные предположения, скоро обновит или удалит.

0 голосов
/ 19 января 2019

Проблема здесь в том, что вы используете евклидово расстояние, чтобы измерить, как далеко находится объект от (0, 0), чтобы попытаться измерить расстояние от линии y = -x. Это не будет работать, однако расстояние Манхэттена будет. 

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

Это упорядочит ваши объекты по вертикали в вашей повернутой системе координат.

...