Jump to content
  • Advertisement
Sign in to follow this  
L. Spiro

I Made an Equation but I Cannot Solve It

This topic is 2799 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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).
Without further ado:


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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by YogurtEmperor
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.

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by YogurtEmperor
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.

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

Quote:
Original post by YogurtEmperor
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…

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 YogurtEmperor
With 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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!