Momentum et ordre des problèmes de mise à jour dans mon moteur physique

22

entrez la description de l'image ici

Cette question est une question "de suivi" de ma précédente, concernant la détection et la résolution des collisions, que vous pouvez trouver ici .


Si vous ne voulez pas lire la question précédente, voici une brève description du fonctionnement de mon moteur physique:

Chaque entité physique est stockée dans une classe appelée SSSPBody.

Seuls les AABB sont pris en charge.

Chaque SSSPBody est stocké dans une classe appelée SSSPWorld, qui met à jour chaque corps et gère la gravité.

À chaque image, SSSPWorld met à jour chaque corps.

Chaque corps mis à jour recherche les corps à proximité dans un hachage spatial, vérifie s'ils doivent détecter les collisions avec eux. Si oui, ils invoquent un événement "collision" et vérifient s'ils doivent résoudre les collisions avec eux. Si oui, ils calculent le vecteur de pénétration et le chevauchement directionnel, puis modifient leur position afin de résoudre la pénétration.

Lorsqu'un corps entre en collision avec un autre, il transfère sa vitesse à l'autre en réglant simplement la vitesse du corps à la sienne.

La vitesse d'un corps est définie sur 0 lorsqu'il n'a pas changé de position depuis la dernière image. S'il entre également en collision avec un corps en mouvement (comme un ascenseur ou une plate-forme mobile), il calcule la différence de mouvement de l'ascenseur pour voir si le corps n'a pas bougé de sa dernière position.

En outre, un corps invoque un événement "écrasé" lorsque tous ses coins AABB chevauchaient quelque chose dans un cadre.

Ceci est le code source COMPLET de mon jeu. Il est divisé en trois projets. SFMLStart est une bibliothèque simple qui gère la saisie, le dessin et la mise à jour des entités. SFMLStartPhysics est le plus important, où se trouvent les classes SSSPBody et SSSPWorld. PlatformerPhysicsTest est le projet de jeu, contenant toute la logique du jeu.

Et c'est la méthode « mise à jour » dans la classe SSSPBody, a commenté et simplifié. Vous ne pouvez y jeter un œil que si vous n'avez pas envie de regarder l'ensemble du projet SFMLStartSimplePhysics. (Et même si vous le faites, vous devriez toujours y jeter un œil car il est commenté.)


Le .gif montre deux problèmes.

  1. Si les corps sont placés dans un ordre différent, des résultats différents se produisent. Les caisses de gauche sont identiques aux caisses de droite, placées uniquement dans l'ordre inverse (dans l'éditeur).
  2. Les deux caisses doivent être propulsées vers le haut de l'écran. Dans la situation de gauche, aucune caisse n'est propulsée. À droite, un seul d'entre eux l'est. Les deux situations sont involontaires.

Premier problème: ordre de mise à jour

C'est assez simple à comprendre. Dans la situation de gauche, la caisse la plus haute est mise à jour avant l'autre. Même si la caisse du bas "transfère" la vitesse à l'autre, elle doit attendre la prochaine image pour se déplacer. Comme il n'a pas bougé, la vitesse de la caisse inférieure est réglée sur 0.

Je n'ai aucune idée de comment résoudre ce problème. Je préférerais que la solution ne dépende pas du "tri" de la liste de mise à jour, car je pense que je fais quelque chose de mal dans la conception du moteur physique.

Comment les principaux moteurs physiques (Box2D, Bullet, Chipmunk) gèrent-ils l'ordre de mise à jour?


Deuxième problème: une seule caisse est propulsée vers le plafond

Je ne comprends pas encore pourquoi cela se produit. Ce que fait l'entité "ressort" est de régler la vitesse du corps à -4000 et de la repositionner au-dessus du ressort lui-même. Même si je désactive le code de repositionnement, le problème persiste.

Mon idée est que lorsque la caisse inférieure entre en collision avec la caisse supérieure, sa vitesse est fixée à 0. Je ne sais pas pourquoi cela se produit.


Malgré la chance de ressembler à quelqu'un qui abandonne au premier problème, j'ai posté tout le code source du projet ci-dessus. Je n'ai rien pour le prouver, mais croyez-moi, j'ai essayé de résoudre ce problème, mais je n'ai tout simplement pas trouvé de solution et je n'ai aucune expérience préalable de la physique et des collisions. J'essaie de résoudre ces deux problèmes depuis plus d'une semaine et maintenant je suis désespéré.

