Optimiser les calculs de gravité

23

J'ai un tas d'objets de taille et de vitesse variables qui gravitent l'un vers l'autre. À chaque mise à jour, je dois parcourir chaque objet et additionner les forces dues à la gravité de tous les autres objets. Il ne évolue pas très bien, est l'un des deux gros goulots d'étranglement que j'ai trouvés dans mon jeu, et je ne sais pas quoi faire pour améliorer les performances.

Il se sent comme je devrais être en mesure d'améliorer les performances. À tout moment, 99% des objets du système n'auront probablement qu'une influence négligeable sur un objet. Bien sûr, je ne peux pas trier les objets par masse et ne considérer que les 10 plus gros objets ou quelque chose du genre, car la force varie plus avec la distance qu'avec la masse (l'équation est dans le sens de force = mass1 * mass2 / distance^2). Je pense qu'une bonne approximation serait de considérer les plus gros objets et les objets les plus proches, en ignorant les centaines de minuscules fragments de roche de l'autre côté du monde qui ne peuvent pas affecter quoi que ce soit - mais afin de savoir quels objets sont le plus proche, je dois parcourir tous les objets, et leurs positions changent constamment, donc ce n'est pas comme si je pouvais le faire une seule fois.

Actuellement, je fais quelque chose comme ça:

private void UpdateBodies(List<GravitatingObject> bodies, GameTime gameTime)
{
    for (int i = 0; i < bodies.Count; i++)
    {
        bodies[i].Update(i);
    }
}

//...

public virtual void Update(int systemIndex)
{
    for (int i = systemIndex + 1; i < system.MassiveBodies.Count; i++)
    {
        GravitatingObject body = system.MassiveBodies[i];

        Vector2 force = Gravity.ForceUnderGravity(body, this);
        ForceOfGravity += force;
        body.ForceOfGravity += -force;
    }

    Vector2 acceleration = Motion.Acceleration(ForceOfGravity, Mass);
    ForceOfGravity = Vector2.Zero;

    Velocity += Motion.Velocity(acceleration, elapsedTime);
    Position += Motion.Position(Velocity, elapsedTime);
}

(notez que j'ai supprimé beaucoup de code - par exemple les tests de collision, je ne répète pas les objets une deuxième fois pour détecter les collisions).

Je ne suis donc pas toujours en train d'itérer sur toute la liste - je ne fais cela que pour le premier objet, et chaque fois que l'objet trouve la force qu'il ressent vers un autre objet, cet autre objet ressent la même force, donc il ne fait que mettre à jour les deux eux - et puis ce premier objet ne doit pas être considéré à nouveau pour le reste de la mise à jour.

Les fonctions Gravity.ForceUnderGravity(...)et Motion.Velocity(...), etc. utilisent simplement un peu de mathématiques vectorielles intégrées de XNA.

Lorsque deux objets entrent en collision, ils créent des débris sans masse. Il est conservé dans une liste séparée et les objets massifs ne parcourent pas les débris dans le cadre de leur calcul de vitesse, mais chaque morceau de débris doit itérer sur les particules massives.

Cela n'a pas à atteindre des limites incroyables. Le monde n'est pas illimité, il contient une frontière qui détruit les objets qui le traversent - j'aimerais pouvoir gérer peut-être un millier d'objets, actuellement le jeu commence à s'étouffer autour de 200.

Avez-vous des idées sur la façon dont je pourrais améliorer cela? Une heuristique que je peux utiliser pour raser la longueur de la boucle de centaines à quelques-unes? Quel code puis-je exécuter moins souvent que chaque mise à jour? Dois-je simplement le multithread jusqu'à ce qu'il soit assez rapide pour permettre un monde de taille décente? Dois-je essayer de décharger les calculs de vitesse sur le GPU? Si oui, comment pourrais-je concevoir cela? Puis-je conserver des données statiques et partagées sur le GPU? Puis-je créer des fonctions HLSL sur le GPU et les appeler arbitrairement (en utilisant XNA) ou doivent-elles faire partie du processus de dessin?

Carson Myers
la source
1
Juste une note, vous avez dit "les objets massifs ne parcourent pas les débris dans le cadre de leur calcul de vitesse, mais chaque morceau de débris doit itérer sur les particules massives". J'ai l'impression que vous supposez que c'est plus efficace. Cependant, itérer 100 objets débris 10 fois chacun, revient toujours à itérer 100 objets massifs 100 fois. Peut-être que ce serait une bonne idée d'itérer chaque objet débris dans la boucle des objets massifs afin de ne pas le faire une deuxième fois.
Richard Marskell - Drackir
Quelle précision avez-vous besoin d'une simulation? Avez-vous vraiment besoin que tout accélère les uns vers les autres? Et avez-vous vraiment besoin d'utiliser un vrai calcul de gravitation? Ou pouvez-vous vous écarter de ces conventions pour ce que vous essayez d'accomplir?
chaosTechnician
@Drackir Je pense que vous avez raison. Une partie de la raison pour laquelle ils sont séparés est parce que les mathématiques sont différentes pour les objets sans masse, et en partie parce qu'ils ne respectaient pas du tout la gravité, il était donc plus efficace de ne pas les inclure. C'est donc un vestige
Carson Myers
@chaosTechnician, il ne doit pas être très précis - en fait, s'il ne représente que les quelques forces les plus dominantes, un système serait plus stable, ce qui est idéal. Mais c'est de découvrir quelles forces sont les plus dominantes de manière efficace avec laquelle j'ai du mal. De plus, le calcul de la gravitation est déjà approximé, c'est juste G * m1 * m2 / r^2, où G est juste pour modifier le comportement. (bien que je ne puisse pas simplement les faire suivre un chemin, car l'utilisateur peut perturber le système)
Carson Myers
Pourquoi chaque morceau de débris doit-il parcourir les particules massives s'il est sans masse? Des collisions?
sam hocevar

Réponses:

26

Cela ressemble à un travail pour une grille. Divisez votre espace de jeu en une grille et conservez pour chaque cellule de la grille une liste des objets qui s'y trouvent actuellement. Lorsque des objets traversent une limite de cellule, mettez à jour la liste dans laquelle ils se trouvent. Lors de la mise à jour d'un objet et de la recherche d'autres personnes avec lesquelles interagir, vous pouvez regarder uniquement la cellule de grille actuelle et quelques cellules voisines. Vous pouvez modifier la taille de la grille pour les meilleures performances (équilibrer le coût de la mise à jour des cellules de la grille - qui est plus élevé lorsque les cellules de la grille sont trop petites - avec le coût des recherches, qui est plus élevé lorsque les cellules de la grille sont trop grand).

Bien entendu, cela empêchera les objets qui sont plus éloignés que quelques cellules de la grille d'interagir du tout, ce qui est probablement un problème car une grande accumulation de masse (soit un gros objet, soit un groupe de nombreux petits objets) devrait , comme vous l'avez mentionné, ont une plus grande région d'influence.

Une chose que vous pourriez faire est de garder une trace de la masse totale dans chaque cellule de la grille et de traiter la cellule entière comme un objet unique pour les interactions plus éloignées. C'est-à-dire: lorsque vous calculez la force sur un objet, calculez l'accélération directe d'objet à objet pour les objets dans quelques cellules de grille voisines, puis ajoutez une accélération de cellule à cellule pour chaque cellule de grille plus éloignée (ou peut-être seulement ceux qui contiennent une masse non négligeable). Par accélération de cellule à cellule, je veux dire un vecteur calculé en utilisant les masses totales des deux cellules et la distance entre leurs centres. Cela devrait donner une approximation raisonnable de la gravité sommée de tous les objets dans cette cellule de grille, mais beaucoup moins cher.

Si le monde du jeu est très vaste, vous pouvez même utiliser une grille hiérarchique , comme un quadtree (2D) ou un octree (3D), et appliquer des principes similaires. Les interactions à plus longue distance correspondraient à des niveaux supérieurs de la hiérarchie.

Nathan Reed
la source
1
+1 pour l'idée de la grille. Je suggère également de suivre le centre de masse de la grille pour garder les calculs un peu plus purs (si nécessaire).
chaosTechnician
J'aime beaucoup cette idée. J'avais envisagé de contenir les objets dans les cellules, mais je l'ai abandonné en considérant deux objets proches qui étaient techniquement dans des cellules différentes - mais je n'ai pas fait le saut mental pour considérer quelques cellules adjacentes, ainsi que la masse combinée d'autres cellules. Je pense que cela devrait très bien fonctionner si je le fais bien.
Carson Myers
8
Il s'agit essentiellement de l'algorithme Barnes-Hut: en.wikipedia.org/wiki/Barnes –Hut_simulation
Russell Borogove
Cela ressemble même à la façon dont la gravité est censée fonctionner en physique - la flexion de l'espace-temps.
Zan Lynx
J'aime l'idée - mais je pense honnêtement qu'elle a besoin d'un tout petit peu plus de raffinement - que se passe-t-il si deux objets sont très proches l'un de l'autre mais dans des cellules séparées? Je pourrais voir comment votre troisième paragraphe pourrait aider - mais pourquoi ne pas simplement faire une élimination circulaire sur les objets en interaction?
Jonathan Dickinson
16

L'algorithme de Barnes-Hut est la voie à suivre avec celui-ci. Il a été utilisé dans les simulations de superordinateurs pour résoudre votre problème exact. Ce n'est pas trop difficile à coder, et c'est très efficace. J'ai en fait écrit une applet Java il n'y a pas si longtemps pour résoudre ce problème.

Visitez http://mathandcode.com/programs/javagrav/ et appuyez sur "start" et "show quadtree".

Dans l'onglet Options, vous pouvez voir que le nombre de particules peut aller jusqu'à 200 000. Sur mon ordinateur, le calcul se termine en environ 2 secondes (le dessin de 200 000 points prend environ 1 seconde, mais le calcul s'exécute sur un thread séparé).

Voici comment fonctionne mon applet:

  1. Créez une liste de particules aléatoires, avec des masses, des positions et des vitesses de départ aléatoires.
  2. Construisez un quadtree à partir de ces particules. Chaque nœud à quatre arbres contient le centre de masse de chaque sous-nœud. Fondamentalement, pour chaque nœud, vous avez trois valeurs: massx, massy et mass. Chaque fois que vous ajoutez une particule à un nœud donné, vous augmentez respectivement massx et massy de particule.x * particule.masse et particule.y * particule.masse. La position (massx / masse, massy / masse) deviendra le centre de masse du nœud.
  3. Pour chaque particule, calculez les forces (décrites en détail ici ). Cela se fait en commençant par le nœud supérieur et en revenant à travers chaque sous-nœud du quadtree jusqu'à ce que le sous-nœud donné soit suffisamment petit. Une fois que vous arrêtez de récurer, vous pouvez calculer la distance entre la particule et le centre de masse du nœud, puis vous pouvez calculer la force en utilisant la masse du nœud et la masse de la particule.

Votre jeu devrait facilement être capable de gérer mille objets qui s’attirent mutuellement. Si chaque objet est "stupide" (comme les particules nues dans mon applet), vous devriez pouvoir obtenir 8 000 à 9 000 particules, peut-être plus. Et cela suppose un seul thread. Avec des applications informatiques multithread ou parallèles, vous pouvez obtenir beaucoup plus de particules que cette mise à jour en temps réel.

Voir aussi: http://www.youtube.com/watch?v=XAlzniN6L94 pour un grand rendu de ce


la source
Le premier lien est mort. L'applet est-il hébergé ailleurs?
Anko
1
Fixé! désolé, j'ai oublié de payer le loyer sur ce domaine, et quelqu'un l'a acheté automatiquement: \ En outre, 3 minutes est un très bon temps de réponse sur un post 8D de 1,3 an
Et je dois ajouter: je n'ai pas le code source. Si vous cherchez du code source, consultez part-nd (écrit en c). Je suis sûr qu'il y en a d'autres aussi.
3

Nathan Reed a une excellente réponse. La version courte consiste à utiliser une technique en phase large qui correspond à la topologie de votre simulation et à exécuter les calculs de gravité uniquement sur des paires d'objets qui vont avoir un effet notable les uns sur les autres. Ce n'est vraiment pas différent de ce que vous feriez pour une détection régulière de collisions à large bande.

Cependant, une autre possibilité est de ne mettre à jour les objets que par intermittence. Fondamentalement, chaque pas de temps (image) ne met à jour qu'une fraction de tous les objets et laisse la vitesse (ou l'accélération, selon vos préférences) la même pour les autres objets. Il est peu probable que l'utilisateur remarque un retard dans les mises à jour à partir de cela tant que les intervalles ne sont pas trop longs. Cela vous donnera une accélération linéaire de l'algorithme, alors regardez bien les techniques à large phase comme Nathan l'a suggéré également, qui peuvent donner des accélérations beaucoup plus importantes si vous avez une tonne d'objets. Bien que pas du tout modélisé de la même manière, c'est un peu comme avoir des «ondes de gravité». :)

De plus, vous pouvez générer un champ de gravité en une seule passe, puis mettre à jour les objets lors d'une deuxième passe. La première passe, vous remplissez essentiellement une grille (ou une structure de données spatiales plus complexe) avec les influences de la gravité de chaque objet. Le résultat est maintenant un champ de gravité que vous pouvez même rendre (semble assez cool) pour voir quelle accélération sera appliquée à un objet à n'importe quel endroit donné. Ensuite, vous parcourez les objets et appliquez simplement les effets du champ de gravité à cet objet. Encore plus cool, vous pouvez le faire sur un GPU en rendant les objets sous forme de cercles / sphères à une texture, puis en lisant la texture (ou en utilisant une autre passe de rétroaction de transformation sur le GPU) pour modifier les vitesses de l'objet.

Sean Middleditch
la source
La séparation du processus en passes est une excellente idée, car l'intervalle de mise à jour est (pour autant que je sache) une très petite fraction de seconde. La texture du champ de gravité est IMPRESSIONNANTE mais peut-être un peu hors de ma portée en ce moment.
Carson Myers
1
N'oubliez pas de multiplier les forces appliquées par le nombre de tranches de temps qui ont été ignorées depuis la dernière mise à jour.
Zan Lynx
@seanmiddlemitch: Pourriez-vous élaborer un peu plus sur la texture du champ de gravité? Je suis désolé, je ne suis pas programmeur graphique, mais cela semble vraiment intéressant; Je ne comprends tout simplement pas comment cela est censé fonctionner. Et / ou peut-être avez-vous un lien vers une description de la technique?
Felix Dombek
@FelixDombek: rendez vos objets sous forme de cercles représentant une zone d'influence. Le fragment shader écrit un vecteur pointant vers le centre de l'objet et avec une ampleur appropriée (basée sur la distance du centre et la masse de l'objet). Le mélange de matériel peut gérer la somme de ces vecteurs en mode additif. Le résultat ne sera pas des champs de gravité précis, mais sera certainement assez bon pour les besoins d'un jeu. Comme encore une autre approche utilisant le GPU, voir cette technique de simulation de gravité à base de N basée sur CUDA: http.developer.nvidia.com/GPUGems3/gpugems3_ch31.html
Sean Middleditch
3

Je recommanderais d'utiliser un Quad Tree. Ils vous permettent de rechercher rapidement et efficacement tous les objets dans une zone rectangulaire arbitraire. Voici l'article wiki sur eux: http://en.wikipedia.org/wiki/Quadtree

Et un lien sans vergogne vers mon propre projet XNA Quad Tree sur SourceForge: http://sourceforge.net/projects/quadtree/

Je tiens également à jour une liste de tous les grands objets afin qu'ils puissent interagir avec tout, quelle que soit la distance.

John McDonald
la source
0

Juste une petite entrée (peut-être naïve). Je ne fais pas de programmation de jeux, mais ce que je ressens, c'est que votre goulot d'étranglement fondamental est le calcul de la gravité due à la gravité. Au lieu d'itérer sur chaque objet X, puis de trouver l'effet gravitationnel de chaque objet Y et de l'ajouter, vous pouvez prendre chaque paire X, Y et trouver la force entre eux. Cela devrait réduire le nombre de calculs de gravité de O (n ^ 2). Ensuite, vous ferez beaucoup d'ajouts (O (n ^ 2)), mais c'est généralement moins cher.

À ce stade, vous pouvez également implémenter des règles telles que "si la force gravitationnelle sera inférieure à \ epsilon car ces corps sont trop petits, définissez la force sur zéro". Il peut être avantageux d'avoir cette structure à d'autres fins également (y compris la détection de collision).

Alex Hirzel
la source
C'est fondamentalement ce que je fais. Après avoir obtenu toutes les paires impliquant X, je ne répète plus sur X. Je trouve la force entre X et Y, X et Z, etc., et j'applique cette force aux deux objets de la paire. Une fois la boucle terminée, le ForceOfGravityvecteur est la somme de toutes les forces, qui est ensuite converti en vitesse et en nouvelle position. Je ne suis pas sûr que le calcul de la gravité soit particulièrement coûteux, et vérifier s'il dépasse d'abord un seuil ne ferait pas gagner un temps considérable, je ne pense pas
Carson Myers
0

En étendant la réponse de seanmiddleditch, j'ai pensé que je pourrais faire la lumière (ironie?) Sur l'idée du champ de gravité.

Tout d'abord, ne le considérez pas comme une texture, mais comme un champ discret de valeurs qui peut être modifié (un tableau à deux dimensions, pour ainsi dire); et la précision ultérieure de la simulation pourrait être la résolution de ce champ.

Lorsque vous introduisez un objet dans le champ, son potentiel de gravitation peut être calculé pour toutes les valeurs environnantes; créant ainsi un puits de gravitation dans le champ.

Mais combien de ces points devez-vous calculer avant qu'il ne devienne plus ou aussi inefficace qu'auparavant? Probablement pas beaucoup, même 32x32 est un champ important à parcourir pour chaque objet. Par conséquent, divisez l'ensemble du processus en plusieurs passes; chacun avec différentes résolutions (ou précision).

C'est-à-dire que la première passe peut calculer la gravité des objets représentés dans une grille 4x4, chaque valeur de cellule représentant une coordonnée 2D dans l'espace. Donner une complexité sous-totale O (n * 4 * 4).

La deuxième passe peut être plus précise, avec un champ de gravité de résolution 64x64, chaque valeur de cellule représentant une coordonnée 2D dans l'espace. Cependant, comme la complexité est très élevée, vous pouvez restreindre le rayon des cellules environnantes affectées (peut-être, seules les cellules 5x5 environnantes sont mises à jour).

Un troisième passage supplémentaire pourrait être utilisé pour les calculs de haute précision, avec peut-être une résolution de 1024x1024. Rappelez-vous à aucun moment que vous effectuez réellement des calculs séparés de 1024x1024, mais que vous opérez uniquement sur des parties de ce champ (peut-être 6x6 sous-sections).

De cette façon, votre complexité globale pour la mise à jour est O (n * (4 * 4 + 5 * 5 + 6 * 6)).

Pour calculer ensuite les changements de vitesse pour chacun de vos objets, pour chaque champ de gravité (4x4, 64x64, 1024x1024), il vous suffit de mapper la position des masses ponctuelles sur une cellule de la grille, d'appliquer ce vecteur de potentiel gravitationnel global des cellules de la grille à un nouveau vecteur; répéter pour chaque "couche" ou "passe"; puis ajoutez-les ensemble. Cela devrait vous donner un bon vecteur de force gravitationnelle résultante.

Par conséquent, la complexité globale est: O (n * (4 * 4 + 5 * 5 + 6 * 6) + n). Ce qui compte vraiment (pour la complexité), c'est le nombre de cellules environnantes que vous mettez à jour lors du calcul du potentiel gravitationnel dans les passes, et non la résolution globale des champs de gravité.

La raison des champs à faible résolution (premiers passages) est évidemment de couvrir l'univers dans son ensemble et de s'assurer que les masses périphériques sont attirées vers des zones plus denses malgré la distance. Utilisez ensuite des champs de résolution plus élevée en tant que couches séparées pour augmenter la précision des planètes voisines.

J'espère que cela a du sens.

caviar décéléré
la source
0

Que diriez-vous d'une autre approche:

Attribuez une zone d'influence aux objets en fonction de leur masse - ils sont tout simplement trop petits pour avoir un effet mesurable au-delà de cette plage.

Maintenant, divisez votre monde en une grille et mettez chaque objet dans une liste de toutes les cellules sur lesquelles il a une influence.

Effectuez vos calculs de gravité uniquement sur les objets de la liste jointe à la cellule dans laquelle se trouve un objet.

Vous devez uniquement mettre à jour les listes lorsqu'un objet se déplace dans une nouvelle cellule de grille.

Plus les cellules de la grille sont petites, moins vous ferez de calcul par mise à jour, mais plus vous ferez de mise à jour des listes.

Loren Pechtel
la source