Target Prediction Formula?

[LurkerAspect]

Hi again wasn't sure where to post this but considering I'll eventually use such a system in WC3, posting here seems appropriate...

OK. So I'm trying to get a general formula where I give a set of variables and get a result. What I want to do is find/create an equation that can predict where to fire a projectile so that it will collide with the target when it reaches that point, where the two paths intercept. You all know how if you give a unit in Wc3 a non-homing projectile, it will try to intercept the target in a similar manner to what I'm looking for.

So, I want to give the coordinates of the target, the coordinates of the shooter, and the speeds of the two objects, and be able to get coordinates back of the intercept point. I'm looking for a formula that can be used on a conventional cartesian plane, and from there I can adapt it to wc3 or whatever.

Does anyone know of such a formula or how I would go about creating one?

 

[perkeyone]

sounds like algebra.

if you can find the speed of a projectile and the movement speed of a unit using a trigger, then im sure it is possible.

in a moment ill try to come up with a formula.

EDIT: lol this might not be algebra after all. could be some vector calculus in there ill see what i can do.

 

[LurkerAspect]

This is possibly the worst forum ever if you want a quick response.

OK, maybe I wasn't clear enough. I have the target (A) and the shooter (B). Shooter fires a missile at A that moves in a straight line at a constant velocity. The target is also moving at a constant velocity in a straight line. They collide at C. I want to find an equation that gives me the coordinates of C.

What I have: The X and Y coordinates of A and B, the angle that the target (A) is moving in, and the speeds of A and B. So broken down into a list, that is:

• A=(Xa;Ya)
• B=(Xb;Yb)
• Speed of A = Va
• Speed of B = Vb
• Angle of A = a (in degrees)

And when plugged into an equation I get C=(Xc;Yc), or in other words, the X and Y coordinates of C.

So far the closest I have found is this:
(s^2-(v.v))*t^2 - (2*((A-B).v))*t - (A-B).(A-B) = 0
Where s=Vb, v=Va, and t is the time in seconds, from this forum, but I don't know how this works at all, because the creators do not specify exactly what A and B are, and when I do the equation twice using A and B as the respective coordinates of A and B for X and Y, it doesn't work out.

And no, I need that equation in standard form, not as a wc3 trigger.

 

[perkeyone]

i dont know what is going on in that other forum, it would take a while for me to understand whats going on in the code posted there.

