Calculating an intercept course to a target with constant direction and velocity (in a 2-dimensional plane)

For some game idea I worked on a bit some time ago I needed a bit of maths. Luckily all that was needed was taught at school and with a bit of thinking (and trying) it all worked out:
diagram of a moving object to be intercepted by a projectile

Let’s consider an object at point A moving with the constant speed vector \vec{v}. At point B we got the ability to fire a projectile with speed s. Where do we have to aim at to hit the object with our projectile? In other words: what is the location of point I or what would be the vector \vec{x}?

Now let us derive the necessary maths and put it into code… (requires understanding of vectors and quadratic equations)

If t denotes the time (such that at t=0 we got our object at point A and our “gun” at point B then the point of interception will be I = \vec{a}+t\cdot\vec{v}. We also have I = \vec{b}+t\cdot\vec{x} since we’re trying to find the point at which object and projectile are at the same place (I) at the same time (t). If we can calculate t we can also calculate I.

A first attempt would be to set equal our two (equal) locations of I that is \vec{a}+t\cdot\vec{v} = \vec{b}+t\cdot\vec{x}. However, we don’t know vector \vec{x} but only its length (i.e. the speed of our projectile) |\vec{x}| = s. Using that last information you can set up an equation system and try to solve it. It’s possible, but very nasty, so let’s take a different approach:

Since the projectile needs time t to get from B to I we can divide this distance by the known speed s to just derive that t. The distance from B to I is |\vec{a}+t\cdot\vec{v} - \vec{b}| and thus we get t=\frac{|\vec{a}+t\cdot\vec{v} - \vec{b}|}{s}. Now we got the problem that our t is on both sides of the equation which unfortunately cannot be solved by “simple” means like multiplying and dividing both sides of the equation with whatever. It appears we’ve got to get rid of the vectors first but before doing so let’s clean up things a bit:

The numerator contains the term \vec{a} - \vec{b} which are two known figures in our problem. Hence we will just use \vec{o} (o like offset between a and b) instead, that is \vec{o} = \vec{a} - \vec{b} which gives us the simpler equation t=\frac{|\vec{o}+t\cdot\vec{v}|}{s}. To get rid of the fraction we also multiply both sides with s and get s \cdot t = |\vec{o} + t \cdot \vec{v}|. Now that’s better! Just let’s get rid of the vectors and their vector length operator in one fell swoop.

Since the length of a vector is the square root of the sum of the squares of its components we get s \cdot t = \sqrt{(o_x + t \cdot v_x)^2+(o_y + t \cdot v_y)^2}, where the subscripts denote the respective components of the vectors. By squaring both sides we can also get rid of the square root: s^2 \cdot t^2 = (o_x + t \cdot v_x)^2+(o_y + t \cdot v_y)^2. Now we finally have a chance to sort out all the variables by simple transformations. The brackets can be squared out either manually or by binomic equivalences and then we can factor out t and order the terms to finally get t^2\cdot(v_x^2 + v_y^2 - s^2) + t\cdot2\cdot(o_x \cdot v_x + o_y \cdot v_y) + o_x^2 + o_y^2= 0 which is a quadratic equation that can be solved. Before doing so however we take a look at its components and try to simplify our calculation. Since we could fill in numbers for all variables but t we do so by substituting with simpler “helper” variables denoted by the following definitions: h_1 := v_x^2 + v_y^2 - s^2;h_2 := o_xv_x + o_yv_y;h_3 = o_x^2+o_y^2. Thus, by dividing our last equation by h_1 we get the simple quadratic equation t^2 +t\cdot 2\cdot h_2 + h_3 which, being quadratic, gives us two (or one, or none) solutions: t_{1,2} = -\frac{h_2}{h_1} \pm \sqrt{(\frac{h_2}{h_1})^2 - \frac{h_3}{h_1}}.

If the expression under the square root is negative the equation got no solution and we can never hit the object with our projectile since it is too slow. If the square root works out to some positive value we got two solutions. Solutions with a negative value for t can be thrown away too, unless you shoot with Tachyon-bullets ;-)

