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

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.

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(N^2)$ , 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!

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.

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.

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.

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

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.