Comment trouver efficacement et en continu toutes les entités dans un rayon?

J'ai un très grand nombre d'entités (unités). À chaque étape, chaque unité doit connaître la position de toutes les unités proches (la distance est inférieure à la constante R donnée ). Toutes les unités se déplacent en continu. C'est en 3D.

En moyenne, il y aura 1% du nombre total d'unités à proximité de toute autre unité donnée avec les contraintes données.

Comment puis-je le faire efficacement, sans bruteforcing?

Utilisez l'un des algorithmes de partitionnement d'espace communs, tels qu'un arbre Quadtree, Octree, BSP ou même un simple système de grille. Chacun a ses avantages et ses inconvénients pour chaque scénario spécifique. Vous pouvez en lire plus à ce sujet dans ces livres .

En général (ou du moins j'ai entendu dire que je ne connais pas trop le raisonnement derrière cela), un Quadtree ou Octree est mieux adapté aux environnements extérieurs, tandis que l'arbre BSP s'adapte mieux aux scènes d'intérieur. Et le choix entre utiliser un Quadtree ou un Octree dépend de la façon dont votre monde est plat. S'il y a peu de variation dans l'axe Y, utiliser un octree serait un gaspillage. Un Octree est essentiellement un Quadtree avec une dimension supplémentaire.

Enfin, ne négligez pas la simplicité de la solution Grid. Beaucoup de gens ignorent qu'une simple grille peut parfois être suffisante (et encore plus efficace) pour leurs problèmes, et passent directement à une solution plus complexe.

Utiliser une grille consiste simplement à diviser le monde en régions régulièrement espacées et à stocker les entités dans la région appropriée du monde. Puis, étant donné une position, trouver les entités voisines reviendrait à parcourir les régions qui croisent votre rayon de recherche.

Disons que votre monde variait de (-1000, -1000) à (1000, 1000) dans le plan XZ. Vous pouvez par exemple le diviser en une grille 10x10, comme ceci:

var grid = new List<Entity>[10, 10];

Ensuite, vous placez les entités dans leurs cellules appropriées dans la grille. Par exemple, une entité avec XZ (-1000, -1000) tomberait sur la cellule (0,0) tandis qu'une entité avec XZ (1000, 1000) tomberait sur la cellule (9, 9). Puis, étant donné une position et un rayon dans le monde, vous pouvez déterminer quelles cellules sont intersectées par ce "cercle" et n'itérer que sur celles-ci, avec un simple double pour.

Quoi qu'il en soit, recherchez toutes les alternatives et choisissez celle qui semble mieux correspondre à votre jeu. J'avoue que je ne connais pas encore suffisamment le sujet pour décider lequel des algorithmes vous conviendrait le mieux.

Modifier J'ai trouvé cela sur un autre forum et cela pourrait vous aider à prendre la décision:

Les grilles fonctionnent mieux lorsque la grande majorité des objets tiennent dans un carré de grille et que la distribution est assez homogène. Inversement, les arbres quadruples fonctionnent lorsque les objets ont des tailles variables ou sont regroupés en petites zones.

Compte tenu de votre vague description du problème, je suis également contre la solution de la grille (c'est-à-dire en supposant que les unités sont petites et réparties de manière assez homogène).

Je l'ai écrit il y a quelque temps. C'est maintenant sur un site commercial, mais vous pouvez obtenir gratuitement la source pour un usage personnel. Il peut être exagéré et il est écrit en Java, mais il est bien documenté, il ne devrait donc pas être trop difficile de le rogner et de le réécrire dans une autre langue. Il utilise essentiellement un Octree, avec des ajustements pour gérer des objets vraiment gros et multi-threading.

J'ai trouvé qu'un Octree offrait la meilleure combinaison de flexibilité et d'efficacité. J'ai commencé avec une grille, mais il était impossible de dimensionner correctement les carrés et de grandes parcelles de carrés vides utilisaient l'espace et la puissance de calcul pour rien. (Et c'était juste en 2 dimensions.) Mon code gère les requêtes de plusieurs threads, ce qui ajoute beaucoup à la complexité, mais la documentation devrait vous aider à contourner cela si vous n'en avez pas besoin.

Pour augmenter votre efficacité, essayez de rejeter trivialement les 99% des "unités" qui ne sont pas près de l'unité cible en utilisant une case à cocher très bon marché. Et j'espère que vous pourrez le faire sans structurer spatialement vos données. Donc, si toutes vos unités sont stockées dans une structure de données plate, vous pouvez essayer de la parcourir du début à la fin et d'abord vérifier que l'unité actuelle est en dehors de la zone de délimitation de l'unité d'intérêt.

Définissez une zone de délimitation surdimensionnée pour l'unité d'intérêt de manière à ce qu'elle puisse rejeter en toute sécurité les articles qui n'ont aucune chance d'être considérés comme "proches" de celle-ci. La vérification de l'exclusion d'une boîte englobante pourrait être moins chère qu'une vérification de rayon. Cependant, sur certains systèmes où cela a été testé, il s'est avéré que ce n'était pas le cas. Les deux fonctionnent presque également. Ceci édité après beaucoup de débats ci-dessous.

Premièrement: clip de boîte englobante 2D.

// returns true if the circle supplied is completely OUTSIDE the bounding box, rectClip
bool canTrivialRejectCircle(Vertex2D& vCentre, WorldUnit radius, Rect& rectClip) {
  if (vCentre.x + radius < rectClip.l ||
    vCentre.x - radius > rectClip.r ||
    vCentre.y + radius < rectClip.b ||
    vCentre.y - radius > rectClip.t)
    return true;
  else
    return false;
}

Par rapport à quelque chose comme ça (en 3D):

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
  D3DVECTOR relPos = obj1->prPosition - obj2->prPosition;
  float dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
  float minDist = obj1->fRadius + obj2->fRadius;
  return dist <= minDist * minDist;
}.

