Résolution de collision

23

Je sais très bien comment vérifier les collisions, mais je ne sais pas comment gérer la collision dans le bon sens.

Simplifié, si deux objets entrent en collision, j'utilise certains calculs pour changer la direction de la vitesse. Si je ne déplace pas les deux objets, ils se chevaucheront toujours et si la vitesse n'est pas assez grande, ils entreront en collision après la prochaine mise à jour. Cela peut entraîner des objets coincés les uns dans les autres.

Mais que faire si j'essaie de déplacer les deux objets pour qu'ils ne se chevauchent pas. Cela semble être une bonne idée, mais j'ai réalisé que s'il y a plus de deux objets, cela devient très compliqué. Et si je déplace les deux objets et que l'un d'eux entre en collision avec d'autres objets, je dois donc les déplacer aussi et ils peuvent entrer en collision avec des murs, etc.

Je pense à un jeu 2D de haut en bas, mais je ne pense pas que cela y soit pour beaucoup. Comment les collisions sont-elles généralement gérées?

Cette question est posée au nom de Wooh

CiscoIPPhone
la source
1
Pouvez-vous préciser le type de jeu? "Top down 2D" pourrait signifier beaucoup de choses: un jeu d'action-aventure de style Zelda, un jeu de tir à défilement vertical ou un jeu de billard de poche. Tous ces éléments auraient des styles standard très différents de gestion des collisions!
Ian Schreiber
2
Je ne peux pas clarifier cela. La question n'est pas de savoir ce qui se passera à la suite d'une collision, mais de gérer le problème des chevauchements multiples. Je pense qu'il suffit de savoir que je fais rebondir des objets les uns sur les autres et je veux qu'ils se comportent de manière réaliste pour répondre à cette question.
CiscoIPPhone

Réponses:

16

Daniel Kodicek couvre ce sujet en détail dans son livre Mathematics & Physics for Programmers .

Kodicek fait deux choses pour obtenir une résolution de collision d'apparence naturelle:

  • Sa fonction de détection de collision calcule l'heure exacte à laquelle deux objets entreront en collision.
  • Il recalcule les nouvelles vitesses au moment de la collision, afin que les objets ne se chevauchent jamais.

J'ai téléchargé une démo basée sur la détection et la résolution des collisions de Kodicek .

mise à jour: voici un algorithme de détection et de résolution des collisions très similaire à la méthode de Kodicek. Avec le code source . Je recommande toujours le livre de Kodicek, car son algorithme est implémenté légèrement différemment et expliqué de manière beaucoup plus approfondie.

Leftium
la source
1
Votre lien de démonstration semble rompu.
ashes999
@ ashes999: lien corrigé maintenant!
Leftium
C'est un algorithme pour les cercles. Et les boîtes?
Anton Chikin
@AntonChikin: l'algorithme de résolution des collisions de Kodicek ne prend que trois entrées: la masse, la vitesse et la normale au point de collision. Kodicek calcule toujours la normale au point de collision lors de la détection des collisions. Il explique de nombreux types différents de détection de collision, y compris une boîte frappant une autre boîte. Branchez simplement cet algorithme de détection de collision dans l'algorithme de résolution de collision. Voir les chapitres 8-10 du livre de Kodicek pour une explication complète. (Notez que la physique rotationnelle nécessite plus de mathématiques, ce qui est également couvert plus loin dans le livre ...)
Leftium
1
@ThomasHilbert: le code source de la démonstration et les exécutables Windows maintenant disponibles sur leftium.com/asteroid
Leftium
6

Que se passe-t-il si vous vérifiez la collision avant que les objets ne bougent, plutôt qu'après? Ou, en d'autres termes, vous rejetez la nouvelle position si les objets entrent en collision, réutilisant l'ancienne dans ce cas?

Pseudocode:

  tmpPosition1 = Obj1.position
  tmpPosition2 = Obj2.position
  updatePosition(Obj1)
  updatePosition(Obj2)
  if collided(Obj1,Obj2) then
      updateVelocities( Obj1, Obj2 )
      Obj1.position = tmpPosition1
      Obj2.position = tmpPosition2
  endif

De cette façon, les objets se heurteront lorsqu'ils sont sur le point d'entrer en collision , si votre étape de mise à jour est suffisamment petite, le joueur ne devrait rien remarquer d'étrange dans la représentation.

