How do I implement a field of vision for AI entities?

Question

I am considering how to implement a field of vision system for my AI entities, but am not sure on the order of steps to take. The thought process that I had was to use a combination of radial distance and dot product.

Keeping in mind that this is a 3D environment (meaning that all vectors have 3 components), and I will be using quaternions for the orientation of all entities.

What order should I do these in? and is my logic accurate?

Dot product: Taking the position of the playerObject, and the position of the AIEntity create a vector, and then take the orientation quaternion, and convert that to a vector of fixed length, and perform the dot product between them (testing for a specific range of values) to see if it is within a given arc.

Radius test: Simple 3D radius to determine distance.

I know for sure that a dot product test should be quite simple (3 subtractions, 3 multiplications, 2 additions, and however many operation to turn a quaternion into a vector), but arriving at the orientation vector I have no direct idea (if this process could be explained it would be of great help, I know I would have to multiply by the needed magnitude after normalizing), and radius test is also simple (3 subtractions, 3 additions, and 4 multiplications) both of these would still include a boolean tests, but which order would reduce faster?

My first guess would be to be the dot product, and then the radius test; As the dot product would be outside of bounds if the player is outside of the arc or to far away, and the radius test would only fail if the object is to far away. I understand that both tests can give false positives, but for some reason I feel that the dot product test would give fewer.

Answer 1

A few things that come to mind:

1. For the first test you shouldn't really (directly) need any quaternions; you have your AI's heading as a vector (and if you don't, you can quickly derive it from their orientation quaternion by transforming one of the axes), and so as you note your cone-of-vision test is just comparing the dot product of the normalized heading vector for your AI with the normalized vector-to-player.
2. While you would still need a distance check, the best way to perform that cull for most AI entities might be 'up-front' and implicit: use your spatial partitioning scheme to avoid ever doing the checks in the first place for AIs that are far enough from the player! In other words, rather than iterating over all AI Entities in the world for the field-of-vision tests, iterate over just a list of the entities that are in cells close enough to the player that you know the distance-based culling has some chance of passing.
3. Most importantly: both of these culling operations are fast enough already that it simply doesn't matter what order you do them in; you could do them both for every AI and it still shouldn't have any measurable impact on your performance. From that perspective, this smacks strongly of premature optimization. I really wouldn't worry about which cull will be more efficient/more effective at this point; unless you have literally thousands of AIs performing this check every frame, it Just Won't Matter.

Answer 2

One method is simply to add a view frustum to the A.I. and do frustum collision detection as you would for object culling in the rendering system. This will allow you to reuse some more code and you can test it out by adding an initial view frustum to the A.I. by reusing a camera object.