5
$\begingroup$

LATER EDIT:

I managed to find the errors in my equations below. It was a sign mistake on one of the terms (- instead of +). Having corrected that, the method which I describe below WORKS, but DON'T USE IT ::- D. My method is convoluted and prone to mistakes (as I proved, haha). The 2 answers below offer much better choices. hardmath found a few of my mistakes and provided an alternative way of obtaining X2 and Y2 using the same system of formulas I used.

On the other hand, joriki provided an alternate solution which is VERY efficient in terms of number of calculations which need to be done each frame. Eventually, I completely dropped my approach and will use his solution.

Thank you hardmath and joriki, and, by all means, Math @ Stack ::- D. You people rule! I humbly thank you for helping a programmer in distress!

ORIGINAL POST:

Hi ::- D. I'm working on a (Flash) game and I have a weapon from which a projectile departs. The projectile travels along a line. I have the slope of the line as well as the origin (1 point). I want to calculate, depending on the Distance, where should I draw the projectile, frame by frame. The distance increases with a certain quantity each frame, as the projectile travels along the line.

I have tried my best to solve this and this is what I did so far. I would not mind if you know a simpler way, but I would very much appreciate it if you would tell me why my method doesn't work (the coordinates I'm getting are very chaotic).

I used these equations to build a system:

http://www.analyzemath.com/Calculators/TwoPointsCalculator.html

d = sqrt [ (x1 -x2)^ + (y1 - y2)^ ]

m = (y2 - y1) / (x2 - x1)

I took out y2:

y2 = m * x2 - m * x1 + y1

From that equation, I know everything except x2. x1, y1 and m are all known. I'm out to find x2 and y2 which are the coordinates of my desired point.

I removed the radical by squaring the first equation and also breaking (solving) the paranthesis. I should mention it's been a very long time since I did any math so please excuse the lack of correct terminology. Also, I'm unfamiliar with how to produce a fast MathJaX of the equations, but I think they're simple enough to be written normally. ^ - means square. I used some extra paranthesis to clear it up.

d^ = x1^ - (2 * x2 * x1) + x2^ + y1^ - (2 * y2 * y1) + y2 ^

Ok so I also know who d is. Now, I took y2 and substituted it in the above equation. This is what resulted:

d^ = x1^ - 2 * x2 * x1  + x2^ + y1^ - 2 * y1 * (m * x2 + K) + (m * x2 +K) ^

Where K is that part which I can calculate from the above y2 equation: y2 = m* x2 -m * x1 + y1

So now I got an equation where I know everything except x2. I reduced this equation to a quadratic equation. The final form (I solved the squared parenthesis above as well) is:

x2^ ( - 1 - m^) + x2 (2 * x1   + 2 *  y1 * m - 2 * m * K) + d^ - x1^ - y1^ + 2 * y1 * K - K ^ = 0

Looks scary doesn't it? laugh.

This seems to be correct so far. Because we're talking about a line, slope and distance, it's obvious that there can be TWO points which are of distance D from my Origin (x1, y1). So I solve the quadratic equation in order to find x2-1 and x2-2 which I can then take to my first equation and get y2-1 and y2-2. So, I moved to solve the quadratic equation. First, I found a, b and c.

a = -1 - m^
b = (2 * x1   + 2 *  y1 * m - 2 * m * K) 
c = d^ -  x1^ - y1^  + 2 * y1 * K - K ^ 

And now, I found the 2 roots:

x2 = (-b + sqrt (b^ - 4ac)) / 2a
x2 = (-b - sqrt (b^ - 4ac)) / 2a

Then, I found the two y2 points. And that's it ::- D.

It doesn't work laugh......... I worked for hours this morning, flexing whatever pathetic math muscles I got left and I worked all this far to end up with:

(x=1509141.9643610462, y=20806970.245399687)

This, in a case where the origin is at 200, 250 and the distance is 1 and the slope is 2.2 or -0.7 or whatever.......

Sometimes, I even get NaN (that is, Not A Number, invalid value in ActionScript 3). So the values I'm getting are DEFINITELY not related to my origin.

A point of interest however: for slope = 1.380657160570366, my projectile ACTUALLY SEEMS TO WORK, as in, it appears a bit TOO far from the Origin (about 50 pixels), but it DOES MOVE along the correct line, albeit, strangely, it ACCELERATES, even though I never increase its speed, I simply increase the distance:

