Intersection between Rectangle and a Circle sector in libgdx

Question

I am programming a game using libgdx. For the Enemies i want to write a simple AI. This AI should track the Player if he was in the field of Vision once. The field of Vision is a circle sector or 2d cone. What would be the most efficient way to reach this? I have allready read the following: Point in circle sector

I could use this with every Corner Point of my Player but i also have the field of Vision given with direction and angle (sector between direction - angle/2 to direction + angle/2). The angle won't be over 180 (as this would be a problem for the algorithm). Would it be a Problem to calculate the Vectors for start and end of sector for every enemie in the game? What would be the best solution and how can i calculate the Vectors out of the given direction and angle?

Answer 1

You can use the solution described in the linked post, but you have to convert your angles to vectors by calculating the sine and cosine of dir +/- angle/2. The linked solution talks about integer arithmetic, but your vectors will be floats:

arm1 = [cos(d - 0.5 * a), sin(d - 0.5 * a)]
arm2 = [cos(d + 0.5 * a), sin(d + 0.5 * a)]

The arguments to cos and sin are in radians. An angle of zero points in the x direction, i.e. east in a traditional Cartesian system.

In order not to do unecessary work, you should check the easy things first.

I would do a simple box check before checking for intersection with the sector: If all four corner points of your rectangle are outside the square box around the enemy, there is no intersection:

if (x0 < x-r && x1 < x-r && x2 < x-r && x3 < x-r) return false;
if (x0 > x+r && x1 > x+r && x2 > x+r && x3 > x+r) return false;
if (y0 < y-r && y1 < y-r && y2 < y-r && y3 < y-r) return false;
if (y0 > y+r && y1 > y+r && y2 > y+r && y3 > y+r) return false;

This simple check should rule out many enemies.

Next, check the radius for all four points as described in the linked answer and return false if none of your corner points is within the radius.

It is only now that we have to calculate the vectors with the trig functions. You can do this with the formula given above. If you have the sine and cosine of the enemy and angle already, you can use addition theoremes to speed up vector calculation:

# sin_d = sin(d), cos_d = cos(d)
# sin_a = sin(0.5 * a), cos_a = cos(0.5 * a)

arm1 = [cos_d * cos_a + sin_d * sin_a, sin_d * cos_a - cos_d * sin_a]
arm2 = [cos_d * cos_a - sin_d * sin_a, sin_d * cos_a + cos_d * sin_a]

The viewing angle is probably a constant for each enemy, so you can precalculate it, and you might already have cos_d and sin_d precomputed as well.

If you are not concerned with accuracy and don't want to get into radians, you could precompute the sines and cosines for one-degree steps and store them in two arrays of size 360. Then calculating the sine will become a matter of looking up an array, i.e. it will be fast, and you can do all your calculations n degrees. (But take care of wrapping: 5° - 15° should then be 350°, not -10°.)