Como ordeno sprites isométricos na ordem correta?

Em um jogo 2D normal de cima para baixo, pode-se usar o eixo da tela y para classificar as imagens. Neste exemplo, as árvores são classificadas corretamente, mas as paredes isométricas não são:

A parede 2 é um pixel abaixo da parede 1, portanto, é desenhada após a parede 1 e termina em cima.

Se eu ordenar pelo eixo isométrico y, as paredes aparecerão na ordem correta, mas as árvores não:

Como faço isso corretamente?

Os jogos isométricos são funcionalmente em 3D; portanto, internamente, você deve armazenar as coordenadas em 3D para cada entidade no jogo. As coordenadas reais que você escolhe são arbitrárias, mas digamos que X e Y são os dois eixos no solo, e Z está fora do solo no ar.

O renderizador então precisa projetar isso em 2D para desenhar coisas na tela. "Isométrico" é uma dessas projeções. Projetar de 3D para 2D isometricamente é bastante simples. Digamos que o eixo X vá do canto superior esquerdo para o canto inferior direito e desça um pixel para cada dois pixels horizontais. Da mesma forma, o eixo Y vai do canto superior direito para o canto inferior esquerdo. O eixo Z vai para cima. Para converter de 3D para 2D, basta:

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

Agora, para sua pergunta original, classificando. Agora que estamos trabalhando com nossos objetos diretamente em 3D, a classificação se torna muito mais simples. Em nosso espaço de coordenadas aqui, o sprite mais distante tem as coordenadas x, ye z mais baixas (ou seja, os três eixos apontam na tela). Então você apenas os classifica pela soma desses:

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

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

Para evitar reorganizar suas entidades a cada quadro, use uma classificação de pombo, detalhada aqui .

Supondo que seus sprites ocupem conjuntos de blocos que são retângulos (se eles ocupam conjuntos arbitrários, então você não pode desenhar corretamente de maneira alguma no caso geral), o problema é que não há uma relação total de ordem entre os elementos, portanto, você não pode classificar usando uma classificação que resultaria em comparações de O (nlogn).

Observe que, para quaisquer dois objetos A e B, A deve ser desenhado antes de B (A <- B), B deve ser desenhado antes de A (B <- A) ou pode ser desenhado em qualquer ordem. Eles formam uma ordem parcial. Se você desenhar alguns exemplos com três objetos sobrepostos, poderá perceber que, embora o primeiro e o terceiro objetos não possam se sobrepor, não tendo uma dependência direta, sua ordem de desenho depende do segundo objeto que está entre eles - dependendo de como Se você colocá-lo, obterá diferentes ordens de desenho. Bottomline - os tipos tradicionais não funcionam aqui.

Uma solução é usar a comparação (mencionada pela Dani) e comparar cada objeto com o outro para determinar suas dependências e formar um gráfico de dependência (que será um DAG). Em seguida, faça uma classificação topológica no gráfico para determinar a ordem do desenho. Se não houver muitos objetos, isso pode ser rápido o suficiente (é O(n^2)).

Outra solução é usar uma quad tree (para equilibrar - pseudo ) e armazenar os retângulos de todos os objetos nela.

Em seguida, percorra todos os objetos X e use a árvore quádrupla para verificar se há algum objeto Y na faixa acima do objeto X que começa com a extremidade esquerda e termina com o canto mais à direita do objeto X - para todos esses Y, Y < - X. Assim, você ainda precisará formar um gráfico e classificar topologicamente.

Mas você pode evitá-lo. Você usa uma lista de objetos Q e uma tabela de objetos T. Você itera todos os slots visíveis, dos valores menores aos maiores no eixo x (uma linha), passando linha por linha no eixo y. Se houver um canto inferior de um objeto nesse slot, faça o procedimento acima para determinar as dependências. Se um objeto X depender de algum outro objeto Y que esteja parcialmente acima dele (Y <- X), e todos esses Y já estiverem em Q, adicione X a Q. Se houver algum Y que não esteja em Q, adicione X a T e denote que Y <- X. Toda vez que você adiciona um objeto a Q, você remove dependências de objetos pendentes em T. Se todas as dependências forem removidas, um objeto de T será movido para Q.

Estamos assumindo que os sprites de objetos não espreitam pelas fendas na parte inferior, esquerda ou direita (apenas na parte superior, como árvores na imagem). Isso deve melhorar o desempenho de um grande número de objetos. Essa abordagem será novamente O(n^2), mas apenas no pior dos casos, que inclui objetos de tamanhos estranhos e / ou configurações estranhas de objetos. Na maioria dos casos, é O(n * logn * sqrt(n)). Saber a altura de seus sprites pode eliminar o sqrt(n), porque você não precisa verificar a faixa inteira acima. Dependendo do número de objetos na tela, você pode tentar substituir a árvore quádrupla por uma matriz indicando quais slots estão ocupados (faz sentido se houver muitos objetos).

