Discussion Most efficient and practical way to do projectile on projectile collisions

[SerraAvenger]

When you are changing v_x/v_y you'll have to do the calculations again, ofc.

 

[Zwiebelchen]

When you are changing v_x/v_y you'll have to do the calculations again, ofc.

And you need knowledge of vector algebra, because collision detection of two moving circles is not that easy to make. I'll try to write a function for you that calculates where and when two missiles of radius r collide with each other.

 

[Zwiebelchen]

Okay, here's the solution to pre-calculating of (linear and planar) missile collision:

See better version two posts below!

It requires Antiarf's Vector Library.


Note:
the [ljass]movex[/ljass] and [ljass]movey[/ljass] variables are not the x and y velocity, but the distance compared to their original spots, the missiles travel in total. Both missiles are considered traveling this distance on an equal amount of time. If you want this to work for different velocities, you need to scale the movement vectors according to your velocity.

Let's say missile 1 travels x = 10 and y = 5 meters during 1 second and missile 2 travels x = 20 and y = 15 meters in total during 2 seconds, then you have to temporary increase the travel distance of missile 1 to x = 10*2 and y = 5*2 to achieve an equal traveling time of both missiles.
Of course, if the function then returns a number higher than 0.5 (which means both missiles later than after 1 second of traveling), both missiles do not collide, as missile 1 doesn't exist anymore at this point.

 

[SerraAvenger]

phew, unnecessary work I'd say. You can just approximate it very good by using cubes, or, even better, just intersecting the parallels. That way you get a time gate in which the things are APPROXIMATELY colliding.

 

[Zwiebelchen]

phew, unnecessary work I'd say. You can just approximate it very good by using cubes, or, even better, just intersecting the parallels. That way you get a time gate in which the things are APPROXIMATELY colliding.

1) How can parallels intersect?

2) Now imagine a very small angle difference between the two missiles and you are doomed:

However, I wrote a better user interface for the system above, which takes missile movement speed:

library CollisionDetection

public struct collision
    real x1
    real y1
    real x2
    real y2
    real time
    
    static method create takes real x1, real y1, real x2, real y2, real time returns collision
        local collision c = collision.allocate()
        set c.x1 = x1
        set c.y1 = y1
        set c.x2 = x2
        set c.y2 = y2
        set c.time = time
        return c
    endmethod
endstruct

