Elliptical Collision Detection.

[SNIPERDUDE]

I was reading a technique for an agent's AI for games (would be a FPS in my case), and one interesting idea I came across was a different approach to a bot's vision. In the illustration they gave they noted an ellipse around the player to elliminate the blind spots created by other methods (and even adds a bit of the ellipse behind the player for simulating a human's "sixth sense" of how we can sense a person standing behind us). They gave a couple diagrams I quickly copied (below), as I couldn't take the article home with me.

My question being this: How would I simulate collision detection for the ellipse below (given a pre-assigned value to how far the bot can see)?


The images I quickly copied, you can use them to help me figure it out:

[DemonWasp]

If the question you want to answer is "are the coordinates (x,y) inside this ellipse?" then the easiest way is very similar to circular collision detection.

The formula for an ellipse is x ^ 2 / a ^ 2 + y ^ 2 / b ^ 2 = 1. You can use this fact to determine where the point is in relation to the ellipse by determining the value of the left hand side. If that value is 1, the point is on the ellipse; if it is less, then the point is inside the ellipse, if it is more, the point is outside the ellipse.

This may be complicated by the fact that your ellipse may be rotated (agent is facing another direction). To solve that problem, it is probably easiest to do a minor amount of trigonometry (or linear algebra, if you're so inclined) to rotate the point you're checking - (x, y) - into the "standard basis" where the ellipse is aligned some particular way, such as horizontally or vertically. Basically, get the coordinates of the target relative to the agent (x', y' ) then use those to detect whether the agent can see the target.

This isn't a simulation - it's exact.

[SNIPERDUDE]

Thanks, I'll try this out and see how it goes. If I have any more questions I'll be sure to ask.

EDIT: Okay, so I just tested out the equation in a Turing simulation (because Turing is just too convenient that way), and it seems to work wonderfully. I'll try adding variable angles in the morning.

Turing:

setscreen ("nobuttonbar, offscreenonly, graphics:450;450") var mx, my, mb : int const x_radius : int := 50 const y_radius : int := 100 const x_center : int := 225 const y_center : int := 225 loop     exit when hasch     Mouse.Where (mx, my, mb)     cls         if (mx - x_center)**2 / x_radius**2 + (my - y_center)**2 / y_radius**2 <= 1 then         drawfilloval (mx, my, 4, 4, brightred)     else         drawfilloval (mx, my, 2, 2, 7)     end if         drawoval (x_center, y_center, x_radius, y_radius, 7)     View.Update end loop

EDIT2: Okay, I was thinking about it only to realize I have no idea about how to make it so it works on whatever angle the player is facing. Any ideas?


EDIT 3: I think I figured it out - took about 90 min of trial + error, and quite a bit of googling too. Let me know if I missed something:

Turing:

setscreen ("nobuttonbar, offscreenonly, graphics:450;450") var mx, my, mb : int const x_radius : int := 50 const y_radius : int := 100 const x_center : int := 225 const y_center : int := 225 const angle : int := 45 var x, y : int := 0 loop     exit when hasch     Mouse.Where (mx, my, mb)     cls     x := round((mx - x_center) * cosd(angle) - (my - y_center) * sind(angle))     y := round((my - y_center) * cosd(angle) + (mx - x_center) * sind(angle))             if (x**2 / x_radius**2) + (y**2 / y_radius**2) <= 1 then         drawfilloval (mx, my, 4, 4, brightred)     else         drawfilloval (mx, my, 2, 2, 7)     end if         if angle = 90 or angle = 270 then         drawoval (x_center, y_center, y_radius, x_radius, 7)     else         drawoval (x_center, y_center, x_radius, y_radius, 7)     end if         View.Update end loop