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

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.

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.

-
An observation: 'then take the orientation quaternion, and convert that to a vector of fixed length, and perform the dot product between them' - Doing that is wrong. A quat gives you an axis of rotation, not the direction in which an object is pointing, looking. You must have your own direction vector attached to the center of that object, in object space. Otherwise, you'll get bogus results. – teodron Apr 30 '12 at 8:15
This kind of assumes that the player is represented by a point rather than a volume. Consider what would happen if that point was at the player's feet, and they stood in front of a low wall. Also consider the "unfairness" if it's at the top of their head, and they are 99% obscured, but instantly "seen". Perhaps a collection of points on the body, and "chance of being seen" based on percent visible (weighted by distance)? – Tim Holt Apr 30 '12 at 18:24
@TimHolt I understand what you are getting at, so I was already planning to have the `point` be at the object center, and then I wasn't planning to use cover systems with this AI build, but if this is to be later used for a cover based shooter then ray tracing along vector to player would be the next inclusion into the system. – gardian06 Apr 30 '12 at 19:28

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.
-
I was planning that each "room" be self contained, and have any given AI entity test against things a room over (just in case the player is hiding in a door), and also having a similar system for the AIEntities to use for path finding (node driven type system then having field of vision control which node the go to) – gardian06 Apr 30 '12 at 19:13
does it matter which axis-vector I use, or will any work? – gardian06 Apr 30 '12 at 19:30
@gardian06 : It depends on your particular setup. Whatever axis-vector marks the NPC's look direction in their local coordinate system is the one you'd use their orientational quaternion to transform into their worldspace look vector; this is just a particular instance of the local-to-world transformation that their orientation quaternion represents. – Steven Stadnicki Apr 30 '12 at 19:38

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.

-
Is that faster than what the OP first had in mind? It certainly does benefit from a fairly decent graphics rendering framework that does have the frustum culling in place already. +1 for the suggestion.. but it might help to expand just a bit on the benefits – teodron Apr 30 '12 at 11:22
The main benifit is simply to reuse some existing code so you can get something running a bit faster and see it working. You would want to adapt it later to get more accurate results (for the player being in cover etc). And if your profiler is telling you there is a problem at that point then it might be worth finding something more efficient. – OriginalDaemon Apr 30 '12 at 12:37
This is a good general approach. The OP's approach relies on rather conical frustums (the nature of the dot product) and although not general enough, it could be sufficient and fast for that particular case. – teodron Apr 30 '12 at 14:03
I was kind of wanting to use the conical nature of the dot product, and I have a feeling that giving each `AIEntity` a camera frustrum would be more expensive then even having to do both tests that I am proposing – gardian06 Apr 30 '12 at 17:52
If you're already making use of a good graphics library then you will probably have good scene culling. If your using this frustum method you can reuse that culling code and get the benefits of culling the scene before testing for visibility. It may not necessarily be faster computationally, but it may be the most efficient use of your time (and could potentially be faster). Remember, A.I. visibility isn't just related to the player, there can be objects and walls to hide behind. – OriginalDaemon May 1 '12 at 0:01