¿Cómo clasifico los sprites isométricos en el orden correcto?

En un juego 2D de arriba hacia abajo normal, uno podría usar el eje y de la pantalla para ordenar las imágenes. En este ejemplo, los árboles están ordenados correctamente, pero las paredes isométricas no:

El muro 2 está un píxel debajo del muro 1, por lo tanto, se dibuja después del muro 1 y termina en la parte superior.

Si clasifico por el eje isométrico y, las paredes aparecen en el orden correcto pero los árboles no:

¿Cómo hago esto correctamente?

Los juegos isométricos son funcionalmente 3D, por lo que internamente, debe almacenar las coordenadas 3D para cada entidad en el juego. Las coordenadas reales que eliges son arbitrarias, pero digamos que X e Y son los dos ejes en el suelo, y Z está despegado en el aire.

El renderizador necesita proyectar eso en 2D para dibujar cosas en la pantalla. "Isométrica" ​​es una de esas proyecciones. Proyectar de 3D a 2D isométricamente es bastante simple. Digamos que el eje X va de arriba a la izquierda a abajo a la derecha y hacia abajo un píxel por cada dos píxeles horizontales. Del mismo modo, el eje Y va de arriba a la derecha a abajo a la izquierda. El eje Z va hacia arriba. Para convertir de 3D a 2D, entonces es solo:

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

Ahora a su pregunta original, ordenando. Ahora que estamos trabajando con nuestros objetos directamente en 3D, la clasificación se vuelve mucho más simple. En nuestro espacio de coordenadas aquí, el sprite más alejado tiene las coordenadas x, y y z más bajas (es decir, los tres ejes apuntan desde la pantalla). Así que simplemente los ordena por la suma de esos:

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 reordenar sus entidades en cada cuadro, use una clasificación de casilleros, detallada aquí .

Suponiendo que sus sprites ocupan conjuntos de mosaicos que son rectángulos (si ocupan conjuntos arbitrarios, entonces no puede dibujar correctamente en el caso general), el problema es que no hay una relación de orden total entre los elementos, por lo que no puede ordenar usando un tipo que resultaría en comparaciones O (nlogn).

Tenga en cuenta que para cualquiera de los dos objetos A y B, A debe dibujarse antes de B (A <- B), B debe dibujarse antes de A (B <- A) o pueden dibujarse en cualquier orden. Forman un orden parcial. Si dibuja algunos ejemplos con 3 objetos superpuestos, puede notar que aunque el primer y el tercer objeto no se superpongan, por lo que no tienen una dependencia directa, su orden de dibujo depende del segundo objeto que esté entre ellos, dependiendo de cómo Si lo coloca, obtendrá diferentes órdenes de dibujo. En pocas palabras: los tipos tradicionales no funcionan aquí.

Una solución es usar la comparación (mencionada por Dani) y comparar cada objeto entre sí para determinar sus dependencias y formar un gráfico de dependencia (que será un DAG). Luego, haga una ordenación topológica en el gráfico para determinar el orden de dibujo. Si no hay demasiados objetos, esto puede ser lo suficientemente rápido (es O(n^2)).

Otra solución es usar un árbol cuádruple (para equilibrar - pseudo ) y almacenar los rectángulos de todos los objetos en él.

Luego, recorra todos los objetos X y use el árbol cuádruple para verificar si hay algún objeto Y en la franja sobre el objeto X, que comienza con el extremo izquierdo y termina con la esquina derecha del objeto X, para todos esos Y, Y < - X. De esta manera, aún tendrá que formar un gráfico y ordenarlo topológicamente.

Pero puedes evitarlo. Utiliza una lista de objetos Q y una tabla de objetos T. Usted itera todas las ranuras visibles de valores más pequeños a más grandes en el eje x (una fila), yendo fila por fila en el eje y. Si hay una esquina inferior de un objeto en esa ranura, realice el procedimiento anterior para determinar las dependencias. Si un objeto X depende de otro objeto Y que está parcialmente por encima de él (Y <- X), y cada uno de estos Y ya está en Q, agregue X a Q. Si hay algo de Y que no está en Q, agregue X a T y denota que Y <- X. Cada vez que agrega un objeto a Q, elimina las dependencias de los objetos pendientes en T. Si se eliminan todas las dependencias, un objeto de T se mueve a Q.

Asumimos que los sprites de los objetos no se asoman desde sus ranuras en la parte inferior, izquierda o derecha (solo en la parte superior, como los árboles en su imagen). Esto debería mejorar el rendimiento de una gran cantidad de objetos. Este enfoque volverá a serlo O(n^2), pero solo en el peor de los casos, que incluye objetos de tamaños extraños y / o configuraciones extrañas de objetos. En la mayoría de los casos, lo es O(n * logn * sqrt(n)). Conocer la altura de tus sprites puede eliminar el sqrt(n), porque no tienes que verificar toda la franja de arriba. Dependiendo del número de objetos en la pantalla, puede intentar reemplazar el árbol cuádruple con una matriz que indique qué ranuras se toman (tiene sentido si hay muchos objetos).

