Existe-t-il un moyen d'augmenter l'efficacité du contrôle de collision d'un système de n objets?

Je fais un jeu qui se compose de nombreux objets à l'écran, dont le joueur. J'ai besoin de savoir quels objets entrent en collision à chaque itération.

J'ai fait quelque chose comme ça:

for (o in objects)
{
   o.stuff();
   for (other in objects)
      if (collision(o, other))
          doStuff();

   bla.draw();
}

Cela a O (n ^ 2), dont on me dit qu'il est mauvais. Comment puis-je le faire plus efficacement, est-ce même possible? Je fais cela en Javascript, et n sera généralement inférieur à 30, sera-ce un problème si cela reste le même?

Avec seulement 30 objets maximum, vous ne devriez pas avoir besoin de beaucoup d'optimisation, sinon de ne pas comparer les deux mêmes paires plus d'une fois par image. Ce que l'exemple de code ci-dessous couvrira. Mais si vous êtes intéressé par différentes optimisations qu'un moteur physique utiliserait, continuez à lire le reste de ce post.

Ce dont vous aurez besoin est une implémentation de partitionnement spatial , comme un Octree (pour les jeux 3D) ou Quadtree (pour les jeux 2D). Celles-ci partitionnent le monde en sous-sections, puis chaque sous-section est partitionnée davantage dans le même manoir, jusqu'à ce qu'elles se soient subdivisées en une taille minimale. Cela vous permet de vérifier très rapidement quels autres objets se trouvent dans la même région du monde qu'un autre, ce qui limite le nombre de collisions que vous devez vérifier.

