Détection de collision basée sur un arbre vs une grille

Je fais un jeu coopératif de type r à 4 joueurs et je suis sur le point d'implémenter le code de détection de collision. J'ai lu de nombreux articles et des trucs sur la façon de gérer la détection de collision, mais j'ai du mal à trouver quoi faire. Il semble que l'arbre quadruple soit la voie la plus courante, mais dans certaines ressources, ils mentionnent la solution basée sur la grille. Pour avoir utilisé une grille pour les détections dans un jeu précédent, je suis à l'aise avec ça, mais est-ce vraiment mieux qu'un arbre quadruple? Je ne sais pas lequel offre les meilleures performances, et j'ai également effectué un petit test de performance, il n'y a pas beaucoup de différence entre les deux solutions.

Est-ce que l'un est meilleur que l'autre ? ou plus élégant? Je ne sais vraiment pas lequel utiliser.

Tout conseil est le bienvenu. Merci.

La bonne réponse dépend un peu du jeu réel que vous concevez, et choisir l'un plutôt que l'autre nécessitera vraiment de mettre en œuvre les deux et de faire un profilage pour savoir lequel est le plus efficace en termes de temps ou d'espace sur votre jeu spécifique.

La détection de grille ne semble s'appliquer qu'à la détection de collisions entre des objets en mouvement et un arrière-plan statique. Le plus grand avantage est que l'arrière-plan statique est représenté comme un tableau de mémoire contigu, et chaque recherche de collision est O (1) avec une bonne localité si vous devez effectuer plusieurs lectures (car les entités couvrent plus d'une cellule dans la grille). L'inconvénient, si l'arrière-plan statique est grand, est que la grille peut être plutôt gaspilleuse d'espace.

Si, au lieu de cela, vous représentez l'arrière-plan statique comme une arborescence quadratique, le coût des recherches individuelles augmente, mais comme de grands blocs de l'arrière-plan occupent une petite quantité d'espace, les besoins en mémoire diminuent et donc une plus grande partie de l'arrière-plan peut se trouver dans le cache. même s'il faut 10 fois plus de lectures pour effectuer une recherche dans une telle structure, si tout est dans le cache, ce sera toujours 10 fois plus rapide qu'une simple recherche avec un échec de cache.

