Amélioration d'une fonction O (N ^ 2) (toutes les entités itérant sur toutes les autres entités)

21

Un peu de contexte, je suis en train de coder un jeu d' évolution avec un ami en C ++, en utilisant ENTT pour le système d'entités. Les créatures se promènent sur une carte 2D, mangent des verts ou d'autres créatures, se reproduisent et leurs traits mutent.

De plus, les performances sont bonnes (60 images par seconde sans problème) lorsque le jeu est exécuté en temps réel, mais je veux pouvoir l'accélérer considérablement pour ne pas avoir à attendre 4h pour voir des changements importants. Je veux donc l'obtenir le plus rapidement possible.

J'ai du mal à trouver une méthode efficace pour que les créatures trouvent leur nourriture. Chaque créature est censée chercher la meilleure nourriture qui soit assez proche d'elle.

Exemple de capture d'écran du jeu

Si elle veut manger, la créature représentée au centre est censée regarder autour d'elle dans un rayon de 149,64 (sa distance de vue) et juger quelle nourriture elle doit rechercher, qui est basée sur la nutrition, la distance et le type (viande ou plante) .

La fonction chargée de trouver à chaque créature sa nourriture consomme environ 70% du temps d'exécution. Simplifiant la façon dont il est écrit actuellement, il ressemble à ceci:

for (creature : all_creatures)
{
  for (food : all_entities_with_food_value)
  {
    // if the food is within the creatures view and it's
    // the best food found yet, it becomes the best food
  }
  // set the best food as the target for creature
  // make the creature chase it (change its state)
}

Cette fonction est exécutée à chaque tick pour chaque créature à la recherche de nourriture, jusqu'à ce que la créature trouve de la nourriture et change d'état. Il est également exécuté à chaque fois que de nouveaux aliments apparaissent pour les créatures qui poursuivent déjà un certain aliment, pour s'assurer que tout le monde cherche le meilleur aliment qui leur soit disponible.

Je suis ouvert aux idées sur la façon de rendre ce processus plus efficace. J'adorerais réduire la complexité de O(N2) , mais je ne sais pas si c'est même possible.

Une façon dont je l'ai déjà amélioré est de trier le all_entities_with_food_valuegroupe de sorte que lorsqu'une créature parcourt des aliments trop gros pour être mangés, elle s'arrête là. Toute autre amélioration est plus que bienvenue!

EDIT: Merci à tous pour les réponses! J'ai implémenté différentes choses à partir de différentes réponses:

J'ai tout d'abord et simplement fait en sorte que la fonction coupable ne s'exécute qu'une fois tous les cinq ticks, ce qui a rendu le jeu environ 4x plus rapide, sans rien changer visiblement au jeu.

Après cela, j'ai stocké dans le système de recherche de nourriture un tableau avec la nourriture engendrée dans la même coche qu'elle fonctionne. De cette façon, je n'ai besoin que de comparer la nourriture que la créature poursuit avec les nouveaux aliments qui sont apparus.

Enfin, après des recherches sur le partitionnement de l'espace et en considérant BVH et quadtree, je suis allé avec ce dernier, car j'ai l'impression que c'est beaucoup plus simple et mieux adapté à mon cas. Je l'ai implémenté assez rapidement et il a considérablement amélioré les performances, la recherche de nourriture prend à peine du temps!

Maintenant, le rendu est ce qui me ralentit, mais c'est un problème pour un autre jour. Merci à tous!

Alexandre Rodrigues
la source
2
Avez-vous testé plusieurs threads sur plusieurs cœurs de processeur s'exécutant simultanément?
Ed Marty
6
Combien de créatures avez-vous en moyenne? Il ne semble pas être si élevé, à en juger par l'instantané. Si c'est toujours le cas, le partitionnement de l'espace n'aidera pas beaucoup. Avez-vous envisagé de ne pas exécuter cette fonction à chaque tick? Vous pouvez l'exécuter toutes les 10 ticks, par exemple. Les résultats de la simulation ne devraient pas changer qualitativement.
Turms
4
Avez-vous effectué un profilage détaillé pour déterminer la partie la plus coûteuse de l'évaluation des aliments? Au lieu de regarder la complexité globale, vous devrez peut-être voir s'il y a un calcul spécifique ou un accès à la structure de la mémoire qui vous étouffe.
Harabeck
Une suggestion naïve: vous pourriez utiliser un quadtree ou une structure de données associée au lieu de la façon O (N ^ 2) que vous faites maintenant.
Seiyria
3
Comme l'a suggéré @Harabeck, je creuserais plus profondément pour voir où dans la boucle tout ce temps est passé. S'il s'agit de calculs de racine carrée pour la distance, par exemple, vous pourriez d'abord comparer les cordons XY pour pré-éliminer beaucoup de candidats avant d'avoir à faire le sqrt cher sur les autres. L'ajout if (food.x>creature.x+149.64 or food.x<creature.x-149.64) continue;devrait être plus facile que l'implémentation d'une structure de stockage "compliquée" SI elle est suffisamment performante. (Rapporté: Il pourrait nous aider si vous avez publié un peu plus du code dans votre boucle interne)
CA

