# I Made an Equation but I Cannot Solve It

## Recommended Posts

L. Spiro    25615
Initially I was a year advanced in math back in school, but by the time I reached grade 10, Algebra II, my interest in all school subjects was so low that I simply did no homework, failed all classes (particularly, I failed Algebra II 3 times), and finally dropped out of high school in the middle of grade 12.

It was not until I started making video games seriously (and professionally) that I found a reason for any of the math they were trying to put into my head.
Luckily, due to the fact that I am not an idiot (in grade 9 when I actually did do my homework, I got a 100% in Geometry, having never missed a single answer on any homework, test or final; something never done before in my school’s history), I was able to catch up on most of all that math on my own, but finally I have created an equation that suits a physical model I also designed, but I am still not at the mathematical level needed to actually solve it.

Now I am the CTO of a game company in Tokyo and I need this solved (that is, better than my guess-and-check iterative method, which does work, but is too slow).

Tp = target position.
Tv = target velocity.
Ta = target acceleration.
Bp = bullet position (when originally fired).
Bs = bullet speed.

length² = A²+B²+C² in 3D.
length²((Tp+Tvt+½×Tat²)-Bp) = (Bs*Bs)

or:
length²((Tp+Tvt+½×Tat²)-Bp)-(Bs*Bs) = 0
Solve for t (time)

The keen observer can see a target moving along a trajectory and a bullet moving as well.
But this is not how to intercept the bullet with the target. As you can see, the direction of the bullet does not matter.
Bullet velocity is not a factor, it is the bullet speed.

This will ultimately be used in the game engine being developed in my company to allow bots to aim at targets.
Here, however, I am not interested in aiming a bot at a target; this equation requires that you solve for t, while the actual direction of the bullet to be fired is unknown.

I will also include this in an upcoming article on game AI and I will give credits to whoever can solve this (please show your work so that I can include an explanation of each step in the article).

Note: I already know how to solve this using iterative methods in C++. I already have bots that are devastatingly accurate (you have a 100% chance of being hit unless you manually change your own trajectory while the bullet is traveling). But when there are too many bots, the engine slows unacceptably. This equation correctly describes the same thing I am performing iteratively, so by solving for t in the equations above I hope I can increase the efficiency of the bot AI dramatically.

Thank you,
L. Spiro

##### Share on other sites
johnstanp    267
The "dimensions" do not match:
length²( Tp ) = L²( squared distance )
Bs * Bs = L²inverse(T²) ( squared velocity ). This term should be multiplied by another one having the dimensions of a squared time.

##### Share on other sites
L. Spiro    25615
I believe the dimensions do match.

length²() takes a 3D vector and returns a scalar value.
Bs is a scalar value, so Bs² is as well.

Think of it this way:
Bv = bullet velocity (3D vector).
length²((Tp+Tvt+½×Tat²)-Bp)-length²(Bv) = 0

Now Bv is a 3D vector just like all the other variables, and like the rest it goes through the length²() function, which results in a single scalar.

Since length²(Bv) basically throws away the directional component of the velocity, it is equivalent to Bs*Bs (where Bs—speed—is a single scalar).
So the simplified and faster form of the equation is what I gave above.

However, since length²() is a function that changes the dimensions, perhaps this equation cannot be solved in this form?

I can see how to rewrite it such that we can remove the length²() function and instead repeat the equation 3 times, once for each of the X, Y, and Z scalars on a 3D vector, but solving for that would give me 3 different t (time) values and I don’t see how that can be useful.

Here is the expanded form:
(((Tpx+Tvxt+½×Taxt²)-Bpx)² + ((Tpy+Tvyt+½×Tayt²)-Bpy)² + ((Tpz+Tvzt+½×Tazt²)-Bpz)²) - (Bs*Bs) = 0

To me that looks even harder to solve (though it is exactly the same thing) but to a mathematical person perhaps it is easier.

I hope to include a solution to this equation in an upcoming article I will be writing for this site, and I will give credit in the article to whoever can solve this (showing each step for how it is solved). I will also provide code for solving it.

Thank you,
L. Spiro

##### Share on other sites
Brother Bob    10344
Quote:
 Original post by YogurtEmperorI believe the dimensions do match.length²() takes a 3D vector and returns a scalar value.Bs is a scalar value, so Bs² is as well.