Je ne pense pas que je puisse trouver une solution par moi-même sans retirer de nombreuses fonctionnalités du jeu (transfert de vitesse et ressorts, par exemple).

Merci beaucoup pour le temps passé à lire cette question, et merci encore plus si vous essayez de trouver une solution ou une suggestion.

Vittorio Romeo
la source
Chaque fois que vous empilez des boîtes, pourriez-vous combiner leur physique pour qu'elles soient considérées comme un seul objet?
CiscoIPPhone

Réponses:

12

En fait, les problèmes d'ordre de mise à jour sont assez courants pour les moteurs de physique des impulsions normales, vous ne pouvez pas simplement retarder l'application de la force comme le suggère Vigil, vous finiriez par briser la conservation de l'énergie lorsqu'un objet entre simultanément en collision avec 2 autres. Habituellement, ils parviennent à créer quelque chose qui semble assez réel, même si un ordre de mise à jour différent aurait produit un résultat sensiblement différent.

Dans tous les cas, pour votre objectif, il y a suffisamment de hoquets dans un système d'impulsions que je vous suggérerais plutôt de construire un modèle de masse-ressort.

L'idée de base est qu'au lieu d'essayer de résoudre une collision en une seule étape, vous appliquez une force aux objets qui entrent en collision, cette force devrait être équivalente à la quantité de chevauchement entre les objets, ce qui est comparable à la façon dont les objets réels lors d'une collision transforment leur l'énergie de mouvement en déformation, puis de nouveau en mouvement, la grande chose à propos de ce système est qu'il permet à la force de voyager à travers un objet sans que cet objet ait à rebondir d'avant en arrière, et cela peut raisonnablement être fait complètement indépendamment de la mise à jour.

Pour que les objets s'arrêtent plutôt que de rebondir indéfiniment, vous devrez appliquer une certaine forme d'amortissement, vous pouvez grandement affecter le style et la sensation de votre jeu en fonction de la façon dont vous le faites, mais une approche très basique serait de appliquer une force à deux objets en contact équivalente à leur mouvement interne, vous pouvez choisir de l'appliquer uniquement lorsqu'ils se rapprochent l'un de l'autre, ou lorsqu'ils s'éloignent l'un de l'autre, ce dernier peut être utilisé pour empêcher complètement les objets de rebondir quand ils touchent le sol, mais les rendront également un peu collants.

Vous pouvez également créer un effet de friction en freinant un objet dans la direction perpendiculaire à une collision, la quantité de freinage doit être équivalente à la quantité de chevauchement.

Vous pouvez contourner assez facilement le concept de masse en faisant en sorte que tous les objets aient la même masse, et les objets immobiles fonctionneront comme ayant une masse infinie si vous négligez simplement de les accélérer.

Un pseudo-code, juste au cas où ce qui précède n'était pas assez clair:

//Presuming that you have done collision checks between two objects and now have  
//numbers for how much they overlap in each direction.
overlapX
overlapY
if(overlapX<overlapY){ //Do collision in direction X
    if(obj1.X>obj2.X){
        swap(obj1,obj2)
    }
    //Spring effect:
    obj1.addXvelocity-=overlapX*0.1 //Constant, the lower this is set the softer the  
                                    //collision will be.
    obj2.addXvelocity+=overlapX*0.1
    //Dampener effect:
    velocityDifference=obj2.Xvelocity-obj1.Xvelocity
    //velocityDifference=min(velocityDifference,0) //Uncomment to only dampen when  
                                                   //objects move towards each other.
    obj1.addXvelocity+=velocityDifference*0.1 //Constant, higher for more dampening.
    obj2.addXvelocity-=velocityDifference*0.1
    //Friction effect:
    if(obj1.Yvelocity>obj2.Yvelocity){
        swap(obj1,obj2)
    }
    friction=overlapX*0.01
    if(2*friction>obj2.Yvelocity-obj1.Yvelocity){
        obj1.addYvelocity+=(obj2.Yvelocity-obj1.Yvelocity)/2
        obj2.addYvelocity-=(obj2.Yvelocity-obj1.Yvelocity)/2
    }
    else{
        obj1.addYvelocity+=friction
        obj2.addYvelocity-=friction
    }
}
else{ //Do collision in direction Y

}

