What's the best method to give an entity a "search" range?

[URSvAir14]

Hello all!
I just have a quick (and fairly noob-ish) question about enemies in a game having a "search" range. Say for instance I want to have a turret that will attack an enemy unit within a specified range, what is the best and most efficient way of finding an enemy unit if you have more than one enemy?

I was thinking about having the turret find the distance between itself and every enemy in the container and then selecting the closest one that is within it's range. However wouldn't that just make the game lag if there are more turrets added? So which method would you guys say is the best for making a "search" range?

Thanks

[MadMartin]

Just do the brute force check "every turret <-> every enemy". If you have few turrets and enemies (like 100 or so) the check shouldn't be that bad on today's computers.

But if you really happen to experience any lags, use a spatial data structure like a quadtree to organize your objects and to reduce the number of tests that are needed.

[URSvAir14]

Okay, thank you

[Nexus]

Already a spatial grid (the non-hierarchical version of quadtrees) will show massive performance improvements. See here for detailed information.

[insomniac]

I use this to check distances.

 /**
 * Finds the distance IN TILES between a pair of x,y coordinates
 */
inline int path_length(int x1, int y1, int x2, int y2)
{
        return std::abs(x1 - x2) + std::abs(y1 - y2);
}

int enemy_distance = path_length(enemy->x, enemy->y, this->x, this->y);

[The Terminator]

You could also render a transparent sf::Circleshape at the same position as the turret and check for collision.

[zsbzsb]

You could also render a transparent sf::Circleshape at the same position as the turret and check for collision.

Ummm, the point to a transparent shape would be what? SFML doesn't even support circular collision detection so you would need to write that yourself and that effectively obsoletes a transparent shape since a transparent shape would have no impact on the collision detection.

[The Terminator]

You can use the points and bounds of the Circleshape in your collision code.

[zsbzsb]

You can use the points and bounds of the Circleshape in your collision code.

Why go to the trouble when something as simple as below works just as effectively and is much more efficient for circular collision detection?

        private static float Distance(Vector2f A, Vector2f B) // returns distance between two points
        {
            return (float)Trigonometry.SqrRoot((B.X - A.X) * (B.X - A.X) + (B.Y - A.Y) * (B.Y - A.Y));
        }
        private static bool Collides(Circle A, Circle B) // simple collision detection between two circles
        {
            float dist = Distance(A.Position, B.Position); // gets distance between circles
            return dist < A.Radius + B.Radius; // if dist < combined radius we have a collision
        }