Comment fonctionne un moteur de collision?

Comment fonctionne exactement un moteur de collision ?

C'est une question extrêmement vaste. Quel code empêche les choses de rebondir les uns contre les autres, quel code fait-il que le joueur marche dans un mur au lieu de marcher à travers le mur? Comment le code actualise-t-il constamment la position du joueur et celle des objets pour que la gravité et la collision fonctionnent comme il se doit?

Si vous ne savez pas ce qu'est un moteur de collision, il est généralement utilisé dans les jeux de plate-forme pour que le joueur frappe réellement les murs, etc. Il existe le type 2D et le type 3D, mais ils accomplissent tous la même chose: la collision.

Alors, qu'est-ce qui fait tourner le moteur de collision?

Il y a une grande différence entre un moteur de collision et un moteur physique. Ils ne font pas la même chose, bien que le moteur physique repose généralement sur un moteur de collision.

Le moteur de collision est ensuite divisé en deux parties: la détection de collision et la réponse à la collision. Ce dernier fait généralement partie du moteur physique. C'est pourquoi les moteurs de collision et les moteurs physiques sont généralement intégrés à la même bibliothèque.

La détection de collision se présente sous deux formes: discrète et continue. Les moteurs avancés prennent en charge les deux, car ils ont des propriétés différentes. En général, la détection de collision en continu est très coûteuse et n’est utilisée que là où elle est réellement nécessaire. La majorité des collisions et de la physique sont traitées à l'aide de méthodes discrètes. Dans les méthodes discrètes, les objets finissent par se pénétrer les uns les autres et le moteur physique s’efforce alors de les écarter. Ainsi, le moteur n’empêche pas un joueur de marcher partiellement à travers un mur ou le sol, il le répare simplement après avoir détecté que le joueur se trouve partiellement dans le mur / le sol. Je vais me concentrer sur la détection discrète des collisions, car c’est ce que j’ai le plus d’expérience en implémentation à partir de zéro.

Détection de collision

La détection de collision est relativement facile. Chaque objet a une transformation et une forme (éventuellement plusieurs formes). Les approches naïves demanderaient au moteur de collision d'effectuer une boucle O (n ^ 2) sur toutes les paires d'objets et de tester s'il y a un chevauchement entre les paires. Dans les approches plus intelligentes, il existe plusieurs structures de données spatiales (par exemple, pour des objets statiques ou dynamiques), une forme de contour pour chaque objet et des sous-formes convexes en plusieurs parties pour chaque objet.

Les structures de données spatiales comprennent des éléments tels que les arbres KD, les arbres AABB dynamiques, les arbres Octrees / Quadtrees, les arbres de partitionnement d’espaces binaires, etc. Chacun a ses avantages et ses inconvénients, c'est pourquoi certains moteurs haut de gamme en utilisent plusieurs. Les arbres AABB dynamiques, par exemple, sont vraiment très rapides et bons pour la gestion de nombreux objets en mouvement, alors qu'un arbre KD peut être plus adapté à la géométrie de niveau statique avec laquelle les objets se heurtent. Il y a aussi d'autres options.

La phase large utilise les structures de données spatiales et un volume englobant abstrait pour chaque objet. Un volume de délimitation est une forme simple qui entoure l’intégralité de l’objet, généralement dans le but de l’enfermer aussi "étroitement" que possible tout en restant peu coûteux pour faire des tests de collision. Les formes de contour les plus courantes sont les zones de contour alignées sur les axes, les zones de contour, les sphères et les capsules. Les AABB sont généralement considérés comme les plus rapides et les plus faciles (les sphères sont plus faciles et plus rapides dans certains cas, mais bon nombre de ces structures de données spatiales nécessiteraient de toute façon une conversion de la sphère en AABB), mais elles tendent également à s'adapter plutôt mal à de nombreux objets. Les capsules sont populaires dans les moteurs 3D pour gérer les collisions au niveau des personnages. Certains moteurs utiliseront deux formes,