Réponses:

34

Je sais que vous ne conceptualisez pas cela comme des collisions, mais ce que vous faites, c'est heurter un cercle centré sur la créature, avec toute la nourriture.

Vous ne voulez vraiment pas vérifier la nourriture dont vous savez qu'elle est éloignée, seulement ce qui se trouve à proximité. C'est le conseil général pour l'optimisation des collisions. Je voudrais encourager la recherche de techniques pour optimiser les collisions et ne pas vous limiter au C ++ lors de la recherche.


Créature, trouver, nourriture

Pour votre scénario, je suggérerais de mettre le monde sur une grille. Faites les cellules au moins le rayon des cercles que vous souhaitez entrer en collision. Ensuite, vous pouvez choisir la cellule sur laquelle se trouve la créature et ses huit voisins maximum et rechercher uniquement les neuf cellules maximum.

Remarque : vous pourriez faire des cellules plus petites, ce qui signifierait que le cercle que vous recherchez s'étendrait au-delà des voisins immidiats, vous obligeant à itérer là-bas. Cependant, si le problème est qu'il y a trop de nourriture, des cellules plus petites pourraient signifier une itération sur moins d'entités alimentaires au total, ce qui à un moment donné tourne en votre faveur. Si vous pensez que c'est le cas, testez.

Si la nourriture ne bouge pas, vous pouvez ajouter les entités alimentaires à la grille lors de la création, de sorte que vous n'avez pas besoin de rechercher quelles entités se trouvent dans la cellule. Au lieu de cela, vous interrogez la cellule et elle contient la liste.

Si vous faites de la taille des cellules une puissance de deux, vous pouvez trouver la cellule sur laquelle se trouve la créature en tronquant simplement ses coordonnées.

Vous pouvez travailler avec une distance au carré (aka ne pas faire sqrt) tout en comparant pour trouver la plus proche. Moins d'opérations sqrt signifie une exécution plus rapide.


Nouveaux aliments ajoutés

Lorsque de nouveaux aliments sont ajoutés, seules les créatures proches doivent être réveillées. C'est la même idée, sauf que vous devez maintenant obtenir la liste des créatures dans les cellules.

Plus intéressant encore, si vous annotez chez la créature à quelle distance se trouve-t-elle de la nourriture qu'elle poursuit ... vous pouvez directement vérifier cette distance.

Une autre chose qui vous aidera est d'avoir la nourriture au courant des créatures qui la poursuivent. Cela vous permettra d'exécuter le code pour trouver de la nourriture pour toutes les créatures qui poursuivent un morceau de nourriture qui vient d'être mangé.

En fait, démarrez la simulation sans nourriture et toutes les créatures ont une distance annotée de l'infini. Commencez ensuite à ajouter de la nourriture. Mettez à jour les distances au fur et à mesure que les créatures se déplacent ... Lorsque la nourriture est mangée, prenez la liste des créatures qui la poursuivaient, puis trouvez une nouvelle cible. Outre ce cas, toutes les autres mises à jour sont gérées lorsque des aliments sont ajoutés.


Sauter la simulation

Connaissant la vitesse d'une créature, vous savez combien elle est jusqu'à ce qu'elle atteigne sa cible. Si toutes les créatures ont la même vitesse, celle qui atteindra en premier est celle avec la plus petite distance annotée.

Si vous connaissez également le temps jusqu'à ce que vous ajoutiez plus de nourriture ... Et j'espère que vous avez une prévisibilité similaire pour la reproduction et la mort, alors vous savez le temps jusqu'au prochain événement (soit de la nourriture ajoutée, soit une créature mangeant).