ive yet to figure out an exact calculation =[
i can help you find an approximation though...

first i would find the distance (d0) along the red line from the shooter (a) and the target (p0)
then i would calculate the time (t0) it would take for the projectile to travel that distance
then using the target's velocity and t0 i would calculate the target's projected position (p1)

next i would repeat the above steps until the difference between p(n) and p(n+1) is very small.
ie,
calculate the distance (d(n)) from a to p(n),
then find the time that it would take (t(n)) to reach that point
project what the target's position (p(n+1)) after that time
find the difference between p(n) and p(n+1)
compare that difference it to a "maximum allowed inaccuracy" constant.
if it is less than the constant, then use p(n+1) as your target.
else loop for (n+1)

EDIT: actually i think i found an exact solution on that forum you were using. im not sure if youve seen it yet so ill give you the link here.
http://www.gamedev.net/community/forums/topic.asp?topic_id=384206

 

[LurkerAspect]

Wow man thanks for the help I wasn't expecting so much of it

I skimmed through that thread quickly and it looks promising, I'll examine it and test it when I have some spare time again, it looks like the kind of thing I was asking for!

+rep

EDIT: I think the only thing I could wish for now is if someone could translate the stuff on that page into english!!! Lol I'm no maths boffin :3

 

[Bogrim]

Basically you're looking for to balance a polar off-set based on the unit's movement speed in the unit's facing angle, using the movement speed as the determinating variable for the off-set amount.

The real problem here is estimating how the unit's movement speed actually affects the off-set distance. I really don't know that, and nothing on the linked math forum is going to help you with that either. But if you do find a way to estimate it, then you have the two points you need to fire your projectile.

 

[perkeyone]

ill try to translate it all out. its gonna be pretty ugly in the end though.
EDIT: actually it didnt turn out that bad... have a look at my post below.

 

[Hatebreeder]

     loop
       exitwhen Count >= (Ticks/Tick)   //Ticks is the Time the projectile will be moving in (in seconds)
          set Count = Count + 1
          set X = X + (Speed/Tick) * Cos(Angle) //Speed is the Speed of the unit and/or missle
          set Y = Y + (Speed/Tick) * Sin(Angle) //Tick is the Timers periodic delay
     endloop

Basically, you can get the X or Y coordinates of where the Missle you want to predict will land in a line.

 

[kingkingyyk3]

Equation 1 : Movement of target (y = mx + c/ax^2 + bx + c)
Equation 2 : Movement of projectile (y = mx + c/ax^2 + bx + c)
To find out where they will collide, put equation 1 = equation 2.
after getting the x value, substitute the x value into equation 1 or equation 2.

 

[perkeyone]

ok i got it all nice and neat for ya.
here are your known variables,

X=initial position of target (x component)
Y=initial position of target (y component)
S=movement speed of target
D=direction of movement (facing angle)
J=initial position of projectile (x component)
K=initial position of projectile (y component)
Z=movement speed of projectile

notice all the variables are capital letters...
i did that on purpose to help make it less confusing when there are sin() cos() and sqrt() in the formula.
now some calculations,

A=(X-J)²+(Y-K)²
B=2S(cos(D)(X-J)+sin(D)(Y-K))
T=2A/(-B±sqrt(B²-4A(S²-Z²)))

since there is a ± in the equation, there are two possible solutions for T.
the correct one is positive. if both are positive then it is the smaller of the two.
the point that you want to target is...

(X+STcos(D),Y+STsin(D))

EDIT: this could easily be translated into jass... also if you want, i can give an in-depth explanation of each step that i used to reach this formula.

 

[LurkerAspect]

Dude that is amazing that's exactly what I wanted After sitting down and actually working out an example via exam pad and matric algebra/science knowledge, it worked beautifully

Could you show it to me in JASS as well, seeming as you offered to? I just want to see how you would go about using a quadratic equation in a coding system like JASS, although I'm sure the answer is a lot simpler than I think

Haha I'm actually not sure how to thank you

EDIT: After you do it in JASS, you should submit it as a system on this forum I'm sure many others would be interested in a projectile interception system

 

[perkeyone]

hehe, actually i dont know jass myself, i just know it would be a pain in the ass to make this in gui where as it would be easy to implement in jass =P

 

[Komaqtion]

I'd believe this should be what you're looking for

library InterceptionFormula

    function GetInterceptionLoc takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns location
        local real difx = castX - targX
        local real dify = castY - targY
        local real interX
        local real interY
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( Cos( targAngle ) * difx + Sin( targAngle ) * dify )
        local real x1 = 2 * dist / ( ( -a ) + SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) ) )
        local real x2 = 2 * dist / ( ( -a ) - SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) ) )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interX = targX + targSpeed * x * Cos( targAngle )
        set interY = targY + targSpeed * x * Sin( targAngle )
        
        return Location( interX, interY )
    endfunction
    
    function GetInterceptionX takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns real
        local real difx = castX - targX
        local real dify = castY - targY
        local real interX
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( Cos( targAngle ) * difx + Sin( targAngle ) * dify )
        local real x1 = 2 * dist / ( ( -a ) + SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) ) )
        local real x2 = 2 * dist / ( ( -a ) - SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) ) )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interX = targX + targSpeed * x * Cos( targAngle )
        
        return interX
    endfunction
    
    function GetInterceptionY takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns real
        local real difx = castX - targX
        local real dify = castY - targY
        local real interY
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( Cos( targAngle ) * difx + Sin( targAngle ) * dify )
        local real x1 = 2 * dist / ( ( -a ) + SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) ) )
        local real x2 = 2 * dist / ( ( -a ) - SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) ) )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interY = targY + targSpeed * x * Sin( targAngle )
        
        return interY
    endfunction
        
endlibrary

 

[BlackRose]