private function Distance takes real x1, real x2, real y1, real y2 returns real
	return SquareRoot((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
endfunction

private function CollisionGetMoveVector takes real x1, real y1, real movex1, real movey1, real x2, real y2, real r1, real r2 returns vector
    local vector movevec = vector.create(movex1, movey1, 0)
    local vector N = vector.create(movex1, movey1, 0)
    local vector C
    local real D
    local real dist = Distance(x1, x2, y1, y2)
    local real sumRadii = r1 + r2
    local real lengthC
    local real F
    local real T
    local real distance
    local real mag = movevec.getLength()
    set dist = dist - sumRadii
    
    //early escape:
    //if length of movevector is less than distance between centers of circles minus their radii,
    //theres no way they can hit
    if mag < dist then
        return 0
    endif
    call N.setLength(1.00)
    set C = vector.create(x2-x1, y2-y1, 0)
    set D = vector.dotProduct(N, C)
    // Another early escape: Make sure that 1 is moving 
    // towards 2! If the dot product between the movevec and 
    // 2.center - 1.center is less that or equal to 0, 
    // 1 isn't isn't moving towards 2
    if D <= 0 then
        return 0
    endif
    set lengthC = C.getLength()
    set F = (lengthC * lengthC) - (D * D)
    // Escape test: if the closest that 1 will get to 2 
    // is more than the sum of their radii, there's no 
    // way they are going collide
    if F >= sumRadii*sumRadii then
        return 0
    endif
    // We now have F and sumRadii, two sides of a right triangle. 
    // Use these to find the third side, sqrt(T)
    set T = sumRadii*sumRadii - F
    // If there is no such right triangle with sides length of 
    // sumRadii and sqrt(f), T will probably be less than 0. 
    // Better to check now than perform a square root of a 
    // negative number.
    if T < 0 then
        return 0
    endif
    // Therefore the distance the circle has to travel along 
    // movevec is D - sqrt(T)
    set distance = D - SquareRoot(T)
    // Finally, make sure that the distance 1 has to move 
    // to touch 2 is not greater than the magnitude of the 
    // movement vector.
    if mag < distance then
        return 0
    endif
    // Set the length of the movevec so that the circles will just touch
    call movevec.setLength(distance)
    call N.destroy()
    call C.destroy()    
    return movevec
endfunction

private function GetCollisionTime takes real x1, real y1, real movex1, real movey1, real x2, real y2, real movex2, real movey2, real r1, real r2 returns real
    //returns a percentage (1 being 100%) that indicates at which point of the movement vector the circles collide.
    //multiply it with the length of the original movement vector and you got the new shortened movement vector
    //returns -1 if the circles do not collide.
    local vector C = CollisionGetMoveVector(x1, y1, movex1-movex2, movey1-movey2, x2, y2, r1, r2)
    local real percentage = -1.
    if C != 0 then
        set percentage = (C.getLength())/(SquareRoot((movex1-movex2)*(movex1-movex2) + (movey1-movey2)*(movey1-movey2)))
    endif
    call C.destroy()
    return percentage
endfunction

public function GetCollisionStruct takes location missile1start, location missile1end, real missile1radius, real missile1speed, location missile2start, location missile2end, real missile2radius, real missile2speed returns collision
    //returns a struct with all useful information for the collision
    local collision data = 0
    local real x1 = GetLocationX(missile1start)
    local real y1 = GetLocationY(missile1start)
    local real x2 = GetLocationX(missile2start)
    local real y2 = GetLocationY(missile2start)
    local real dx1 = GetLocationX(missile1end)-x1
    local real dy1 = GetLocationY(missile1end)-y1
    local real dx2 = GetLocationX(missile2end)-x2
    local real dy2 = GetLocationY(missile2end)-y2
    local real time1 = SquareRoot(dx1*dx1 + dy1*dy1) / missile1speed
    local real time2 = SquareRoot(dx2*dx2 + dy2*dy2) / missile2speed
    local real collisiontime
    //temporarily scale both missile move vectors to the same move speed
    if time1 < time2 then
        set dx1 = dx1 * time2/time1
        set dy1 = dy1 * time2/time1
    else
        set dx2 = dx2 * time1/time2
        set dy2 = dy2 * time1/time2
    endif
    set collisiontime = GetCollisionTime(x1, y1, dx1, dy1, x2, y2, dx2, dy2, missile1radius, missile2radius)
    if collisiontime >= 0 then
        if time1 < time2 then
            if collisiontime <= time1/time2 then
                set x1 = x1+dx1*collisiontime
                set y1 = y1+dy1*collisiontime
                set x2 = x2+dx2*collisiontime
                set y2 = y2+dy2*collisiontime
                set data = collision.create(x1, y1, x2, y2, time2*collisiontime)
            endif
        else
            if collisiontime <= time2/time1 then
                set x1 = x1+dx1*collisiontime
                set y1 = y1+dy1*collisiontime
                set x2 = x2+dx2*collisiontime
                set y2 = y2+dy2*collisiontime
                set data = collision.create(x1, y1, x2, y2, time1*collisiontime)
            endif
        endif
    endif
    return data
endfunction

endlibrary

 

[SerraAvenger]

1)
Seems like you misunderstood me.
I meant not intersecting parallels of course. It is quite hard to intersect parallels in wc3.

What I meant was drawing parallels to the actual movement graphs, then intersecting parallels from graph a with those of graph b. I can't be bothered to think about which parallels need to be intersected to get the time frame right now, though.
EDIT2: Just in case you need further explanation: YES, the distance between the parallel and the actual movement graph is 50% of the diameter.

2)