Passez à ce moment. Vous n'avez pas besoin de simuler des créatures se déplaçant.

Theraot
la source
1
"et ne cherchez que là-bas." et les cellules voisines immédiates - ce qui signifie 9 cellules au total. Pourquoi 9? Parce que si la créature est juste au coin d'une cellule.
UKMonkey
1
@UKMonkey "Faites les cellules au moins le rayon des cercles que vous voulez entrer en collision", si le côté de la cellule est le rayon et la créature est dans le coin ... eh bien, je suppose que vous n'avez besoin de rechercher que quatre dans ce cas. Cependant, bien sûr, nous pouvons rendre les cellules plus petites, ce qui pourrait être utile s'il y a trop de nourriture et trop peu de créatures. Edit: je vais clarifier.
Theraot
2
Bien sûr - si vous voulez travailler si vous avez besoin de chercher dans des cellules supplémentaires ... mais étant donné que la plupart des cellules n'auront pas de nourriture (à partir de l'image donnée); il sera plus rapide de rechercher seulement 9 cellules que de déterminer les 4 dont vous avez besoin.
UKMonkey
@UKMonkey, c'est pourquoi je n'ai pas mentionné cela au départ.
Theraot
16

Vous devez adopter un algorithme de partitionnement d'espace comme BVH pour réduire la complexité. Pour être spécifique à votre cas, vous devez créer un arbre composé de boîtes englobantes alignées sur l'axe qui contiennent des morceaux de nourriture.

Pour créer une hiérarchie, placez les aliments près les uns des autres dans les AABB, puis placez ces AABB dans des AABB plus grands, encore une fois, en fonction de la distance entre eux. Faites cela jusqu'à ce que vous ayez un nœud racine.

Pour utiliser l'arborescence, effectuez d'abord un test d'intersection cercle-AABB contre un nœud racine, puis si une collision se produit, testez contre les enfants de chaque nœud consécutif. À la fin, vous devriez avoir un groupe de morceaux de nourriture.

Vous pouvez également utiliser la bibliothèque AABB.cc.

Ocelot
la source
1
Cela réduirait en effet la complexité de N log N, mais il serait également coûteux de faire le partitionnement. Étant donné que j'aurais besoin de faire le partitionnement à chaque tick (puisque les créatures se déplacent à chaque tick), cela en vaut-il la peine? Existe-t-il des solutions pour aider à partitionner moins souvent?
Alexandre Rodrigues
3
@AlexandreRodrigues vous n'avez pas à reconstruire l'arbre entier à chaque tick, seulement à mettre à jour les parties qui se déplacent, et seulement quand quelque chose sort d'un conteneur AABB particulier. Pour améliorer encore les performances, vous souhaiterez peut-être engraisser les nœuds (en laissant un peu d'espace entre les enfants) afin de ne pas avoir à reconstruire la branche entière lors d'une mise à jour de feuille.
Ocelot
6
Je pense qu'un BVH pourrait être trop complexe ici - une grille uniforme implémentée comme une table de hachage est assez bonne.
Steven
1
@Steven en implémentant BVH, vous pouvez facilement étendre l'échelle de la simulation à l'avenir. Et vous ne perdez rien vraiment si vous le faites pour une simulation à petite échelle non plus.
Ocelot
2

Bien que les méthodes de partition d'espace décrites puissent en effet réduire le temps, votre problème principal n'est pas seulement la recherche. C'est le volume de recherches que vous faites qui ralentit votre tâche. Donc, vous optimisez la boucle intérieure, mais vous pouvez également optimiser la boucle extérieure.

Votre problème est que vous continuez à interroger les données. C'est un peu comme avoir des enfants sur le siège arrière demandant une millième fois "sommes-nous là encore", il n'y a pas besoin de le faire, le chauffeur informera quand vous y serez.

Au lieu de cela, vous devez vous efforcer, si possible, de résoudre chaque action jusqu'à son achèvement, de la placer dans une file d'attente et de laisser ces événements de bulle sortir, cela peut apporter des modifications à la file d'attente, mais c'est correct. C'est ce qu'on appelle la simulation d'événements discrets. Si vous pouvez implémenter votre simulation de cette façon, vous recherchez une accélération considérable qui dépasse de loin celle que vous pouvez obtenir grâce à une meilleure recherche de partition d'espace.

