trouver des objets dans un rayon

Question

Vous cherchez un moyen léger pour trouver des objets dans un rayon.

Jusqu'à présent, la réponse qui est évident pour moi est d'aller à travers chaque objet, en comparant sa position x et y avec le centre du rayon.

Exemple:

Turret -. La recherche de cibles dans un rayon

TargetArray -. Éventail de cibles possibles

WithinRangeArray - tableau nous poussons les cibles applicables à

Distance^2 = (TargetArray[n].x - Turret.x)^2  +  (TargetArray[n].y - Turret.y)^2

if( Distance^2 < maxRadius^2 ){
WithinRangeArray.push(TargetArray[n])
}

Éviter la racine carrée doit me sauver une puissance de traitement. Mais j'ai le sentiment qu'il peut y avoir d'autres algorithmes / théories / méthodes qui peuvent être mieux (plus léger).

La longueur idéale de TargetArray. 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 zone centrée sur votre position de la tourelle. Si le target_x

Answer 2

En 2D vous pourriez mettre en œuvre un quadtree et en 3D vous pourriez mettre en œuvre un Octo ce qui signifie que vous seriez en mesure de regrouper des objets et plus efficacement éliminer les grands groupes d'entre eux avant de vérifier réellement sur leurs distances exactes. Vous devez google pour eux si vous voulez en savoir plus. Ce sont des structures de données très utiles pour les mondes d'objets.

La mise en œuvre finale ne peut pas économiser de l'espace autant, mais il sera très rapide parce que vous pouvez jeter un grand nombre d'objets très rapidement.

Answer 3

Vous pouvez stocker les cibles possibles dans une multiset calée sur la place de la grille qu'ils occupent. Ensuite, vous devez seulement itérer sur les cibles qui sont en carrés de grille assez près de la place de la grille de la tourelle qu'ils pourraient être des cibles.

Si oui ou non cela vaut la peine de faire, dépend du nombre de cibles et le nombre de cibles qui sont susceptibles d'être gamme sont acceptés dans les. Je travaille sur une application avec des cibles des centaines de milliers de cinque seulement 10 ou 20 sont susceptibles d'être Withinn gamme. Dans cette situation, il vaut la peine d'investir dans une grande complexité pour élaguer la liste des cibles potentielles. En vous cas, avec seulement 500 cibles, il pourrait bien ne pas être utile.