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

[Jesus4Lyf]

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).

That's my point.

>There is no way it can fail.
A bold statement for a game with teleport spells. If a missile heads straight for a unit, and just misses a linear missile along the way, and then the unit blinks back to the other side of the linear missile, it will be chance whether or not the homing missile hits the linear missile, based on whether or not it recalculates right then.

It's all a bit silly. The linear method actually assumes that nothing interacts with missiles. I've made a map that speeds up/slows down/freezes/pauses missiles in AoE's before. That would screw up linear missiles trajectory paths completely. Furthermore, they were all homing missiles. There is no doubt this would be a periodical O(n^2) solution! It is checking each missile against each other missile (without checking the reverse, so yes, n(n-1), which is still O(n^2)). Worse yet, the calculations are far more intensive than just range checks, everything needs to be recalculated at once when a spell interacts with them (lag!) and it still isn't as accurate as simple range checks.

On the other hand, that's an amazing idea for a map that only needs to handle the collision of linear projectiles.

 

[Zwiebelchen]

That's my point.

>There is no way it can fail.
A bold statement for a game with teleport spells. If a missile heads straight for a unit, and just misses a linear missile along the way, and then the unit blinks back to the other side of the linear missile, it will be chance whether or not the homing missile hits the linear missile, based on whether or not it recalculates right then.

Well ... this is just settings and depends on the turning rate of your homing missiles. Having homing missiles that do change direction by 180 degrees instantly would look ugly anyways.
But I agree that the "linear overlay" of curved missile paths may have problems with teleportation if the current line doesn't get recalculated after the instant direction switch. However, this may really be the only case where it would really fail - compared to those MANY cases where periodic distance checks fail (low missile radii, high missile speeds, etc.).

It's all a bit silly. The linear method actually assumes that nothing interacts with missiles. I've made a map that speeds up/slows down/freezes/pauses missiles in AoE's before.

Well, you could always just recalculate the collision when the missile gets freezed/paused/unfreezed/whatever.

Furthermore, they were all homing missiles. There is no doubt this would be a periodical O(n^2) solution!

Yes, if all are homing missiles, then it really is O(n^2). Then, however, I do not really know how efficient enumeration on WC3 really is and it all depends on the update interval.
Then again, the algorythm is posted is far from being efficiently written. I think you could do the same with much less operations.

Worse yet, the calculations are far more intensive than just range checks, everything needs to be recalculated at once when a spell interacts with them (lag!)

Well, if only one missile gets freezed, you'd only need to compare one missile vs all, so it would 'only' be O(n) in this case.

and it still isn't as accurate as simple range checks.

This, however, is not true. The linear projection method is 100% accurate (if you recalculate it everytime there is a change in movement speed). For curved missile paths, it depends on the number of line segments, but I would still say that its a lot more accurate than periodic distance checks, which require large collision radi or high intervals in order to really have a dense and failure-proof checkpath.

On the other hand, that's an amazing idea for a map that only needs to handle the collision of linear projectiles.

Yes, I agree that it may not be suited for really flexible missile systems (especially if Kenny does not use periodic checks, but UnitEntersRect, which beats everything else in terms of speed), but the algorythm is still amazing if you ask me and may be used somewhere else, (I always wanted to create a pool minigame) where you need 100% exact collision coordinates (for example to create reflections, bouncing, or anything else that requires impulse laws of physic) for linear projectiles.

In fact, With UnitEntersRect or periodic distance checks, you can not do reflection at all. You NEED to use pre-calculation.

 

[the Immortal]

Would anyone be interested in writing a periodic algorithm for collision checking with O(logn*n) complexity? Been studying different trees, including kd, for the last 2 weeks for classes, and wouldn't mind a small training.

.. if, from OP's words, a O(n*n) system could reach 100 w/o lag, using this method should be much faster, like up to 1k missiles w/o lag.


But will only do it if someone thinks it might be needed..

 

[SerraAvenger]

periodic distance checks are n^2 too, aright?

UnitEntersRect has a loads of downsides... but since wc3 isn't processed concurrently it will work as long as everything a missile might get in contact with has such a rect too.

Because moving a rect somewhere doesn't fire the event for those units that are in the new area - at least IIRC.

 

[the Immortal]

> periodic distance checks are n^2 too, aright?
Not necessarily. There exists a way to do it with n*logn (binary) complexity, but it's not that easy to write / optimize / balance the needed tree. Still, as I said I can give it a shot if someone's interested.

 

[Jesus4Lyf]

Experience dictates to me, by the way, that trying excessively hard to optimise leaves inefficient and unmaintainable code (although it may be kind of cool).

 

[SerraAvenger]

> periodic distance checks are n^2 too, aright?
Not necessarily. There exists a way to do it with n*logn (binary) complexity, but it's not that easy to write / optimize / balance the needed tree. Still, as I said I can give it a shot if someone's interested.

I'd love to see the algorithm. +5 rep from me for sure if you do it.

 

[the Immortal]

Will give it a shot when I have some free time then. But gotta think it over carefully first. A normal kd-tree wouldn't be approppriate as there's no effective/fast way to insert points and keep it balanced. A (simpler) qtree/bin might be better. Can't promise anything though. /slacker

 

[Elfian]

EDIT: Apff, never saw this thread was so f... old ;D

local integer i = 0
local integer k = 0

loop
   set i = i + 1
   set k = i

   loop
      set k = k + 1
      if(distance.. projectile[i], projectile[k] bla bla) then
          collision!!
      endif

      exitwhen k == MAX_OBJECTS
    endloop

    exitwhen i == MAX_OBJECTS
endloop

How about that? Did someone say that already? :^| By the way, what about making 200 recycleable projectiles from the initialization and registering to every one of them the event 'units gets in range', there was such an event right? :^|

 

[Weep]

How about that? Did someone say that already? :^|

That's O(n^2), which is about as unoptimal as possible.

By the way, what about making 200 recycleable projectiles from the initialization and registering to every one of them the event 'units gets in range', there was such an event right? :^|

I'm guessing you didn't read the thread... Not only was it suggested, but there was a discussion about why that would work poorly.

 

[Infinitegde]

I made a qtree collision detection system in java for a different game. Implementation was needlessly annoying. took me 3 tries, and the 4th time i realized how simple it was. That was in java... A fully fledged programming language. It pains me to think of what it would be like to code in vJass.

 

[emjlr3]

i know this is past due- but to add something to the discussion

somewhere, sometime ago, someone told me that groupenum was faster then a unitinrange event - though this is probably assuming small work loads (aka missile intersecting enemy targets, rather then 100 missile enumeration)

and from what has been stated before, it may just have been that unitinrange was slow to trigger, not a cpu intensive process