Le point des propriétés addXvelocity et addYvelocity est que celles-ci sont ajoutées à la vitesse de leur objet une fois la gestion des collisions terminée.

Modifier:
vous pouvez faire des choses dans l'ordre suivant, où chaque puce doit être effectuée sur tous les éléments avant que la suivante ne soit effectuée:

  • Détectez les collisions, elles peuvent être résolues dès qu'elles sont détectées.
  • Ajoutez les valeurs addVelocity aux valeurs de vitesse, ajoutez la gravité Yvelocity, réinitialisez les valeurs addVelocity à 0, déplacez les objets en fonction de leur vitesse.
  • Rendez la scène.

De plus, je me rends compte que ce qui suit peut ne pas être complètement clair dans mon message initial, sous l'influence des objets de gravité qui se chevaucheront lorsqu'ils se poseront les uns sur les autres, cela suggère que leur boîte de collision devrait être légèrement plus élevée que leur représentation graphique pour éviter le chevauchement visuellement. Ce problème sera moindre si la physique est exécutée à un taux de mise à jour plus élevé. Je vous suggère d'essayer de fonctionner à 120 Hz pour un compromis raisonnable entre le temps CPU et la précision physique.

Edit2:
Flux de moteur physique très basique:

  • Les collisions et la gravité produisent une force / accélération. acceleration = [Complicated formulas]
  • La force / accélération est ajoutée à la vitesse. velocity += acceleration
  • La vélocité est ajoutée à la position. position += velocity
aaaaaaaaaaaa
la source
Ça a l'air bien, jamais pensé à un ressort de masse pour les plateformes. Bravo pour quelque chose d'éclairant :)
EnoughTea
Je vais essayer de l'implémenter dans quelques heures, quand je serai de retour à la maison. Dois-je déplacer les corps (Position + = Vitesse) simultanément, puis vérifier les collisions, ou déplacer et vérifier les collisions une par une? [De plus, dois-je modifier manuellement la position pour résoudre les collisions? Ou est-ce que changer la vitesse va s'en occuper?]
Vittorio Romeo
Je ne sais pas trop comment interpréter votre première question. La résolution des collisions changera la vitesse et n'influencera donc qu'indirectement la position.
aaaaaaaaaaaa
Le fait est que je déplace des entités en réglant manuellement leur vitesse à une certaine valeur. Pour résoudre les chevauchements, je supprime la distance de chevauchement de leur position. Si j'utilise votre méthode, devrai-je déplacer des entités en utilisant des forces ou autre chose? Je n'ai jamais fait ça auparavant.
Vittorio Romeo
Techniquement, oui il faudra utiliser des forces, dans mon morceau de code c'est cependant un peu simplifié avec tous les objets ayant le poids 1, et la force étant donc égale à l'accélération.
aaaaaaaaaaaa
14

Eh bien, vous n'êtes évidemment pas quelqu'un qui abandonne facilement, vous êtes un vrai homme de fer, j'aurais jeté les mains en l'air beaucoup plus tôt, car ce projet ressemble beaucoup à une forêt de varech :)

Tout d'abord, les positions et les vitesses sont définies partout, du point de vue du sous-système physique, c'est la recette d'une catastrophe. En outre, lorsque vous modifiez des éléments intégraux par différents sous-systèmes, créez des méthodes privées telles que "ChangeVelocityByPhysicsEngine", "ChangeVelocityBySpring", "LimitVelocity", "TransferVelocity" ou quelque chose du genre. Il ajoutera une capacité de vérifier les changements apportés par une partie spécifique de la logique et fournira une signification supplémentaire à ces changements de vitesse. De cette façon, le débogage serait plus facile.

Premier problème.

Sur la question elle-même. Maintenant, vous appliquez simplement les corrections de position et de vitesse "au fur et à mesure" par ordre d'apparence et de logique de jeu. Cela ne fonctionnera pas pour des interactions complexes sans coder en dur la physique de chaque chose complexe. Un moteur physique séparé n'est alors pas nécessaire.