Finalmente, siéntase libre de inspeccionar este código fuente para algunas ideas: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala

No creo que haya una solución matemática. Probablemente no tenga suficientes datos en el mundo 2D en el que viven sus artículos. Si sus paredes se reflejaran en X, estarían en el orden "correcto". Por otra parte, es posible que pueda realizar pruebas de superposición con el cuadro delimitador de la imagen de alguna manera, pero esta es un área con la que no estoy familiarizado.

Probablemente debería ordenar por pantalla Y por mosaico y decir que cualquier cosa más complicada es un "problema de diseño". Por ejemplo, si está creando el contenido, solo dígales a sus diseñadores el algoritmo de clasificación y empuje wall2 2 píxeles hacia arriba para solucionar el problema. Así es como tuvimos que arreglarlo en el juego isométrico en el que trabajé. Esto podría incluir tomar elementos "largos" y dividirlos en trozos del tamaño de un mosaico.

Si permite que los usuarios editen el contenido, lo más seguro es hacer que todo esté basado en mosaicos y, como máximo, un mosaico grande. De esa manera evitas el problema. Es posible que pueda sobrevivir haciendo todo más grande que un mosaico, pero posiblemente solo si es cuadrado. No he jugado con eso.

La clasificación isométrica perfecta es difícil. Pero para un primer enfoque, para ordenar adecuadamente sus elementos, debe usar una función de comparación más compleja con cada objeto superpuesto. Esta función debe verificar esta condición: un objeto superpuesto "a" está detrás de "b" si:

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

Por supuesto, esta es una primera idea para una implementación isométrica ingenua. Para un escenario más complejo (si desea ver la rotación, las posiciones por píxel en el eje z, etc.) deberá verificar más condiciones.

Utilizo una fórmula muy simple que funciona bien con mi pequeño motor isométrico en OpenGL:

Cada uno de ustedes objetos (árboles, baldosas, personajes, ...) tienen una posición X e Y en la pantalla. Debe habilitar las PRUEBAS DE PROFUNDIDAD y encontrar el buen valor Z para cada valor. Puede simplemente a lo siguiente:

z = x + y + objectIndex

Utilizo un índice diferente para el piso y los objetos que estarán sobre el piso (0 para el piso y 1 para todos los objetos que tienen una altura). Esto debería funcionar bien.

Amplia respuesta con múltiples soluciones, imágenes y todas las matemáticas aquí:

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

Si compara los valores de y en la misma posición x, funcionará siempre. Por lo tanto, no compare centro a centro. En su lugar, compare el centro de un sprite con la misma posición x en el otro sprite.

Pero, esto requiere algunos datos de geometría para cada sprite. Podría ser tan fácil como dos puntos de los lados izquierdo a derecho que describen el límite inferior del sprite. O bien, puede analizar los datos de imagen de sprites y encontrar el primer píxel que no es transparente.

Un enfoque más fácil es dividir todos los sprites en tres grupos: diagonal a lo largo del eje x, diagonal a lo largo del eje y y plano. Si dos objetos son diagonales a lo largo del mismo eje, ordénelos según el otro eje.

Debe asignar identificadores únicos a todos los objetos del mismo tipo. Luego, clasifica todos los objetos por sus posiciones y dibuja grupos de objetos en orden de identificación. De modo que el objeto 1 en el grupo A nunca sobregirará el objeto 2 en el grupo A, etc.

Esto no es realmente una respuesta, sino solo un comentario y un voto positivo que me gustaría dar a la respuesta de axel22 aquí /gamedev//a/8181/112940

No tengo suficiente reputación para votar ni comentar otras respuestas, pero el segundo párrafo de su respuesta es probablemente lo más importante que uno debe tener en cuenta al tratar de clasificar las entidades en un juego isométrico sin depender de 3D "moderno" técnicas como un Z-buffer.

En mi motor quería hacer cosas "de la vieja escuela", puro 2D. Y pasé mucho tiempo reventando mi cerebro tratando de entender por qué mi llamada a "ordenar" (en mi caso era c ++ std :: sort) no funcionaba correctamente en ciertas configuraciones de mapas.

Solo cuando me di cuenta de que esta es una situación de "orden parcial" fue que pude resolverlo.

Hasta ahora, todas las soluciones de trabajo que he encontrado en la web utilizan algún tipo de clasificación topológica para tratar el problema correctamente. La clasificación topológica parece ser el camino a seguir.