Oh that's hawt. It works. Thanks Komaqtion <3

Just one thing:

You can optimize this by making the SquareRoot a variable?

_
        local real x1 = 2 * dist / ( ( -a ) + SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) ) )
        local real x2 = 2 * dist / ( ( -a ) - SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) ) )

 

[LurkerAspect]

Haha I don't have a clue whats going on there but it's freaking cool nah I just mean I'm too tired to analyze it right now, but thanks a lot for doing that for me I still really think you should release it as a system, or has that already happened? I'm a bit out of synch with The Helper right now

 

[Komaqtion]

library InterceptionFormula

    function GetInterceptionLoc takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns location
        local real difx = castX - targX
        local real dify = castY - targY
        local real interX
        local real interY
        local real cosa = Cos( targAngle )
        local real sina = Sin( targAngle )
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( cosa * difx + sina * dify )
        local real sqr = SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) )
        local real x1 = 2 * dist / ( ( -a ) + sqr )
        local real x2 = 2 * dist / ( ( -a ) - sqr )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interX = targX + targSpeed * x * cosa
        set interY = targY + targSpeed * x * sina
        
        return Location( interX, interY )
    endfunction
    
    function GetInterceptionX takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns real
        local real difx = castX - targX
        local real dify = castY - targY
        local real interX
        local real cosa = Cos( targAngle )
        local real sina = Sin( targAngle )
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( cosa * difx + sina * dify )
        local real sqr = SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) )
        local real x1 = 2 * dist / ( ( -a ) + sqr )
        local real x2 = 2 * dist / ( ( -a ) - sqr )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interX = targX + targSpeed * x * cosa
        
        return interX
    endfunction
    
    function GetInterceptionY takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns real
        local real difx = castX - targX
        local real dify = castY - targY
        local real interY
        local real cosa = Cos( targAngle )
        local real sina = Sin( targAngle )
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( cosa * difx + sina * dify )
        local real sqr = SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) )
        local real x1 = 2 * dist / ( ( -a ) + sqr )
        local real x2 = 2 * dist / ( ( -a ) - sqr )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interY = targY + targSpeed * x * sina
        
        return interY
    endfunction
        
endlibrary

Small optimization there, as requested by BlackRose

U really think this should be submitted ? :S
Maybe I can try to extend it a bit more first, any ideas ?
( Sorry for stealing the thread, but just need a small answer )

 

[LurkerAspect]

I do think you should submit it, people would be interested in a system like this if they were using their own custom projectile systems, because this greatly improves projectile accuracy.

Also, an idea I have, perhaps you can just bunch it up into one function that simply returns the angle the projectile should travel at? Then you could just do this while sliding an object:

local real A = GetAngleToInterceptPoint(x1,x2,y1,y2,v1,v2)
...
call SetUnitX(unit, x+step*Cos(a*bj_DEGTORAD))

etc.

 

[Komaqtion]

Now, I don't know of there's an easier way to get this angle then to go through all of this math again, but this works at least

