Optimiser les calculs de gravité

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?

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.

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

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.

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.

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).

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.

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.