Как отсортировать изометрические спрайты в правильном порядке?

В обычной 2D-игре сверху вниз можно использовать ось y экрана для сортировки изображений. В этом примере деревья правильно отсортированы, но изометрические стены не:

Стена 2 находится на один пиксель ниже стены 1, поэтому она рисуется после стены 1 и заканчивается сверху.

Если я сортирую по изометрической оси Y, стены появляются в правильном порядке, но деревья не:

Как мне сделать это правильно?

Изометрические игры являются функционально трехмерными, поэтому внутри вы должны хранить трехмерные координаты для каждого объекта в игре. Фактические координаты, которые вы выбираете, являются произвольными, но, скажем, X и Y - две оси на земле, а Z - в воздухе.

Затем рендереру нужно спроецировать это в 2D, чтобы рисовать вещи на экране. «Изометрия» - одна из таких проекций. Проецирование из 3D в 2D изометрически довольно просто. Предположим, что ось X идет от верхнего левого угла до нижнего правого и вниз на один пиксель для каждых двух горизонтальных пикселей. Аналогично, ось Y идет сверху вниз справа налево. Ось Z идет прямо вверх. Чтобы конвертировать из 3D в 2D, просто:

function projectIso(x, y, z) {
    return {
        x: x - y,
        y: (x / 2) + (y / 2) - z
    };
}

Теперь к вашему первоначальному вопросу, сортировка. Теперь, когда мы работаем с нашими объектами непосредственно в 3D, сортировка становится намного проще. В нашем координатном пространстве самый дальний спрайт имеет самые низкие координаты x, y и z (т.е. все три оси направлены от экрана). Таким образом, вы просто сортируете их по сумме этих:

function nearness(obj) {
    return obj.x + obj.y + obj.z;
}

function closer(a, b) {
    if (nearness(a) > nearness(b)) {
        return "a";
    } else {
        return "b";
    }
}

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

Если предположить, что ваши спрайты занимают наборы плиток, которые являются прямоугольниками (если они занимают произвольные наборы, то в общем случае вы вообще не сможете правильно нарисовать), проблема в том, что между элементами нет отношения общего порядка, поэтому вы не можете сортировать они используют сортировку, которая приведет к O (nlogn) сравнениям.

Обратите внимание, что для любых двух объектов A и B либо A должно быть нарисовано до B (A <- B), B должно быть нарисовано до A (B <- A), либо они могут быть нарисованы в любом порядке. Они образуют частичный порядок. Если вы нарисуете несколько примеров с 3 перекрывающимися объектами, вы можете заметить, что, хотя 1-й и 3-й объекты могут не перекрываться, поэтому не имеют прямой зависимости, их порядок рисования зависит от 2-го объекта, который находится между ними - в зависимости от того, как Вы разместите его, вы получите различные заказы на рисование. Итог - традиционные сорта здесь не работают.

Одним из решений является использование сравнения (упомянутого Dani) и сравнение каждого объекта с другим объектом для определения их зависимостей и формирования графа зависимостей (который будет DAG). Затем выполните топологическую сортировку на графике, чтобы определить порядок рисования. Если не так много объектов, это может быть достаточно быстро (этоO(n^2) ).

Другое решение заключается в использовании (для балансировки - псевдо ) четырехугольное дерево и сохранить в нем прямоугольники всех объектов.

Затем выполните итерацию по всем объектам X и используйте четырехугольное дерево, чтобы проверить, есть ли какие-либо объекты Y в полосе над объектом X, который начинается с самого левого и заканчивается самым правым углом объекта X - для всех таких Y, Y < - X. Таким образом, вам все равно придется формировать график и топологически сортировать.

Но вы можете избежать этого. Вы используете список объектов Q и таблицу объектов T. Итерируете все видимые слоты от меньших к большим значениям по оси X (одна строка), переходя строка за строкой по оси Y. Если в этом слоте есть нижний угол объекта, выполните описанную выше процедуру, чтобы определить зависимости. Если объект X зависит от некоторого другого объекта Y, который частично над ним (Y <- X), и каждый такой Y уже находится в Q, добавьте X к Q. Если есть некоторый Y, которого нет в Q, добавьте X к T и обозначим Y <- X. Каждый раз, когда вы добавляете объект в Q, вы удаляете зависимости объектов, ожидающих в T. Если все зависимости удалены, объект из T перемещается в Q.

Мы предполагаем, что объектные спрайты не выглядывают из своих слотов снизу, слева или справа (только сверху, как деревья на вашей картинке). Это должно улучшить производительность для большого количества объектов. Этот подход снова будет O(n^2), но только в худшем случае, который включает в себя объекты странного размера и / или странные конфигурации объектов. В большинстве случаев это так O(n * logn * sqrt(n)). Знание высоты ваших спрайтов может устранить sqrt(n), потому что вам не нужно проверять всю полосу выше. В зависимости от количества объектов на экране вы можете попробовать заменить дерево квадратов массивом, указывающим, какие слоты заняты (имеет смысл, если объектов много).

