Comment mettre en œuvre une détection de collision 2D rapide et précise?

11

Je sais très bien comment détecter si deux ou plusieurs objets 2D entrent en collision, mais je suis intéressé à savoir comment vérifier s'il y a collision. Dans les projets précédents, je venais de faire vérifier chaque objet par rapport à tout autre objet (je sais, niveau de stupidité O (n ^ 2)) et cela a créé un gameplay moins que fluide.

Divers forums saluent la grandeur des Quadtrees, des B-Trees et de tout autre type d'arbre ou de structure auquel vous pouvez penser.

Quelle est la structure la plus efficace pour déterminer si une collision doit être vérifiée?

2d collision-detection data-structure Mike Cluck
la source
1
Une chose que vous voudrez peut-être considérer est uniquement de vérifier les collisions pour les objets qui ont bougé et les seuls objets qui sont proches de vous. Mon système actuel fonctionne bien (des centaines de milliers d'objets) - et c'est tout ce que je fais.
ultifinitus
Je pense que gamedev.stackexchange.com/questions/14369/… pourrait vous aider beaucoup. il était à l'origine destiné à un algorithme pour le traitement parallèle, mais je pense que le même algorithme pourrait également améliorer les applications à thread unique.
Ali1S232
1
@ultifinitus C'est essentiellement ce que je demande. Comment puis-je déterminer quels objets se trouvent à proximité sans parcourir chaque objet et vérifier sa position?
Mike Cluck
Mike, vous pouvez m'envoyer un email pour un code spécifique que j'ai utilisé, c'est en c ++ - ou je peux vous donner la structure de base, bien que cela puisse devenir assez ambigu et compliqué à cause de cela.
ultifinitus
1
Ce n'est pas un doublon parce que je demandais quel type de structure est le mieux adapté pour déterminer si nous devrions prendre la peine de vérifier une collision. Cette autre question portait sur les collisions transparentes et non transparentes. Sans oublier, cette question a été posée environ un an avant celle à laquelle vous vous êtes connecté.
Mike Cluck du

Réponses:

12

Pour un jeu en 2D, à moins que les objets 2D ne soient très fortement répartis sur un côté de votre carte, une grille uniforme est presque toujours la voie à suivre. La complexité de la mémoire est simple, (proportionnelle aux dimensions de votre carte), et avec une distribution raisonnable, a O (1) le temps de recherche et une moyenne de journal (numberOfObjects / (lignes * colonnes)) ^ 2 tests d'intersection fait par cellule. Vous pouvez décider de ne vérifier que les cellules sur lesquelles un objet a été déplacé, ce qui rend la géométrie statique beaucoup plus efficace. Il est facile de modifier une grille uniforme à la volée (beaucoup moins pénible que dans les solutions arborescentes) et il est plus simple à mettre en œuvre. La seule fois où je dirais de ne pas l'utiliser dans un jeu 2D, c'est lorsque les besoins en mémoire d'une grille uniforme deviennent trop importants (disons une simulation d'espace où les niveaux sont rares mais énormes).

Darcy Rayner
la source
Comment cette solution gère-t-elle les objets qui bordent 2 ou 4 cellules de grille?
ashes999
1
N'importe quelle cellule dans laquelle l'objet se chevauche, il est considéré comme étant, donc un objet peut être dans plusieurs cellules. La plupart des structures de données spatiales traiteront la question des chevauchements de la même manière.
Darcy Rayner
Wow, c'est plutôt intelligent. +1 Bravo mec.
ashes999
1

Si votre monde a une dimension très "longue" (appelez-la X), par rapport aux autres, vous pouvez conserver les objets dans une liste ordonnée que vous pouvez trier à nouveau au fur et à mesure qu'ils se déplacent, puis la détection de collision signifie uniquement vérifier les objets qui se chevauchent dans l'axe X.

Une autre possibilité est de garder des listes d'objets actifs / passifs, et de ne pas se soucier des objets passifs (qui ne bougent pas du tout).

Si ce sont tous des objets de taille moyenne qui sont visibles par le joueur sur l'écran, tout contre tout n'est probablement pas trop mal.

A part ça, je suis avec Darcy, une grille uniforme est bonne.

MarkR
la source