There remains one case to be taken care of: h_1 might be 0 which would result in a division by 0 in the aproach shown above. But actually the case where h_1 is 0 is the mathematically simpler case. The quadratic equation collapses and all that remains is the simple equation t\cdot2\cdot h_2 + h_3 = 0 which of course results in t = -\frac{h_3}{2h_2}. Thanks to David (see comments below) for pointing that out. It got rid of an ugly ‘quick fix’ I used before.

And now in the form of Java code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
	/**
	 * Calculates the point of interception for one object starting at point
	 * <code>a</code> with speed vector <code>v</code> and another object
	 * starting at point <code>b</code> with a speed of <code>s</code>.
	 * 
	 * @see <a
	 *      href="http://jaran.de/goodbits/2011/07/17/calculating-an-intercept-course-to-a-target-with-constant-direction-and-velocity-in-a-2-dimensional-plane/">Calculating
	 *      an intercept course to a target with constant direction and velocity
	 *      (in a 2-dimensional plane)</a>
	 * 
	 * @param a
	 *            start vector of the object to be intercepted
	 * @param v
	 *            speed vector of the object to be intercepted
	 * @param b
	 *            start vector of the intercepting object
	 * @param s
	 *            speed of the intercepting object
	 * @return vector of interception or <code>null</code> if object cannot be
	 *         intercepted or calculation fails
	 * 
	 * @author Jens Seiler
	 */
	public static Point2D calculateInterceptionPoint(final Point2D a, final Point2D v, final Point2D b, final double s) {
		final double ox = a.getX() - b.getX();
		final double oy = a.getY() - b.getY();
 
		final double h1 = v.getX() * v.getX() + v.getY() * v.getY() - s * s;
		final double h2 = ox * v.getX() + oy * v.getY();
		double t;
		if (h1 == 0) { // problem collapses into a simple linear equation 
			t = -(ox * ox + oy * oy) / 2*h2;
		} else { // solve the quadratic equation
			final double minusPHalf = -h2 / h1;
 
			final double discriminant = minusPHalf * minusPHalf - (ox * ox + oy * oy) / h1; // term in brackets is h3
			if (discriminant < 0) { // no (real) solution then...
				return null;
			}
 
			final double root = Math.sqrt(discriminant);
 
			final double t1 = minusPHalf + root;
			final double t2 = minusPHalf - root;
 
			final double tMin = Math.min(t1, t2);
			final double tMax = Math.max(t1, t2);
 
			t = tMin > 0 ? tMin : tMax; // get the smaller of the two times, unless it's negative
			if (t < 0) { // we don't want a solution in the past
				return null;
			}
		}
 
		// calculate the point of interception using the found intercept time and return it
		return new Point2D.Double(a.getX() + t * v.getX(), a.getY() + t * v.getY());
	}
  1. Thanks, Jaran!

    This is exactly what I was looking for – you explain the maths really well (and I can see how it can be extended to 3D relatively simply).

    It’s helped me just code it up in C++.

    David

    • Thanks for your feedback. If you happen to write some piece of code that extends the maths to the 3rd dimension I’d appreciate if you’d posted it here :-)

  2. I started expanding the code to work in 3D dimensions, but my problem was essentially still in a 2D plane so I ended up just using the two relevant components instead. Bits like the magnitude of the vector work out simply but I’m not sure about the calculation of the substitutions yet, hopefully there’s still a way to do it!

    One thing that caught me out is the case where ‘h1′ is zero. You adjust it to be a small number yourself in the code above, but the collision equation actually simplifies because the t^2 term disappears. You just get the linear equation:

    t*2*(ox*vx + oy*vy) + ox^2 + oy^2 = 0
    or
    t = -(ox^2 + oy^2) / (2 * (ox*vx + oy*vy))

    So that may save some processing in some cases – or seems a bit neater at any rate. :)

    • Hey David. Thanks for pointing that out. Of course you are right and I updated my article and the code. Much nicer now! :grin:

  3. niel jonny

    could some one explain what the small “a” and “b” mean and whats their purpose

  4. “a” and “b” are the position vectors that point from the origin of your coordinate system to the location of the object to be intercepted (A) and your “interceptor gun” (B).

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>