Si l'objet n'est pas rejeté de manière triviale, vous effectuez un test de collision plus coûteux et plus précis. Mais vous ne cherchez que des proximités, le test de sphère est donc adapté à cela, mais uniquement pour le 1% d'objets qui survivent au rejet trivial.

Cet article prend en charge la case de rejet trivial. http://www.h3xed.com/programming/bounding-box-vs-bounding-circle-collision-detection-performance-as3

Si cette approche linéaire ne vous donne pas les performances dont vous avez besoin, une structure de données hiérarchique peut être requise, comme les autres affiches en ont parlé. Les R-Trees valent la peine d'être considérés. Ils prennent en charge les changements dynamiques. Ce sont les BTrees du monde spatial.

Je ne voulais tout simplement pas que vous vous donniez autant de mal à introduire une telle complexité si vous pouviez l'éviter. Et qu'en est-il du coût de mise à jour de cette structure de données complexe lorsque les objets se déplacent plusieurs fois par seconde?

Gardez à l'esprit qu'une grille est une structure de données spatiales profondes à un niveau. Cette limite signifie qu'elle n'est pas vraiment évolutive. À mesure que le monde grandit, le nombre de cellules que vous devez couvrir augmente également. Finalement, ce nombre de cellules devient lui-même un problème de performances. Cependant, pour un monde de taille donnée, cela vous donnera une amélioration considérable des performances sans partitionnement spatial.

Je dois en faire une réponse parce que je n'ai pas les points à commenter ou à voter. Pour 99% des personnes qui posent cette question, une boîte englobante est la solution, comme décrit par Ciaran. Dans un langage compilé, il rejettera 100 000 unités non pertinentes en un clin d'œil. Il y a beaucoup de frais généraux liés aux solutions sans force brute; avec de plus petits nombres (disons moins de 1000), ils seront plus chers en termes de temps de traitement que la vérification de la force brute. Et cela prendra beaucoup plus de temps de programmation.

Je ne sais pas ce que signifie «un très grand nombre» dans la question, ni ce que les autres personnes recherchant ici des réponses signifieront par là. Je soupçonne que mes chiffres ci-dessus sont conservateurs et pourraient être multipliés par 10; Personnellement, je suis tout à fait préjugé contre les techniques de force brute et je suis sérieusement ennuyé de leur efficacité. Mais je ne voudrais pas que quelqu'un avec, disons, 10 000 unités perde du temps avec une solution sophistiquée alors que quelques lignes de code rapides feront l'affaire. Ils peuvent toujours avoir envie plus tard s'ils en ont besoin.

De plus, je noterais qu'une vérification de sphère englobante nécessite une multiplication là où la boîte englobante ne le fait pas. La multiplication, de par sa nature, prend plusieurs fois plus de temps que l'addition et les comparaisons. Il y a forcément une combinaison de langage, de système d'exploitation et de matériel où la vérification de la sphère sera plus rapide qu'une case à cocher, mais dans la plupart des endroits et des fois, la case à cocher doit être plus rapide, même si la sphère rejette quelques unités non pertinentes. boîte accepte. (Et là où la sphère est plus rapide, une nouvelle version du compilateur / interprète / optimiseur est très susceptible de changer cela.)