Share
De nombreux jeux nécessitent l'utilisation d'algorithmes de détection de collision pour déterminer le moment où deux objets sont entrés en collision, mais ces algorithmes sont souvent des opérations coûteuses et peuvent considérablement ralentir le jeu. Dans cet article, nous allons en apprendre davantage sur les quadtrees et sur la manière de les utiliser pour accélérer la détection des collisions en sautant des paires d'objets trop éloignés l'un de l'autre pour entrer en collision..
Remarque: Bien que ce tutoriel ait été écrit en Java, vous devriez pouvoir utiliser les mêmes techniques et concepts dans presque tous les environnements de développement de jeux..
La détection des collisions est une partie essentielle de la plupart des jeux vidéo. Dans les jeux 2D et 3D, il est important de détecter la collision entre deux objets, car une détection de collision médiocre peut conduire à des résultats très intéressants:
Cependant, la détection de collision est également une opération très coûteuse. Disons que 100 objets doivent être vérifiés pour éviter les collisions. La comparaison de chaque paire d'objets nécessite 10 000 opérations, ce qui représente beaucoup de vérifications.!
Une façon d'accélérer les choses est de réduire le nombre de vérifications à effectuer. Deux objets situés aux extrémités opposées de l'écran ne peuvent probablement pas entrer en collision. Il n'est donc pas nécessaire de rechercher une collision entre eux. C'est là qu'un quadtree entre en jeu.
Un quadtree est une structure de données utilisée pour diviser une région 2D en parties plus faciles à gérer. C'est un arbre binaire étendu, mais au lieu de deux nœuds enfants, il en a quatre..
Dans les images ci-dessous, chaque image est une représentation visuelle de l'espace 2D et les carrés rouges représentent des objets. Pour les besoins de cet article, les sous-nœuds seront étiquetés dans le sens anti-horaire comme suit:
Un quadtree commence comme un seul nœud. Les objets ajoutés au quadtree sont ajoutés au noeud unique.
Lorsque plusieurs objets sont ajoutés au quadtree, il se divisera en quatre sous-noeuds. Chaque objet sera ensuite placé dans l'un de ces sous-noeuds en fonction de son emplacement dans l'espace 2D. Tout objet qui ne peut pas tenir entièrement à l'intérieur de la limite d'un nœud sera placé dans le nœud parent.
Chaque sous-noeud peut continuer à se subdiviser à mesure que d'autres objets sont ajoutés.
Comme vous pouvez le constater, chaque nœud ne contient que quelques objets. Nous savons alors que, par exemple, les objets du nœud supérieur gauche ne peuvent pas entrer en collision avec les objets du nœud inférieur droit. Il n'est donc pas nécessaire d'exécuter un algorithme de détection de collision coûteux entre de telles paires..
Jetez un coup d'œil à cet exemple JavaScript pour voir un arbre à quatre en action.
L'implémentation d'un quadtree est assez simple. Le code suivant est écrit en Java, mais les mêmes techniques peuvent être utilisées pour la plupart des autres langages de programmation. Je vais commenter après chaque extrait de code.
Nous allons commencer par créer la classe principale Quadtree. Ci-dessous le code pour Quadtree.java.
Classe publique Quadtree private int MAX_OBJECTS = 10; private int MAX_LEVELS = 5; privé int niveau; objets de liste privés; limites du rectangle privé; nœuds privés Quadtree []; / * * Constructeur * / public Quadtree (int pLevel, Rectangle pBounds) niveau = pLevel; objets = new ArrayList (); bounds = pBounds; nœuds = new Quadtree [4];
le Quadtree la classe est simple. MAX_OBJECTS définit le nombre d'objets qu'un nœud peut contenir avant qu'il ne se divise et MAX_LEVELS définit le sous-noeud de niveau le plus profond. Niveau est le niveau de noeud actuel (0 étant le noeud le plus haut), bornes représente l'espace 2D occupé par le nœud, et noeuds sont les quatre sous-noeuds.
Dans cet exemple, les objets que le quadtree va contenir sont Les rectangles, mais pour votre propre quadtree cela peut être ce que vous voulez.
Ensuite, nous allons implémenter les cinq méthodes d’un quadtree: clair, Divisé, getIndex, insérer, et récupérer.
/ * * Efface le quadtree * / public void clear () objects.clear (); pour (int i = 0; i < nodes.length; i++) if (nodes[i] != null) nodes[i].clear(); nodes[i] = null;
le clair méthode efface le quadtree en effaçant récursivement tous les objets de tous les nœuds.
/ * * Divise le nœud en 4 sous-nœuds * / private void split () int subWidth = (int) (bounds.getWidth () / 2); int subHeight = (int) (bounds.getHeight () / 2); int x = (int) bounds.getX (); int y = (int) bounds.getY (); nœuds [0] = nouveau quadruplet (niveau + 1, nouveau rectangle (x + subWidth, y, subWidth, subHeight)); noeuds [1] = nouveau quadruplet (niveau + 1, nouveau rectangle (x, y, sous-largeur, sous-hauteur)); nœuds [2] = nouveau quadruplet (niveau + 1, nouveau rectangle (x, y + subHeight, subWidth, subHeight)); nœuds [3] = nouveau quadruplet (niveau + 1, nouveau rectangle (x + subWidth, y + subHeight, subWidth, subHeight));
le Divisé la méthode divise le nœud en quatre sous-nœuds en divisant le nœud en quatre parties égales et en initialisant les quatre sous-nœuds avec les nouvelles limites.
/ * * Détermine le nœud auquel l'objet appartient. -1 signifie que * l'objet ne peut pas entrer complètement dans un nœud enfant et fait partie * du nœud parent * / private int getIndex (Rectangle pRect) int index = -1; double verticalMidpoint = bounds.getX () + (bounds.getWidth () / 2); double horizontalMidpoint = bounds.getY () + (bounds.getHeight () / 2); // L'objet peut s'inscrire parfaitement dans les quadrants supérieurs du topQuadrant booléen = (pRect.getY () < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint); // L'objet peut s'inscrire complètement dans les quadrants de gauche if (pRect.getX () < verticalMidpoint && pRect.getX() + pRect.getWidth() < verticalMidpoint) if (topQuadrant) index = 1; else if (bottomQuadrant) index = 2; // Object can completely fit within the right quadrants else if (pRect.getX() > verticalMidpoint) if (topQuadrant) index = 0; else if (bottomQuadrant) index = 3; return index;
le getIndex La méthode est une fonction d'assistance du quadtree. Il détermine à quel endroit un objet appartient dans l'arbre à quatre en déterminant le noeud dans lequel l'objet peut s'intégrer..
/ * * Insère l'objet dans le quadtree. Si le nœud * dépasse la capacité, il se scinde et ajoute tous les objets * aux nœuds correspondants. * / public void insert (rectangle pRect) if (nœuds [0]! = null) int index = getIndex (pRect); if (index! = -1) nœuds [index] .insert (pRect); revenir; objects.add (pRect); if (objects.size ()> MAX_OBJECTS && level < MAX_LEVELS) if (nodes[0] == null) split(); int i = 0; while (i < objects.size()) int index = getIndex(objects.get(i)); if (index != -1) nodes[index].insert(objects.remove(i)); else i++;
le insérer la méthode est où tout est réuni. La méthode détermine d’abord si le nœud a des nœuds enfants et essaie d’y ajouter l’objet. S'il n'y a pas de nœud enfant ou si l'objet ne rentre pas dans un nœud enfant, l'objet est ajouté au nœud parent..
Une fois que l'objet est ajouté, il détermine si le nœud doit être fractionné en vérifiant si le nombre actuel d'objets dépasse le nombre maximal d'objets autorisés. La scission entraîne l’insertion par le nœud de tout objet pouvant s’intégrer dans un nœud enfant, au nœud enfant; sinon l'objet restera dans le noeud parent.
/ * * Retourne tous les objets pouvant entrer en collision avec l'objet donné * / public Liste récupérée (Liste returnObjects, Rectangle pRect) int index = getIndex (pRect); if (index! = -1 && nœuds [0]! = null) nœuds [index] .retrieve (returnObjects, pRect); returnObjects.addAll (objets); return returnObjects;
La dernière méthode du quadtree est la récupérer méthode. Il renvoie tous les objets dans tous les nœuds avec lesquels l'objet donné pourrait potentiellement entrer en collision. C’est cette méthode qui permet de réduire le nombre de paires pour vérifier la collision avec.
Maintenant que nous avons un arbre sur quatre entièrement fonctionnel, il est temps de l'utiliser pour réduire les contrôles nécessaires à la détection des collisions..
Dans un jeu typique, vous commencerez par créer le quadtree et en dépassant les limites de l'écran..
Quadtree quad = nouveau Quadtree (0, nouveau Rectangle (0,0,600,600));
À chaque image, vous insérez tous les objets dans l’arbre en faisant d'abord l’effacement, puis en utilisant la insérer méthode pour chaque objet.
quad.clear (); pour (int i = 0; i < allObjects.size(); i++) quad.insert(allObjects.get(i));
Une fois que tous les objets ont été insérés, vous allez parcourir chaque objet et récupérer une liste d'objets avec lesquels il pourrait éventuellement entrer en collision. Vous vérifierez ensuite les collisions entre chaque objet de la liste et l'objet initial à l'aide d'un algorithme de détection de collision..
List returnObjects = new ArrayList (); pour (int i = 0; i < allObjects.size(); i++) returnObjects.clear(); quad.retrieve(returnObjects, objects.get(i)); for (int x = 0; x < returnObjects.size(); x++) // Run collision detection algorithm between objects
Remarque: Les algorithmes de détection de collision sortent du cadre de ce didacticiel. Voir cet article pour un exemple.
La détection de collision peut être une opération coûteuse et peut ralentir les performances de votre partie. Les quad-arbres constituent un moyen d'aider à accélérer la détection des collisions et à maintenir votre jeu à des vitesses optimales..
Articles Similaires
Accentsconagua