Squares collide more easily than circles.
EDIT: OF COURSE the side of the cube needs to be the diameter of the sphere...

 

[Zwiebelchen]

1)
Seems like you misunderstood me.
I meant not intersecting parallels of course. It is quite hard to intersect parallels in wc3.

What I meant was drawing parallels to the actual movement graphs, then intersecting parallels from graph a with those of graph b. I can't be bothered to think about which parallels need to be intersected to get the time frame right now, though.

2)

Squares collide more easily than circles.
EDIT: OF COURSE the side of the cube needs to be the diameter of the sphere...

to 1)
I thought about that too, but it's not going to work, unfortunately, as a mere intersection of lines does not neccesarily require that they really collide with each other.
You can determine the intersection point of those parallels, yes, but then you'd require the "time zone" approach again:
determine wether both missiles are at intersection point almost at the same time, and if they do, they collided. However ...

2) ... even with squares, the thing I mentioned about low angles causing problems when using the time zone approach is still there. The shape of the collision geometry has no influence on that. The time zone approach only works properly for high angle differences.

 

[SerraAvenger]

to 1)
I thought about that too, but it's not going to work, unfortunately, as a mere intersection of lines does not neccesarily require that they really collide with each other.
You can determine the intersection point of those parallels, yes, but then you'd require the "time zone" approach again:
determine wether both missiles are at intersection point almost at the same time, and if they do, they collided. However ...

2) ... even with squares, the thing I mentioned about low angles causing problems when using the time zone approach is still there. The shape of the collision geometry has no influence on that.[/QUOTE]

1) Of course, it doesn't require it; But the collision of the spheres requires the intersection of the lines.

2) Well... I have something like that in mind: Actualy have a "time zone" approach on the squares. Not on the circles. That way, we could easily get if the x coordinates will collide, then we can just as easily get if the y coordinates will collide, and if both do, they collide. Since what we intersect is not the parallels, it is the area in between them (which we do by intersecting the parallels). Might be that I'm just too tired and all of that won't work at all. Just my fuzzy brain.

@dit: I thought you were talking about the parallels. Hence your picture didn't make any sense. The parallels intersected a long time before

PS: Now I made this awesome&beautiful gimp handdrawing for naught! ;D


Schlaf gut.

Edit: Is that really needed? If they land both within the time frame in the area of intersect, they are colliding anyhow. And also we just did show that both x'n'y collide by intersecting the parallels. Need sleep-.-

 

[Zwiebelchen]

Hmm, I made a drawing to show you that even parallel intersection doesn't work properly in certain cases:

Imagine the big circle being much slower than the small circle.

You can see that the intersection method fails here even with parallel intersection.

The problem that appears when trying the area-intersection approach of squares: How are you going to determine when the squares overlap each other? This would be a function of two variables (f(x,y) instead of f(x) for line intersection), which leads to extremely complicated maths. You'd need to iterate in order to prevent that, which would be rather unperformant.

The only way to prevent iteration and looping processes is by determining line intersections. However: intersection methods will always have drawbacks, even for squares with cornerpoint parallels, as the following drawing shows:

The vector relative-movement approach I posted is the best way to do it, I think.

 

[Kenny]

Hmm... Seems to me that using a region would still probably win in terms of efficiency. Or am I wrong?

It doesn't seem as though Zwiebelchen's method on the previous page would allow for 75+ projectile's with collision enabled. Or am I missing something?

 

[Zwiebelchen]

Hmm... Seems to me that using a region would still probably win in terms of efficiency. Or am I wrong?

It doesn't seem as though Zwiebelchen's method on the previous page would allow for 75+ projectile's with collision enabled. Or am I missing something?