Por fim, sinta-se à vontade para inspecionar este código-fonte em busca de algumas idéias: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala

Eu não acho que exista uma solução matemática. Você provavelmente não possui dados suficientes no mundo 2D em que seus itens estão vivendo. Se suas paredes fossem espelhadas em X, elas estariam na ordem "correta". Então, novamente, você poderá realizar testes de sobreposição com a caixa delimitadora da imagem, mas essa é uma área com a qual não estou familiarizado.

Você provavelmente deve classificar por tela Y por bloco e dizer que algo mais complicado é um "problema de design". Por exemplo, se você estiver criando o conteúdo, informe aos designers o algoritmo de classificação e mova wall2 2 pixels para corrigir o problema. Foi assim que tivemos que consertar no jogo isométrico em que trabalhei. Isso pode incluir pegar itens "longos" e dividi-los em pedaços do tamanho de blocos.

Se você estiver permitindo que os usuários editem o conteúdo, a coisa mais segura a fazer é tornar tudo baseado em blocos e, no máximo, um bloco. Dessa forma, você evita o problema. Você pode conseguir fazer tudo maior do que um ladrilho, mas possivelmente apenas se for quadrado. Eu não brinquei com isso.

A classificação isométrica perfeita é difícil. Mas, para uma primeira abordagem, para classificar corretamente seus itens, você deve usar uma função de comparação mais complexa com cada objeto sobreposto. Esta função deve verificar esta condição: Um objeto sobreposto "a" fica atrás de "b" se:

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

Obviamente, essa é a primeira idéia para uma implementação isométrica ingênua. Para um cenário mais complexo (se você deseja ver a rotação, as posições por pixel no eixo z etc.), precisará verificar mais condições.

Eu uso uma fórmula muito simples que funciona bem com meu pequeno mecanismo isométrico no OpenGL:

Cada um de vocês (árvores, ladrilhos, caracteres, ...) tem uma posição X e Y na tela. Você precisa ativar o DEPTH TESTING e encontrar o bom valor de Z para cada valor. Você pode simplesmente o seguinte:

z = x + y + objectIndex

Uso um índice diferente para o piso e os objetos que estarão acima do piso (0 para o piso e 1 para todos os objetos que têm altura). Isso deve funcionar muito bem.

Resposta abrangente com várias soluções, imagens e toda a matemática aqui:

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

Se você comparar os valores y na mesma posição x, ele funcionará sempre. Portanto, não compare centro a centro. Em vez disso, compare o centro de um sprite com a mesma posição x no outro sprite.

Mas isso requer alguns dados de geometria para cada sprite. Pode ser tão fácil quanto dois pontos dos lados esquerdo e direito que descrevem o limite inferior para o sprite. Ou você pode analisar os dados da imagem dos sprites e encontrar o primeiro pixel que não é transparente.

Uma abordagem mais fácil é dividir todos os sprites em três grupos: diagonal ao longo do eixo x, diagonal ao longo do eixo y e plana. Se dois objetos forem ambos diagonais no mesmo eixo, classifique-os com base no outro eixo.

Você precisa atribuir IDs exclusivos a todos os objetos do mesmo tipo. Em seguida, você classifica todos os objetos por suas posições e desenha grupos de objetos na ordem de seus IDs. Para que o objeto 1 no grupo A nunca substitua o objeto 2 no grupo A etc.

Esta não é realmente uma resposta, mas apenas um comentário e uma votação que gostaria de dar à resposta deste axel22 aqui /gamedev//a/8181/112940

Não tenho reputação suficiente para votar ou comentar outras respostas, mas o segundo parágrafo de sua resposta é provavelmente a coisa mais importante que se deve ter em mente ao tentar classificar as entidades em um jogo isométrico sem depender do 3D "moderno" técnicas como um buffer Z.

No meu motor, eu queria fazer coisas "old-school", 2D puro. E gastei muito tempo tentando entender por que minha chamada para "classificar" (no meu caso era c ++ std :: sort) não estava funcionando corretamente em determinadas configurações de mapas.

Somente quando percebi que essa é uma situação de "ordem parcial" é que consegui resolvê-la.

Até agora, todas as soluções de trabalho que encontrei na Web usavam algum tipo de classificação topológica para lidar com o problema corretamente. A classificação topológica parece ser o caminho a percorrer.