Trouver des objets dans un rayon

Question

À la recherche d'un moyen léger pour trouver des objets dans un rayon.

Jusqu'à présent, la réponse qui me semble évidente est de parcourir chaque objet, en comparant sa position x et y avec le centre du rayon.

Exemple :

Tourelle - à la recherche de cibles dans un rayon.

TableauCible - tableau des cibles potentielles.

TableauDansRayon - tableau dans lequel nous ajoutons les cibles applicables.

Distance^2 = (TableauCible[n].x - Tourelle.x)^2 + (TableauCible[n].y - Tourelle.y)^2

if( Distance^2 < maxRayon^2 ){
TableauDansRayon.push(TableauCible[n])
}

Éviter la racine carrée devrait me faire économiser un peu de puissance de traitement. Mais j'ai le sentiment qu'il peut y avoir d'autres algorithmes/théories/méthodes qui pourraient être meilleurs (plus légers).

Longueur idéale de TableauCible : moins de 500 cibles à la fois.

Answer 1

Avant de calculer la distance radiale, vérifiez d'abord si l'objet se trouve dans la boîte centrée sur l'emplacement de votre tourelle. Si target_x < turret_x-range alors il est hors de portée et il n'est pas nécessaire de vérifier la distance, vérifiez également turret_x+range, turret_y-range, turret_y+range. Cela nécessite un maximum de 4 comparaisons et 4 opérations d'addition/soustraction pour déterminer si la cible est dans la boîte.

Answer 2

En 2D, vous pourriez implémenter un Quadtree et en 3D, vous pourriez implémenter un Octree, ce qui signifie que vous seriez en mesure de regrouper des objets et de les éliminer plus efficacement avant de vérifier leurs distances exactes. Vous devriez les rechercher sur Google si vous voulez en savoir plus. Ce sont des structures de données très utiles pour les mondes d'objets.

L'implémentation finale pourrait ne pas économiser autant d'espace, mais elle sera incroyablement rapide car vous pourrez éliminer un grand nombre d'objets très rapidement.

Answer 3

Vous pourriez stocker les cibles potentielles dans un multi-ensemble indexé sur le carré de grille qu'elles occupent. Ensuite, vous n'avez qu'à parcourir les cibles qui se trouvent dans des carrés de grille suffisamment proches du carré de grille de la tourelle pour qu'elles puissent être des cibles.

Savoir si cela vaut la peine de le faire dépend du nombre de cibles et du nombre de cibles susceptibles d'être à portée. Je travaille sur une application avec des centaines de milliers de cibles, parmi lesquelles seules 10 ou 20 sont susceptibles d'être à portée. Dans cette situation, il est utile d'investir dans une complexité significative pour élaguer la liste des cibles potentielles. Dans votre cas, avec seulement 500 cibles, cela pourrait ne pas être utile.

Answer 4

Je recommande vivement cet article pour des idées