# DiscussionMost efficient and practical way to do projectile on projectile collisions

#### Jesus4Lyf

##### Good Idea™
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

##### You can change this now in User CP.
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

##### I know, I know...
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

##### Cuz I can
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

##### I know, I know...
> 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

##### Good Idea™
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

##### Cuz I can
> 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

##### I know, I know...
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

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

Code:
``````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

##### Godspeed to the sound of the pounding
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

##### O.O
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

##### Change can be a good thing
Staff member
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

General chit-chat
Help Users
• No one is chatting at the moment.
• The Helper:
that sucks
• jonas:
@midnight8 how is it looking
• midnight8:
meh, me, wife and her friend thaty traveled with us all have covid, seems to be winding down some for me at least. Felt like complete shit, been sleeping a lot, just bieng lazy as hell. I feel like that today has probably been like 11 or 12 days since exposure. Have not had any fever today, and have not taken any meds, so hopefully by monday or tuesday I will be good to go, sadly have passed it on to our teen son, I guess that was pretty much unavoidable
• The Helper:
hope you get to feeling better and get vaccinated my friend
• midnight8:
I will at some point, but so many vaccinated people still getting it. One of the bands we watch in vegas, all 4 had been vaccinated and are now positive.
• Ghan:
Symptoms?
• Ghan:
I think the symptoms are typically less severe if previously vaccinated.
• midnight8:
I have had all of the symptoms, taste is slightly starting to come back, but smell, no. Honestly, just been a little miserable, have never felt in any danger from it. Being trapped at home sucks. lol
• midnight8:
meh, got a little fever again this morning, guess gonna be a few more days
• The Helper:
I went to Comicon this last weekend I hope I dont get it I feel fine and I am not vaccinated and did not wear a mask
• The Helper:
Comicon really was not packed though like it was in the past. I am not really worried though it was the most people I have been around in a year.
• tom_mai78101:
Still, getting vaccinated is a good idea. We're getting Delta variant spikes here in Boston.
• The Helper:
I am not against vaccination at all I just have a serious procrastination problem I plan on getting vaccinated soon
• midnight8:
was kinda same with me, I was gonna do it, and life got in the way.
• midnight8:
we wore mask in some places, but at 118 degrees outside, little rough.
• The Helper:
yeah i had another friend in Vegas talking about that heat damn
• The Helper:
Well I do not think I got Covid from the Comicon
+1
• tom_mai78101:
Pushed out a new Pokemon Walking algorithm build. With a new system in place, I'll probably start tackling triggers and NPCs,
+1
• Varine:
Is it fucking hot everywhere?
• Varine:
What's a pokemon walking algorithm?
• jonas:
it's an engine for pokemon games that closely emulates the walking behavior of pokemon red/blue/yellow
• jonas:
basically if you wanted to implement pokemon yellow from scratch, and you'd want it to feel as close as possible to the real thing, you'd start with that
• Varine:
Like from the Gameboy games? I'm not at all familiar with Pokemon.
• jonas:
yeah
• The Helper:
I only played the Pokemon games on the Gamecube and Wii and such not on the portables my kids had all those games but I never really played on the portables. Now that I think about maybe once sooooo long ago.

### Members online

No members online now.