Comment trier les sprites isométriques dans le bon ordre?

Dans un jeu 2D descendant normal, on pourrait utiliser l'axe y de l'écran pour trier les images. Dans cet exemple, les arbres sont correctement triés mais les murs isométriques ne le sont pas:

Le mur 2 est un pixel en dessous du mur 1, il est donc dessiné après le mur 1 et se termine sur le dessus.

Si je trie par l'axe y isométrique, les murs apparaissent dans le bon ordre mais les arbres ne le font pas:

Comment dois-je procéder correctement?

Les jeux isométriques sont fonctionnellement en 3D, donc en interne, vous devez stocker les coordonnées 3D pour chaque entité du jeu. Les coordonnées réelles que vous choisissez sont arbitraires, mais disons que X et Y sont les deux axes au sol, et Z est au-dessus du sol dans les airs.

Le moteur de rendu doit ensuite projeter cela en 2D pour dessiner des éléments à l'écran. "Isométrique" est une de ces projections. La projection isométrique de la 3D à la 2D est assez simple. Disons que l'axe X va de haut en bas à bas à droite et descend d'un pixel pour deux pixels horizontaux. De même, l'axe Y va de haut en bas à bas à gauche. L'axe Z monte tout droit. Pour convertir de 3D en 2D, il suffit alors:

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

Passons maintenant à votre question d'origine, le tri. Maintenant que nous travaillons avec nos objets directement en 3D, le tri devient beaucoup plus simple. Dans notre espace de coordonnées ici, le sprite le plus éloigné a les coordonnées x, y et z les plus basses (c'est-à-dire que les trois axes pointent de l'écran). Donc, vous les triez simplement par la somme de ceux-ci:

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

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

Pour éviter de trier à nouveau vos entités à chaque trame, utilisez un tri par pigeonnier, détaillé ici .

