Arbre KD entièrement dynamique vs Quadtree?

En travaillant sur mon jeu, je suis au point où j'ai besoin de suivre toutes les unités dans le monde afin de pouvoir effectuer des vérifications de combat auprès du plus proche voisin. Il s'agit d'un jeu de type RTS, avec potentiellement des milliers de petites unités automatisées se déplaçant.

J'ai étudié les KD-Trees et les Quadtrees (en particulier les Point Quadtrees). J'essaie toujours d'apprendre les détails de leur fonctionnement, mais jusqu'à présent, Point Quadtrees a le plus de sens pour moi. Cependant, j'ai l'impression que les arbres KD sont plus rapides à rechercher, ce qui est important avec le nombre de points que j'aurai dans l'arbre.

D'un autre côté, dans mon cas, je vais suivre un grand nombre d'unités qui sont toujours en mouvement. D'image en image, leurs positions seront toujours différentes. Les Quadtrees sont apparemment plus rapides à rééquilibrer que les KD-Trees, mais je ne sais pas si cela s'applique lorsque vous rééquilibrez chaque point de l'arborescence.

Je me demande s'il serait préférable dans ce cas de simplement supprimer l'arbre de chaque image et de le reconstruire à partir de zéro, plutôt que d'essayer de rééquilibrer chaque point de l'arbre? Si un Quadtree est plus rapide à rééquilibrer, cela signifie-t-il également qu'il est plus rapide à construire à partir de zéro? Si c'est le cas, cela pourrait être plus important pour les performances que la vitesse de recherche de KD-Tree, selon le poids de la création de l'arbre, mais je ne sais pas ...

Les arbres KD ne sont définitivement pas assez dynamiques pour être considérés honnêtement. Déplacer quelques unités peut facilement vous obliger à reconstruire tout l'arbre KD. De plus, un arbre KD est très efficace pour les requêtes, mais pas tant pour la recherche de voisins.

Un quadtree est plus flexible dans le temps, car les modifications sont conservées plus localement. L'inconvénient est que si vous avez plusieurs unités à un endroit qui se déplacent souvent, cela peut se subdiviser trop et nécessiter beaucoup de mises à jour en raison du mouvement des unités. Vous pouvez définir un seuil en dessous duquel aucune subdivision ne peut se produire. Mais attention, cela implique que beaucoup d'unités pourraient potentiellement être dans le même carré de feuilles.

Si toutefois vous ne souhaitez trouver que toutes les unités dans un rayon constant r , vous n'avez pas besoin immédiatement de quadtree et d'arbre kd. Vous pouvez simplement créer un tableau 2D de cellules de côté de longueur r et empiler vos unités dans chaque cellule en fonction de leur position. De cette façon, vous avez toujours au pire 9 cellules à rechercher. Ce n'est que si votre carte est immense , qu'une telle grille serait trop grande à mettre en œuvre.

Il y a deux autres structures entièrement différentes dont nous n'avons pas parlé: les AABB hiérarchiques et la table de hachage sensible aux conditions locales. Si l'origine de chaque AABB hiérarchique est décrite par rapport à l'AABB parent, il a l'avantage que si un grand groupe d'unités conserve sa formation, vous n'avez pas besoin de mettre à jour les AABB plus petits car ils conservent les mêmes positions relatives. Bien sûr, la rotation de la formation peut entraîner de nombreuses mises à jour, dans ce cas, l'utilisation d'autres volumes de délimitation comme des sphères ou des boîtes de délimitation orientées (OBB) peut être plus efficace.

Les tables de hachage sensibles aux données locales ne fournissent que des solutions approximatives de manière efficace, donc je ne m'embêterais pas avec elles.

Qu'est ce que je ferais ? Je commencerais probablement par une simple grille, et lorsque j'en aurais besoin, je la mettrais à niveau vers un quadtree et si j'en ai besoin, je la combinerai avec une hiérarchie de volume englobante sous un certain seuil: les quadtrees fonctionnent bien à grande échelle échelle, les volumes limites relatifs fonctionnent bien à petite échelle. En le faisant progressivement, je n'ai pas à passer une heure depuis le début pour obtenir immédiatement la meilleure structure de données .

Les suggestions de Lærne sont excellentes, mais je suggérerais également un arbre de volume de délimitation dynamique d'AABB. Sur le plan conceptuel, l'arborescence de volumes de délimitation dynamique conserve un arbre équilibré de nœuds qui peut être interrogé à tout moment pour les éléments proches en passant un AABB et en récupérant une paire qui se chevauchent. L'arbre n'est pas reconstruit à chaque image. Au lieu de cela, l'AABB de chaque nœud est légèrement gonflé lorsqu'il est placé dans l'arborescence, et l'arbre n'est reconstruit que lorsque l'AABB réel du nœud n'est plus contenu par l'AABB gonflé. Je l'utilise dans mon moteur physique et cela fonctionne très bien.

Le code source de Box2D a une grande implémentation de celui-ci.

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.h

Voici un bon examen de leur mise en œuvre:

http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/