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

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.

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(Θ)