Partitionnement de l'espace quand tout bouge

Contexte

Avec un ami, je travaille sur un jeu 2D qui se déroule dans l'espace. Pour le rendre aussi immersif et interactif que possible, nous voulons qu'il y ait des milliers d'objets flottant librement, certains regroupés, d'autres à la dérive dans un espace vide.

Défi

Pour décharger le moteur de rendu et de physique, nous devons implémenter une sorte de partitionnement spatial. Nous devons surmonter deux défis. Le premier défi est que tout bouge, donc la reconstruction / mise à jour de la structure de données doit être extrêmement bon marché car cela devra être fait à chaque trame. Le deuxième défi est la distribution des objets, comme dit précédemment, il pourrait y avoir des grappes d'objets ensemble et de vastes espaces vides et, pour aggraver encore, il n'y a pas de limite à l'espace.

Technologies existantes

J'ai examiné des techniques existantes telles que les arbres BSP, les arbres Quad, les arbres kd et même les arbres R, mais pour autant que je sache, ces structures de données ne sont pas parfaites depuis la mise à jour de nombreux objets qui ont été déplacés vers d'autres cellules est relativement cher.

Ce que j'ai essayé

J'ai pris la décision d'avoir besoin d'une structure de données plus orientée vers l'insertion / la mise à jour rapide que pour redonner le moins de résultats possibles à une requête. À cette fin, j'ai rendu les cellules implicites afin que chaque objet, étant donné sa position, puisse calculer dans quelle (s) cellule (s) il devrait être. Ensuite, j'utilise un HashMapqui mappe les coordonnées des cellules à un ArrayList(le contenu de la cellule). Cela fonctionne assez bien car il n'y a pas de mémoire perdue sur les cellules «vides» et il est facile de calculer les cellules à inspecter. Cependant, la création de tous ces ArrayLists (pire cas N) est coûteuse et augmente donc HashMapbeaucoup de fois (bien que cela soit légèrement atténué en lui donnant une grande capacité initiale).

Problème

OK donc cela fonctionne mais n'est pas très rapide. Maintenant, je peux essayer de micro-optimiser le code JAVA. Cependant, je n'attends pas trop de cela, car le profileur me dit que la plupart du temps est consacré à la création de tous les objets que j'utilise pour stocker les cellules. J'espère qu'il y a d'autres astuces / algorithmes qui rendent cela beaucoup plus rapide alors voici à quoi ressemble ma structure de données idéale:

• La priorité numéro un est la mise à jour / reconstruction rapide de toute la structure de données
• Il est moins important de diviser finement les objets en bacs de taille égale, nous pouvons dessiner quelques objets supplémentaires et effectuer quelques vérifications de collision supplémentaires si cela signifie que la mise à jour est un peu plus rapide
• La mémoire n'est pas vraiment importante (jeu PC)

La technique que vous utilisez est très similaire à une technique de physique informatique appelée dynamique moléculaire, où les trajectoires des atomes (généralement maintenant dans la plage de particules de 100k à 10M) sont suivies avec de très petits pas de temps. Le problème principal est que pour calculer la force sur une particule, vous devez comparer sa position à la position de toutes les autres particules, qui évolue très mal (n au carré).

Il y a une astuce que je peux suggérer, qui vous oblige à choisir une distance maximale que les choses peuvent interagir. Comme point de départ, je commencerais par quelque chose comme 1/10 de la longue dimension de votre espace et je m'ajusterais au goût (une coupure plus longue signifie plus précise, mais plus de calculs).

La méthode consiste à parcourir chaque particule (i). (I) obtient un tableau où toutes les particules dans la plage de i sont ajoutées au tableau. Ce que vous obtenez à la fin est un tableau 2d, où la ième entrée est un tableau de la particule dans la plage de i. Pour calculer les forces pour i, il suffit de vérifier les entrées dans le tableau de i.

L'art de cette méthode consiste à choisir la distance de coupure et le rembourrage supplémentaire (par exemple 20%). Le gain de vitesse est que vous n'avez qu'à vérifier quelques interactions pour chaque particule, et vous recalculez les voisins uniquement toutes les plusieurs étapes. Je suggérerais de choisir une vitesse quelque peu rapide et de déterminer combien de pas de temps il faudrait pour traverser la région de "rembourrage". Agrandir le rembourrage (50% ou même 100% de la coupure) vous donne plus d'étapes entre les recalculs du voisin, mais rend chaque étape un peu plus lente. L'équilibrage de ceci est un compromis.

Une autre astuce dans le calcul des distances consiste à travailler avec d ^ 2 au lieu de d, en supprimant un tas d'appels à pow () et sqrt ().

Edit: difficile de trouver un lien de référence qui n'est pas super technique. C'est le seul que j'ai pu trouver.

Votre propre solution semble assez bonne si vous pouvez réaliser la construction de la structure de données en o (n), alors je dirais que l'optimisation doit être faite sur le choix de la structure de données plutôt que sur l'algorithme.

J'ai une implémentation similaire avec quelques différences: La structure de données principale est un tableau de taille fixe (comme ArrayList) qui est le meilleur pour un accès direct à un élément. Chaque cellule du tableau contient une liste chaînée, ce qui est le meilleur pour les insertions et aussi bien que la liste de tableaux à boucler. Nous aurons besoin plus tard de supprimer des éléments de la liste liée, donc pour rendre cette opération très rapide, une idée est de stocker dans chaque élément de la liste un itérateur qui pointe vers lui-même (vous avez dit que la mémoire n'était pas un problème, non?)

Pour l'initialisation, chaque "particule" est insérée à la fin de la liste liée qui correspond à la cellule du tableau qui correspond à sa position dans l'espace, en supposant que l'espace est partitionné en tuiles de taille fixe. Nous sommes donc toujours avec une complexité o (n), mais nous optimisons le tout en utilisant des conteneurs plus adaptés à l'usage.

Chaque "particule" a une référence à sa liste chaînée contenant pour fournir un accès rapide à ses voisins.

À chaque image, nous pouvons faire l'interaction entre chaque particule avec sa liste de voisins, et je dirais aussi avec les 8 tuiles environnantes pour éviter les effets de seuil près des bordures de tuiles.

Il n'est pas nécessaire de recalculer l'intégralité du partitionnement à chaque trame; nous avons seulement besoin de retirer et de remettre un élément lorsqu'il se déplace sur plus d'une distance donnée ou, par sécurité, toutes les X images. Une idée pourrait être de stocker la position de chaque élément au moment où il a été inséré dans une liste chaînée, et à chaque image de comparer la position actuelle avec l'ancienne.