Tuesday, January 8, 2013

The Math Behind Vision Cones in Unity 3D



Lately, I've been tinkering with with an early Unity 3D prototype of a top-down action game and I figured I should implement vision cones to add a stealth element to dealing with the enemies. My initial solution was to stick a cube collider in front of enemies to represent their vision.

Simple, but crude: It doesn't take into account whether the player's character is obscured by a piece of the environment.



I thought to myself, there must be some way to represent a cone through math. In terms of collision, rectangles and cubes are simply sets of points and spheres are a radius and a center point. Are cones much more complex?

I did some Googling and found this Gamasutra article: http://www.gamasutra.com/view/feature/2888/building_an_ai_sensory_system_.php?print=1

Honestly, I didn't get very far into the article before I found what I needed. Basically we can think of a Cone as a small section of a circle or a slice of pie. To sum it up, building the math behind a the cone involves 3 steps:

1. Figure out whether the player is within a circle around the enemy. This is determined by finding the magnitude(or square magnitude for efficiency) of a vector from the enemy position to the player position.

2. Figure out whether the player is standing in the subsection of the circle around the enemy. To determine this, we need to figure out the angle between the enemy's forward vector and the vector from the enemy to the player.

3. Is the player obscured by anything? To figure this out, shoot a raycast from the enemy to the player. If nothing is in the way, continue.


Above, Angle A is the angle between the Enemy Forward Vector and the vector from the Enemy to the Player. Angle B is the angle between the Enemy Forward Vector and the edge of the Enemy Vision Cone. If the Player is inside the cone Angle A will be smaller than Angle B.

The mathematical function for the angle between two vectors is described in detail here: http://www.wikihow.com/Find-the-Angle-Between-Two-Vectors

With this I had the math to write up a function in C# in a Unity script:


[SerializeField] private float m_halfConeSize = 45f;  
     
//Step 1: With a sphere collider, we can figure out when things are
// within a circle around us.

void OnTriggerStay(Collider col)  
     {  
         Vector3 myPos = transform.position;  
         Vector3 myVector = transform.forward;  
         Vector3 theirPos = col.transform.position;  
         Vector3 theirVector = theirPos - myPos;  

         //Step 2: Is the object in front of this enemy?

         float angle = Vector3.Angle(myVector, theirVector);  
         bool isInFront = angle < m_halfConeSize;  

         //Step 3: Is there anything obscuring the object?
         Debug.DrawLine(myPos, theirPos, isInFront ? Color.green : Color.red);  
         if(isInFront)  
         {  
             //Bit shift the layermask so that this linecast only hits actors we want it to.  
             int mask = 1 << LayerMask.NameToLayer ("Env");   
             if(!Physics.Linecast(myPos, theirPos, mask))  
             {  
                 SenseSomething(col.gameObject);  
             }  
         }  
     }  

I took a few shortcuts. Notably, I did not calculate the distance between the Player and the Enemy in Step 1. Instead, I let Unity's collision system handle that. OnTriggerStay is called every frame as long as the triggering collision continues to happen.

However, I was not satisfied with the efficiency of this code. The angle-between-two vectors function uses at least a single square root because magnitudes are involved. Square roots are some of the most inefficient math computations. So I used a trick I picked up while working on a physics platformer prototype a few years ago: if I take the equation and use square magnitudes instead of magnitudes, I can eliminate the square roots. This makes the values from the magnitudes much higher, but the length of the vectors does not factor into the angle.

EDIT: I talked to a Math teacher friend of mine and it turns out, this square magnitude variation on the equation is not equivalent. We can see the two charted on this Wolfram Alpha graph. For negative X values, I flip the values manually in the code below so the negative values aren't negated. What we have here is a close approximation, but it is not 100% accurate.


Where VP is the vector from the Enemy to the Player and VF is the Enemy's forward vector.

 [SerializeField] private float m_halfConeSize = 45f;  

    //Step 1: With a sphere collider, we can figure out when things are
    // within a circle around us.

     void OnTriggerStay(Collider col)  
     {  
         Vector3 myPos = transform.position;  
         Vector3 myVector = transform.forward;  
         Vector3 theirPos = col.transform.position;  
         Vector3 theirVector = theirPos - myPos;  

         //Step 2: Is the object in front of this enemy?

         float mag = Vector3.SqrMagnitude(myVector) * Vector3.SqrMagnitude(theirVector);  
         
         if(mag == 0f) //prevent divide by zero.  
             return;  

         float dotProd = Vector3.Dot(myVector, theirPos - myPos);  
         bool isNegative = dotProd < 0f;  
         dotProd = dotProd * dotProd;  
         //The Square operation will eliminate negative values, but we want to retain them.
         if(isNegative)  
             dotProd *= -1;  

         float sqrAngle = Mathf.Rad2Deg * Mathf.Acos(dotProd/mag);  
         bool isInFront = sqrAngle < m_halfConeSize;  
         if(col.gameObject.name == "Player")  
             print(sqrAngle + " " + col.gameObject.name);  

         //Step 3: Is there anything obscuring the object?

         Debug.DrawLine(myPos, theirPos, isInFront ? Color.green : Color.red);  
         if(isInFront)  
         {  
         //Bit shift the layermask so that this linecast only hits actors we want it to.  
             // We want the Env objects to block our linecast.  
             int mask = 1 << LayerMask.NameToLayer ("Env");   
             if(!Physics.Linecast(myPos, theirPos, mask))  
             {  
                 //print("sensing something " + col.gameObject.name);  
                 SenseSomething(col.gameObject);  
             }  
         }  
     }  

1 comment:

Richard C. Lambert said...

Wow what a Great Information about World Day its exceptionally pleasant educational post. a debt of gratitude is in order for the post.
c sharp