Objekte im Radius finden

Question

Auf der Suche nach einem leichten Weg, um Objekte in einem Radius zu finden.

Bisher ist die Antwort, die mir offensichtlich ist, durch jedes Objekt zu gehen und seine X- und Y -Position mit der Mitte des Radius zu vergleichen.

Beispiel:

Turret - Auf der Suche nach Zielen im Radius.

TargetArray - Auswahl möglicher Ziele.

WithinRangeArray - Array Wir drücken anwendbare Ziele auf

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

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

Das Vermeiden der Quadratwurzel sollte mir eine Verarbeitungsleistung ersparen. Aber ich habe das Gefühl, dass es andere Algorithmen/Theorien/Methoden gibt, die besser sein können (leichter).

Ideale Länge von TargetArray: weniger als 500 Ziele gleichzeitig.

Answer 1

Bevor Sie die radiale Entfernung berechnen, überprüfen Sie zunächst, ob sich das Objekt in der Schachtel auf Ihrem Turmort befindet. Wenn das Target_x <Turret_x-Reichweite außerhalb des Bereichs ist und die Entfernung nicht überprüfen muss, überprüfen Sie auch Turret_x+Range, Turret_y-Range, Turret_Y+Range. Dies erfordert maximal 4 Vergleiche und 4 Hinzufügen/Subtrahieren von OPs, um festzustellen, ob sich das Ziel in der Box befindet.

Answer 2

In 2D können Sie einen Quadtree implementieren und in 3D einen Octree implementieren, was bedeutet, dass Sie Objekte gruppieren und große Gruppen von ihnen effizienter verwerfen können, bevor Sie ihre genauen Entfernungen tatsächlich überprüfen. Sie sollten für sie googeln, wenn Sie mehr wissen möchten. Sie sind sehr nützliche Datenstrukturen für Welten von Objekten.

Die endgültige Implementierung spart möglicherweise nicht so viel Platz, aber sie wird unglaublich schnell sein, da Sie eine große Anzahl von Objekten sehr schnell verwerfen können.

Answer 3

Sie können die möglichen Ziele in einem Multiset speichern, das auf dem Rasterplatz kieft, das sie besetzen. Dann müssen Sie nur über die Ziele iterieren, die sich in den Gitterquadraten befinden, die sich nahe genug am Rasterplatz des Turms befinden, dass sie möglicherweise Ziele sind.

Ob dies wert ist oder nicht, hängt von der Anzahl der Ziele und der Anzahl der Ziele ab, die sich wahrscheinlich mit Reichweite befinden. Ich arbeite an einer Bewerbung mit Hunderttausenden Zielen, von denen nur 10 oder 20 in Reichweite sind. In dieser Situation lohnt es sich, in eine erhebliche Komplexität zu investieren, um die potenzielle Zielliste zu beschneiden. In Ihrem Fall kann es sich bei nur 500 Zielen nicht lohnen.