Detecting collisions between a line and a sprite.

[Atom Ant]

Here is my problem: I have a two player game where each player controls a little car that can shoot a laser, which is represented by a flashing line. I can't seem to figure out an equation to detect whether or not the line comes in contact with the enemy vehicle. I'm guessing that I need to find the angle from one player's vehicle to another and compare that with the angle that the attacking player is shooting his laser, but that's all I can figure out right now.

Thanks in advance.

[Rattrapmax6]

Have it compair the X Y of the line ment to contact the car against the car's X Y... that seems to be what you want... :wink:

[Atom Ant]

Thanks for the help, but I came up with a new way to attack which doesn't involve lasers. The math is less complicated and it's more fun this way, anyhow. Huzzah!

[Mitthrawnuruodo]

Here's something I did:
[syntax="qbasic"]doY% = 0
doR% = 0
IF x% >= x2% AND x% <= x2% + LenPic2% THEN doY% = 1
IF x% + LenPic1% >= x2% AND x% + LenPic1% <= x2% + LenPic2% THEN doY% = 1
IF x2% >= x% AND x2% <= x% + LenPic1% THEN doY% = 1
IF x2% + LenPic2% >= x% AND x2% + LenPic2% <= x% + LenPic1% THEN doY% = 1
IF doY% = 1 THEN
IF y% >= y2% AND y% <= y2% + HigPic2% THEN doR% = 1
IF y% + HigPic1% >= y2% AND y% + HigPic1% <= y2% + HigPic2% THEN doR% = 1
IF y2% >= y% AND y2% <= y% + HigPic1% THEN doR% = 1
IF y2% + HigPic2% >= y% AND y2% + HigPic2% <= y% + HigPic1% THEN doR% = 1
END IF
IF doR% = 1 THEN
'Do event handler here
END IF[/syntax]
Its short + sweet can compare collision dectecting of any two pics of any size and any units as long as the units are the same. All you need to know is the x + y coordinates of each pic and their length + height.

[shiftLynx]

If you define the area occupied by a vehicle as a circle, things get a lot easier. Consider the vector equation of a line: p = a + xd where p is any point on the line, a is a definite point on the line and d is the direction. Let a be the position of the shooter and d the direction of the bullet (i.e. the direction of the shooter when the bullet was released).

Now consider an enemy at point q with a radius r.

Basically you want to know if, for any value of x, does it come within r of q (i.e. does it touch or come into the circle).

Distance from p to q is |q-p|.

Hence, if |q-p| = r then a collision occurred.

To tidy up the left hand side, let's go to cartesian form. Remember the aim here is to find some value of x that satisfies this new equation.

Let Ex, Ey = enemy position in cartesian form
Let Px, Py = some position on the bullet line in cartesian form
Let Dx, Dy = bullet direction

SQR(((Ex - Px) * (Ex - Px)) + ((Ey - Py) * (Ey - Py))) = r

Thus:

(Ex - Px)^2 + (Ey - Py)^2 <= r^2

Since Px = Ax + xDx and Py = Ax + xDy:-

(Ex - Ax - xDx)^2 + (Ey - Ay - xDy)^2 = r^2

Expanding:

x^2 Dx^2 - 2x(ExDx - AxDx) - 2ExAx + Ex^2 + Ax^2 + x^2 Dy^2 - 2x(EyDy - AyDy) - 2EyAy + Ey^2 + Ay^2 = r^2

Factorising for co-efficients of common powers of x:

x^2(Dx^2 + Dy^2) - 2x(ExDx - AxDx + EyDy - AyDy) - 2ExAx - 2EyAy + Ex^2 + Ey^2 + Ax^2 + Ay^2 - r^2 = 0

Now you can use the discriminant function to determine whether any real solutions to this equation exist.

Using b^2 - 4ac >= 0

Let f(E, r, A, D) = 4((ExDx - AxDx + EyDy - AyDy)^2 - (Dx^2 + Dy^2)(Ex^2 + Ey^2 + Ax^2 + Ay^2 - 2ExAx - 2EyAy - r^2))

Now, if f(E, r, A, D) >= 0 then the line intersects with the enemy. You will probably want to check the value for 'x' that the intersection occurs at, if it does at all, to make sure that it is in range of the bullet line.

By the way, if you're happy using dot products, etc., you'll find the above mess turns into a much nicer-to-look-at form:

f(E, r, A, D) = 4(( (E . D) - (A . D) )^2 + (D . D)( (E . E) + (A . A) - 2(A . E) - r^2))

This will give you a value for 'b^2 - 4ac' in the famous auto-magic quadratic-equation-solver-equation:

x = (-b +/- SQR(b^2 - 4ac)) / 2a

So, you can do this to find the value of x that the line intersects at:

x1 = (-b + SQR(f(E, r, A, D))) / 2a
x2 = (-b - SQR(f(E, r, A, D))) / 2a

Notice you end up with 2 values of x; find the point that is closest to the bullet launch position (A) and that's where abouts the bullet hit on the enemy. You could even use this to spawn a nice particle effect at the correct impact location.

It's very late where I am (5:00 am) so I might have messed up some of that maths. There's quite a bit of theory missing, like checking whether the value of x calculated is too far away from the bullet's current location to count as a hit or not.

Hope this helps a bit.

-shiftLynx

[Anonymous]

If you define the area occupied by a vehicle as a circle, things get a lot easier.

WHAT??!??!?!?!?

what the hell is hard then

[shiftLynx]

Hard would be detecting the collision between a line and a polygon (in an elegant, generic solution).

I forgot to mention, as well, that if you use the vector form of the collision discriminant function, it will work equally well in any other number of dimensions (most obviously, your game could be made to be 3D and the collision detection code would still work).

-shiftLynx

[Mitthrawnuruodo]

From a circle in #D no way, you need a height. Not only that but those divides + squares takes a lot more calcs for the computer...

Also can it work with two objects of any length + height?

[shiftLynx]

A 3D circle is called a sphere and still only has one parameter: radius. Therefore, the algorithm will still work for bounding-sphere collision.

If you wanted an elliptical shape to bound the players then things would get a bit more complicated because of the mathematical form of ellipses... circles and spheres are a lot easier to deal with.

Thinking of 2D objects as circles works perfectly for small graphics around which you can easily draw a circle and avoid including much empty space.

The final function that I worked towards only requires multiplication, which is about as fast as you will get it. If you really need to know the co-ordinates of the collision, then you could find the value of x (which requires 1 call to the square root function and 1 division -- not too CPU intensive at all, considering collisions will not be occuring very often. From this you can find the position vector of the impact and draw an explosion at the correct place.

If you're only interested in "does the line hit the player at all" then you only need multiplications; it's extremely fast. This would be sufficient in a simple 2D space game, for example... just draw an explosion at the enemy location.

Also can it work with two objects of any length + height?

If you want polygon-based 3D shapes and to detect these collisions, you'll need to do a bit more processing to detect whether any point on the bullet line lies on the surface of one of the planes.

By the way, this is method of detecting a collision can be extended further to be used in raytracing.

-shiftLynx

[thegrogen]

Not only that but those divides + squares takes a lot more calcs for the computer...

One solution to that is to use look-up tables.