_ProjectileDistance += _ProjectileSpeed;
var newCoords: Point = GetPointAlongLine(weaponRootPointX, weaponRootPointY, _ProjectileDistance, _ProjectileSlope);
Projectile.x = newCoords.x;
Projectile.y = newCoords.y;

And for those who know programming as well, here is what all I said looks like in code:

  var a: Number = - 1 - slope * slope;
  var b: Number = 2 * x1 + 2 * y1 * slope - 2 * slope * y2KnownPart;
  var c: Number = distance*distance - x1*x1 - y1*y1 - 2 * y1 * y2KnownPart - y2KnownPart*y2KnownPart;

  var x2Root1: Number = (- b + Math.sqrt(b*b - 4 * a * c)) / (2 * a);
  var x2Root2: Number = (- b - Math.sqrt(b*b - 4 * a * c)) / (2 * a);
  var y2Root1: Number = slope * x2Root1 + y2KnownPart;
  var y2Root2: Number = slope * x2Root2 + y2KnownPart;

Sorry for the long post ::- D. I hope somebody will have the patience to read until this line ::- D. If you did, know that you're doing it for a good cause ::- D. My games are free, so is my software, just look here ::- D https://sourceforge.net/users/echysttas

2 Answers 2

7

Your approach is way too complicated -- I won't take the time to find where you made a mistake, but instead show how it can be done much simpler:

The distance $d$ is the hypotenuse of a right triangle formed by the two axis-parallel segments of lengths $\Delta y := y_2-y_1$ and $\Delta x := x_2-x_1$, much like in this picture I found on the web:

enter image description here
(source: sternenwind.ch)

The slope $m$ is $\Delta y/\Delta x$, which is the tangent of the angle $\alpha$ between the line and the $x$-axis: $m=\tan\alpha$. The increments $\Delta x$ and $\Delta y$ are given by the cosine and sine, respectively, of that angle times the hypotenuse, so all you have to do is calculate $\alpha=\arctan m$ and then $\Delta x = d\cos \alpha$ and $\Delta y=d\sin\alpha$. If your calculations are time-critical, you can get by with a couple fewer transcendental operations, but this is the most straightforward way.

Edit: Actually, you'll want to use the atan2 function that a lot of programming environments have, with arguments $\Delta y$ and $\Delta x$, since you lose a sign when you form $m=\Delta y/\Delta x$, i.e. you no longer know which direction along the line the projectile is travelling.

