Comment déterminer l'ordre de tirage dans un jeu flash en vue isométrique?

12

C'est pour un jeu flash, avec vue isométrique. J'ai besoin de savoir comment trier un objet pour qu'il n'y ait pas besoin de vérifier le z-buffer lors du dessin. Cela peut sembler facile, mais il y a une autre restriction, une scène peut avoir plus de 10 000 objets, donc l'algorithme doit être exécuté en moins de O (n ^ 2). Tous les objets sont des boîtes rectangulaires et 3-4 objets se déplacent dans la scène. Quelle est la meilleure façon de procéder?

MISE À JOUR

dans chaque tuile, il n'y a qu'un objet (je veux dire que les objets ne peuvent pas s'empiler les uns sur les autres). et nous accédons à la fois à la carte des objets et les objets ont leur propre position.

UPDATE2

voir ces chiffres:

entrez la description de l'image ici entrez la description de l'image ici

dans le premier un premier objet bleu doit être dessiné puis vert puis rouge. tandis que dans le second, vous devez les dessiner dans l'ordre inverse. vous devez d'abord dessiner un objet rouge, puis vert et enfin bleu. comme vous pouvez le voir, il n'y a pas de différence de position entre les objets bleus et rouges, ils ont tous deux une distance différente de la caméra, etc. mais en raison de leur position relative par rapport à la boîte verte, vous devez modifier leur ordre de dessin entre deux images. c'est ce qui fait de ce problème un gâchis.

note latérale: puisque tous les objets sont des prismes rectangulaires, il est mathématiquement prouvable qu'il existe au moins un ordre de dessin pour satisfaire les besoins du problème.

Ali1S232
la source
2
Vous devez publier plus d'informations. Les objets peuvent-ils s'empiler (3d)? Les objets ont des positions ou la carte a des objets? etc.
kaoD
2
Est-ce la même chose que gamedev.stackexchange.com/questions/8151/…
Tetrad
@Tetrad oui, mais il y a un peu de différence sur les objets que nous mettons dans la scène.
Ali1S232
Les objets @Gajet (après votre mise à jour) ne peuvent être que 1 * X et X * 1 ou également X * Y? Pourriez-vous vous permettre de diviser les objets en plusieurs sous-objets? (comme le vert étant 4 objets sous-verts) L'orientation de l'objet est-elle fixe?
kaoD
Aussi: combien de tuiles adjacentes la hauteur de votre objet obscurcit-elle?
kaoD

Réponses:

8

C'est en fait très simple si vos objets correspondent à vos carreaux isométriques. Jetez un oeil à cette image:

Ordre de dessin isométrique

Vous devez d'abord dessiner l'objet en position rouge, puis les objets en bleu, puis en vert, puis en jaune, puis en magenta, etc. ayant la position comme attribut. Si ce n'est pas votre cas, vous devez conserver une structure de données distincte, la mettre à jour chaque fois qu'un objet se déplace (ce qui devrait également être assez facile.)

Cela a un nouveau problème: vous pouvez facilement voir comment maintenant sa complexité est O (N) où N est la taille de votre carte ( N=W*H). Pour surmonter ce problème, créez simplement une nouvelle structure de données linéaire où chaque index de votre structure correspond à une profondeur donnée, en la mettant à jour chaque fois qu'un objet change de profondeur.

Le cas où un objet ne correspond pas à une seule tuile est un peu plus difficile, donc je le posterai si vous en avez besoin dès que vous mettez à jour votre question.

kaoD
la source
cet algorithme est également le premier qui m'est venu à l'esprit, mais voyez ma mise à jour, c'est pourquoi vous ne pouvez pas l'utiliser sans changement.
Ali1S232
1
@Gajet et c'est le genre de chose que vous devez publier dans votre question en premier lieu: P
kaoD
3
C'est la voie à suivre, divisez les grandes pièces en «tuiles» +1
Valmond
2

Je n'ai aucune connaissance particulière à ce sujet, mais voici une pensée.

Commencez par marquer chaque cellule comme "non dessinée". (Ou, de manière équivalente, utilisez un tableau pour représenter l'emplacement de la chose "dessinée" la plus proche sur chaque "ligne presque éloignée" de cellules, ou un ensemble, etc.) Ensuite, pour chaque cellule (je les parcourrais probablement dans l'ordre décrit par kaoD): vérifiez si cette cellule a été dessinée; s'il n'a pas été dessiné et contient un objet, vérifiez si chaque cellule qui serait obscurcie par cet objet a été dessinée et sinon dessinez-la récursivement; dessinez l'objet contenu par cette cellule si nécessaire; et marquez cette cellule et toutes les cellules occupées par son objet comme "dessinées".

Je suppose que vous pouvez rapidement mapper une cellule à l'objet à l'intérieur, le cas échéant. Je crois que c'est le temps O (n), bien qu'il puisse finir par construire une grande pile (que vous voudrez peut-être transformer en une liste liée si vous craignez de manquer d'espace de pile).

Si vous avez vraiment besoin d'une liste, vous pouvez l'ajouter à une liste au lieu de la dessiner. Je soupçonne que commencer avec une liste principalement triée n'aide pas.

Vincent Povirk
la source
Je crois que cet algorithme peut être vu comme une forme de tri topologique adapté au problème; J'étais sur le point de m'orienter vaguement dans cette direction. Le tri topologique est une solution à la plupart des problèmes de commande / dépendance.
Kevin Reid
1

J'utiliserais l'algorithme du peintre avec une distance en taxi de la cellule la plus éloignée de la caméra, en dessinant d'abord celles qui sont les plus proches de la caméra, puis en se déplaçant vers l'extérieur.

Modifier: cela ne fonctionne que si vous pouvez dessiner le contenu de chaque cellule individuellement.

Quasiperfect
la source
cela pourrait fonctionner, mais je ne peux pas dire en quoi il diffère des algorithmes byte56 ou kaoD suggérés. il me semble qu'il a toujours les mêmes problèmes que ceux décrits dans ma deuxième édition.
Ali1S232
1

Qu'est-ce qui vous fait croire qu'il est «mathématiquement prouvable qu'il existe au moins un ordre de tirage pour répondre aux besoins du problème»? Voici un contre-exemple trivial où vous ne pouvez pas vous fier aux objets de tri z:

entrez la description de l'image ici

sam hocevar
la source
Par simple curiosité ... pourriez-vous élaborer le contre-exemple? Ce n'est pas une grille.
kaoD
notez bien qu'il n'y a qu'un seul objet sur chaque tuile, et l'objet peut occuper une ou plusieurs tuiles, mais elles ont toujours une projection rectangulaire sur le plan. ces deux conditions suffisent à prouver cette affirmation.
Ali1S232
D'accord, avec ces restrictions et le fait que la grille soit plate, il y a une solution. Je le posterai plus tard.
sam hocevar