Наконец, не стесняйтесь проверять этот исходный код на предмет некоторых идей: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala

Я не думаю, что есть математическое решение. Вероятно, у вас недостаточно данных в 2D-мире, в котором живут ваши предметы. Если бы ваши стены были зеркально отображены на X, они были бы в «правильном» порядке. С другой стороны, вы можете каким-то образом провести тестирование с перекрытием с помощью ограничительной рамки изображения, но это область, с которой я не знаком.

Вы, вероятно, должны отсортировать по экрану Y на плитку и сказать, что все более сложное - это «проблема дизайна». Например, если вы создаете контент, просто сообщите своим дизайнерам алгоритм сортировки и добавьте wall2 на 2 пикселя вверх, чтобы решить проблему. Вот как мы должны были это исправить в изометрической игре, над которой я работал. Это может включать в себя брать «длинные» предметы и разбивать их на куски размером с плитку.

Если вы разрешаете пользователям редактировать контент, то совершенно безопасно сделать так, чтобы все было на основе плиток и не более одной плитки. Таким образом, вы избежите проблемы. Возможно, вам удастся сделать все больше, чем плитка, но, возможно, только если она квадратная. Я не играл с этим.

Идеальная изометрическая сортировка - это сложно. Но для первого подхода, чтобы правильно отсортировать ваши элементы, вы должны использовать более сложную функцию сравнения с каждым перекрывающимся объектом. Эта функция должна проверять это условие: перекрывающийся объект «a» находится позади «b», если:

(a.posX + a.sizeX <= b.posX) или (a.posY + a.sizeY <= b.posY) или (a.posZ + a.sizeZ <= b.posZ)

Конечно, это первая идея для наивной изометрической реализации. Для более сложного сценария (если вы хотите вращение вида, положение на пиксель на оси z и т. Д.), Вам нужно проверить больше условий.

Я использую очень простую формулу, которая хорошо работает с моим маленьким изометрическим движком в OpenGL:

Каждый из ваших объектов (деревья, плитка для пола, персонажи, ...) имеет X и Y позиции на экране. Вам нужно включить ГЛУБИННОЕ ТЕСТИРОВАНИЕ и найти правильное значение Z для каждого значения. Вы можете просто следующее:

z = x + y + objectIndex

Я использую и другой индекс для пола и объектов, которые будут над полом (0 для пола и 1 для всех объектов, которые имеют высоту). Это должно работать просто отлично.

Обширный ответ с несколькими решениями, картинками и всей математикой здесь:

/programming/892811/drawing-isometric-game-worlds

Если вы сравните значения y в одной и той же позиции x, это будет работать каждый раз. Поэтому не сравнивайте центр с центром. Вместо этого сравните центр одного спрайта с той же позицией х на другом спрайте.

Но это требует некоторых геометрических данных для каждого спрайта. Это может быть так же просто, как две точки слева направо, которые описывают нижнюю границу спрайта. Или вы можете проанализировать данные изображения спрайтов и найти первый непрозрачный пиксель.

Более простой подход - разделить все спрайты на три группы: диагональ по оси x, диагональ по оси y и плоскость. Если два объекта имеют диагональ вдоль одной оси, отсортируйте их по другой оси.

Вам необходимо назначить уникальные идентификаторы всем объектам одного типа. Затем вы сортируете все объекты по их позициям и рисуете группы объектов в порядке их идентификаторов. Таким образом, объект 1 в группе A никогда не заменит объект 2 в группе A и т. Д.

На самом деле это не ответ, а просто комментарий и голосование, которое я хотел бы дать этому ответу axel22 здесь /gamedev//a/8181/112940

У меня недостаточно репутации, чтобы голосовать или комментировать другие ответы, но второй абзац его ответа, вероятно, самая важная вещь, о которой следует помнить, пытаясь отсортировать объекты в изометрической игре, не полагаясь на «современное» 3D. методы, такие как Z-буфер.

В моем движке я хотел делать вещи "старой школы", чистый 2D. И я потратил много времени, пытаясь понять, почему мой вызов «sort» (в моем случае это был c ++ std :: sort) не работал правильно на определенных конфигурациях карты.

Только когда я понял, что это ситуация «частичного порядка», я смог ее решить.

До сих пор все рабочие решения, которые я нашел в Интернете, использовали некоторую топологическую сортировку для правильного решения проблемы. Топологическая сортировка, кажется, путь.