They are both scalars, but have different units, which is what johnstanp means with dimension. It's not whether they are scalars or vectors.

Your first post had this equation, so let's analyze the unit of each term: length2((Tp+Tvt+1/2*Tat2)-Bp) = (Bs*Bs)

Each component of Tp have unit m (meter, to get some real unit instead of some abstract length unit).

Each component of Tv have unit m/s, and t has unit s, so Tvt has unit m/s*s=m.
1/2 has unit 1 (no unit), each component of Ta have unit m/s2, and t has unit s, so each component of 1/2*Tat2 has unit 1*m/s2*s2=m.

Thus, the unit for all three terms in the inner summation all have unit m, and can be added.

Each component of Bp has unit m, and can thus be subtracted from the inner summation, which also had unit m.

length2 then calculates the squared length of the vector, and has unit m2.

Bs has unit m/s, so Bs*Bs has unit m2/s2.

The left hand side has unit m2, but the right hand side has unit m2/s2, and they can never be equal, because you're comparing values with different units. Basically, you're asking if x meter is equal to y meters per second. It doesn't make sense: even if x and y happens to have the same scalar value, they have different units.

##### Share on other sites
L. Spiro    25615
Whoops, I made a mistake when I rewrote my equation (before I posted it here it was in another format, which was correct).

It was supposed to be:
length²((Tp+Tvt+½×Tat²)-Bp)-(Bst*Bst) = 0

Or:
(((Tpx+Tvxt+½×Taxt²)-Bpx)² + ((Tpy+Tvyt+½×Tayt²)-Bpy)² + ((Tpz+Tvzt+½×Tazt²)-Bpz)²) - Bst² = 0

Naturally, speed multiplied by time (then squared) was my intent. Does this fix the dimension problem?
I am pretty sure this accurately reflects my concept, and I know that my concept is correct and works.

Considering my explained self-taught mathematical background, it is reasonable for me not to understand his terminology (how “dimensions” apply to math are obviously not how they apply to vectors), and I felt I responded cordially, taking into account “I might not know exactly what he means so I should explain how I think it is correct directly and without sounding as though I am arguing,” so was a drop to my “user rating” really necessary?
Especially when this is for a GameDev article (in addition to my work), meaning something I plan to give back to the community…

With my hotfix, is the dimensionality problem solved, and can this equation be solved for t?

L. Spiro

##### Share on other sites
Brother Bob    10344
Quote:
 Original post by YogurtEmperorNaturally, speed multiplied by time (then squared) was my intent. Does this fix the dimension problem?I am pretty sure this accurately reflects my concept, and I know that my concept is correct and works.

Yes, units match now; they are m2/s2 on both sides.

Quote:
 Original post by YogurtEmperorConsidering my explained self-taught mathematical background, it is reasonable for me not to understand his terminology (how “dimensions” apply to math are obviously not how they apply to vectors), and I felt I responded cordially, taking into account “I might not know exactly what he means so I should explain how I think it is correct directly and without sounding as though I am arguing,” so was a drop to my “user rating” really necessary?Especially when this is for a GameDev article (in addition to my work), meaning something I plan to give back to the community…

Individual ratings are not really relevant; only on average does it have a sensible meaning. You cannot know where ratings are coming from either, it may not even be this thread.

Terminology is something that can be different sometimes, especially between fields. Dimension is a term that can be used both for describing the size of vectors, or refer to unit of values. If you're coming from a field (or self-taught) where dimension is not used to denote unit, then of course it may be confusing. Personally, with what I think you thought dimension meant in johnstanp's context (length of vector), then of course your response was reasonable. I see nothing wrong with that.

Quote:
 Original post by YogurtEmperorWith my hotfix, is the dimensionality problem solved, and can this equation be solved for t?

Yes, it should be possible to find an analytical solution. Try expand the left hand side in terms of t, and you should end up with a normal second degree polynomial of t, for which there are trivial analytical solutions.

##### Share on other sites
Brother Bob    10344
Actually, you should get a fourth order polynomial of t if you expand it, so the analytical solution may not be so trivial after all, sorry. It may be possible to simplify it though, but I personally don't have the option to look into it at the moment.