La dernière phase de la détection de collision consiste à détecter exactement où la géométrie se croise. Cela implique généralement l'utilisation d'un maillage (ou d'un polygone en 2D), mais pas toujours. Le but de cette phase est de déterminer si les objets entrent réellement en collision, si un niveau de détail précis est requis (par exemple, une collision de balles dans un tireur, où vous voulez pouvoir ignorer les tirs qui manquent de peu), et également pour savoir exactement où les objets entrent en collision, ce qui affectera la façon dont les objets répondent. Par exemple, si une boîte repose sur le bord d’une table, le moteur doit savoir à quels points la table la pousse contre la boîte; En fonction de la position de la boîte, celle-ci peut commencer à basculer et à tomber.

Génération de collecteur de contact

Les algorithmes utilisés ici incluent les algorithmes populaires de raffinement de portail GJK et Minkowski, ainsi que le test de séparation des axes. Comme les algorithmes populaires ne fonctionnent généralement que pour les formes convexes, il est nécessaire de diviser de nombreux objets complexes en sous-objets convexes et d'effectuer des tests de collision pour chacun d'eux individuellement. C'est l'une des raisons pour lesquelles les maillages simplifiés sont souvent utilisés pour les collisions, ainsi que la réduction du temps de traitement pour utiliser moins de triangles.

Certains de ces algorithmes vous indiquent non seulement que les objets sont entrés en collision avec certitude, mais également à quel endroit ils sont entrés en collision - à quel point ils se pénètrent et quels sont les "points de contact". Certains algorithmes nécessitent des étapes supplémentaires, telles que la coupure de polygone, pour obtenir ces informations.

Réponse physique

À ce stade, un contact a été découvert et il y a suffisamment d'informations pour que le moteur physique puisse traiter le contact. La manipulation de la physique peut devenir très complexe. Des algorithmes plus simples fonctionnent pour certains jeux, mais même quelque chose d'aussi simple que de garder une pile de boîtes stable s'avère être assez difficile et nécessite beaucoup de travail et des bidouilles non évidentes.

Au niveau le plus élémentaire, le moteur physique opère comme ceci: il prend les objets en collision et leur collecteur de contact et calcule les nouvelles positions requises pour séparer les objets en collision. Cela déplacera les objets vers ces nouvelles positions. Il calculera également le changement de vitesse résultant de cette poussée, combiné aux valeurs de restitution (rebondissement) et de frottement. Le moteur physique appliquera également toutes les autres forces agissant sur les objets, telles que la gravité, pour calculer les nouvelles vitesses de ces objets, puis (nouvelle image) leurs nouvelles positions.

Une réponse physique plus avancée se complique rapidement. L'approche ci-dessus va échouer dans de nombreuses situations, y compris un objet placé au-dessus de deux autres. Traiter chaque paire séparément provoquera une "instabilité" et les objets rebondiront beaucoup. La technique la plus élémentaire consiste à effectuer un certain nombre d'itérations de correction de la vitesse sur les paires d'objets en collision. Par exemple, avec une boîte "A" placée au-dessus de deux autres boîtes "B" et "C", la collision AB sera traitée en premier, ce qui amènera la boîte A à basculer plus loin dans la boîte C. Ensuite, la collision AC sera gérée le soir. sortez les cases un peu, mais en tirant A vers le bas et en B. Ensuite, une autre itération est effectuée, de sorte que l'erreur AB causée par la correction AC est légèrement résolue, ce qui crée un peu plus d'erreur dans la réponse AC. Ce qui est traité quand AC est traité à nouveau. Le nombre d'itérations effectuées n'est pas fixe et il n'y a pas de moment où il devient «parfait», mais plutôt quel que soit le nombre d'itérations qui cesse de donner des résultats significatifs. Un premier essai typique est de 10 itérations, mais il faut peaufiner le meilleur chiffre pour un moteur particulier et les besoins d’un jeu particulier.

Mise en cache des contacts

Il existe d'autres astuces qui s'avèrent très utiles (plus ou moins nécessaires) pour gérer de nombreux types de jeux. La mise en cache des contacts est l’une des plus utiles. Avec un cache de contacts, chaque ensemble d'objets en conflit est enregistré dans une table de recherche. Lors de la détection d'une collision, chaque trame est interrogée sur ce cache afin de déterminer si les objets étaient précédemment en contact. Si les objets n'étaient pas précédemment en contact, un événement "nouvelle collision" peut être généré. Si les objets étaient précédemment en contact, les informations peuvent être utilisées pour fournir une réponse plus stable. Toute entrée du cache de contacts qui n'a pas été mise à jour dans un cadre indique que deux objets se sont séparés et qu'un événement "objet séparant" peut être généré. La logique du jeu a souvent des utilisations pour ces événements.

Il est également possible que la logique de jeu réponde aux nouveaux événements de collision et les signale comme ignorés. Ceci est très utile pour implémenter certaines fonctionnalités communes aux plates-formes, telles que celles sur lesquelles vous pouvez passer mais que vous pouvez utiliser. Les implémentations naïves peuvent simplement ignorer les collisions qui ont une plate-forme descendante normale -> collisions de personnages (indiquant que la tête du joueur touche la base de la plate-forme), mais sans la mise en cache des contacts, cela se brisera si la tête du joueur se soulève sur la plate-forme puis il commence tomber. À ce stade, le contact normal peut finir par pointer vers le haut, ce qui oblige le joueur à apparaître à travers la plate-forme alors qu'il ne le devrait pas. Avec la mise en cache des contacts, le moteur peut examiner de manière fiable la normale de la collision initiale et ignorer tous les autres événements de contact jusqu'à ce que la plate-forme et le joueur se séparent à nouveau.

En train de dormir

Une autre technique très utile consiste à marquer les objets comme étant "endormis" s'ils ne sont pas en interaction. Les objets en sommeil ne reçoivent pas de mises à jour physiques, n'entrent pas en collision avec d'autres objets en sommeil et restent simplement figés dans le temps jusqu'à ce qu'un autre objet qui ne s'endorme pas entre en collision avec eux.

L’impact est que toutes les paires d’objets en collision qui sont simplement assis là et ne font rien ne prennent pas de temps de traitement. De plus, comme il n’ya pas une quantité constante de minuscules corrections physiques, les piles seront stables.

Un objet est un candidat pour dormir lorsqu'il a une vitesse proche de zéro pour plus d'une image. Notez que l'epsilon que vous utilisez pour tester cette vitesse proche de zéro sera probablement un peu plus élevé que la comparaison habituelle epsilon en virgule flottante, car vous devez vous attendre à une certaine gigue avec des objets empilés et vous voulez que des piles entières s'endorment si elles ' Restez "assez proche" de l'écurie. Le seuil nécessitera bien sûr des ajustements et de l’expérimentation.

Contraintes

Le dernier élément majeur de nombreux moteurs physiques est le résolveur de contraintes. Le but d'un tel système est de faciliter la mise en œuvre d'éléments tels que les ressorts, les moteurs, les axes de roues, les corps mous simulés, les tissus, les cordes et les chaînes, et parfois même les fluides (bien que les fluides soient souvent mis en œuvre sous un système totalement différent).

Même les bases de la résolution de contraintes peuvent être très intensives en mathématiques et vont au-delà de mon expertise dans ce domaine. Je recommande de consulter l'excellente série d'articles de Randy Gaul sur la physique pour une explication plus détaillée du sujet.

Le problème général: déterminer laquelle de toutes les combinaisons possibles d'objets a un volume d'intersection non nul.

L’approche générale naïve est simple: pour chaque paire d’objets possible, calculez le volume d’intersection. Cela n’est généralement pas pratique, car cela nécessite O (n ^ 2) opérations d’intersection relativement coûteuses.

Par conséquent, les implémentations pratiques sont souvent spécialisées et émettent certaines hypothèses permettant d'éviter les contrôles d'intersection ou de réduire leur coût. Le partitionnement spatial tire parti du fait que les objets sont généralement petits par rapport au volume total et réduira généralement le nombre de comparaisons à O (n log n). Les boîtes englobantes et les sphères englobantes alignées sur l'axe fournissent des vérifications d'intersection grossières peu coûteuses, à condition que les objets obéissent à certaines hypothèses de compacité. Etc.

Un "moteur de collision" que j'ai utilisé était extrêmement facile à saisir.

Fondamentalement, l’API fournissait une sorte d’objet possédant une méthode collidesWith, telle que

1. ses paramètres étaient différents types d'objets qui étaient "éligibles" pour la collision
2. il est retourné vrai ou faux selon que la collision s'est produite ou non
3. une option permettait de choisir si tous les rectangles de délimitation des objets déclenchaient un événement de collision ou si seuls les pixels opaques à l'intérieur de ces rectangles (détection au niveau du pixel)

Dans ma candidature, je viens d'appeler périodiquement collidesWithpour savoir si une collision s'est produite ou non.

Assez simple n'est-ce pas?

Peut-être que la seule chose qui exigeait un effort d'imagination mineur était lorsque les rectangles simples ne suffisaient pas pour simuler la géométrie des objets en collision. Dans ce cas, il faudrait simplement utiliser plusieurs objets pouvant être collidés au lieu d’un seul.

Généralement, lorsque vous découvrez que le rectangle de collision unique ne fait pas ce dont vous avez besoin, vous inventez un moyen de décomposer les choses en sous-éléments plus rectangulaires afin que, une fois combinés, ces éléments simulent / approchent le comportement souhaité.

• Les utilisateurs finaux ne se soucient pas du nombre d'objets derrière la scène. Ils sont heureux tant que le résultat final correspond à ce qu'ils attendent, par exemple une maison entourée d'une clôture dans la cour:

  

Je pense que vous êtes un peu confus sur ce dont vous parlez et que vous parlez de différentes choses.

la possibilité de dire que cet objet est déplacé de l'emplacement X à l'emplacement Y est basé sur la physique (cela affecte également la façon dont ils se déplacent et pourquoi ils se déplacent)

la méthode utilisée pour la détection de collision est déterminée en fonction de la structure de votre jeu. Si votre jeu est un grand monde ouvert, alors vous devriez sérieusement envisager le partitionnement de l'espace (quad-tree [oct-tree pour la 3D], BSP, une grille traditionnelle ou une approche de test à l'ancienne).