Edit: hardmath's answer is roughly what I had in mind when I said "If your calculations are time-critical, you can get by with a couple fewer transcendental operations". Note, however, that in both answers the transcendental operations have to be performed only once (a square root in hardmath's case, three trigonometric functions in my case), and then calculating the projectile's position for each $d$ only involves multiplications.

  • 0
    Hi and thanks for answering ::- ). So, Delta X and Delta Y are the points I'm interested in, right? Then why do you say I should use atan2 (yes, I have it in AS3)? Only to find direction? Also, I do this calculation at each frame (30 times / second). The slope and distance, x1 and y1 are given. All the rest, I calculate each time, every frame. What do you mean by 'only multiplications'?2011-03-06
  • 2
    @Axonn: I defined $\Delta x$ and $\Delta y$ in the answer. They're not the points you're looking for; they're just what I defined them to be. I also wrote why you should use atan2 in the answer -- not "only to find direction", but for the reason I gave in the answer. By "only multiplications" I mean that once you've calculated $\cos\alpha$ and $\sin\alpha$ once and for all, then all you need to do per frame is the multiplications in $\Delta x = d\cos\alpha$ and $\Delta y = d\sin\alpha$, and all calls to transcendental functions are executed just once and not per frame.2011-03-06
  • 0
    Oh sorry! My mistake. My memory got reset after the drawing *laugh* so I forgot that you already told me what Delta X and Delta Y are. I didn't understand what you meant by losing the sign when I do Delta Y / Delta X, that's why I asked about atan2. Sorry, perhaps I'm missing some basic math notions here ::- (. Also, I can't call atan2 with DeltaX / DeltaY because I don't have them. You defined them as y2 - y1 but I don't have y2. I do understand how I can find them with your method: I can find angle Alfa as atan(m) (because I got m)and then I use d cos alfa to find DeltaX, using that I get X22011-03-06
  • 2
    @Axonn: Sorry, you're right, I was being quite unclear. I didn't mean $\Delta y$ and $\Delta x$ in the calculation of the current point of the projectile, but in your initial calculation of the slope. I presume that at some point you must calculate the slope from something that contains information about the direction the weapon is pointing -- either you have the angle $\alpha$ at which the weapon is inclined, in which case you don't need the slope or the $\arctan$, or you have a point towards which the weapon is pointing, and I meant the $\Delta x$ and $\Delta y$ with respect to that point.2011-03-06
  • 2
    @Axonn: Put differently: If you have only the slope, you're missing part of the information about where the weapon was pointing when the projectile was fired. Presumably you have that missing information somewhere; at least you should, since it obviously makes a difference whether the weapon fires forwards or backwards :-) Also, this is not specific to my answer -- any answer based only on $m$ will necessarily give an ambiguous answer defined only up to a sign -- as does hardmath's answer.2011-03-06
  • 0
    Yes, I do have the slope (m). I have a point towards which the gun is pointing, so I just use that to get my m. Anyway, I used your idea and it worked! I found DX and DY and then got X2 and Y2from them. I did like so: var alfa: Number = Math.atan(slope); var dx: Number = distance * Math.cos(alfa); var dy: Number = distance * Math.sin(alfa); ret.x = x1 + dx; ret.y = y1 + dy; **only problem** is that once the slope changes sign, the projectile travels in the opposite direction, but that's a ridiculous 'if' instruction that I will install right now ::- D. Thank you!EDIT: actually it's a simple if2011-03-06
  • 2
    @Axonn: I think you missed the point about the atan2. Calculating the slope from the point towards which the gun is pointing, then getting an angle from that with atan and then using an if statement to get the sign right is again unnecessarily complicated. You can avoid all that by never calculating the slope, but just directly calculating $\alpha$ from the point you have towards which the gun is pointing, using atan2($\Delta y$,$\Delta x$), where $\Delta y$ and $\Delta x$ are calculated using the point towards which the weapon is pointing as the point $(x_2,y_2)$ on the line.2011-03-06
  • 0
    Right @ the m issue. I figured that's why I got a quadratic equation after all ::- D. 2 points are valid, depending upon the direction. The problem I'm facing now is that I can't yet find how to convert the slope to a proper angle. When it changes sign, so does my direction, and doing Math.abs won't help because I think it's a quadrant issue here ::- D. EDIT: going to try it with atan2 now ::- D.2011-03-06
  • 0
    Yes, your atan2 thingy worked ::- D. This way, I don't even need the slope any more. I just need to memorize 2 initial points. The weapon's pivot point and the whatever-its-pointing at, which is simply the mouse' location on the Stage ::- D. Quite simple. It works aaaand, indeed, I must calculate atan2 only once, after that, I just use alfa ::- D. Thank you very much ::- D.2011-03-06
  • 2
    @Axonn: You're welcome. If you use atan2 once and then use $\alpha$ in each frame, you're still unnecessarily recalculating the sine and cosine, which are the same for each frame. You should calculate those once, too, and then just do the multiplications with $d$ in each frame. Multiplications are a lot faster than evaluations of transcendental functions.2011-03-06
  • 0
    D'uh, right ::- D. Thanks for the heads up, haha. I got a bit too enthusiastic that it's working ::-D. Now I'm going to try hardmath's solution and to see what I got messed up in my original convoluted approach. I really need to practice a bit more with all this stuff. I'm going to stumble upon more and more math and it's about jolly time I study more of it ::- D. Thank you for all the effort!2011-03-06
  • 0
    Hah, I found my error and fixed it. Now I got this problem solved in 3 ways. I edited my original post. I will go with your solution ::- D.2011-03-06
2

I think you missed a chance to keep the problem simple. Since m, x1, y1, d are known, you are asking to solve two equations for the two unknowns x2, y2:

$$ (x2 - x1)^2 + (y2 - y1)^2 = d^2 $$

$$ (y2 - y1) / (x2 - x1) = m $$

But this is simpler to state in terms of unknowns u = x2 - x1 and v = y2 - y1. Once you've found u, v it is trivial to get x2, y2 by adding x1, y1 respectively. So consider the two equations:

$$ u^2 + v^2 = d^2 $$

