Comment puis-je optimiser un moteur de collision où l'ordre est important et la collision est conditionnelle en fonction du groupe d'objets?

Si c'est votre première fois sur cette question, je vous suggère de lire d'abord la partie pré-mise à jour ci-dessous, puis cette partie. Voici cependant une synthèse du problème:

Fondamentalement, j'ai un moteur de détection et de résolution de collision avec un système de partitionnement de grille où les groupes d'ordre de collision et de collision sont importants. Un corps à la fois doit se déplacer, puis détecter la collision, puis résoudre les collisions. Si je déplace tous les corps en même temps, puis que je génère des paires de collisions possibles, c'est évidemment plus rapide, mais la résolution se brise car l'ordre de collision n'est pas respecté. Si je déplace un corps à la fois, je suis obligé de faire contrôler les collisions par les corps et cela devient un problème ^ 2. Mettez les groupes dans le mix, et vous pouvez imaginer pourquoi ça devient très lent très vite avec beaucoup de corps.

Mise à jour: j'ai travaillé très dur sur cela, mais je n'ai pas réussi à optimiser quoi que ce soit.

J'ai réussi à implémenter la "peinture" décrite par Will et à changer des groupes en bits, mais c'est une accélération très très mineure.

J'ai également découvert un gros problème: mon moteur dépend de l'ordre de collision.

J'ai essayé une implémentation de génération unique de paires de collisions , qui accélère certainement beaucoup, mais a cassé l' ordre de collision .

Laissez-moi expliquer:

• dans ma conception d'origine (ne pas générer de paires), cela se produit:

  1. un seul corps bouge
  2. après avoir bougé, il rafraîchit ses cellules et obtient les corps contre lesquels il entre en collision
  3. s'il chevauche un corps contre lequel il doit se résoudre, résoudre la collision

  cela signifie que si un corps bouge et frappe un mur (ou tout autre corps), seul le corps qui a bougé résoudra sa collision et l'autre corps ne sera pas affecté.

  C'est le comportement que je désire .

  Je comprends que ce n'est pas courant pour les moteurs physiques, mais cela a beaucoup d'avantages pour les jeux de style rétro .

• dans la conception de grille habituelle (générant des paires uniques), cela se produit:

  1. tous les corps bougent
  2. après que tous les corps se soient déplacés, rafraîchissez toutes les cellules
  3. générer des paires de collisions uniques
  4. pour chaque paire, gérer la détection et la résolution des collisions

  dans ce cas, un mouvement simultané aurait pu entraîner le chevauchement de deux corps, et ils se résoudraient en même temps - ce qui fait que les corps se «repoussent» et rompent la stabilité de la collision avec plusieurs corps

  Ce comportement est courant pour les moteurs physiques, mais il n'est pas acceptable dans mon cas .

J'ai également trouvé un autre problème, qui est majeur (même s'il n'est pas susceptible de se produire dans une situation réelle):

• considérer les corps des groupes A, B et W
• A entre en collision et se résout contre W et A
• B entre en collision et se résout contre W et B
• A ne fait rien contre B
• B ne fait rien contre A

il peut y avoir une situation où beaucoup de corps A et de corps B occupent la même cellule - dans ce cas, il y a beaucoup d'itérations inutiles entre les corps qui ne doivent pas réagir les uns aux autres (ou seulement détecter une collision mais pas les résoudre) .

Pour 100 corps occupant la même cellule, c'est 100 ^ 100 itérations! Cela se produit car des paires uniques ne sont pas générées - mais je ne peux pas générer de paires uniques , sinon j'obtiendrais un comportement que je ne souhaite pas.

Existe-t-il un moyen d'optimiser ce type de moteur de collision?

Ce sont les lignes directrices qui doivent être respectées:

• L'ordre de collision est extrêmement important!

  • Les corps doivent se déplacer un par un , puis vérifier les collisions un par un et se résoudre après le mouvement un par un .

• Les corps doivent avoir 3 groupes de bits de groupe

  • Groupes : groupes auxquels appartient le corps
  • GroupsToCheck : groupes contre lesquels le corps doit détecter une collision
  • GroupsNoResolve : groupes contre lesquels le corps ne doit pas résoudre la collision
  • Il peut y avoir des situations où je veux seulement qu'une collision soit détectée mais pas résolue

Pré-mise à jour:

Avant - propos : Je suis conscient que l'optimisation de ce goulot d'étranglement n'est pas une nécessité - le moteur est déjà très rapide. Cependant, pour des raisons amusantes et éducatives, j'aimerais trouver un moyen de rendre le moteur encore plus rapide.