Yes, you are missing something. The collision detection algorythm on the last page has to be run only (n-1) times upon missile creation (for n being your number of currently existing missiles) instead of (n-1) times per tick.
No more periodic checks or events required. You know right from the moment of creation, where and when other missiles are going to collide with your created missile (as long as the missile movement is linear).
In fact, the number of missiles you can create with that is almost unlimited, though the creation process of missiles may cause a short fps drop when having lots of missiles.

 

[Kenny]

No more periodic checks or events required. You know right from the moment of creation, where and when other missiles are going to collide with your created missile (as long as the missile movement is linear).

Hmm... That kinda sucks for homing projectiles and spells that modify the projectiles direction.

But other than that, the idea seems solid. I wish I knew how to implement it.. Haha.

 

[Jesus4Lyf]

Actually, doing that is also the most accurate way to handle collisions. But really, if you aren't doing homing missiles, you're probably lame.

 

[Zwiebelchen]

You can still use the linear check algorythm even for homing missiles - you just need to check it periodically instead and divide your pathway into segments. This will approximate your circular move pathway to a polygonal way.
This would still require A LOT less checks and calculations than using periodic enumerations, as the tick interval can be much larger (depending on the turn rate of your missile).

You'd require a lot less checks over your course (blue circles) than by doing periodic enumeration (red circles).
However, as the amount of processing time needed by this algorythm gets higher the more missiles you have [O(n-1)], the amount of homing missiles would still be limited and - depending on the speed of enumeration - the region approach might be better.
You could dramatically reduce the amount of calculations by doing some hashing or more 'early escapes', so that the algorythm doesn't need to check all other missiles every time, but only those that are likely to hit each other.
Let's say the maximum range of all missiles is 2000, then you only need to compare your missile with all other missiles within 4000. You can use your rect here again.

I thought the implementation of that algorythm is self explaing?
Put all your missile parameters of two missiles you want to compare into the GetCollisionStruct function and it returns you a struct of collision data. Probably the only variable you need from that struct is the time when the collision happens.
Then all you need to do is destroying both missiles after this amount of time (if they both still exist ... it may be possible that they collided with another missile before - in that case, of course, you must not destroy them).

 

[Kenny]

After reading over it again it does seem quite self explanatory. However, am I right in saying that the method you posted requires the linear projectiles to have a fixed target position (at which they will cease moving/be destroyed)?

If so, that may become a problem as it effects what the users is able to do with the system.

Currently, you can target an XYZ coordinate, but have the projectile travel for 10 seconds, even if it passed the targeted coordinates after the first half a second.

 

[Jesus4Lyf]

