Je me suis toujours posé cette question. Dans un jeu comme GTA où il y a des dizaines de milliers d'objets, comment le jeu sait-il dès que vous êtes sur un paquet de santé ?
Il ne peut pas y avoir un écouteur d'événements pour chaque objet ? L'itération n'est pas bonne non plus ? Je me demande juste comment c'est réellement fait.
Il n'y a pas de réponse unique à cette question, mais les mondes de grande taille sont souvent divisés en espace en utilisant quelque chose de l'ordre du Quadtree ou kd-tree qui ramène les temps de recherche des plus proches voisins en dessous du temps linéaire (puissance fractionnaire, ou au pire O( N^(2/3) ) pour un jeu 3D). Ces méthodes sont souvent appelées BSP pour le partitionnement de l'espace binaire.
En ce qui concerne la détection des collisions, chaque objet a aussi généralement une volume limite maillage (ensemble de polygones formant une coque convexe) qui lui est associé. Ces maillages très simplifiés (parfois un simple cube) ne sont pas dessinés mais sont utilisés dans la détection des collisions. La méthode la plus rudimentaire consiste à créer un plan perpendiculaire à la ligne reliant les points médians de chaque objet, le plan coupant la ligne au point médian de celle-ci. Si le volume limite d'un objet comporte des points de part et d'autre de ce plan, il s'agit d'une collision (il suffit de tester l'un des deux volumes limites par rapport au plan). Une autre méthode est la méthode améliorée GJK algorithme de distance. Si vous souhaitez vous plonger dans un tutoriel, consultez le site Leçon OpenGL #30 de NeHe Productions .
Par ailleurs, les volumes limites peuvent également être utilisés pour d'autres optimisations telles que ce que l'on appelle les requêtes d'occlusion . Il s'agit de déterminer quels objets se trouvent derrière d'autres objets (occluders) et ne doivent donc pas être traités/rendus. Les volumes limites peuvent également être utilisés pour abattage de troncs d'arbres qui consiste à déterminer les objets qui se trouvent en dehors du volume de vision en perspective (trop près, trop loin ou au-delà de l'angle de votre champ de vision) et qui n'ont donc pas besoin d'être rendus.
Comme l'a fait remarquer Kylotan, l'utilisation d'un volume englobant peut générer des faux positifs lors de la détection de l'occlusion et ne fonctionne tout simplement pas du tout pour certains types d'objets tels que les tores (par exemple, regarder à travers le trou d'un beignet). La détection correcte de l'occlusion de ce type d'objets est un tout autre sujet sur le site de suppression des portails .
Quadtrees et octrees , un autre quadtree Il existe des moyens populaires, utilisant le partitionnement de l'espace, pour y parvenir. L'exemple suivant montre une réduction de 97 % du traitement par rapport à une recherche brute de collisions paire par paire.
La méthode "sweep-and-prune" est une technique courante dans les moteurs physiques de jeux. Cette méthode est expliquée dans Notes de David Baraff sur le SIGGRAPH (voir le chapitre Mouvement avec contraintes). Havok l'utilise certainement, je pense que c'est une option dans Bullet, mais je ne suis pas sûr pour PhysX.
L'idée est que vous pouvez regarder les chevauchements des AABBs (axis-aligned bounding boxes) sur chaque axe ; si la projection des AABBs de deux objets se chevauchent sur les trois axes, alors les AABBs doivent se chevaucher. Vous pouvez vérifier chaque axe relativement rapidement en triant les points de départ et d'arrivée des AABB ; il y a beaucoup de cohérence temporelle entre les images puisque la plupart des objets ne se déplacent pas très vite, donc le tri ne change pas beaucoup.
Une fois que le balayage et l'élagage ont détecté un chevauchement entre les AABB, vous pouvez procéder à une vérification plus détaillée des objets, par exemple sphère ou boîte. Si la vérification détaillée révèle une collision, vous pouvez alors résoudre la collision en appliquant des forces, et/ou déclencher un événement de jeu ou jouer un effet sonore.
Correct. Normalement, il n'y a pas un écouteur d'événements pour chaque objet. Il y a souvent une structure arborescente non binaire en mémoire qui imite la carte de votre jeu. Imaginez une carte du métro ou du sous-sol. Cette structure de mémoire est une collection d'objets dans le jeu. Vous, le joueur, les monstres et les objets que vous pouvez ramasser ou les objets qui peuvent exploser et vous faire du mal. Ainsi, lorsque le joueur se déplace dans le jeu, le pointeur de l'objet joueur est déplacé dans la structure mémoire du jeu/carte.
voir Comment faire en sorte que mes entités de jeu connaissent les choses qui les entourent ?
Il y a beaucoup d'optimisations qui peuvent être utilisées. Premièrement - tout objet (disons avec l'indice i par exemple) est délimité par un cube, avec des coordonnées centrales CXi , CYi et la taille Si Deuxièmement, la détection des collisions fonctionne avec des estimations :
a) Trouvez toutes les paires de cubes i,j avec la condition : Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)
b) Nous travaillons maintenant uniquement avec les paires obtenues en a). Nous calculons les distances entre elles de manière plus précise, quelque chose comme Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj)) Les objets sont maintenant représentés comme des ensembles de quelques figures simples - cubes, sphères, cônes - et nous utilisons des formules de géométrie pour vérifier les intersections de ces figures.
c) Les objets de b) dont les intersections ont été détectées sont traités comme des collisions avec calcul physique, etc.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