En plus du partitionnement spatial, je recommanderais de créer un AABB ( boîte de délimitation alignée sur l'axe ) pour chacun de vos objets physiques. Cela vous permet de comparer l'AABB d'un objet par rapport à un autre, ce qui est beaucoup plus rapide qu'une vérification détaillée par poly entre objets.

Cela peut être encore plus loin pour les objets physiques complexes ou volumineux, où vous pouvez subdiviser le maillage physique lui-même, en donnant à chaque sous-forme son propre AABB que vous pouvez vérifier uniquement si les AABB de deux objets se chevauchent.

La plupart des moteurs physiques désactiveront la simulation physique active sur les corps physiques une fois qu'ils se seront arrêtés. Lorsqu'un corps physique est désactivé, il n'a qu'à vérifier la collision avec son AABB à chaque trame, et si quelque chose entre en collision avec l'AABB, il le réactivera et fera un contrôle de collision plus granulaire. Cela réduit les temps de simulation.

En outre, de nombreux moteurs physiques utilisent des «îlots de simulation», c'est-à-dire un groupe de corps physiques proches les uns des autres. Si tout dans l'îlot de simulation est au repos, l'îlot de simulation se désactive. L'avantage de l'îlot de simulation est que tous les corps à l'intérieur peuvent cesser de vérifier les collisions une fois que l'îlot est inactif, et la seule vérification de chaque trame est de voir si quelque chose est entré dans l'AABB de l'îlot. Ce n'est qu'une fois que quelque chose entre dans l'AABB de l'île que chacun des corps de l'île devra vérifier les collisions. L'îlot de simulation se réactive également si un corps à l'intérieur de celui-ci recommence à se déplacer tout seul. Si un corps s'éloigne suffisamment du centre du groupe, il est retiré de l'île.

À la fin, vous vous retrouvez avec quelque chose comme ça (en pseudo-code):

// Go through each leaf node in the octree. This could be more efficient
// by keeping a list of leaf nodes with objects in it.
for ( node in octreeLeafNodes )
{
    // We only need to check for collision if more than one object
    // or island is in the bounds of this octree node.
    if ( node.numAABBsInBounds > 1)
    {
        for ( int i = 0; i < AABBNodes.size(); ++i )
        {
           // Using i+1 here allows us to skip duplicate checks between AABBS
           // e.g (If there are 5 bodies, and i = 0, we only check i against
           //      indexes 1,2,3,4. Once i = 1, we only check i against indexes
           //      2,3,4)
           for ( int j = i + 1; j < AABBNodes.size(); ++j )
           {
               if ( AABBOverlaps( AABBNodes[i], AABBNodes[j] ) )
               {
                   // If the AABB we checked against was a simulation island
                   // then we now check against the nodes in the simulation island

                   // Once you find overlaps between two actual object AABBs
                   // you can now check sub-nodes with each object, if you went
                   // that far in optimizing physics meshes.
               {
           }
        }
    }
}

Je recommanderais également de ne pas avoir autant de boucles dans des boucles comme celle-ci, l'exemple ci-dessus était juste pour que vous ayez l'idée, je le décomposerais en plusieurs fonctions qui vous donnent la même fonctionnalité que quelque chose comme ce qui est montré ci-dessus.

Assurez-vous également de ne pas modifier le conteneur AABBNodes lors de sa boucle, car cela pourrait signifier des contrôles de collision manqués. Cela peut sembler du bon sens, mais vous seriez surpris de la facilité avec laquelle les choses réagissant aux collisions provoquent des changements que vous ne prévoyez pas. Par exemple, si une collision faisait que l'un des objets entrant en collision changeait suffisamment de position pour les supprimer de l'AABB du nœud Octree que vous vérifiiez, cela pourrait altérer ce conteneur. Pour résoudre ce problème, je recommande de conserver une liste de tous les événements de collision qui se produisent pendant les vérifications, puis une fois toutes les vérifications terminées, parcourez la liste et envoyez tous les événements de collision.

Votre exemple teste chaque paire d'objets plusieurs fois.

Prenons un exemple très simple avec un tableau contenant 0,1,2,3

Avec votre code, vous obtenez ceci:

• À la boucle 0, vous testez contre 1, 2 et 3
• À la boucle 1, vous testez contre 0, 2 et 3 ===> (0-1 déjà testé)
• À la boucle 2, vous testez contre 0, 1 et 3 ===> (0-2 / 1-2 déjà testé)
• À la boucle 3, vous testez contre 0, 1 et 2 ===> (0-3 / 1-3 / 2-3 déjà testé)

Voyons maintenant le code suivant:

for(i=0;i<=objects.length;i++)
{
    objects[i].stuff();

    for(j=i+1;j<=objects.length;j++)
    {
        if (collision(objects[i], objects[j]))
        doStuff();
    }

    bla.draw();
}

Si nous utilisons à nouveau le tableau contenant 0,1,2,3, nous avons le comportement suivant:

• À la boucle 0, vous testez contre 1, 2, 3
• À la boucle 1, vous testez contre 2, 3
• À la boucle 2, vous testez contre 3
• À la boucle 3, vous testez contre rien

Avec le deuxième algorithme, nous avons obtenu 6 tests de collision tandis que le précédent demandait 12 tests de collision.

Concevez votre algorithme en fonction de vos besoins, mais gardez le détail de l'implémentation encapsulé. Même en Javascript, les concepts de base de la POO s'appliquent.

Pour N =~ 30, O(N*N) n'est pas un problème, et votre recherche linéaire sera probablement aussi rapide que n'importe quelle alternative. Mais vous ne voulez pas coder en dur les hypothèses dans votre code. En pseudocode, vous auriez une interface

interface itemContainer { 
    add(BoundingBox);
    remove(BoundingBox);
    BoundingBox[] getIntersections();
}

Cela décrit ce que votre liste d'éléments peut faire. Ensuite, vous pouvez écrire une classe ArrayContainer qui implémente cette interface. En Javascript, le code ressemblerait à ceci:

function ArrayContainer() { ... } // this uses an array to store my objects
ArrayContainer.prototype.add = function(box) { ... };
ArrayContainer.prototype.remove = function(box) { ... };
ArrayContainer.prototype.getIntersections = function() { ... };

function QuadTreeContainer { ... } // this uses a quadtree to store my objects
... and implement in the add/remove/getIntersections for QuadTreeContainer too

Et voici un exemple de code qui crée 300 boîtes englobantes et obtient toutes les intersections. Si vous avez correctement implémenté ArrayContainer et QuadTreeContainer, la seule chose que vous devez modifier dans votre code est de passer var allMyObjects = new ArrayContainer()àvar allMyObjects = QuadTreeContainer() .

var r = Math.random;
var allMyObjects = new ArrayContainer();
for(var i=0; i<300; i++)
    allMyObjects.add(new BoundingBox(r(), r()));
var intersections = allMyObjects.getIntersections();

Je suis allé de l'avant et j'ai fouetté l'implémentation du ArrayContainer standard ici:

http://jsfiddle.net/SKkN5/1/

Vous devez également prendre en compte les types d'objets pouvant entrer en collision de manière sensible.

Par exemple, le joueur doit probablement être vérifié pour une collision avec tout sauf ses propres balles. Cependant, les ennemis peuvent avoir seulement besoin de vérifier les balles des joueurs. Les balles n'ont presque certainement pas besoin d'entrer en collision les unes avec les autres.

Pour l'implémenter efficacement, vous souhaiterez probablement conserver des listes d'objets distinctes, une par type d'objet.