la búsqueda de objetos dentro de un radio

Question

Busca una manera ligera para encontrar los objetos dentro de un radio.

Hasta ahora, la respuesta que es obvio para mí es ir a través de cada objeto, comparando su posición xey con el centro del radio.

Ejemplo:

Turret -. En busca de objetivos en un radio

TargetArray -. Variedad de posibles objetivos

WithinRangeArray - gama empujamos objetivos aplicables a

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

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

Evitar la raíz cuadrada me debe guardar cierta capacidad de procesamiento. Pero tengo la sensación de que puede haber otros algoritmos / teorías / métodos que pueden ser mejor (más ligero).

duración ideal de TargetArray:. Menos de 500 objetivos a la vez

Answer 1

Antes de calcular la distancia radial, primera comprobación para ver si el objeto está dentro de la caja centrada en su ubicación torreta. Si el target_x

Answer 2

En 2D se podría implementar un Quadtree y en 3D que podría implementar un octárbol que significa que usted sería capaz de agrupar objetos y más eficientemente descartar grandes grupos de ellos antes de que realmente comprobar para arriba en sus distancias exactas. Usted debe de google para ellos si usted quiere saber más. Son estructuras de datos muy útiles para el mundo de los objetos.

La implementación final puede no ahorrar espacio como mucho, pero va a ser muy rápido porque se puede descartar un gran número de objetos muy rápidamente.

Answer 3

Se puede almacenar los objetivos posibles en un conjunto múltiple introducido en el cuadro de la cuadrícula que ocupan. A continuación, sólo se necesita iterar sobre los objetivos que están en cuadrículas lo suficientemente cerca de cuadrícula de la torreta de que podrían ser objetivos.

Si es o no vale la pena hacerlo, depende del número de objetivos y el número de objetivos que pueden ser gama EL PLAZO. Estoy trabajando en una aplicación con cientos de miles objetivos, de poco con sólo el 10 o 20 es probable que sean withinn gama. En esta situación, vale la pena invertir en una complejidad significativa para podar la lista de objetivos potenciales. En caso de que, con sólo 500 objetivos bien puede no valer la pena.