Si j'étais confronté au choix? J'irais avec l'implémentation de la grille, car c'est stupide et simple à faire, mieux vaut passer mon temps sur d'autres problèmes plus intéressants. Si je remarque que mon jeu tourne un peu lentement, je vais faire un profilage et voir ce qui pourrait utiliser de l'aide. S'il semble que le jeu passe beaucoup de temps à détecter les collisions, j'essaierais une autre implémentation, comme un quadtree (après avoir épuisé toutes les corrections faciles d'abord), et chercher si cela a aidé.

Edit: Je n'ai aucune idée du lien entre la détection de collision de grille et la détection de collisions de plusieurs entités mobiles, mais à la place, je répondrai comment un index spatial (Quadtree) améliore les performances de détection par rapport à la solution itérative. La solution naïve (et généralement parfaitement fine) ressemble un peu à ceci:

foreach actor in actorList:
    foreach target in actorList:
        if (actor != target) and actor.boundingbox intersects target.boundingbox:
            actor.doCollision(target)

Cela a évidemment des performances autour de O (n ^ 2), avec n le nombre d'acteurs qui sont actuellement en vie dans le jeu, y compris les balles et les vaisseaux spatiaux et les extraterrestres. Il peut également comprendre de petits obstacles statiques.

Cela fonctionne parfaitement bien tant que le nombre de ces articles est raisonnablement petit, mais commence à paraître un peu pauvre lorsqu'il y a plus de quelques centaines d'objets à comparer. 10 objets résultent en seulement 100 contrôles de collision, 100 résultats en 10 000 contrôles. 1000 entraîne un million de chèques.

Un index spatial (comme les arbres quadruples) peut énumérer efficacement les éléments qu'il collecte en fonction de relations géométriques. cela changerait l'algorithme de collision en quelque chose comme ceci:

foreach actor in actorList:
    foreach target in actorIndex.neighbors(actor.boundingbox):
       if (actor != target) and actor.boundingbox intersects target.boundingbox:
            actor.doCollision(target)

L'efficacité de ceci (en supposant une distribution uniforme des entités): est généralement O (n ^ 1,5 log (n)), car l'index prend environ log (n) comparaisons à parcourir, il y aura environ sqrt (n) voisins à comparer , et il n'y a pas d'acteurs à vérifier. En réalité, cependant, le nombre de voisins est toujours assez limité, car si une collision se produit, la plupart du temps l'un des objets est supprimé ou éloigné de la collision. vous obtenez donc juste O (n log (n)). Pour 10 entités, vous faites (environ) 10 comparaisons, pour 100, vous en faites 200, pour 1000 vous en faites 3000.

Un index vraiment intelligent peut même combiner la recherche de voisin avec l'itération en bloc et effectuer un rappel sur chaque entité qui se croise. Cela donnera une performance d'environ O (n), car l'index est analysé une fois plutôt que d'être interrogé n fois.

Désolé de ressusciter le fil ancien, mais les grilles anciennes plates IMHO ne sont pas utilisées assez souvent pour ces cas. Il y a beaucoup d'avantages à une grille dans la mesure où l'insertion / le retrait de cellules est bon marché. Vous n'avez pas à vous soucier de libérer une cellule car la grille n'a pas pour objectif d'optimiser les représentations éparses. Je dis qu'après avoir réduit le temps de sélection, sélectionnez un groupe d'éléments dans une base de code héritée de plus de 1200 ms à 20 ms en remplaçant simplement le quadruple arbre par une grille. Pour être honnête cependant, cet arbre quadruple a été vraiment mal implémenté, stockant un tableau dynamique séparé par nœud feuille pour les éléments.

L'autre que je trouve extrêmement utile est que vos algorithmes de tramage classiques pour dessiner des formes peuvent être utilisés pour effectuer des recherches dans la grille. Par exemple, vous pouvez utiliser la pixellisation de ligne de Bresenham pour rechercher des éléments qui coupent une ligne, la pixellisation de ligne de balayage pour trouver quelles cellules coupent un polygone, etc. Étant donné que je travaille beaucoup dans le traitement d'image, il est vraiment agréable de pouvoir utiliser exactement la même chose. code optimisé que j'utilise pour tracer des pixels sur une image comme j'utilise pour détecter des intersections contre des objets en mouvement dans une grille.

Cela dit, pour rendre une grille efficace, vous ne devriez pas avoir besoin de plus de 32 bits par cellule de grille. Vous devriez pouvoir stocker un million de cellules dans moins de 4 mégaoctets. Chaque cellule de grille peut simplement indexer le premier élément de la cellule, et le premier élément de la cellule peut alors indexer l'élément suivant dans la cellule. Si vous stockez une sorte de conteneur à part entière avec chaque cellule, cela devient explosif dans l'utilisation de la mémoire et les allocations rapidement. Au lieu de cela, vous pouvez simplement faire:

struct Node
{
    int32_t next;
    ...
};

struct Grid
{
     vector<int32_t> cells;
     vector<Node> nodes;
};

Ainsi:

D'accord, ainsi de suite aux inconvénients. J'y arrive certes avec un parti pris et une préférence pour les grilles, mais leur principal inconvénient est qu'elles ne sont pas rares.

L'accès à une cellule de grille spécifique en fonction d'une coordonnée est à temps constant et ne nécessite pas de descendre dans un arbre qui est moins cher, mais la grille est dense, pas clairsemée, vous pourriez donc avoir à vérifier plus de cellules que nécessaire. Dans les situations où vos données sont très peu réparties, la grille peut nécessiter une vérification plus approfondie pour déterminer les éléments qui se croisent, par exemple une ligne ou un polygone rempli ou un rectangle ou un cercle de délimitation. La grille doit stocker cette cellule 32 bits même si elle est complètement vide, et lorsque vous effectuez une requête d'intersection de forme, vous devez vérifier ces cellules vides si elles intersectent votre forme.

Le principal avantage du quadruple arbre est naturellement sa capacité à stocker des données éparses et à ne les subdiviser que si nécessaire. Cela dit, il est plus difficile à mettre en œuvre très bien, surtout si les choses bougent à chaque image. L'arbre doit subdiviser et libérer les nœuds enfants à la volée très efficacement, sinon il se dégrade en une grille dense gaspillant les frais généraux pour stocker les liens parent-> enfant. Il est très possible d'implémenter un quad-tree efficace en utilisant des techniques très similaires à ce que j'ai décrit ci-dessus pour la grille, mais cela va généralement être plus long. Et si vous le faites comme je le fais dans la grille, ce n'est pas nécessairement optimal non plus, car cela entraînerait une perte de capacité à garantir que les 4 enfants d'un nœud à quatre arbres sont stockés de manière contiguë.

De plus, un quadruple arbre et une grille ne font pas un travail magnifique si vous avez un certain nombre de grands éléments qui couvrent une grande partie de la scène entière, mais au moins la grille reste plate et ne se subdivise pas au nième degré dans ces cas . L'arbre quadruple devrait stocker des éléments dans des branches et pas seulement des feuilles pour gérer raisonnablement de tels cas, sinon il voudra se subdiviser comme un fou et dégrader la qualité extrêmement rapidement. Il y a plus de cas pathologiques comme celui-ci que vous devez gérer avec un arbre quadruple si vous voulez qu'il gère la plus large gamme de contenu. Par exemple, un autre cas qui peut vraiment trébucher sur un quadruple arbre est si vous avez une cargaison d'éléments coïncidents. À ce stade, certaines personnes ont simplement recours à la définition d'une limite de profondeur pour leur arbre quadruple pour l'empêcher de se subdiviser à l'infini. La grille a un attrait qu'elle fait un travail décent,

La stabilité et la prévisibilité sont également bénéfiques dans un contexte de jeu, car parfois vous ne voulez pas nécessairement la solution la plus rapide possible pour le cas commun si cela peut occasionnellement entraîner des hoquets dans les taux de trame dans de rares cas par rapport à une solution qui est assez rapide tout- autour, mais ne conduit jamais à de tels hoquets et maintient des fréquences d'images lisses et prévisibles. Une grille a ce genre de dernière qualité.

Cela dit, je pense vraiment que c'est au programmeur. Avec des choses comme grille vs quad-arbre ou octree vs kd-arbre vs BVH, mon vote est sur le développeur le plus prolifique avec un record pour créer des solutions très efficaces quelle que soit la structure de données qu'il utilise. Il y a aussi beaucoup au niveau micro, comme le multithreading, SIMD, les dispositions de mémoire compatibles avec le cache et les modèles d'accès. Certaines personnes pourraient considérer ces micro mais elles n'ont pas nécessairement un micro impact. De telles choses pourraient faire une différence de 100 fois d'une solution à l'autre. Malgré cela, si on me donnait personnellement quelques jours et qu'on me disait que je devais mettre en œuvre une structure de données pour accélérer rapidement la détection de collision des éléments se déplaçant autour de chaque trame, je ferais mieux dans ce court laps de temps en mettant en œuvre une grille qu'un quad -arbre.