Je crée un moteur de détection / réponse de collision C ++ 2D à usage général, en mettant l'accent sur la flexibilité et la vitesse.

Voici un schéma très basique de son architecture:

Fondamentalement, la classe principale est World, qui possède (gère la mémoire) de a ResolverBase*, a SpatialBase*et a vector<Body*>.

SpatialBase est une classe virtuelle pure qui traite de la détection de collision à large phase.

ResolverBase est une classe virtuelle pure qui traite de la résolution des collisions.

Les corps communiquent World::SpatialBase*avec les SpatialInfoobjets appartenant aux corps eux-mêmes.

Il existe actuellement une classe spatiale:, Grid : SpatialBasequi est une grille 2D fixe de base. Il a sa propre classe d'information, GridInfo : SpatialInfo.

Voici à quoi ressemble son architecture:

La Gridclasse possède un tableau 2D de Cell*. La Cellclasse contient une collection de (n'appartenant pas) Body*: a vector<Body*>qui contient tous les corps qui se trouvent dans la cellule.

GridInfo les objets contiennent également des pointeurs n'appartenant pas aux cellules dans lesquelles se trouve le corps.

Comme je l'ai dit précédemment, le moteur est basé sur des groupes.

• Body::getGroups()renvoie un std::bitsetde tous les groupes dont le corps fait partie.
• Body::getGroupsToCheck()renvoie un std::bitsetde tous les groupes contre lesquels le corps doit vérifier la collision.

Les corps peuvent occuper plus d'une seule cellule. GridInfo stocke toujours des pointeurs non propriétaires vers les cellules occupées.

Après le déplacement d'un seul corps, la détection de collision se produit. Je suppose que tous les corps sont des boîtes englobantes alignées sur l'axe.

Fonctionnement de la détection de collisions à large phase:

Partie 1: mise à jour des informations spatiales

Pour chacun Body body:

1. • Les cellules occupées en haut à gauche et les cellules occupées en bas à droite sont calculées.
   • S'ils diffèrent des cellules précédentes, body.gridInfo.cellsest effacé et rempli de toutes les cellules que le corps occupe (2D pour la boucle de la cellule la plus en haut à gauche à la cellule en bas à droite).

2. body est désormais assuré de savoir quelles cellules il occupe.

Partie 2: contrôles de collision réels

Pour chacun Body body:

• body.gridInfo.handleCollisions est appelé:

void GridInfo::handleCollisions(float mFrameTime)
{
    static int paint{-1};
    ++paint;

    for(const auto& c : cells)
        for(const auto& b : c->getBodies())
        {
            if(b->paint == paint) continue;
            base.handleCollision(mFrameTime, b);
            b->paint = paint;
        }
}

void Body::handleCollision(float mFrameTime, Body* mBody)
    {
        if(mBody == this || !mustCheck(*mBody) || !shape.isOverlapping(mBody->getShape())) return;

        auto intersection(getMinIntersection(shape, mBody->getShape()));

        onDetection({*mBody, mFrameTime, mBody->getUserData(), intersection});
        mBody->onDetection({*this, mFrameTime, userData, -intersection});

        if(!resolve || mustIgnoreResolution(*mBody)) return;
        bodiesToResolve.push_back(mBody);
    }

• La collision est alors résolue pour chaque corps bodiesToResolve.

• C'est ça.

Donc, j'essaie d'optimiser cette détection de collision à large phase depuis un bon moment maintenant. Chaque fois que j'essaie autre chose que l'architecture / la configuration actuelle, quelque chose ne se passe pas comme prévu ou je fais des suppositions sur la simulation qui s'avèrent plus tard fausses.

Ma question est: comment puis-je optimiser la phase large de mon moteur de collision ?

Y a-t-il une sorte d'optimisation magique C ++ qui peut être appliquée ici?

L'architecture peut-elle être repensée afin de permettre plus de performances?

• Implémentation réelle: SSVSCollsion
• Body.h , Body.cpp
• World.h , World.cpp
• Grid.h , Grid.cpp
• Cell.h , Cell.cpp
• GridInfo.h , GridInfo.cpp

Sortie Callgrind pour la dernière version: http://txtup.co/rLJgz

getBodiesToCheck()

Il pourrait y avoir deux problèmes avec la getBodiesToCheck()fonction; premier:

if(!contains(bodiesToCheck, b)) bodiesToCheck.push_back(b);

Cette partie est O (n ² ) n'est-ce pas?

Plutôt que de vérifier si le corps est déjà dans la liste, utilisez plutôt la peinture .

loop_count++;
if(!loop_count) { // if loop_count can wrap,
    // you just need to iterate all bodies to reset it here
}
bodiesToCheck.clear();
for(const auto& q : queries)
    for(const auto& b : *q)
        if(b->paint != loop_count) {
            bodiesToCheck.push_back(b);
            b->paint = loop_count;
        }
return bodiesToCheck;

Vous êtes en train de déréférencer le pointeur dans la phase de collecte, mais vous le feriez quand même dans la phase de test, donc si vous avez suffisamment de L1, ce n'est pas grave. Vous pouvez également améliorer les performances en ajoutant des conseils de prélecture au compilateur __builtin_prefetch, par exemple , bien que ce soit plus facile avec les for(int i=q->length; i-->0; )boucles classiques et autres.

C'est un simple ajustement, mais ma deuxième pensée est qu'il pourrait y avoir un moyen plus rapide d'organiser cela:

Vous pouvez à la place utiliser des bitmaps et éviter le bodiesToCheckvecteur entier . Voici une approche:

Vous utilisez déjà des clés entières pour les corps, mais vous les recherchez ensuite dans des cartes et des objets et vous en tenez aux listes. Vous pouvez passer à un allocateur de slot, qui n'est en fait qu'un tableau ou un vecteur. Par exemple:

class TBodyImpl {
   public:
       virtual ~TBodyImpl() {}
       virtual void onHit(int other) {}
       virtual ....
       const int slot;
   protected:
      TBodyImpl(int slot): slot(slot_) {}
};

struct TBodyBase {
    enum ... type;
    ...
    rect_t rect;
    TQuadTreeNode *quadTreeNode; // see below
    TBodyImpl* imp; // often null
};

std::vector<TBodyBase> bodies; // not pointers to them

Cela signifie que tout ce dont vous avez besoin pour effectuer les collisions réelles est dans une mémoire linéaire compatible avec le cache, et vous ne sortez que sur le bit spécifique à l'implémentation et le joignez à l'un de ces emplacements si cela est nécessaire.

Pour suivre les allocations dans ce vecteur de corps, vous pouvez utiliser un tableau d'entiers comme bitmap et utiliser le twiddling de bits ou__builtin_ffs etc. Vous pouvez même parfois compacter le tableau s'il devient déraisonnablement grand et que les lots sont marqués comme supprimés, en déplaçant ceux à la fin pour combler les lacunes.

vérifier une seule fois chaque collision

Si vous avez vérifié si a entre en collision avec b , vous n'avez pas besoin de vérifier si b entre en collision avec a aussi.

Il résulte de l'utilisation d'identifiants entiers que vous évitez ces vérifications avec une simple instruction if. Si l'ID d'une collision potentielle est inférieur ou égal à l'ID en cours de vérification, il peut être ignoré! De cette façon, vous ne vérifierez chaque association possible qu'une seule fois; cela fera plus de la moitié du nombre de contrôles de collision.

unsigned * bitmap;
int bitmap_len;
...

for(int i=0; i<bitmap_len; i++) {
  unsigned mask = bitmap[i];
  while(mask) {
      const int j = __builtin_ffs(mask);
      const int slot = i*sizeof(unsigned)*8+j;
      for(int neighbour: get_neighbours(slot))
          if(neighbour > slot)
              check_for_collision(slot,neighbour);
      mask >>= j;
  }

respecter l'ordre des collisions

Plutôt que d'évaluer une collision dès qu'une paire est trouvée, calculez la distance à atteindre et stockez-la dans un tas binaire . Ces tas sont la façon dont vous effectuez généralement les files d'attente prioritaires dans la recherche de chemin, c'est donc un code utilitaire très utile.

Marquez chaque nœud avec un numéro de séquence, de sorte que vous pouvez dire:

• A ¹⁰ frappe B ¹² à 6
• A ¹⁰ frappe C ¹² à 3

De toute évidence, après avoir rassemblé toutes les collisions, vous commencez à les extraire de la file d'attente prioritaire, le plus tôt en premier. Ainsi, le premier que vous obtenez est A ¹⁰ frappe C ¹² à 3. Vous incrémentez le numéro de séquence de chaque objet (le ¹⁰ bits), évaluez la collision, calculez leurs nouveaux chemins et stockez leurs nouvelles collisions dans la même file d'attente. La nouvelle collision est A ¹¹ frappe B ¹² à 7. La file d'attente a maintenant:

• A ¹⁰ frappe B ¹² à 6
• A ¹¹ frappe B ¹² à 7

Ensuite, vous sautez de la file d'attente prioritaire et son A ¹⁰ frappe B ¹² à 6. Mais vous voyez que A ¹⁰ est périmé ; A est actuellement à 11. Vous pouvez donc annuler cette collision.

Il est important de ne pas prendre la peine d'essayer de supprimer toutes les collisions périmées de l'arbre; retirer d'un tas coûte cher. Jetez-les simplement lorsque vous les faites éclater.

la grille

Vous devriez plutôt envisager d'utiliser un quadtree. C'est une structure de données très simple à mettre en œuvre. Souvent, vous voyez des implémentations qui stockent des points, mais je préfère stocker des rects et stocker l'élément dans le nœud qui le contient. Cela signifie que pour vérifier les collisions, il vous suffit d'itérer sur tous les corps et, pour chacun, de les comparer à ces corps dans le même nœud à quatre arbres (en utilisant l'astuce de tri décrite ci-dessus) et à tous ceux dans les nœuds à quatre arbres parents. Le quadruple arbre est lui-même la liste des collisions possibles.

Voici un simple Quadtree:

struct Object {
    Rect bounds;
    Point pos;
    Object * prev, * next;
    QuadTreeNode * parent;
};

struct QuadTreeNode {
    Rect bounds;
    Point centre;
    Object * staticObjects;
    Object * movableObjects;
    QuadTreeNode * parent; // null if root
    QuadTreeNode * children[4]; // null for unallocated children
};

Nous stockons les objets mobiles séparément car nous n'avons pas à vérifier si les objets statiques vont entrer en collision avec quoi que ce soit.

Nous modélisons tous les objets sous forme de boîtes englobantes alignées sur l'axe (AABB) et nous les mettons dans le plus petit QuadTreeNode qui les contient. Lorsqu'un QuadTreeNode a beaucoup d'enfants, vous pouvez le subdiviser davantage (si ces objets se répartissent bien entre les enfants).

Chaque tick du jeu, vous devez rentrer dans le quadtree et calculer le mouvement - et les collisions - de chaque objet mobile. Il doit être vérifié pour les collisions avec:

• chaque objet statique dans son nœud
• chaque objet mobile dans son nœud qui est avant (ou après; choisissez simplement une direction) dans la liste movableObjects
• chaque objet mobile et statique dans tous les nœuds parents

Cela générera toutes les collisions possibles, sans ordre. Vous faites ensuite les mouvements. Vous devez hiérarchiser ces mouvements en fonction de la distance et de «qui bouge en premier» (ce qui est votre exigence particulière), et les exécuter dans cet ordre. Utilisez un tas pour cela.

Vous pouvez optimiser ce modèle quadtree; vous n'avez pas besoin de stocker réellement les limites et le point central; c'est entièrement dérivable lorsque vous marchez dans l'arbre. Vous n'avez pas besoin de vérifier si un modèle est dans les limites, vérifiez seulement de quel côté il est du point central (un test "d'axe de séparation").

Pour modéliser des choses qui volent rapidement comme des projectiles, plutôt que de les déplacer à chaque étape ou d'avoir une liste de `` balles '' distincte que vous vérifiez toujours, mettez-les simplement dans le quadtree avec le rect de leur vol pour un certain nombre d'étapes de jeu. Cela signifie qu'ils se déplacent dans le quadtree beaucoup plus rarement, mais vous ne comparez pas les balles contre des murs éloignés, c'est donc un bon compromis.

Les gros objets statiques doivent être divisés en composants; un grand cube devrait avoir chaque face stockée séparément, par exemple.

Je parie que vous n'avez qu'une tonne de cache manqués lors de l'itération sur les corps. Mettez-vous en commun tous vos corps en utilisant un schéma de conception orienté données? Avec une large bande N ^ 2, je peux simuler des centaines et des centaines , tout en enregistrant avec fraps, de corps sans aucune chute de fréquence d'images dans les régions inférieures (moins de 60), et tout cela sans allocateur personnalisé. Imaginez simplement ce qui peut être fait avec une utilisation appropriée du cache.

L'indice est ici:

const std::vector<Body *>

Cela soulève immédiatement un énorme drapeau rouge. Attribuez-vous à ces organismes de nouveaux appels bruts? Y a-t-il un allocateur personnalisé utilisé? Il est très important que vous ayez tous vos corps dans un vaste tableau dans lequel vous parcourez linéairement . Si parcourir la mémoire de façon linéaire n'est pas quelque chose que vous pensez pouvoir implémenter, envisagez plutôt d'utiliser une liste liée de manière intrusive.

De plus, vous semblez utiliser std :: map. Savez-vous comment la mémoire dans std :: map est allouée? Vous aurez une complexité O (lg (N)) pour chaque requête de carte, et cela peut probablement être augmenté à O (1) avec une table de hachage. En plus de cela, la mémoire allouée par std :: map va également horriblement vider votre cache.

Ma solution consiste à utiliser une table de hachage intrusive à la place de std :: map. Un bon exemple de listes liées de manière intrusive et de tables de hachage intrusives se trouve dans la base de Patrick Wyatt au sein de son projet coho: https://github.com/webcoyote/coho

Donc, en bref, vous devrez probablement créer des outils personnalisés pour vous, à savoir un allocateur et des conteneurs intrusifs. C'est le mieux que je puisse faire sans profiler le code pour moi.

Réduisez le nombre de corps pour vérifier chaque image:

Ne vérifiez que les corps qui peuvent réellement bouger. Les objets statiques ne doivent être affectés à vos cellules de collision qu'une seule fois après avoir été créés. Maintenant, vérifiez uniquement les collisions pour les groupes qui contiennent au moins un objet dynamique. Cela devrait réduire le nombre de contrôles de chaque trame.

Utilisez un quadtree. Voir ma réponse détaillée ici

Supprimez toutes les allocations de votre code de physique. Vous voudrez peut-être utiliser un profileur pour cela. Mais j'ai seulement analysé l'allocation de mémoire en C #, donc je ne peux pas m'empêcher avec C ++.

Bonne chance!

Je vois deux candidats à problème dans votre fonction de goulot d'étranglement:

La première est la partie «contient» - c'est probablement la principale raison du goulot d'étranglement. C'est une itération à travers des corps déjà trouvés pour chaque corps. Vous devriez peut-être plutôt utiliser une sorte de table de hachage / table de hachage au lieu de vecteur. L'insertion devrait alors être plus rapide (avec recherche de doublons). Mais je ne connais pas de chiffres précis - je n'ai aucune idée du nombre de corps qui sont itérés ici.

Le deuxième problème pourrait être vector :: clear et push_back. Clear peut ou non évoquer une réallocation. Mais vous voudrez peut-être l'éviter. La solution pourrait être un tableau d'indicateurs. Mais vous pouvez probablement avoir beaucoup d'objets, il est donc inefficace d'avoir une liste de tous les objets pour chaque objet. Une autre approche pourrait être agréable, mais je ne sais pas quelle approche: /

Remarque: je ne connais rien de C ++, seulement Java, mais vous devriez être en mesure de comprendre le code. La physique est un langage universel non? Je me rends également compte que c'est un poste vieux d'un an, mais je voulais juste le partager avec tout le monde.

J'ai un modèle d'observation qui, fondamentalement, après le déplacement de l'entité, il renvoie l'objet avec lequel il est entré en collision, y compris un objet NULL. Tout simplement:

( Je refais Minecraft )

public Block collided(){
   return World.getBlock(getLocation());
}

Alors dites que vous vous promenez dans votre monde. chaque fois que vous vous appelez, move(1)appelezcollided() . si vous obtenez le bloc que vous voulez, alors peut-être que les particules volent et vous pouvez vous déplacer de gauche à droite et en arrière mais pas en avant.

En utilisant cela de manière plus générique que juste minecraft comme exemple:

public Object collided(){
   return threeDarray[3][2][3];
}

Simplement, ayez un tableau pour indiquer les coordonnées qui, littéralement comment Java le fait, utilise des pointeurs.

L'utilisation de cette méthode nécessite encore autre chose qu'a priori méthode a de détection de collision. Vous pouvez boucler cela, mais cela va à l'encontre du but. Vous pouvez l'appliquer aux techniques de collision large, moyenne et étroite, mais seul, c'est une bête surtout quand cela fonctionne assez bien pour les jeux 3D et 2D.

Maintenant, en jetant un coup d'œil de plus, cela signifie que, selon ma méthode minecraft collide (), je me retrouverai à l'intérieur du bloc, donc je devrai déplacer le joueur à l'extérieur. Au lieu de vérifier le joueur, je dois ajouter une boîte englobante qui vérifie quel bloc frappe de chaque côté de la boîte. Problème résolu.

le paragraphe ci-dessus peut ne pas être aussi facile avec des polygones si vous voulez de la précision. Pour plus de précision, je suggérerais de définir un cadre de délimitation de polygone qui n'est pas un carré, mais pas tesselé. sinon, un rectangle est très bien.