##### Share on other sites
sprite_hound    461
Hmm. I get a second order polynomial, but I could well be going wrong somewhere:

(Tpx + Tvxt + Taxt^2/2 - Bpx)^2 + (Tpy + Tvy + Tayt^2/2 - Bpy)^2 + (Tpz + Tvzt + Tazt^2/2 - Bpz)^2 - (Bsx + Bsy + Bsz)^2t^2 = 0

(Tpx^2 + Tvx^2t^2 + Tax^2Tt^4/4 - Bpx^2) + (Tpy^2 + Tvy^2t^2 + Tay^2t^4/4 - Bpy^2) + (Tpz^2 + Tvz^2t^2 + Taz^2t^4/4 - Bpz^2) - (Bsx^2 + Bsy^2 + Bsz^2)t^2 = 0

(Tpx^2 + Tpy^2 + Tpz^2) - (Bpx^2 + Bpy^2 + Bpz^2) + t^2(Tvx^2 + Tvy^2 + Tvz^2 - (Bsx^2 + Bsy^2 + Bsz^2)) + t^4((Tax^2 + Tay^2 + Taz^2) / 4) = 0

Tp^2 - Bp^2 + t^2(Tv^2-Bs^2) + t^4(Ta^2 / 4) = 0

t^2(Ta / 2) + t(Tv-Bs) + Tp - Bp = 0

Edit: corrected, hopefully (I think it should be Bs^2t^2 in your last equation...)

Edit2: Actually, this is completely wrong...

[Edited by - sprite_hound on November 15, 2010 1:27:33 PM]

##### Share on other sites
johnstanp    267
The equation should actually be:
length²((Tp+Tvt+½×Tat²)-Bp) = (Bs*t)²

I didn't pay attention to sprite_hound[/edit]

##### Share on other sites
Brother Bob    10344
You have a fourth order polynomial of t; your second to fourth lines have t4 terms. I also said it may be possible to simplify it, which you demonstrated was possible.

##### Share on other sites
sprite_hound    461
@johnstanp: I may still have been posting / editing, since I only realised afterwards.

@BrotherBob: Ah, yeah. :)

##### Share on other sites
L. Spiro    25615
Well it is past midnight here and I have already had a few drinks so I am not in any state to analyse the math in detail now, but a few things I can see that I want to question or clarify.

#1:
Quote:
 Original post by johnstanpThe equation should actually be:length²((Tp+Tvt+½×Tat²)-Bp) = (Bs*t)²

Is this the same as length²((Tp+Tvt+½×Tat²)-Bp)-(Bst*Bst) = 0, or did I miss a detail?
I originally started with your form (well almost) but my basic knowledge of math lead me to put all of the terms on the left side and 0 on the right, but I may be wrong in doing so. Or I missed something you changed.

#2:
Quote:
 Original post by sprite_houndt^2(Ta / 2) + t(Tv-Bs) + Tp - Bp = 0

So this is the fully simplified version of the whole thing?
After confirmation, I was originally going to say that I wanted to wait until I had a clear head to try to visualize this model in my head and see if it models exactly what my original concept was (which I will explain in the article if you haven’t seen how it is meant to work yet (actually I will explain it in the article even if you have)) and see if I could solve for t on my own from there.
But two things:
- A: (Tv-Bs). How does that work? Tv is a 3D vector and Bs is a single scalar. I could do a component-wise subtraction, but I want to verify—is this really what you meant? “Target Velocity” Tv and “Bullet Speed” Bs may have been cause for confusion; if you treat these both as 3D vectors I can see how you would reach this conclusion, but since one of them is actually scalar I want to be sure this is not a conclusion reached in confusion.
- B: For the article, I want to explain what the purpose of each step is, just like in “Real-Time Collision Detection” by Christer Ericson. Can you include a comment that just says what each step is doing? Of course I am not going to try to sound like a bad-ass in the article who knows how to solve these kinds of equations; I will make it clear that I myself am not mathematically inclined enough to solve these kinds of equations and that I relied on a named 3rd party.

Thank you,
L. Spiro

##### Share on other sites
Steve132    433
I've solved something similar to this before, and yes, it is a 4th order polynomial. There are a number of ways to solve it, but all the ones I used involve some kind of iterative relaxation (like newtons method and other solutions).