Afin de faire des interactions complexes sans hacks, vous devez ajouter une étape supplémentaire entre la détection des collisions en fonction des positions qui ont été modifiées par les vitesses initiales et les changements finaux des positions en fonction de la "post-vitesse". J'imagine que ça se passerait comme ceci:

  • intégrer la vitesse en utilisant toutes les forces agissant sur les corps (vous appliquez directement des corrections de vitesse, laissez les calculs de vitesse à votre moteur physique et utilisez des forces pour déplacer les choses à la place) , puis utilisez la nouvelle vitesse pour intégrer les positions.
  • détecter les collisions, puis restaurer la vitesse et les positions,
  • puis traiter les collisions (en utilisant des impulsions sans mise à jour immédiate de la position, ofc, seule la vitesse est modifiée jusqu'à l'étape finale)
  • réintégrer la nouvelle vitesse et traiter à nouveau toutes les collisions à l'aide d'impulsions, sauf que les collisions sont désormais inélastiques.
  • faire l'intégration finale des positions en utilisant la vitesse résultante.

D'autres choses peuvent apparaître, comme traiter les secousses, le refus de s'empiler lorsque le FPS est petit, ou d'autres choses comme ça, soyez prêt :)

Deuxième problème

La vitesse verticale de ces deux caisses "à port en lourd" ne change jamais de zéro. Étrangement, dans la boucle de mise à jour de PhysSpring, vous affectez la vitesse, mais dans la boucle de mise à jour de PhysCrate, elle est déjà nulle. Il est possible de trouver une ligne où la vélocité va mal, mais j'ai arrêté le débogage ici car c'est la situation "Reap What You Sew". Il est temps d'arrêter le codage et de tout repenser lorsque le débogage devient difficile. Mais s'il arrive à un point où il est impossible, même pour l'auteur du code, de comprendre ce qui se passe dans le code, votre base de code est déjà morte sans que vous vous en rendiez compte :)

Troisième problème

Je pense que quelque chose ne fonctionne pas lorsque vous devez recréer une partie de Farseer pour faire un simple jeu de plateforme basé sur des tuiles. Personnellement, je considérerais votre moteur actuel comme une expérience formidable, puis je l'abandonnerais complètement pour une physique basée sur des carreaux plus simple et plus directe. Ce faisant, il serait sage de reprendre des choses comme Debug.Assert et peut-être même, oh l'horreur, des tests unitaires, car il serait possible de détecter des choses inattendues plus tôt.

EnoughTea
la source
J'ai aimé cette comparaison "forêt de varech".
Den
En fait, j'ai un peu honte d'utiliser de tels mots, mais je sentais que si cela se traduisait par une refactorisation ou deux, alors ce serait justifié.
EnoughTea
Avec un seul test à t , n'y aura- t -il pas toujours une possibilité que cela se produise? J'imagine que vous auriez besoin d'intégrer les vitesses à t , puis de vérifier les collisions en t + 1 avant de régler les vitesses à 0?
Jonathan Connell
Oui, nous détectons les collisions à venir après avoir intégré l'état initial à venir de t à t + dt en utilisant Runge-Kutta ou quelque chose.
EnoughTea
"intégrer la vitesse en utilisant toutes les forces agissant sur les corps" "laisser les calculs de vitesse à votre moteur physique" - je comprends ce que vous essayez de dire, mais je n'ai aucune idée de la façon de procéder. Y a-t-il un exemple / article que vous pouvez me montrer?
Vittorio Romeo
7

Lorsqu'un corps entre en collision avec un autre, il transfère sa vitesse à l'autre en réglant simplement la vitesse du corps à la sienne.

Votre problème est que ce sont des hypothèses fondamentalement erronées sur le mouvement, donc ce que vous obtenez ne ressemble pas au mouvement car vous le connaissez.

Lorsqu'un corps entre en collision avec un autre, l'élan est conservé. Penser à ceci comme "A frappe B" contre "B frappe A" revient à appliquer un verbe transitif à une situation intransitive. A et B entrent en collision; l'impulsion résultante doit être égale à l'impulsion initiale. Autrement dit, si A et B sont de masse égale, ils voyagent maintenant tous les deux avec la moyenne de leurs vitesses d'origine.

Vous aurez également probablement besoin d'un peu de collision et d'un solveur itératif, ou vous rencontrerez des problèmes de stabilité. Vous devriez probablement lire certaines des présentations d'Erin Catto sur GDC.