CeeJay
la source
1
C'est assez ennuyeux, car vous ne pouvez pas vous déplacer facilement parallèlement aux objets, car vous ne pouvez pas vous déplacer si vous touchez d'autres objets.
Ikke
Sauf si vous résolvez x et y séparément
instantaphex
6

Chaque fois que deux objets se chevauchent, vérifiez s'ils se rapprochent ou s'éloignent l'un de l'autre. Ne faites la collision que s'ils se rapprochent l'un de l'autre.

C'est assez facile avec les mathématiques vectorielles, calculez simplement:

dot_product (B.position - A.position, A.velocity - B.velocity)

Si le résultat est positif, les objets se rapprochent.

aaaaaaaaaaaa
la source
4

Je pourrais me méprendre, mais il semble que vous posiez deux questions: 1. Quels sont les moyens généraux de gérer la résolution des collisions? Le terme que vous recherchez est «simulation basée sur les impulsions», et il y a un tas d'articles qui peut le faire mieux que moi.

En résumé, vous voulez faire avancer votre simulation physique dans l'espace de momentum, qui est la masse multipliée par la vitesse (ne faites pas les choses en fonction de la force, votre intégrateur ne le fait pas correctement de toute façon).

Pour la réponse angulaire, heureusement, les moments d'inertie les plus grands et les plus faibles peuvent toujours être réduits à deux axes orthogonaux (en 2D), ce qui signifie qu'une multiplication matricielle fonctionnera généralement, et si vous les alignez avec les axes X et Y, cela se transforme en un vecteur 2D.

Lorsque vous avez une collision, vous déterminez la réponse en fonction des moments linéaires et angulaires au point de collision, et un bon facteur de fudge est, si vous avez une interpénétration, d'appliquer une force de pénalité (comme mentionné ci-dessus) pour séparer les deux corps.

À partir du moment où vous finirez par ajouter de plus en plus de règles pour contrôler les comportements aberrants, comme limiter le moment angulaire maximal afin que les choses ne tournent pas comme des sommets, etc., mais c'est un bon début.

Restez simple si vous le pouvez.

  1. Comment résoudre les problèmes de collision multi-corps

La seule vraie façon de le faire est avec un système d'équations linéaires et beaucoup de résolution. La façon pratique de le faire est d'avoir un système comme celui ci-dessus et de faire en sorte que la physique se résorbe naturellement au fil du temps.

La plupart des jeux qui font des choses comme rouler ou se tenir debout sur des surfaces mobiles, ont un modèle hybride où vos pieds sont attachés à une surface (ou des roues à la route) pour s'adapter au temps physique (ce qui entraînerait des cycles d'interpénétration-réponse et ne fonctionnerait pas).

J'espère que cela t'aides. Si vous avez besoin d'exemples mathématiques, faites-le moi savoir.

Aaron Brady
la source
3

La façon dont cela est généralement résolu dans les moteurs physiques consiste à appliquer une force de pénalité. Déplacer le corps rigide après l'interpénétration n'aura pas l'air bien si vos corps rigides se déplacent à des vitesses plus élevées (vous verrez des mouvements saccadés momentanés), bien que dans un premier temps, vous devriez essayer cela et voir si cela convient à vos besoins.

A penalty forceest appliqué comme un amortisseur à ressort, où la force de pénalité est augmentée plus vous avez pénétré le corps rigide et est diminué dans les cadres suivants. Considérez-le comme des ressorts. Lorsque deux corps rigides pénètrent entre eux, ils rencontrent chacun un ressort invisible qui amortit leur progression (c'est-à-dire qui empêche plus d'inter-pénétration) et applique le précédentpenalty force jusqu'à ce que les corps ne pénètrent plus.

C'est un sujet large mais j'espère que les informations ci-dessus vous aideront à démarrer.

Samaursa
la source
Donc, au lieu d'empêcher l'interpénétration, cette méthode le permet mais offre une résistance, presque comme si les objets étaient compressés?
CiscoIPPhone
Il offre une résistance, oui, la résistance augmente plus le corps essaie de pénétrer. En pratique, si vous avez un temps de delta suffisamment bas (par exemple 10 ms), il ne produira aucune inter-pénétration. Cependant, le véritable avantage de cette méthode est lorsque vous avez des corps qui ont pénétré pour diverses raisons (la position a été modifiée, ce sont des corps rigides en réseau et leurs positions ont été corrigées) et doivent maintenant être séparés, car sans cette technique, les corps va exploser plutôt que de se séparer progressivement.
Samaursa