However, a google search reveals the following:

http://en.wikipedia.org/wiki/Quartic_function#The_general_case.2C_along_Ferrari.27s_lines

So there's that. Good luck.

##### Share on other sites
Steve132    433
Quote:
 Original post by sprite_houndHmm. I get a second order polynomial, but I could well be going wrong somewhere:Tp^2 - Bp^2 + t^2(Tv^2-Bs^2) + t^4(Ta^2 / 4) = 0t^2(Ta / 2) + t(Tv-Bs) + Tp - Bp = 0

I'm pretty sure this step is invalid. Unless I'm mistaken, there is no proof that the roots of (a^2 t^4+b^2 t^2+c^2) are the same as the roots of (a t^2 + b t + c)

##### Share on other sites
Steve132    433
Sorry to post so many times... One thing I wanted to mention: Guess and check is a pretty terrible "iterative solution." If you want to solve this, there's no reason an iterative solver has to be slow. Hell, most matrix decompositions are "iterative" and yet you can find a solution for a smallish matrix in very very short time because the algorithms are well understood and well optimized.

Now that you have the closed form, try implementing a real iterative root finder for a 4th order polynomial and I imagine the speed will be MUCH greater then whatever you are currently doing, despite the fact that its not a closed form solution.

##### Share on other sites
sprite_hound    461

Quote:
 #2:- A: (Tv-Bs). How does that work? Tv is a 3D vector and Bs is a single scalar. I could do a component-wise subtraction, but I want to verify—is this really what you meant? “Target Velocity” Tv and “Bullet Speed” Bs may have been cause for confusion; if you treat these both as 3D vectors I can see how you would reach this conclusion, but since one of them is actually scalar I want to be sure this is not a conclusion reached in confusion.

Yeah, I was assuming it was a 3d vector. I actually now think my whole working is very wrong due to forgetting how to multiply out brackets. [embarrass]

[Edited by - sprite_hound on November 15, 2010 1:35:51 PM]

##### Share on other sites
johnstanp    267
Quote:
 Original post by YogurtEmperorIs this the same as length²((Tp+Tvt+½×Tat²)-Bp)-(Bst*Bst) = 0, or did I miss a detail?

f²(x)-y²=0 is not equivalent to f²(x-y)=0
To prove it: simply take a counter example.

Let's f(x)=x;
x²-y²=0 is equivalent to (x-y)²=0?
The solutions of x²-y²=0 are x=y or x=-y
The unique solution of (x-y)²=0 is x=y.

It is not forbidden to do the following:
A := complex expression
B := another complex expression

A²-B²=0 <=> (A-B)(A+B)=0 <=> A=B OR A=-B
so lenth²(X) = Y² is equivalent to (length(X)-Y)(length(X)+Y)=0
But length(X) involves a square root. So it's easier working with length²(X)-Y²=0. But it introduces a solution that will have to be rejected when Y!=0 since length(X) cannot be negative.

As already said, you should have a 4th order polynomial at the left side (or whatever side you chose to put all the non zero terms) when developing your equation. There is an analytical solution to such a problem: actually there are analytical solutions up to the fourth order if I remember well.
Quartic_function

Good work! :-)

[Edited by - johnstanp on November 15, 2010 1:13:45 PM]

##### Share on other sites
ZaHgO    146

http://mathworld.wolfram.com/QuarticEquation.html

but currently I have no time to solve it, maybe tonight, if no one else has by then.

##### Share on other sites
L. Spiro    25615
Quote:
 Original post by johnstanpf²(x)-y²=0 is not equivalent to f²(x-y)=0

I’m not rearranging the terms that way.
length²((Tp+Tvt+½×Tat²)-Bp) = Bst² // If these two terms are equal (this is the form you said the equation should be), then
length²((Tp+Tvt+½×Tat²)-Bp)-Bst² = 0 // Subtracting them results in 0.

I do not know enough about Algebra II to know why you put x and y together when you moved the y term to the left. From my primitive understanding, I am not doing this.

