{"id":41,"date":"2011-07-17T14:13:18","date_gmt":"2011-07-17T12:13:18","guid":{"rendered":"http:\/\/jaran.de\/goodbits\/?p=41"},"modified":"2016-02-14T12:33:31","modified_gmt":"2016-02-14T11:33:31","slug":"calculating-an-intercept-course-to-a-target-with-constant-direction-and-velocity-in-a-2-dimensional-plane","status":"publish","type":"post","link":"http:\/\/jaran.de\/goodbits\/2011\/07\/17\/calculating-an-intercept-course-to-a-target-with-constant-direction-and-velocity-in-a-2-dimensional-plane\/","title":{"rendered":"Calculating an intercept course to a target with constant direction and velocity (in a 2-dimensional plane)"},"content":{"rendered":"

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:
\n\"diagram<\/p>\n

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}?<\/p>\n

Now let us derive the necessary maths and put it into code… (requires understanding of vectors and quadratic equations)<\/p>\n

<\/p>\n

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.<\/p>\n

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:<\/p>\n

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:<\/p>\n

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<\/a> in one fell swoop.<\/p>\n

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<\/a> 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}}.<\/p>\n

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<\/a> \ud83d\ude09<\/p>\n

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.<\/p>\n

And now in the form of Java code:<\/p>\n

 \r\n\t\/**\r\n\t * Calculates the point of interception for one object starting at point\r\n\t * a<\/code> with speed vector v<\/code> and another object\r\n\t * starting at point b<\/code> with a speed of s<\/code>.\r\n\t * \r\n\t * @see Calculating\r\n\t *      an intercept course to a target with constant direction and velocity\r\n\t *      (in a 2-dimensional plane)<\/a>\r\n\t * \r\n\t * @param a\r\n\t *            start vector of the object to be intercepted\r\n\t * @param v\r\n\t *            speed vector of the object to be intercepted\r\n\t * @param b\r\n\t *            start vector of the intercepting object\r\n\t * @param s\r\n\t *            speed of the intercepting object\r\n\t * @return vector of interception or null<\/code> if object cannot be\r\n\t *         intercepted or calculation fails\r\n\t * \r\n\t * @author Jens Seiler\r\n\t *\/\r\n\tpublic static Point2D calculateInterceptionPoint(final Point2D a, final Point2D v, final Point2D b, final double s) {\r\n\t\tfinal double ox = a.getX() - b.getX();\r\n\t\tfinal double oy = a.getY() - b.getY();\r\n\t\t\r\n\t\tfinal double h1 = v.getX() * v.getX() + v.getY() * v.getY() - s * s;\r\n\t\tfinal double h2 = ox * v.getX() + oy * v.getY();\r\n\t\tdouble t;\r\n\t\tif (h1 == 0) { \/\/ problem collapses into a simple linear equation \r\n\t\t\tt = -(ox * ox + oy * oy) \/ (2*h2);\r\n\t\t} else { \/\/ solve the quadratic equation\r\n\t\t\tfinal double minusPHalf = -h2 \/ h1;\r\n\t\t\t \r\n\t\t\tfinal double discriminant = minusPHalf * minusPHalf - (ox * ox + oy * oy) \/ h1; \/\/ term in brackets is h3\r\n\t\t\tif (discriminant < 0) { \/\/ no (real) solution then...\r\n\t\t\t\treturn null;\r\n\t\t\t}\r\n\t\t \r\n\t\t\tfinal double root = Math.sqrt(discriminant);\r\n\t\t \r\n\t\t\tfinal double t1 = minusPHalf + root;\r\n\t\t\tfinal double t2 = minusPHalf - root;\r\n\t\t \r\n\t\t\tfinal double tMin = Math.min(t1, t2);\r\n\t\t\tfinal double tMax = Math.max(t1, t2);\r\n\t\t \r\n\t\t\tt = tMin > 0 ? tMin : tMax; \/\/ get the smaller of the two times, unless it's negative\r\n\t\t\tif (t < 0) { \/\/ we don't want a solution in the past\r\n\t\t\t\treturn null;\r\n\t\t\t}\r\n\t\t}\r\n\t \r\n\t\t\/\/ calculate the point of interception using the found intercept time and return it\r\n\t\treturn new Point2D.Double(a.getX() + t * v.getX(), a.getY() + t * v.getY());\r\n\t}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
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: Let’s …<\/p>\n
Read more »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0},"categories":[5,8,9],"tags":[],"_links":{"self":[{"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/posts\/41"}],"collection":[{"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/comments?post=41"}],"version-history":[{"count":43,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/posts\/41\/revisions"}],"predecessor-version":[{"id":475,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/posts\/41\/revisions\/475"}],"wp:attachment":[{"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/media?parent=41"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/categories?post=41"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/jaran.de\/goodbits\/wp-json\/wp\/v2\/tags?post=41"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}