No, the complexity would be a straight O(n^2). Just less periodic.
Firstly, in computer science, O(n-1) == O(n) (there's no such thing as a constant, only the highest order is observed).
Secondly, you would still need to check each projectile against each other projectile.

Surely the most efficient is a unit enters range event with no-locust projectiles?. Did I miss something? No periodic actions except for moving the projectile...

 

[Kenny]

Surely the most efficient is a unit enters range event with no-locust projectiles?. Did I miss something? No periodic actions except for moving the projectile...

You are right in saying that. It would definately be the best way of doing it. However, non-locust projectiles are crap and butt-ugly.

Also you can encounter problems with projectiles missing eachother at high speeds (skipping the enters range radius).

 

[Weep]

Firstly, in computer science, O(n-1) == O(n) (there's no such thing as a constant, only the highest order is observed).

O(8191) ~ O(1) >> O(n)?

Surely the most efficient is a unit enters range event with no-locust projectiles?. Did I miss something?

You missed that unit enters range only checks every 0.1 second or so, according to "Troll-Brain research", and is not very responsive.

 

[Jesus4Lyf]

O(8191) ~ O(1)

Yes, yes.. well..

>You missed that unit enters range only checks every 0.1 second or so, according to "Troll-Brain research", and is not very responsive.
It fires 8 times a second in my tests. So you could choose projectile speeds/collision sizes accordingly, or use the region thing...

I'd hate any O(n^2) approach more than the above.

 

[Zwiebelchen]

After reading over it again it does seem quite self explanatory. However, am I right in saying that the method you posted requires the linear projectiles to have a fixed target position (at which they will cease moving/be destroyed)?

Yes, however, the target position can be as far away as you want. However, logic should tell you that there is no real infinite missile movement and that it makes no sense to have real infinite movement, as the map borders limit your movement anyways.

If so, that may become a problem as it effects what the users is able to do with the system.

Not really. As I said, the missile destination point can be as far away as you want. If required, you can simulate infinite movement by just placing the destination point on the map border.
You will want to limit the maximum range of your projectiles, though, to improve performance of your map.

Currently, you can target an XYZ coordinate, but have the projectile travel for 10 seconds, even if it passed the targeted coordinates after the first half a second.

Just extrapolate the target point by missilespeed*duration and you got your new 'real' missile destination.

No, the complexity would be a straight O(n^2). Just less periodic.

Not really, as each calculation has to be done only once per missile (for homing missiles x times with x being the amount of line segments).
The number of comparisons increases with the number of missiles, but not at the power of two, more like in faculty.
example: The first missile needs no checks. The second missile has to check against the first. The third missile has to check against missile 1 and 2, etc.
So basicly, you need (1+2+3+...) checks, not n².

Secondly, you would still need to check each projectile against each other projectile.

Only once per projectile, so, if you do not spawn all at the same time, the processing amount spreads over the game, - and only if you have no early-escape checks in your system, you really need to check all.

Surely the most efficient is a unit enters range event with no-locust projectiles?. Did I miss something? No periodic actions except for moving the projectile...

If what Azlier and Weed said is true, then this is nothing else than a periodic enumeration.



The best way to do your missile system should look like this:

1) When creating a missile, enum all units inside a constant-defined rect (diameter: missile max-range * 4) around the missile, to exclude all other missiles, that are not able to cross your new missile's path.
2) store the enumeration result to a unit group and attach it to your missile.
(Note: you also require to add your newly created missile unit to the groups of the enumed missiles, to ensure two-way security)

Now you have to do a case selection:

3a) if the missile is not a homing missile, just compare your missile with all members of this group and you already got your expected collision time (this does not mean that the missile is not able to collide with another missile before that).
4a) Attach your new expected collision time as a timer and the expected collision object to your missile
5a) After the collision timer of your missile expired, check wether both your missile and your collision object are still alive and wether their distance is really <= (r1+r2) (this is required, in case the other missile is a homing missile and changed direction) and destroy both of them, if the distance is smaller or equal.

3b) if your missile is a homing missile, split the movement into linear segments and do the calculation for the first segment target destination
4b and 5b) same as 4a and 5a
6b) if your missile reaches the destination point, repeat from 3b until the missile reaches its target.


Now maybe you are asking "So if the other missile is homing and changes direction, there may be bugs?".
No. As the other missile does the same calculations as your current missile, you have a two-way proximity check. Even if the expected collision point of your linear missile will be lost once the other missile changes course, the homing missile will still know exactly when it passes the linear missile's course and trigger the collision.
Same goes for homing vs. homing collision. One of those two missiles is always right with the collision point, as the algorythm that was 'later' processed always has the correct data. There is no way it can fail.


So it all boils down to this:

• One rect enumeration upon missile creation
• n calculations in total for linear missiles with n being the number of missiles in the enumed group
• n * x calculations in total for homing missiles with n being the number of missiles in the enumed group and x being the number of line segments of your pathway
• 100% accuracy, even for extremely small collision radii of linear missiles
• very high accuracy even for homing missiles, depending on the number of segments and the turning rate

I believe this is far more efficient than any periodic event-based or enumeration method can ever be. And as a bonus, it's far more accurate and allows smaller and circular missile radii. You could even create bouncing missiles with that algorythm, as the collision points of both colliding missiles are 100% accurate and thus allow impulse-physics.