la ricerca di oggetti all'interno raggio

Question

Cercando un modo leggero per trovare oggetti all'interno di un raggio.

Finora la risposta è ovvia, per me, è di passare attraverso ogni oggetto, confrontando la posizione x e y con il centro del raggio.

Esempio:

Turret - alla ricerca di bersagli nel raggio.

TargetArray - matrice di possibili obiettivi.

WithinRangeArray - matrice di spingere applicabile obiettivi

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

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

Evitando la radice quadrata deve salvare me un po ' di potenza di elaborazione.Ma ho la sensazione che ci possono essere altri algoritmi/teorie e metodi che possono essere meglio (più leggero).

Lunghezza ideale di TargetArray:meno di 500 bersagli alla volta.

Answer 1

Prima di calcolare distanza radiale, primo controllo per vedere se l'oggetto è all'interno della casella centrata sulla tua posizione torretta. Se il target_x

Answer 2

In 2D è possibile implementare un Quadtree e in 3D è possibile implementare un Octree che significa che si sarebbe in grado di raggruppare gli oggetti in modo più efficiente e scartare i grandi gruppi di loro prima di poter realmente il controllo su loro distanze esatte. Si dovrebbe google per loro se volete sapere di più. Essi sono molto utili strutture di dati per i mondi di oggetti.

L'implementazione finale non può risparmiare spazio tanto ma sarà incredibilmente veloce, perché è possibile eliminare un gran numero di oggetti molto rapidamente.

Answer 3

È possibile memorizzare i possibili obiettivi in un multiset digitato sulla griglia di quadrati che occupano.Basta poi scorrere gli obiettivi che sono in quadrati della griglia abbastanza vicino alla torretta del quadrato di superficie che potrebbero essere obiettivi.

Se o non questo è la pena di fare, dipende dal numero di obiettivi e il numero di obiettivi che sono suscettibili di essere entro la portata.Sto lavorando su un'applicazione con centinaia di migliaia obiettivi con solo 10 o 20 sono suscettibili di essere withinn gamma.In questo caso, vale la pena di investire in una notevole complessità di sfoltire il potenziale di lista dei target.Nel vostro caso, con soli 500 obiettivi potrebbe non essere la pena.