library InterceptionFormula

    function GetInterceptionLoc takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns location
        local real difx = castX - targX
        local real dify = castY - targY
        local real interX
        local real interY
        local real cosa = Cos( targAngle )
        local real sina = Sin( targAngle )
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( cosa * difx + sina * dify )
        local real sqr = SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) )
        local real x1 = 2 * dist / ( ( -a ) + sqr )
        local real x2 = 2 * dist / ( ( -a ) - sqr )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interX = targX + targSpeed * x * cosa
        set interY = targY + targSpeed * x * sina
        
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "DifX: " + R2S( difx ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "DifY: " + R2S( dify ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "InterX: " + R2S( interX ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "InterY: " + R2S( interY ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "CosA: " + R2S( cosa ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "SinA: " + R2S( sina ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "Dist: " + R2S( dist ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "A: " + R2S( a ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "Sqr: " + R2S( sqr ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "X1: " + R2S( x1 ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "X2: " + R2S( x2 ) )
        debug call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "X: " + R2S( x ) )
        
        return Location( interX, interY )
    endfunction
    
    function GetInterceptionX takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns real
        local real difx = castX - targX
        local real dify = castY - targY
        local real interX
        local real cosa = Cos( targAngle )
        local real sina = Sin( targAngle )
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( cosa * difx + sina * dify )
        local real sqr = SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) )
        local real x1 = 2 * dist / ( ( -a ) + sqr )
        local real x2 = 2 * dist / ( ( -a ) - sqr )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interX = targX + targSpeed * x * cosa
        
        return interX
    endfunction
    
    function GetInterceptionY takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns real
        local real difx = castX - targX
        local real dify = castY - targY
        local real interY
        local real cosa = Cos( targAngle )
        local real sina = Sin( targAngle )
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( cosa * difx + sina * dify )
        local real sqr = SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) )
        local real x1 = 2 * dist / ( ( -a ) + sqr )
        local real x2 = 2 * dist / ( ( -a ) - sqr )
        
        local real x
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interY = targY + targSpeed * x * sina
        
        return interY
    endfunction
    
    function GetInterceptionAngle takes real castX, real castY, real castSpeed, real targX, real targY, real targSpeed, real targAngle returns real
        local real difx = castX - targX
        local real dify = castY - targY
        local real interX
        local real interY
        local real cosa = Cos( targAngle )
        local real sina = Sin( targAngle )
        
        local real dist = difx * difx + dify * dify
        
        local real a = 2 * targSpeed * ( cosa * difx + sina * dify )
        local real sqr = SquareRoot( ( a * a ) - ( 4 * dist * ( targSpeed * targSpeed - castSpeed * castSpeed ) ) )
        local real x1 = 2 * dist / ( ( -a ) + sqr )
        local real x2 = 2 * dist / ( ( -a ) - sqr )
        
        local real x
        local real angle
        
        if x1 >= 0 and x2 >= 0 then
            
            if x1 < x2 then
                set x = x1
            else
                set x = x2
            endif
            
        elseif x1 < 0 then
            set x = x2
        else
            set x = x1
        endif
        
        set interX = targX + targSpeed * x * cosa
        set interY = targY + targSpeed * x * sina
        
        set angle = bj_RADTODEG * Atan2( interY - castY, interX - castX ) 
        
        return angle
    endfunction
        
endlibrary

 

[LurkerAspect]

Well if you are going to post it as a system, then you'll have to submit it before I do cos I have my own equivalent:

function GetAngleToInterception takes unit target, unit shooter, real bulletspeed returns real angle
    local real x1 = GetUnitX(target)
    local real y1 = GetUnitY(target)
    local real x2 = GetUnitX(shooter)
    local real y2 = GetUnitY(shooter)
    local real v = GetUnitMoveSpeed(target)
    local real at = GetUnitFacing(target)
    local real A = 0
    local real B = 0
    local real t1 = 0
    local real t2 = 0
    local real t3 = 0
    
    set A = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)
    set B = 2*v*(Cos(at*bj_DEGTORAD)*(x1-x2)+Sin(at*bj_DEGTORAD)*(y1-y2))
    set t1 = (2*A)/(-B-SquareRoot(B*B-4*A*(v*v-bulletspeed*bulletspeed)))
    set t2 = (2*A)/(-B+SquareRoot(B*B-4*A*(v*v-bulletspeed*bulletspeed)))
        
    if t1 > 0 and t1 < t2 then
        set t3 = t1
    else
        set t3 = t2
    endif
        
    return bj_RADTODEG*(Atan2((y1+v*t3*Sin(at*bj_DEGTORAD))-y2,(x1+v*t3*Cos(at*bj_DEGTORAD)-x2)))
endfunction

I hope you'll excuse the degrees, but here in South Africa, we don't work in silly units like feet, radians, miles, and pounds

EDIT: Hmm, this system does have problems aiming at static targets... is there a function that returns the instantaneous speed of a unit?

 

[Komaqtion]

Now that is just lame, if you take my, BlackRose's and perkeyone's work (And that I've actually put everything together for you) and submit this as your own... But fine then

And what do you mean by "instantaneous speed" ?
Like, not movement-speed ?