I do understand the Newton–Raphson method; I have used it before.
If I could rewrite this so that the Newton–Raphson method could be used here, yes, that would be a much faster iterative method. And even acceptable in terms of performance I think.
But I don’t know how to get the equation there, and frankly I am not sure I could solve it even in the form of a Quartic function; as for that, I will see once it gets into that form. I want to give it a shot for the challenge, but I will not hold a grudge if someone shows the solution all the way down to “t = blah blah blah”.
If multiple solutions are posted (Newton–Raphson method and the Quartic function) I will post both methods in the article and give credits to both people.

Regards,
L. Spiro

##### Share on other sites
ZaHgO    146
Length ^ 2 ( Tp + (Tv * t) + ((1 / 2) * Ta * (t ^ 2)) - Bp) - (Bs^2 * (t ^ 2)) = 0
-------------------------------
(Tpx + (Tvx * t) + ((1/2) * Tax * t^2) - Bpx) ^ 2 + (Tpy + (Tvy * t) + ((1/2) * Tay * t^2) - Bpy) ^ 2 + (Tpz + (Tvz * t) + ((1/2) * Taz * t^2) - Bpz) ^ 2 - (Bs^2 * t^2) = 0
-------------------------------
Tpx^2 + (Tvx^2 * t^2) + ((1/4) * Tax^2 * t^4) - Bpx^2 + (2 * Tpx * Tvx * t) + (Tpx * Tax * t^2) - (2 * Tpx * Bpx) + (Tvx * Tax * t^3) - (2 * Tvx * Bpx * t) - (Tax * Bpx * t^2) +
Tpy^2 + (Tvy^2 * t^2) + ((1/4) * Tay^2 * t^4) - Bpy^2 + (2 * Tpy * Tvy * t) + (Tpy * Tay * t^2) - (2 * Tpy * Bpy) + (Tvy * Tay * t^3) - (2 * Tvy * Bpy * t) - (Tay * Bpy * t^2) +
Tpz^2 + (Tvz^2 * t^2) + ((1/4) * Taz^2 * t^4) - Bpz^2 + (2 * Tpz * Tvz * t) + (Tpz * Taz * t^2) - (2 * Tpz * Bpz) + (Tvz * Taz * t^3) - (2 * Tvz * Bpz * t) - (Taz * Bpz * t^2)
- (Bs^2 * t^2) = 0

-------------------------------

((1/4) * (Tax^2 + Tay^2 + Taz^2) * t^4) +
(((Tvx * Tax) + (Tvy * Tay) + (Tvz * Taz)) * t^3) +
((Tvx^2 + Tvy^2 + Tvz^2 + (Tpx * Tax) + (Tpy * Tay) + (Tpz * Taz) - (Tax * Bpx) - (Tay * Bpy) - (Taz * Bpz) - Bs^2) * t^2) +
(2 * ((Tpx * Tvx) + (Tpy * Tvy) + (Tpz * Tvz) - (Tvx * Bpx) - (Tvy * Bpy) - (Tvz * Bpz)) * t) +
Tpx^2 + Tpy^2 + Tpz^2 - Bpx^2 - Bpy^2 - Bpz^2 - (2 * ((Tpx * Bpx) + (Tpy * Bpy) + (Tpz * Bpz)))
= 0
-------------------------------

Wich is of the form

