Closest point on a path to a point, or: Dear target, sorry I missed you.

Question

For a 2D game I'm working on, I'd like to figure out when a projectile reaches its closest to point to its target.

A projectile is a point that moves by a constant dx,dy per frame. A target is another point whose speed relative to the projectile is slow enough as to be considered stationary. I want to have the projectile explode when it is (approximately) as close to the target as it will be.

What's a good way to calculate this?

Absolute precision is not critical, this is the client-side simulation of an event that has already been resolved on the server. I'd prefer an algorithm that was fast and simple to one that was pixel perfect.

Answer 1

Calculate the normal to the path that intersects with the target. The intersection of the normal and the path will be the closest point on the path to the target.

Answer 2

Minimum Distance between a Point and a Line: (which is in effect what the problem boils down to)

http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/

More referenece material in his general geometry section:

http://local.wasp.uwa.edu.au/~pbourke/geometry/

Answer 3

Keep track of the previous distance, and check for the first moment the distance starts to increase.

if ((currentDistance==0) || (currentDistance > previousDistance)) Explode()

It is only this simple because you path geometry is trivial (i.e. a straight line), but it works just fine.

This has the added advantage of working when the target is faster than you describe as well, so long as both tracks are straight (or at least gently curving).

Limitation, you step size needs to be small compared to the "size" of the explosion, or this won't work right. In that case, you would need to precompute the next distance...

Answer 4

Seems like your 'projectile' is basically moving in a straight line.

A simple was to visualize is to transform your 2D plane so that the line becomes the x axis. This would involve a rotation by arctan(dy/dx).

Apply the same transform to the point in question, and obtain the y coordinate.

If you care to, you could do this manually and figure out, but game APIs should already be well suited to this.

Answer 5

You could just use the Pythagorean theorem which just uses the (a)2 + (b)2 = (c)2 formula. So, your distance would be equal the SQUARE ROOT of the product. Here is a good article on how to implement it using points on a grid.

http://www.mathwarehouse.com/algebra/distance_formula/