Pour souligner le point dans une carrière précédente, j'ai fait des simulateurs d'usine. Nous avons simulé des semaines de flux de matières entières de grandes usines / aéroports à chaque niveau d'article avec cette méthode en moins d'une heure. Alors que la simulation basée sur le temps ne pouvait simuler que 4 à 5 fois plus rapidement qu'en temps réel.

Aussi, en tant que fruit très bas, pensez à découpler vos routines de dessin de votre simulation. Même si votre simulation est simple, il y a encore des frais généraux de dessin. Pire encore, le pilote d'affichage peut vous limiter à x mises à jour par seconde alors qu'en réalité, vos processeurs pourraient faire les choses 100 fois plus rapidement. Cela souligne la nécessité d'un profilage.

joojaa
la source
@Theraot nous ne savons pas comment les choses de dessin sont structurées. Mais oui, les drawcalls deviendront des goulots d'étranglement une fois que vous serez assez rapide de toute façon
joojaa
1

Vous pouvez utiliser un algorithme de balayage pour réduire la complexité de Nlog (N). La théorie est celle des diagrammes de Voronoi, ce qui rend une partition de la zone entourant une créature en régions constituées de tous les points plus proches de cette créature que toute autre.

L'algorithme dit de Fortune fait cela pour vous dans Nlog (N), et la page wiki qui contient du pseudo-code pour l'implémenter. Je suis sûr qu'il existe également des implémentations de bibliothèque. https://en.wikipedia.org/wiki/Fortune%27s_algorithm

nabla
la source
Bienvenue à GDSE et merci d'avoir répondu. Comment appliqueriez-vous cela exactement à la situation de l'OP? La description du problème indique qu'une entité doit considérer tous les aliments à sa distance de vue et sélectionner le meilleur. Un Voronoi traditionnel exclurait dans la gamme des aliments plus proches d'une autre entité. Je ne dis pas qu'un Voronoi ne fonctionnerait pas, mais il n'est pas évident d'après votre description comment OP devrait en utiliser un pour le problème tel que décrit.
Pikalek
J'aime cette idée, j'aimerais qu'elle se développe. Comment représentez-vous le diagramme de voronoi (comme dans la structure des données en mémoire)? Comment l'interrogez-vous?
Theraot
@Theraot vous n'avez pas besoin du diagramme de voronoi juste la même idée de sweepline.
joojaa
-2

La solution la plus simple serait d'intégrer un moteur physique et d'utiliser uniquement l'algorithme de détection de collision. Construisez simplement un cercle / sphère autour de chaque entité et laissez le moteur physique calculer les collisions. Pour la 2D, je suggérerais Box2D ou Chipmunk , et Bullet pour 3D.

Si vous pensez que l'intégration d'un moteur physique complet est trop, je suggérerais de regarder dans les algorithmes de collision spécifiques. La plupart des bibliothèques de détection de collision fonctionnent en deux étapes:

  • Détection de phase large: l'objectif de cette étape est d'obtenir la liste des paires d'objets candidats susceptibles d'entrer en collision le plus rapidement possible. Deux options courantes sont:
    • Balayer et tailler : triez les boîtes englobantes le long de l'axe X et marquez la paire d'objets qui se croisent. Répétez pour tous les autres axes. Si une paire candidate réussit tous les tests, elle passe à l'étape suivante. Cet algorithme est très bon pour exploiter la cohérence temporelle: vous pouvez conserver les listes d'entités triées et les mettre à jour à chaque image, mais comme elles sont presque triées, ce sera très rapide. Il exploite également la cohérence spatiale: parce que les entités sont triées par ordre spatial croissant, lorsque vous vérifiez les collisions, vous pouvez vous arrêter dès qu'une entité ne se heurte pas, car toutes les suivantes seront plus éloignées.
    • Structures de données de partitionnement spatial, comme les arbres quadruples, les octrois et les grilles. Les grilles sont faciles à implémenter, mais peuvent être très gaspilleuses si la densité d'entité est faible et très difficiles à implémenter pour un espace illimité. Les arbres spatiaux statiques sont également faciles à implémenter, mais difficiles à équilibrer ou à mettre à jour sur place, vous devrez donc le reconstruire à chaque image.
  • Phase étroite: les paires de candidats trouvées sur la phase large sont ensuite testées avec des algorithmes plus précis.
José Franco Campos
la source