[Solved] Missile predict target's movement alogrithm

[Natu]

Guys help me! I suck at math!
So, what I'm trying to do is cast a spell to a target unit. That spell fires a missile, predicting where this target is currently moving. It's like the default missile attack with Homing set to false.
I already searched a bunch examples and references at gamedev and other sites but I can't just make it work!

This is my function, which I salvaged from gamedev and converted it to vjass.

function intercept takes UNIT src, UNIT trg, real bulletSpeed returns nothing
    // position
    local real dx = src.x - trg.x
    local real dy = src.y - trg.y
    // velocity
    local real vx = src.vx - trg.vx
    local real vy = src.vy - trg.vy
    
    local real a = vx * vx + vy * vy - bulletSpeed * bulletSpeed
    local real b = 2. * (vx * dx + vy * dy)
    local real c = dx * dx + dy * dy
    local real disc = b * b - 4. * a * c
   
    local real t0
    local real t1
   
    if (disc >= 0) then
   
        set t0 = (-b - SquareRoot(disc)) / (2. * a)
        set t1 = (-b + SquareRoot(disc)) / (2. * a)

        if (t0 < 0. or (t1 < t0 and t1 >= 0.)) then
            set t0 = t1
        endif
        if (t0 >= 0.) then
            set TARGET_X = vx + dx / t0
            set TARGET_Y = vy + dy / t0
        endif
    endif
endfunction

I'm sorry if I'm being picky, but if you can, please spare me with complex math lectures or attach link of math equation stuffs. I can't understand it anyway nor interested in it!

If you would be so kind, just give me a function that works T-T

 

[Fruit Forest]

If you would be so kind, just give me a function that works T-T

Here is simple example what doesn't count bullet speed. If you want the counting the bullet speed, then you have to write in trigger 4 giant quadratic equation. I also implemented the movement detection so the archer wouldn't try to predict the movement if the unit stays.

 

[The_Silent]

This would be a lot easier with vectors and raycasters.

Something like:

    local real dist = CurrentUnitMovementSpeed * timeItTakesForTheMissileToReachThePoint
    local real angle = FacingAngleOfTarget
    local real x = GetLocationX(targetCurrentLocation) + dist * Cos(angle * bj_DEGTORAD)
    local real y = GetLocationY(targetCurrentLocation) + dist * Sin(angle * bj_DEGTORAD)
    return Location(x, y)

This will give you the point the unit will be in if it continues in a straight line at a constant speed. This however, will not take obstacles, and the fact that the unit might stop right after the missile is fired, into mind.

 

[Wietlol]

