Travailler avec beaucoup de cubes. Amélioration des performances?

Edit: Pour résumer la question, j'ai un monde basé sur les voxels (style Minecraft (Merci Communist Duck)) qui souffre de mauvaises performances. Je ne suis pas positif sur la source, mais j'aimerais avoir des conseils sur la façon de s'en débarrasser.

Je travaille sur un projet où un monde se compose d'une grande quantité de cubes (je vous donnerais un nombre, mais ce sont des mondes définis par l'utilisateur). Mon test est autour de blocs (48 x 32 x 48).

Fondamentalement, ces blocs ne font rien en eux-mêmes. Ils sont juste assis là.

Ils commencent à être utilisés pour l'interaction avec les joueurs.

J'ai besoin de vérifier avec quels cubes la souris des utilisateurs interagit (survol, clic, etc.) et pour détecter les collisions lorsque le joueur se déplace.

Maintenant, j'ai eu un énorme décalage au début, parcourant chaque bloc.

J'ai réussi à réduire ce décalage, en parcourant tous les blocs et en trouvant quels blocs se trouvent dans une plage particulière du personnage, puis en bouclant uniquement ces blocs pour la détection de collision, etc.

Cependant, je vais toujours à un 2fps déprimant.

Quelqu'un at-il d'autres idées sur la façon dont je pourrais réduire ce décalage?

Btw, j'utilise XNA (C #) et oui, c'est 3d.

On dirait que vous cherchez à en apprendre davantage sur les arbres!

Et je suis sérieux, si vous parcourez actuellement un tableau de tous vos cubes, alors vous devriez vraiment examiner différentes structures de données spatiales. Dans ce cas, la meilleure façon de réimaginer votre monde de cube est comme un arbre.

Avant d'entrer dans les raisons pour lesquelles, réfléchissons à notre problème. Nous recherchons une solution où, pour le moins de frais possible, nous pouvons récupérer une liste des cubes à proximité avec lesquels le joueur peut entrer en collision. Cette liste doit être aussi petite, mais précise que possible.

Maintenant, pour déterminer cette zone, nous devons mapper l'espace de coordonnées de notre joueur à l'espace de coordonnées de la carte du cube; c'est-à-dire que nous devons mapper la position en virgule flottante du lecteur sur un index discret du tableau multidimensionnel de cubes (par exemple, la notation pourrait être world[31][31][31], c'est-à-dire le milieu exact pour un tableau multidimensionnel 64 * 64 * 64).

Nous pourrions simplement calculer les blocs environnants en utilisant cette même indexation discrète, en échantillonnant peut-être uniquement les cubes voisins, mais cela nécessite toujours un recalcul constant et ne permet aucun objet dont l'emplacement n'est pas discret (c.-à-d. Qui peut ne pas correspondre au cube carte).

La situation idéale est un ensemble de seaux qui contiennent nos ensembles de cubes pour des sections particulières de notre carte de cubes, divisés également afin qu'au lieu de recalculer la zone environnante, nous entrons et sortons simplement de ces zones . Pour tout calcul non trivial, conserver nos données de cette manière pourrait éliminer l'itération de tous les cubes, et uniquement de ces ensembles individuels qui se trouvent à proximité.

La question est: comment mettre en œuvre cela?

Pour le monde 64 * 64 * 64, imaginez qu'il se décompose en 8 * 8 * 8 zones . Cela signifie que dans votre monde, vous aurez 8 zones par axe (X, Y, Z). Chacune de ces zones contiendra 8 cubes, facilement récupérables grâce à ce nouvel index simplifié.

Si vous deviez effectuer une opération sur un ensemble de cubes voisins, au lieu d'itérer chaque cube de votre monde, vous pouvez simplement parcourir ces zones , décomposant le nombre maximal d'itérations des 64 * 64 * 64 d'origine (262144) à seulement 520 (8 * 8 * 8 + 8).

Maintenant, effectuez un zoom arrière sur ce monde de zones et placez les zones dans des super-zones plus grandes ; où chaque super-zone contient 2 * 2 * 2 zones régulières . En tant que votre monde contient actuellement 512 (8 * 8 * 8) zones , nous pouvons briser les 8 * 8 * 8 zones en 64 (4 * 4 * 4) super-zones en divisant 8 zones par 2 zones par super-zone . En appliquant la même logique que ci-dessus, cela briserait les itérations maximales de 512 à 8 pour trouver la super-zone ; puis un maximum de 64 pour trouver la zone de progression(total max 72)! Vous pouvez voir comment cela vous fait déjà économiser beaucoup d'itérations (262144: 72).

