How can I check if one game object can see another?

Question

I have an object, that is facing a particular direction with (for instance) a 45 degree field of view, and a limit view range. I have done all the initial checks (Quadtree node, and distance), but now I need to check if a particular object is within that view cone, (In this case to decide only to follow that object if we can see it).

Apart from casting a ray for each degree from Direction - (FieldOfView / 2) to Direction + (FieldOfView / 2) (I am doing that at the moment and it is horrible), what is the best way to do this visibility check?

Answer 1

Compute the angle between your view direction (understood as a vector) and the vector that starts at you and ends at the object. If it falls under FieldOfView/2, you can view the object.

That angle is:

arccos(scalarProduct(viewDirection, (object - you)) / (norm(viewDirection)*norm(object - you))).

Answer 2

I've worked in the video game industry, and I can say that doing trig functions like arccos every frame is less than ideal. Instead, you precompute the cosine of the angle for the cone:

float cos_angle = cos(PI/4); // 45 degrees, for example

Then, each frame you can quickly check if a point falls inside that cone by comparing that with the dot product of the cone and the .

vector test_point_vector = normalize(test_point_loc - cone_origin);
float dot_product = dot(normalized_cone_vector, text_point_vector);
bool inside_code = dot_product > cos_angle;

There are no trig functions, just some multiplication, division, and addition. Most game engines have an optimized normalize() function for vectors.

This works because of this equation:

A · B = |A| * |B| * cos(Θ)

If you normalize the vectors (A -> An), the equation is simplified:

An · Bn = cos(Θ)

Answer 3

Get the angle between the viewer's heading vector and the vector from viewer to target. If that angle is less than (FieldOfView/2), then the target is in the viewer's field of view.

If your vectors are 2d or 3d this will work the same way. (In 3D, if you have a view frustum instead of cone, then you'll need to separate the angles into two components.) You just need to find the angle between the two vectors.

If you want to test targets which are larger than a single point, you'll need multiple points for each target, such as the corners of a bounding box. If the vector from viewer to any of these points gives an angle inside the field of view, then that corner of the box is visible.

Answer 4

If you're doing 3D and can define the viewing range as a frustrum, then you can use something similar to this Frustrum Culling technique.

Answer 5

Good answers already but I just wanted to give you a link to the Wolfire blog, they recently started a algebra series that take the "field of view" equation as one example. Go read it, its well written and easy.