Jump to content
  • Advertisement
Sign in to follow this  
Matis

Distance between two trajectories

This topic is 1128 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

Hello,

 

First of all, I'd like to welcome everyone as this is my first post here smile.png. Secondly, sorry for the length of this post, I'll try to be as concise as possible rolleyes.gif.

 

I work on a 2D space shooting game with physics, so that ships have inertia etc. I'd like to implement projectile dodging by AI. In order to do that I must determine whether given ship is going to collide with given projectile. I want to check if at any point in time within some time frame [0, T] distance between points representing ship and projectile falls below some threshold and, if it does, consider it to be a collision. So, I have come up with equations of motion for ship and projectile and constructed a distance function with respect of time (I skipped square root):

$$D(t) = (x_{ship}(t)-x_{projectile}(t))^2 + (y_{ship}(t)-y_{projectile}(t))^2 $$

Since I'm only interested if that distance ever falls below some threshold, I think that it's enough to find minimum of aforementioned function for time in range [0, T]. To find that minimum I want to check D(t) value for:

 

$$t = 0$$

$$t = T$$

$$t \rightarrow D'(t) = 0$$

 

Is this correct up to this point? Is there any simpler way to achieve the same?

 

Now, time for the hard part smile.png. Checking distance at t = 0 and t = T is trivial, finding roots of D'(t) isn't sad.png.

 

Projectile always moves with uniform motion. Ship, however, can move in one of following ways:

  1. If ship's engine is turned off, it moves with uniform motion.
  2. If ship's engine is on, but it doesn't rotate, it moves with uniformly accelerated motion.
  3. If ship's engine is on and it rotates, it moves with non-uniformly accelerated motion.

Case 1. is simple and I was able to deduce a formula for finding root of D'(t), but I have problems with points 2. and 3.

 

In case 2. ship's equations of motion are like this:

 

$$x_{ship}(t) = x_0 + v_{x0}t + \frac{|F|\sin(\alpha)t^2}{2m}$$

$$y_{ship}(t) = y_0 + v_{y0}t + \frac{|F|\cos(\alpha)t^2}{2m}$$

 

where F is engine's force, alpha is ship's rotation (engine's force vector is applied with this rotation) and m is ship's mass, v_x0 and x_0 are ship's initial velocity and position respectively. The problem I have with these equations is that they give me a ridiculously complex cubic equation when I want to compute D'(t), and since I target mobile devices I need something simpler. Maybe there is some better way to check for collision in this case?

 

In case 3. I'm not sure if my equation of motion is correct. This is how I deduced it (only for x axis, y axis is similar):

  1. First I came up with acceleration function (omega is ship's rotation speed): $$a_x(t) = \sin(\alpha+\omega t)\frac{|F|}{m}$$
  2. I integrated it once and got velocity function: $$v_x(t) = v_{x0} - \frac{|F|}{m\omega}\cos(\alpha + \omega t)$$
  3. I integrated it once more and got position function: $$x_{ship}(t) = x_0 + v_{x0}t - \frac{|F|}{m\omega^2}\sin(\alpha + \omega t)$$

I'm worried, because I'd expect that

$$x_{ship}(0) = x_0$$

but it isn't. My physics and math skills are extremely rusty, so I'd be grateful if anyone could point me what I did wrong here.

 

Thanks for any input!

Share this post


Link to post
Share on other sites
Advertisement

About 2: Compute point of crossing paths like you're not accelerating, missile gives you a time when it crosses the path of the ship. Then check at that time where the ship is exactly.

Maybe you can do something similar for 3 as well? A rotating ship is on a circular path???? (not sure at all about that Edit: it's not, I am just rambling, see below). Then try to compute time from the paths (as in, distance between line and circle is much easier than going by movement equations). As for the actual math, I really wouldn't know, sorry sad.png

 

 

Edit: Please ignore the 'circle' path idea. If you accelerate, you're moving faster and faster, and with a constant rotation speed, you're not going to stay in the same circular path.

Nonetheless, it may be possible to find an easier solution with the principle of splitting path from time. Maybe there is an approximation of a path for the first X seconds? (Which should be enough for missile hit forecasting.)

Edited by Alberth

Share this post


Link to post
Share on other sites

I approximate both ship's and projectile's shape with a circle of given radius. That's why I need to check the distance between both trajectories and checking if paths cross is not enough. Also, I can't ignore acceleration in case 2., as it makes motion curvilinear instead of linear (ship can accelerate in different direction than it's initial velocity).

 

As for splitting path from time, I'm unsure how to do that or if that would help, as ship's trajectory in 3. might be a complex curve and I have no idea how to approximate it :(.

Share this post


Link to post
Share on other sites

In case 3, you are integrating wrong, losing the t and t^2 factors from the force terms (which are dimensionally incorrect) which would indeed make x(0)=x0.

Share this post


Link to post
Share on other sites
I thought about your problem while doing shopping, and concluded at the end, I would probably just do a quick simulation instead of trying to get an exact solution. Obviously the latter is preferred, but with a somewhat bigger time step you should get a nice enough prediction of what will happen without wasting a lot of CPU time.

Share this post


Link to post
Share on other sites

In case 3, you are integrating wrong, losing the t and t^2 factors from the force terms (which are dimensionally incorrect) which would indeed make x(0)=x0.

 
So the equation should look like this?:
$$x_{ship}(t) = x_{0} + v_{x0}t - \frac{|F|t^2}{m\omega^2}\sin(\alpha + \omega t)$$
 
I used WolframAlpha to compute these integrals and t^2 wasn't there. (Example: http://www.wolframalpha.com/input/?i=integrate+-a*cos(b%2Bcx)). Where does that t^2 would come from? Or maybe I misunderstood you?
 

I would probably just do a quick simulation instead of trying to get an exact solution


That's what I'll probably have to do. Hopefully it'll be fast and accurate enough smile.png.

Share this post


Link to post
Share on other sites
Your integrals are just leaving out the initial integration constant at t = 0 which balances out the initial acceleration (when alpha is not zero) so that x(0) = x0. Remember that in general:

\[ v_x(t) = v_{x_0} + \int_{0}^t a_x(t') ~ \mathrm{d}t' \]
 
And similarly:
 
\[ x(t) = x_0 + \int_{0}^t v_x(t') ~ \mathrm{d}t' \]
 
You need to take into account the initial acceleration (and hence velocity) at t = 0 to get the correct results, else you'll be off.
 
smile.png
 
EDIT: to be clear, that means that the correct equations are:

\[ v_x(t) = v_{x0} - \frac{|F|}{m\omega}\cos(\alpha + \omega t) \color{blue}{ + \frac{|F| \cos(\alpha)}{m \omega} } \]

\[ x(t) = x_0 + v_{x0} t \color{blue}{ + \frac{|F| \cos(\alpha)}{m \omega} t } - \frac{|F|}{m\omega^2}\sin(\alpha + \omega t) \color{blue}{ + \frac{|F| \sin(\alpha)}{m \omega^2} } \]

Which as you will observe cancels out to x0 when \( t = 0 \).

(please double check those integrals for sign errors, but rest assured the math works) Edited by Bacterius

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!