Quadtree pour la détection des collisions 2D
j'essaye d'utiliser un quadtree pour la détection de collision 2D, mais je suis un peu perplexe sur la façon de l'implémenter. Tout d'abord, j'aurais un quadtree qui contient quatre sous-arbres (un représentant de chaque quadrant), ainsi qu'une collection d'objets qui ne rentre pas dans un seul sous-arbre.
en vérifiant un objet pour les collisions dans l'arbre, je ferais quelque chose comme ceci (grâce à QuadTree pour la détection de collision 2D ):
- Vérifiez l'objet pour les collisions avec des objets dans le noeud courant.
- pour tout sous-arbre dont l'espace chevauche l'objet, récurse.
pour trouver toutes les collisions à l'intérieur d'un arbre quadrillé:
- cochez chaque objet du noeud courant en regard de chaque autre objet du noeud courant.
- cochez chaque objet dans le noeud courant par rapport à chaque sous-arborescence.
à insérer dans un quadrillage:
- Si l'objet s'inscrit dans plusieurs sous-arbres, puis ajouter le noeud courant, et retour.
- sinon, revenez dans la sous-arborescence qui le contient.
pour mettre à jour un quadtree:
- Récurse in each subtree.
- si l'un des éléments du noeud courant ne correspond plus complètement à l'arbre courant, déplacer vers le parent.
- si un élément du noeud courant entre dans un sous-arbre, insérez-le dans le sous-arbre.
ça va? Peut-il être amélioré?
3 réponses
votre structure quadtree n'est pas optimale. Vous avez raison de stocker 4 sous-arbres par noeud, mais les objets réels ne doivent être stockés que dans les feuilles, pas les noeuds intérieurs. Par conséquent, la collection contenant les objets réels doit être déplacée vers les feuilles.
regardons la mise en œuvre des opérations :
- insérer un objet dans le quadtree :
Vérifiez si l'objet coupe le noeud courant. Si oui, de manière récursive. Si vous avez atteint le niveau de la feuille, insérez l'objet dans la collection. - supprimer un objet du quadtree :
Exécutez exactement les mêmes étapes que si vous insérez l'objet, mais quand vous avez atteint le niveau de la feuille supprimez-le de la collection. - Tester si un objet croise tout objet à l'intérieur du quadtree :
Exécutez exactement les mêmes étapes que si vous insérez l'objet, mais lorsque vous avez atteint le niveau de la feuille vérifier la collision avec tous les objets de la collection. - essai pour toutes les collisions entre tous les objets à l'intérieur du quadtree :
Pour chaque objet dans le quadtree exécuter le test de collision d'objet simple. - mise à Jour du quadtree :
Supprimez tous les objets du quadtree dont la position a été modifiée et insérez-les à nouveau.
plusieurs avantages :
- en stockant uniquement des objets dans les feuilles, il est très facile de gérer les opérations sur le quadtree (moins de cas spéciaux)
- le quadtree peut avoir des feuilles de différentes profondeurs, vous permettant ainsi d'adapter la densité du quadtree en fonction de la région du territoire qu'il couvre. Cette adaptation peut se produire à l'exécution, maintenant ainsi le rapport objet / noeud optimal.
seulement disatvantage :
- les objets peuvent appartenir à plusieurs collections à l'intérieur du quadtree. Vous allez avoir besoin d'une collection linéaire supplémentaire en dehors du quadtree pour énumérer chaque objet sans duplicata.
ne sont pas toujours la meilleure structure de données pour la détection des collisions. Le dessus d'un quadtree peut potentiellement être illimité (si vous ne limitez pas la profondeur de l'arbre), et dans le pire des cas, n'abandonnez aucune vitesse. Au lieu de cela, vous pourriez vouloir envisager d'utiliser une grille clairsemée, qui donne de meilleures performances qu'un quadtree seulement sans la hauteur supplémentaire de traverser plusieurs niveaux d'arbre.
il y a aussi d'autres approches complètement différentes qui pourrait être encore mieux. Par exemple, vous pouvez essayer d'implémenter L'algorithme de Zomorodian et Edelsbrunner, comme je l'ai fait dans le module suivant:
voici aussi quelques articles que j'ai écrits qui traitent de ces questions plus en détail:
- http://0fps.net/2015/01/07/collision-detection-part-1/
- http://0fps.net/2015/01/18/collision-detection-part-2 /
- http://0fps.net/2015/01/23/collision-detection-part-3-benchmarks /
en particulier, si vous regardez les points de référence dans la dernière section, vous verrez que de toutes les bibliothèques étudiées, les quadtrees ont eu tendance à donner de très mauvais résultats par rapport à d'autres méthodes de détection de collision comme les arbres R, grilles ou arbres de segments.
Je ne suis pas sûr de l'efficacité du cpu, mais il semble bien fonctionner sur mon duo de base dans eclipse, fonctionne toujours à plus de 2400 fps lol..
fondamentalement, j'ai ajouté une liste à des objets pouvant entrer en collision pour stocker des références à des objets de noeud de quadtree avec lesquels j'ai associé l'objet (en insérant dans le quadtree). J'ai aussi ajouté une liste à chaque noeud quadtree, qui stocke des références à tous les objets jugés dans les limites de ce noeud. Donc chaque noeud n'en aura qu'un l'apparition de chaque objet. chaque noeud stocke également une référence à son noeud parent, pour la navigation vers les noeuds voisins si je veux vérifier l'un d'eux après le noeud inital pour une plus grande précision de collision.
il est très facile d'obtenir des références à tous les autres objets dans une cellule:
list temp_checklist = object.cells[cell_index].objects
//('objects' being some sort of array or list of object references as described above)
espère que ça aide quelqu'un ;)