En supposant que vos sprites occupent des ensembles de carreaux qui sont des rectangles (s'ils occupent des ensembles arbitraires, vous ne pouvez pas du tout dessiner correctement dans le cas général), le problème est qu'il n'y a pas de relation d'ordre total entre les éléments, donc vous ne pouvez pas trier les utilisant un tri qui entraînerait des comparaisons O (nlogn).

Notez que pour deux objets A et B, A doit être dessiné avant B (A <- B), B doit être dessiné avant A (B <- A) ou ils peuvent être dessinés dans n'importe quel ordre. Ils forment un ordre partiel. Si vous vous dessinez quelques exemples avec 3 objets qui se chevauchent, vous remarquerez peut-être que même si le 1er et le 3ème objet ne se chevauchent pas, n'ayant donc pas de dépendance directe, leur ordre de dessin dépend du 2ème objet qui les sépare - selon la façon dont vous le placez, vous obtiendrez différents ordres de dessin. Conclusion - les tris traditionnels ne fonctionnent pas ici.

Une solution consiste à utiliser la comparaison (mentionnée par le Dani) et à comparer chaque objet les uns aux autres pour déterminer leurs dépendances et former un graphe de dépendances (qui sera un DAG). Effectuez ensuite un tri topologique sur le graphique pour déterminer l'ordre de dessin. S'il n'y a pas trop d'objets, cela peut être assez rapide (c'estO(n^2) ).

Une autre solution consiste à utiliser un (pour l'équilibrage - pseudo ) arbre quadruple et à y stocker les rectangles de tous les objets.

Ensuite, parcourez tous les objets X et utilisez l'arborescence quadruple pour vérifier s'il y a des objets Y dans la bande au-dessus de l'objet X qui commence par le plus à gauche et se termine par le coin le plus à droite de l'objet X - pour tous ces Y, Y < - X. Comme ça, vous devrez toujours former un graphe et trier topologiquement.

Mais vous pouvez l'éviter. Vous utilisez une liste d'objets Q et une table d'objets T. Vous parcourez tous les emplacements visibles des valeurs les plus petites aux plus grandes sur l'axe des x (une ligne), en allant ligne par ligne sur l'axe des y. S'il y a un coin inférieur d'un objet à cet emplacement, effectuez la procédure ci-dessus pour déterminer les dépendances. Si un objet X dépend d'un autre objet Y qui est en partie au-dessus de lui (Y <- X), et que chacun de ces Y est déjà dans Q, ajoutez X à Q. S'il y a un Y qui n'est pas dans Q, ajoutez X à T et dénotons Y <- X. Chaque fois que vous ajoutez un objet à Q, vous supprimez les dépendances des objets en attente dans T. Si toutes les dépendances sont supprimées, un objet de T est déplacé vers Q.

Nous supposons que les sprites d'objets ne sortent pas de leurs emplacements en bas, à gauche ou à droite (uniquement en haut, comme les arbres dans votre image). Cela devrait améliorer les performances d'un grand nombre d'objets. Cette approche sera à nouveau O(n^2), mais seulement dans le pire des cas, qui comprend des objets de taille étrange et / ou des configurations d'objets étranges. Dans la plupart des cas, c'est le cas O(n * logn * sqrt(n)). La connaissance de la hauteur de vos sprites peut éliminer le sqrt(n), car vous n'avez pas à vérifier toute la bande ci-dessus. Selon le nombre d'objets à l'écran, vous pouvez essayer de remplacer l'arborescence quadruple par un tableau indiquant les emplacements à prendre (cela a du sens s'il y a beaucoup d'objets).

Enfin, n'hésitez pas à inspecter ce code source pour trouver des idées: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala

Je ne pense pas qu'il existe de solution mathématique. Vous n'avez probablement pas assez de données dans le monde 2D dans lequel vos objets vivent. Si vos murs étaient reflétés sur X, ils seraient dans le "bon" ordre. Là encore, vous pourriez peut-être faire des tests de chevauchement avec le cadre de délimitation de l'image, mais c'est un domaine que je ne connais pas.

Vous devriez probablement trier par écran Y par tuile et dire que tout ce qui est plus compliqué est un "problème de conception". Par exemple, si vous créez le contenu, dites simplement à vos concepteurs l'algorithme de tri et placez wall2 2 pixels pour résoudre le problème. C'est ainsi que nous avons dû le corriger dans le jeu isométrique sur lequel j'ai travaillé. Cela peut inclure la prise d'objets "longs" et leur décomposition en morceaux de la taille d'une tuile.

Si vous autorisez les utilisateurs à modifier le contenu, la chose la plus sûre à faire est de faire en sorte que tout soit basé sur des tuiles et au maximum une tuile. De cette façon, vous évitez le problème. Vous pourriez peut-être vous en sortir en faisant tout plus grand qu'une tuile, mais peut-être seulement si elle est carrée. Je n'ai pas joué avec ça.

Un tri isométrique parfait est difficile. Mais pour une première approche, pour trier correctement vos articles, vous devez utiliser une fonction de comparaison plus complexe avec chaque objet qui se chevauchent. Cette fonction doit vérifier cette condition: Un objet se chevauchant "a" est derrière "b" si:

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

Bien sûr, c'est une première idée pour une implémentation isométrique naïve. Pour un scénario plus complexe (si vous voulez une rotation de vue, des positions par pixel sur l'axe z, etc.), vous devrez vérifier plus de conditions.

J'utilise une formule très simple qui fonctionne bien avec mon petit moteur isométrique en OpenGL:

Chacun de vous (arbres, carreaux de sol, personnages, ...) a une position X et Y à l'écran. Vous devez activer le TEST DE PROFONDEUR et trouver la bonne valeur Z pour chaque valeur. Vous pouvez simplement accéder aux éléments suivants:

z = x + y + objectIndex

J'utilise un index différent pour le sol et les objets qui seront au-dessus du sol (0 pour le sol et 1 pour tous les objets qui ont une hauteur). Cela devrait très bien fonctionner.

Réponse complète avec plusieurs solutions, images et tous les calculs ici:

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

Si vous comparez les valeurs y à la même position x, cela fonctionnera à chaque fois. Donc, ne comparez pas centre à centre. Comparez plutôt le centre d'un sprite avec la même position x sur l'autre sprite.

Mais cela nécessite des données de géométrie pour chaque sprite. Cela pourrait être aussi simple que deux points de gauche à droite qui décrivent la limite inférieure du sprite. Ou, vous pouvez analyser les données d'image des sprites et trouver le premier pixel qui n'est pas transparent.

Une approche plus simple consiste à diviser tous les sprites en trois groupes: diagonale le long de l'axe x, diagonale le long de l'axe y et plate. Si deux objets sont tous deux diagonaux le long du même axe, triez-les en fonction de l'autre axe.

Vous devez attribuer des identifiants uniques à tous les objets du même type. Ensuite, vous triez tous les objets par leur position et dessinez des groupes d'objets dans l'ordre de leurs identifiants. Pour que l'objet 1 du groupe A ne dépasse jamais l'objet 2 du groupe A, etc.

Ce n'est pas vraiment une réponse, mais juste un commentaire et un vote positif que je voudrais donner à la réponse de cet axel22 ici /gamedev//a/8181/112940

Je n'ai pas assez de réputation pour voter ou commenter d'autres réponses, mais le deuxième paragraphe de sa réponse est probablement la chose la plus importante à prendre en compte lorsque l'on essaie de trier les entités dans un jeu isométrique sans s'appuyer sur la 3D "moderne" des techniques comme un Z-buffer.

Dans mon moteur, je voulais faire des choses "old-school", pure 2D. Et j'ai passé beaucoup de temps à essayer de comprendre pourquoi mon appel à "trier" (dans mon cas c'était c ++ std :: sort) ne fonctionnait pas correctement sur certaines configurations de carte.

Ce n'est que lorsque j'ai réalisé qu'il s'agissait d'une situation "d'ordre partiel" que j'ai pu la résoudre.

Jusqu'à présent, toutes les solutions de travail que j'ai trouvées sur le Web ont utilisé une sorte de tri topologique pour traiter correctement le problème. Le tri topologique semble être la voie à suivre.