la meilleure façon de mettre en œuvre un système de détection de collision est de le faire par étapes.

1. placez tous les objets dans un volume / forme de liaison générique, puis testez-les

2. si 1 réussit, répétez l'opération avec un volume / une forme plus complexe, répétez l'opération jusqu'à ce que vous soyez prêt à tester la géométrie absolue

3. testez la géométrie absolue le nombre de fois où vous répétez l'étape 2 doit être déterminé en fonction de la complexité de vos formes et de leur précision.

vous devez considérer chacune de ces étapes comme étant précoces et dans le but d’éliminer les collisions au fur et à mesure, et de ne rendre la vérité à l’étape 3 que si elles se touchent réellement.

Puis pour la dernière partie est résolution de collision. cela détermine ce qui se passe après la découverte d'une collision et la preuve qu'il s'agit bien d'une collision, et ce qu'il faut faire à ce sujet. cela est généralement traité par la physique.

la boucle traditionnelle ressemble à ceci:

receive input
update physics
collision detection
collision resolution
render
repeat

Au niveau de la carte graphique (où vous traitez habituellement avec des triangles), l’idée générale est de partitionner votre scène de façon à ne pas avoir à vérifier tous les N triangles (ceci peut être fait comme une étape de pré-traitement ), puis déterminez où vous vous trouvez dans la scène et vérifiez uniquement les 10 à 50 triangles de cette partition.

Voir arbres BSP et Kd pour plus d'informations. Il existe également d'autres approches de partitionnement.

Tout d'abord, je pense que le travail le plus important d'un moteur de collision consiste à déterminer ce qui n'est pas nécessaire de vérifier la collision dans une situation particulière, image par image, et à éliminer ces objets de contrôles ultérieurs.

Deuxièmement, mais aussi important, vérifiez de manière plus détaillée (précise) les objets restants qui n’ont pas été triés lors de cette première étape.

Troisièmement, utilisez les méthodes les plus efficaces / appropriées pour effectuer les contrôles.