Je suis sûr que vous pouvez voir maintenant à quel point les arbres sont utiles. Chaque zone est une branche sur l'arbre, avec chaque super-zone comme branche précédente. Vous parcourez simplement l'arbre pour trouver ce dont vous avez besoin; en utilisant des ensembles de données plus petits pour minimiser le coût global.

Le diagramme ci-dessous devrait vous aider à visualiser le concept. (image de Wikipedia: Octrees ):

Avertissement:

Dans une configuration idéale comme ci-dessus, où votre monde de voxels est déjà disposé dans un tableau multidimensionnel de taille fixe, vous pouvez simplement interroger la position du joueur, puis indexer les blocs environnants avec un coût O (1)! (Voir l'explication d'Olhovskys) Mais cela devient plus difficile lorsque vous commencez à considérer que votre monde est rarement de taille fixe dans un jeu de voxels; et vous pourriez avoir besoin de votre structure de données pour pouvoir charger des super-zones entières du disque dur dans la mémoire. Contrairement à un tableau multidimensionnel de taille fixe, les arbres le permettent facilement sans trop de temps consacré aux algorithmes combinatoires.

Je suis d'accord avec la réponse de Daniels, en ce sens que l'itération à travers de grandes quantités de boîtes est la cause la plus probable, et qu'en utilisant le partitionnement spatial, vous pouvez accélérer le jeu beaucoup - mais le problème pourrait également être ailleurs et vous pourriez perdre votre temps .

Afin d'augmenter considérablement la vitesse de votre jeu, vous devez profiler votre code. Identifiez où se trouve le goulot d'étranglement, cela vous permettra d'apporter les plus grandes améliorations.

Il existe de nombreuses façons de profiler votre code, vous pouvez rouler votre propre classe d'analyse des performances (qui pourrait utiliser la classe Stopwatch (MSDN) ), ou vous pouvez utiliser PIX pour avoir une idée générale de l'occupation du CPU / GPU .

Vous pouvez également placer des marqueurs d'événement PIX dans votre code, qui s'afficheront sous forme de régions colorées dans les affichages PIX. Il n'y a pas d'interface C # officielle pour ces fonctions, mais ce fil vous montre comment créer vous-même une interface C #.

Si votre lecteur est grand par rapport à la taille des cubes, alors vous voulez probablement un octree ou une autre structure de partitionnement spatial, comme d'autres l'ont suggéré.

Cependant, si votre joueur est petit par rapport à la taille des cubes, alors le moyen le plus rapide pour détecter une collision avec les cubes est de faire une recherche linéaire simple de la zone autour du joueur.

Étant donné que votre joueur est plus petit que 1 cube, il vous suffit de tester la collision contre les 27 cubes voisins, tout au plus.

Cela suppose que vous stockez les cubes dans un tableau dans lequel vous pouvez indexer, avec un emplacement dans le tableau pour chaque cube.

Comme d'autres l'ont souligné, vous devez profiler votre code pour voir ce qui vous ralentit réellement.

Si je devais deviner cependant, je dirais que vous faites probablement un appel de tirage pour chaque cube, ce qui serait de loin votre goulot d'étranglement. Pour résoudre ce problème, vous devez examiner l'instanciation de la géométrie.

Une autre suggestion pour accélérer les choses: vos blocs sont approximativement fixes - cela signifie qu'il n'y a aucun moyen qu'un joueur puisse entrer en collision avec la plupart d'entre eux. Ajoutez un booléen aux blocs indiquant s'ils sont exposés ou non. (Cela peut être recalculé en regardant leurs voisins.) Un bloc qui n'est pas exposé n'a pas besoin d'être vérifié pour les collisions.

Il est évident que Minecraft fait quelque chose de similaire à cela - j'ai frappé un morceau non chargé une fois qui m'a donné une vue sur le monde - je pouvais voir à travers le sol solide, tout ce qui s'est révélé était les espaces ouverts (le côté le plus éloigné de c'était une surface exposée et donc rendue.)

J'ai eu ce problème avec mon moteur voxel.

Solution: (beaucoup plus simple que les octets) Au lieu de parcourir tous les blocs, utilisez simplement une équation pour déterminer la position du bloc dans le tableau des blocs.

BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;

Ensuite, si vous voulez voir si un bloc existe:

Blocks[BlockIndex].Type > -1;

Ou comme vous déterminez si le bloc existe.