The difficulty depends on how you want to define your missile speed.
If you want to have 3d movement calculations, then your horizontal speed will be less if you aim higher.
So, to reach a larger horizontal distance, your horizontal speed decreases/increases.
If you want how WC3 uses missile speed (at a fixed horizontal speed with a fixed angle and a dynamic distance, then it is pretty easy.

 

[Natu]

Here is simple example what doesn't count bullet speed. If you want the counting the bullet speed, then you have to write in trigger 4 giant quadratic equation. I also implemented the movement detection so the archer wouldn't try to predict the movement if the unit stays.

Thanks dude, I can use this as reference.

This will give you the point the unit will be in if it continues in a straight line at a constant speed. This however, will not take obstacles, and the fact that the unit might stop right after the missile is fired, into mind.

How do you calculate timeItTakesForTheMissileToReachThePoint?
Oh, obstacles and height doesn't matter. I want simple.

If you want how WC3 uses missile speed (at a fixed horizontal speed with a fixed angle and a dynamic distance, then it is pretty easy.

This. The calculations tho. I don't know how to time it properly.

 

[The_Silent]

I don't know how missile movement works in wc3. Assuming you're using the dafault one, I think it is essentially the same as unit movement speed, but I don't exactly get how that works. It might be x "cordinates points" per second, and there is 128 per square. So 350 unit/missile movement might be just under 3 squares per second. Again, just guessing. You will have to experiment with this.

Assuming they are not too diffirent, try using this equation, experimenting with different x-values:
distance = (missileSpeed/unitSpeed)*x

X is units of wc3 distance. So, again, 128 is one 'medium' ingame square. Also, really slow missiles (slower than the unit it is targeting) will screw this equation up. But, from most angles, that missile will never reach the target anyway, so that makes sense i suppose.

 

[Wietlol]

http://danikgames.com/blog/how-to-intersect-a-moving-target-in-2d/ explains it pretty well how the calculations could be done.


There may be scenarios in which the target will never be hit (in case of where the target is moving exactly away from the source and the target is moving equally as fast or faster.
Another cause can be that the distance that the missile has to travel is exceeding it's maximum distance, in which case, you should just take the direction and recalculate the "impact" point.

 

[Flux]

Here.

Current editing to explain the math behind it.

In the demo, I was able to compute the launching angle of the missile which is a long formula so I broken it up to bits.

Formula

            //Spawn a target at random location with random facing
            local real targetX = GetRandomReal(-1500, 1500)
            local real targetY = GetRandomReal(-1500, 1500)
            local real targetAngle = GetRandomReal(-bj_PI, bj_PI)
            local unit target = CreateUnit(Player(0), TARGET_ID, targetX, targetY, targetAngle*bj_RADTODEG)
            //Calculate firing angle based on source and target information
            //You can actually do it with fewer lines but I'm gonna break it up for simplicity
            local real dy = targetY - SOURCE_Y
            local real dx = targetX - SOURCE_X
            local real distance = SquareRoot(dx*dx + dy*dy)
            local real targetSpeed = GetUnitMoveSpeed(target)
            local real angle = Acos(targetSpeed*(dy*Cos(targetAngle) - dx*Sin(targetAngle))/(MISSILE_SPEED*distance)) + Atan(-dx/dy)
            //After testing, I've found out it failed when target is on quadrant 3 or quadrant 4.
            //Can't figure out where I got wrong in the math, but I was able to solve it by adding this:
            if dy < 0 then
                set angle = angle + bj_PI
            endif
            call Missile.create(angle)

Math Derivation

I was able derive the launching angle using vectors.
Note: Bold letters are vector quantities

Let:
Missile Speed = S_spd
Target Speed = T_spd
t = Time it takes before predicted hit
A = Correct Launching Angle to hit
B = Target Facing Angle
Our vector quantities can be expressed as:
S = S_x + S_y
S_x = S_spd*t*Cos(A), S_y = S_spd*t*Sin(A)
T = T_x + T_y
T_x = T_spd*t*Cos(B), T_y = T_spd*t*Sin(B)
d = d_x + d_y
d_x = TargetX - SourceX, d_y = TargetY - SourceY
^To keep it short, I'll write dx and dy instead.

Equation 1:
S_spd*t*Cos(A) - T_spd*t*Cos(B) = dx

Equation 2:
S_spd*t*Sin(A) - T_spd*t*Sin(B) = dy

If we divide Equation 1 by Equation 2, 't' will cancel.
(S_spd*Cos(A) - T_spd*Cos(B))*(dy) = (S_spd*Sin(A) - T_spd*t*Sin(B))*dx

By expanding the terms and isolating 'A':
dy*Cos(A) - dx*Sin(A) = T_spd*(dy*Cos(B) - dx*Sin(B))/S_spd

If you look closely to the left side of the equation, the trigonometric equation can be expressed as a single trigonometric function:
dy*Cos(A) - dx*Sin(A) = √(dy² + dx²)*Cos(A - Atan(-dx/dy))
Proof

Going back:
Cos(A - Atan(-dx/dy)) = T_spd*(dy*Cos(B) - dx*Sin(B))/(S_spd*√(dy² + dx²))

Therefore:
A = Acos(T_spd*(dy*Cos(B) - dx*Sin(B))/(S_spd*√(dy² + dx²))) + Atan(-dx/dy)

@Ralle, do we have math bb codes? [sup] and [sub] are not included in here so maybe there's other bb codes that I'm not aware of.

 

[Natu]

http://danikgames.com/blog/how-to-intersect-a-moving-target-in-2d/ explains it pretty well how the calculations could be done.

There may be scenarios in which the target will never be hit (in case of where the target is moving exactly away from the source and the target is moving equally as fast or faster.
Another cause can be that the distance that the missile has to travel is exceeding it's maximum distance, in which case, you should just take the direction and recalculate the "impact" point.

Oh that blog, I can understand it finally.
So I followed it and it went great. The missile accuracy is a lot better now, tho I was aiming for 100% accuracy. But this is acceptable enough.

I don't know how missile movement works in wc3. Assuming you're using the dafault one, I think it is essentially the same as unit movement speed, but I don't exactly get how that works. It might be x "cordinates points" per second, and there is 128 per square. So 350 unit/missile movement might be just under 3 squares per second. Again, just guessing. You will have to experiment with this.

Assuming they are not too diffirent, try using this equation, experimenting with different x-values:
distance = (missileSpeed/unitSpeed)*x

X is units of wc3 distance. So, again, 128 is one 'medium' ingame square. Also, really slow missiles (slower than the unit it is targeting) will screw this equation up. But, from most angles, that missile will never reach the target anyway, so that makes sense i suppose.

I experimented a little bit and seems like I just have to multiply unit movement speed by the timer period (522*0.025). I'll see if I can improve this further.

Here.

Current editing to explain the math behind it.

Wow, you just saved my sorry ass dude. This is great stuff! Very clear, and comes with a demo too! Now all I need is to read-learn it before I can implement this to mine. So happy!

I'll be sure to credit you guys (if ever i finish it)! Thanks again!

 

[Flux]

Wow, you just saved my sorry ass dude. This is great stuff! Very clear, and comes with a demo too! Now all I need is to read-learn it before I can implement this to mine. So happy!

I edited my previous post to explain the math behind it. Good luck!

 

[Natu]

Will do my best. Thanks for the trouble!

Edit: So detailed! Really appreciate it xD