A * t^4 + B * t^3 + C * t^2 + D * t + F = 0 (1)
(using F instead of E on porpuese just to avoid getting it confused with Euler's number)

Having:
A = (1/4) * (Tax^2 + Tay^2 + Taz^2)
B = (Tvx * Tax) + (Tvy * tay) + (Tvz * Taz)
C = Tvx^2 + Tvy^2 + Tvz^2 + (Tpx * Tax) + (Tpy * Tay) + (Tpz * Taz) - (Tax * Bpx) - (Tay * Bpy) - (Taz * Bpz) - Bs^2
D = 2 * ((Tpx * Tvx) + (Tpy * Tvy) + (Tpz * Tvz) - (Tvx * Bpx) - (Tvy * Bpy) - (Tvz * Bpz))
F = Tpx^2 + Tpy^2 + Tpz^2 - Bpx^2 - Bpy^2 - Bpz^2 - (2 * ((Tpx * Bpx) + (Tpy * Bpy) + (Tpz * Bpz)))

Now I put the equation (1) on an oline solver in:
http://www.quickmath.com/webMathematica3/quickmath/page.jsp?s1=equations&s2=solve&s3=basic

and solved it for t, but the results are just obscene. You'll have to replace and maybe simplify if possible. I have no time to that now. You'll have to take wathever result is real and positive, if none is then the bullet can't reach the target.

##### Share on other sites
johnstanp    267
Quote:
Original post by YogurtEmperor
Quote:
 Original post by johnstanpf²(x)-y²=0 is not equivalent to f²(x-y)=0

I’m not rearranging the terms that way.
length²((Tp+Tvt+½×Tat²)-Bp) = Bst² // If these two terms are equal (this is the form you said the equation should be), then
length²((Tp+Tvt+½×Tat²)-Bp)-Bst² = 0 // Subtracting them results in 0.

I do not know enough about Algebra II to know why you put x and y together when you moved the y term to the left. From my primitive understanding, I am not doing this.

##### Share on other sites
L. Spiro    25615
Good work ZaHgO, but can you explain what each step is doing?
Aside from wanting to put these steps in the article, I also want to learn from it myself.

So that is a Quartic function?
Not sure how to solve it but I will look it up before I post asking how.

L. Spiro

##### Share on other sites
Fenrisulvur    186
Quote:
 Original post by YogurtEmperorThe keen observer can see a target moving along a trajectory and a bullet moving as well.But this is not how to intercept the bullet with the target. As you can see, the direction of the bullet does not matter.Bullet velocity is not a factor, it is the bullet speed.

Hmm, strange question. Here's what I have:

I'm picturing the target as a projectile (which is in essence the nature of any motion described by a polynomial of degree 2 with constant coefficients); and as the bullet's trajectory isn't given, I sort-of see this as a "non-deterministic" sphere expanding from a centrepoint, with a bullet prepped at whatever location on the sphere the target happens to first coincide with - not unlike a nondeterministic Turing machine, as an aside. :)
Does this interpretation seem fair?

Well, I have aesthetic tastes and happen to value my corneas, so I'm LaTeXing my math. I give the target's position by the following function:

$\vec{x}(t) = \vec{x_{0}} + \vec{v_{0}}t + \frac{\vec{a_{0}}t^2}{2}.$

We are looking for the first t such that

$\left|\vec{x}(t) - \vec{B}\right| = bt$

where b is the bullet's "speed", and the B vector is the bullet's originating location in space; hence

$\left|\vec{x_{0}} - \vec{B} + \vec{v_{0}}t + \frac{\vec{a_{0}}t^2}{2}\right| = bt.$

Indeed the norm is defined algebraically as the square root of the dot product, which is available to us, so

$\left(\vec{x_{0}} - \vec{B} + \vec{v_{0}}t + \frac{\vec{a_{0}}t^2}{2}\right) \bullet \left(\vec{x_{0}} - \vec{B} + \vec{v_{0}}t + \frac{\vec{a_{0}}t^2}{2}\right) = b^2t^2$

and by distributivity,

$\left(\vec{x_0} - \vec{B} \right )\bullet\left(\vec{x_0} - \vec{B} \right )\; +\; 2\,t\left(\vec{x_0} - \vec{B} \right )\bullet\vec{v_0} \;+\; t^2$$\left(\left(\vec{x_0} - \vec{B} \right )\bullet\vec{a_0} + \vec{v_0}\bullet\vec{v_0} - b^2\right )\;+\; t^3\cdot\vec{v_0}\bullet\vec{a_0} \;+\; \frac{t^4}{4}\cdot\vec{a_0}\bullet\vec{a_0} = 0$

which indeed is a scalar quartic in t, and you can easily scrape off those coefficients and evaluate them to give a general form

$c_0 + c_1t + c_2t^2 + c_3t^3 + c_4t^4 = 0\:, \;\textup{all} \;c_i \in \mathbb{R}$
EDIT: how the hell did I manage to miswrite a general form? Gah.

[Edited by - Fenrisulvur on November 20, 2010 8:17:08 AM]

##### Share on other sites
L. Spiro    25615
Your results are not the same as ZaHgO’s. Is this an alternative to the same final result?
Finding the roots will be a problem for me at my level in math.

As for the concept, I want to save the details for the paper, but you are on the right track.
The final result an AI bot will need to hit a target is not the time of the hit, but the direction it needs to point when firing the bullet.
Both t and the direction are solved at the same time when you have a linear projectile. Changing the direction does not change t, so solving for t, moving the target to that location (using Tp+Tvt+½×Tat²), and then a simple vector subtraction/normalization gives the bot the answer.

The equation I posted here expresses this by removing direction from the bullet and considering the target and the bullet as two spheres, one expanding linearly (the bullet) and one changing size in relationship to the distance from the target to the bullet starting point over time. The radius from the target to the bot’s firing point (which matches the bullet starting point) makes one sphere, and when it is equal in size to the linearly-expanding sphere created by the radius from the bullet to its starting location, you get t for time of hit.
If you are using a linear projectile, changing the direction of the bullet will not change the time of hit.

But when you have a grenade or arching weapon, changing the direction the bot faces significantly changes the t of impact. You can no longer just solve for t with my equation, face the bot at the predicted target point, and call it a day.

I will present the concepts and math for how to account for this, and for other variables such as inertia imparted into the bullet from the bot (for example, in many FPS games, rockets take 50% of your player velocity when fired, and all realistic war games add your full player velocity to tossed grenades), accounting for the target bouncing off walls/terrain, and more in my article.
To my knowledge not much of this is documented, and I know for a fact it is not documented all in one place. I plan to make the most comprehensive and complete guide on bot aiming, and I hope it will serve as a definitive reference on the subject.

L. Spiro

##### Share on other sites
Fenrisulvur    186
Quote:
 Original post by YogurtEmperorYour results are not the same as ZaHgO’s. Is this an alternative to the same final result?

Actually, indeed it is. I've merely spared myself a lot of pain by phrasing mine in more powerful notation.

To see the equivalence, all you need to know is the definition of the dot product. For any two vectors v and w in n-dimensional cartesian space,

$\vec{v}\bullet\vec{w} =_{def} \sum_{i = 1}^{n}v_iw_i = v_1w_1 + v_2w_2 + \cdots + v_nw_n\in\mathbb{R}.$

A little less abstractly, the 3D version is

$\vec{v}\bullet\vec{w} = v_xw_x + v_yw_y + v_zw_z.$

From here you should be able to expand each of the coefficients in my solution and see that they correspond exactly to ZaHgO's answer.

Quote:
 Original post by YogurtEmperorFinding the roots will be a problem for me at my level in math.

Well, have you considered chopping the acceleration term? You speak of a bullet, which I'd expect to be in flight for significantly less than a second in the average case. If you neglect acceleration of the target, then both the cubic and quartic terms disappear and you're left with a trivially-solvable quadratic in t. This may not bode well if you're intending on generalizing to projectiles with significantly more airtime, though, but on that note I think much of this mathematics would need re-working to cater for that kind of scenario.

By-the-by, cutting the position formula short at the second time derivative (acceleration) is a completely arbitrary thing to do, as well. We could give target position in terms of arbitrarily many derivatives, say n of them:

$\vec{x}(t) = \sum_{k = 0}^{n}\vec{x}^{\,(k)}(0)\,\frac{t^k}{k!} = \vec{x_0} + \vec{v_0}\,t + \vec{a_0}\,\frac{t^2}{2} + \vec{b_0}\,\frac{t^3}{3!} + \cdots + \vec{x}^{\,(n)}(0)\,\frac{t^n}{n!}$

where, for example, b is Jerk, the third time-derivative of position (ie. the first derivative of acceleration), and so-on.
As n goes to infinity, we get something known as an "analytic series", and it converges because that k! expression (ie. k factorial) dividing each term gets ridiculously big very quickly, so a certain way down the series the values being added up become insignificantly tiny, no matter which value of t you're evaluating the sum for.

Nevertheless, we're interested in truncating it to some n amount of terms, because we want to solve the thing. Well, it's not terribly difficult to deduce that

$\left|\: \sum_{k = 0}^{n}\vec{x}^{\,(k)}(0)\,\frac{t^k}{k!}\;-\;\vec{B} \:\right|^2 = O(t^{\,2n}).$

That is, for every extra term you throw onto the end of the position formula, the degree of the polynomial you need to find the roots for goes up by 2.