$$ v/u = m $$

Now $v = m u$ from the 2nd eqn. can be substituted into the 1st eqn. giving us simply:

$$ (m^2 + 1)u^2 = d^2 $$

whose solution is obviously (assuming d > 0):

$$ u = \pm d/ \sqrt{m^2 + 1} $$

and correspondingly:

$$ v = \pm m d/ \sqrt{m^2 + 1} $$

where the same choice of plus-or-minus sign must be made in both formulas.

Out of an abundance of caution one should substitute these back into the equations for u, v above, to make sure we haven't introduced artifact roots (we have not). Geometrically the picture is a line through the origin intersecting the circle of radius d at a point (u,v) along a line of slope m.

Finally, add (x1,y1) to (u,v) to get (x2,y2) and you are done. Presumably there's some information about the direction you are traveling that tells which of the two solutions is the one you want...

  • 0
    LOL, nice thinking hardmath ::- D. Thank you! Still, would you mind just looking at what I did and explain to me where I messed up? ::- (2011-03-06
  • 1
    @Axonn: I see that the quadratic you get for x2 has a leading coefficient `a = -1 - m`. But that coefficient should involve $m^2$ since the leading term comes from squaring `m * x2 + K` in the equation just above that.2011-03-06
  • 0
    Oh yes you're right! I also found 2 other mistakes which I corrected. But do you think that the reasoning was ok? If I fix the other mistakes could it work? Eventually I'm going to apply your or joriki's solution, but I'm wondering if my way *could* have worked.2011-03-06
  • 2
    @Axonn: Yes, I think in principle your approach could have worked. But if you want to do this sort of thing in the future, it would be good to understand why it was so unnecessarily complicated and how you could have avoided that. You only had to solve a quadratic equation because you used inconvenient variables. By introducing $u$, $v$ / $\Delta x$, $\Delta y$, you could have avoided all that, even without any of the specifics of hardmath's or my solution.2011-03-06
  • 0
    I wanted to try and have a go at this problem by myself before coming here ::- D. Try to solve as much as possible. Since it's been 10 years since I last did any math problem-solving, it's a miracle for me that I made it this far *laugh*. I'm not even ashamed I didn't see the nice simplification hardmath found. I hate that on this website I can't vote for 2 answers at once ::- D. I like both solutions. Hardmath solved my silliness while you provided an alternative way, using much less calculus.2011-03-06
  • 1
    @Axonn: I didn't mean to imply that you shouldn't have tried to solve it yourself first (quite to the contrary :-) -- I was just trying to say that you can learn something from our answers beyond this specific calculation, since they can tell you something about how to choose variables conveniently to simplify your calculations.2011-03-06
  • 1
    @joriki: +1 Axonn's approach can no doubt be made to work, but if you have to hack your way through an underbrush of formulas and substitutions, the only thing that gives any confidence in having found the "last mistake" is going through the calculations more than once and getting the same result. It gives much more confidence if the path can be stripped down enough that one can check the solution from end to end.2011-03-06
  • 0
    I applied your solution as well, hardmath, and it indeed worked ::- D. Now the last thing on my plate for this particular topic is to hack my way through the underbrush of formulas LOL, just to see where I messed it up. If hardmath's way worked, it's definitely a mistake in there somewhere ::- D. Thank you guys! You shall be remembered ::- D.2011-03-06
  • 0
    I eventually found my error as well and edited my original post. Thank you a lot for the simplified solution hardmath ::- ).2011-03-06
  • 0
    @hardmath (I was looking at this problem today and came across this post) I was just thinking about how you say v/u = m, and how that means you must be assuming u is nonzero, so by u^2+v^2 = d^2, d can't be 0, so you don't really need to say "assuming d>0". maybe there should be a comment about the value of u at some point?2015-12-02
  • 0
    @alphagamma: Sure, $u = x_2 - x_1$, and from the original problem statement we should take $x_2 \neq x_1$. Thus $u$ (or $\Delta x$ if you prefer) should be nonzero. The picture in joriki's Answer may be helpful to see why (in the game programming context) two distinct points are intended.2015-12-02
  • 0
    I guess from the game programmer's perspective, he should put in a special case for when u == 0, but v != 0.2015-12-02
  • 0
    i.e., if u==0, then x2 = x1, y2=y1+d or y2=y1-d or something like that2015-12-02