[resolved] Oval collision detection - how to?

About the easiest thing one can do is a circular collision detection. You just calculate the distance from center to center and if the result is smaller than the summed radii the circles are colliding.

But in my game the objects have oval shadows, well basically just circles with half the height. I noticed the collision detection should match the shadows, otherwise it feels weird when playing.

So how can I check if 2 ovals are colliding? The ovals are not roated, as said before they are just half-the-height shrinked circles.

Any ideas?

Thanks, Fox

Just a guess but how about doubling the Y component of the distance vector (in a separate variable).

Don't know if that'll work or not to be honest, use the same circle code as before with this new y value.

First of all, are your "ovals" ellipses? I mean, can they be described by a simple equation or are they defined as a bunch of arbitrary coordinates (i.e. a polygon)?

...and are all "ovals" of the same size?

Well, I'm going to assume you work with ellipses all of the same size and the same orientation as you've mentioned they are not rotated (this latter assumption considerably simplifies the problem).

Let's consider a pair of ellipses. I'll set the coordinate origin at the center of one of them (see figure).

A collision will take place if

F = OO' - (OM + ON) <=0

By symmetry, OM = ON so:

F = OO' - 2*OM <=0

In order to find OM we need the intercept of the first ellipse with the line connecting the centers, i.e. we must solve this system of equations:

(x/a)² + (y/b)² = 1
y = (q/p)x

where a and b are the semiaxes and (p,q) are the coordinates of the center for the second ellipse. This leads to:

(x/a)² + ((qx/p)/b)² = 1

and finally:

x = abp/Sqrt(a²q² + b²p²)
y = abq/Sqrt(a²q² + b²p²)

so that OM = Sqrt(x² + y²) = ab*Sqrt(p² + q²) / Sqrt(a²q² + b²p²)

The distance OO' is:

OO' = Sqrt(p² + q²)

Therefore the condition for collision becomes:

0 >= F = Sqrt(p² + q²) - 2ab*Sqrt(p² + q²) / Sqrt(a²q² + b²p²) =
Sqrt(p² + q²) * [1 - 2ab / Sqrt(a²q² + b²p²)]

Because Sqrt(p² + q²) is positive, then:

1 - 2ab / Sqrt(a²q² + b²p²) <= 0

which can be finally expressed more ellegantly as:

Sqrt[(p / a)² + (q / b)²] <= 2

Yes, that's exactly what I meant! Thanks a lot krtxmrtz, excellent work ^^;

@wossname: Guess that would work, too. *check* It does, why didn't I think of that sooner? *hehe* Was late that evening.. -.-'

Krtxmrtz,

Nice demonstration but I think there is some thing wrong about it. I checked both conditions (which are equivalent, as you say):

1) OO' - 2*OM <=0
2) Sqrt[(p / a)2 + (q / b)2] <= 2

by assuming random values for p and q and results don´t always match. Try, for instance, a = 15; b = 10; p = 25 and q = 15. Equation 1) returns -9,44 < 0, which satisfies, but equation 2) returns 2,24 > 2, which doesn´t. I add an Excel file where you can give any values to a and b and let p and q vary randomly.

Please correct me if I am wrong.

Today (12 of November) I exchanged the Excel file that I had attached to this post by another one which is now correct after the Krtxmrtz comments made in the next posts.

Quote:

---

Originally Posted by Rassis

Krtxmrtz,
Please correct me if I am wrong.

---

Well, I've spotted a mistake in cell G9: the last term "+F4^2" should be "+C5^2*F4^2". Check it up.

You are right. I am so sorry. Thank you and congratulations for the ellegant demonstration (I rated your post).

Quote:

---

Originally Posted by Rassis

You are right. I am so sorry. Thank you and congratulations for the ellegant demonstration (I rated your post).

---

Anyway, thanks for checking it. Although this time it was correct, I often make mistakes when cumbersome algebraic derivations are involved.

I just forgot to mention that,

Sqrt[(p / a)² + (q / b)²] <= 2

should actually be evaluated as:

(p / a)² + (q / b)² <= 4

in order to speed up the code, specially if the number of ovals to be tested is large. But probably you had already thought of that.

I’d like to leave here a new Excel application with the correction of my mistake spotted today by Krtxmrtz. It does confirm the correctness of the expression deducted by him.

Thanks again to both of you :)