la source
2
Ils n'obtiendraient la moyenne de la vitesse d'origine que si la collision est complètement inélastique, par exemple A et B sont des morceaux de pâte.
Mikael Öhman
"en réglant simplement la vitesse du corps à la sienne". Ce sont des déclarations comme celle-ci qui expliquent pourquoi cela ne fonctionne pas. En général, j'ai toujours constaté que des personnes inexpérimentées écrivent des systèmes de physique sans comprendre les principes sous-jacents impliqués. Vous ne réglez jamais simplement la vitesse ou simplement ... Toute modification des propriétés d'un corps doit être une application directe des lois de la dynamique; y compris la conservation de la quantité de mouvement, de l'énergie, etc.
MrCranky
Il est plus facile de supposer des corps inélastiques lorsque vous essayez de faire tourner un moteur en premier lieu, moins c'est compliqué, mieux c'est pour résoudre les problèmes.
Patrick Hughes
4

Je pense que vous avez fait un effort vraiment noble, mais il semble que la structure du code pose des problèmes fondamentaux. Comme d'autres l'ont suggéré, il peut être utile de séparer les opérations en parties discrètes, par exemple:

  1. Phase large : parcourez tous les objets - effectuez un test rapide (par exemple, AABB) pour déterminer quels objets peuvent entrer en collision - jetez ceux qui ne le sont pas.
  2. Phase étroite : boucle à travers tous les objets en collision - calculez un vecteur de pénétration pour la collision (par exemple, en utilisant SAT).
  3. Réponse à la collision : parcourez la liste des vecteurs de collision - calculez un vecteur de force basé sur la masse, puis utilisez-le pour calculer un vecteur d'accélération.
  4. Intégration : Parcourez tous les vecteurs d'accélération et intégrez la position (et la rotation si nécessaire).
  5. Rendu : parcourez toutes les positions calculées et effectuez le rendu de chaque objet.

En séparant les phases, tous les objets sont mis à jour progressivement en synchronisation et vous n'aurez pas les dépendances d'ordre avec lesquelles vous vous débattez actuellement. Le code s'avère également généralement plus simple et plus facile à modifier. Chacune de ces phases est assez générique, et il est souvent possible de remplacer de meilleurs algorithmes après avoir un système fonctionnel.

Cela dit, chacune de ces parties est une science en soi et peut prendre beaucoup de temps à essayer de trouver la solution optimale. Il peut être préférable de commencer avec certains des algorithmes les plus couramment utilisés:

  • Détection de collision à large phase : hachage spatial .
  • Détection de collision en phase étroite : Pour une physique des carreaux simple, vous pouvez simplement appliquer des tests d'intersection AABB (Axis Aligned Bounding Box). Pour les formes plus complexes, vous pouvez utiliser le théorème d'axe de séparation . Quel que soit l'algorithme que vous utilisez, il doit renvoyer la direction et la profondeur d'une intersection entre deux objets (appelé vecteur de pénétration).
  • Réponse à la collision : utilisez Projection pour résoudre l'interpénétration.
  • Intégration : l'intégrateur est le plus grand déterminant de la stabilité et de la vitesse du moteur. Deux options populaires sont l' intégration de Verlet (rapide mais simple) ou RK4 (précise mais lente). L'utilisation de l'intégration de verlet peut conduire à une conception extrêmement simple car la plupart des comportements physiques (rebond, rotation) fonctionnent sans trop d'effort. L'une des meilleures références que j'ai vues pour l'apprentissage de l'intégration RK4 est la série de Glen Fiedler sur la physique des jeux .

Un bon (et évident) point de départ est les lois du mouvement de Newton .

lukevanin
la source
Merci pour la réponse. Comment puis-je transférer la vitesse entre les corps? Cela se produit-il pendant la phase d'intégration?
Vittorio Romeo
Dans un sens, oui. Le transfert de vitesse commence par la phase de réponse à la collision. C'est à ce moment que vous calculez les forces agissant sur les corps. La force se traduit par une accélération en utilisant la formule accélération = force / masse. L'accélération est utilisée dans la phase d'intégration pour calculer la vitesse, qui est ensuite utilisée pour calculer la position. La précision de la phase d'intégration détermine la précision avec laquelle la vitesse (et par la suite la position) change avec le temps.
Luke Van En