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

[Kenny]

Okay I thought I'd make this a discussion since I need as many ideas as possible from people, and I am willing to discuss pros and cons of each idea.

I have a projectile system that can handle approximately 100+ projectiles with no visible lag or delay, and my computer is nothing special.

First off, I know 100+ probably isn't that great, but it does what I need it to do.

Secondly, if I active collision for each projectile, the limit sadly drops from that 100+ to around 15-35 depending on what method I use for collision.

I would really like this limit to reach about 50+ without any visible lag or delay if possible.

Ideas I've tried:

- Using a linked list to [ljass]loop[/ljass] through all projectile instances, checking if they are in range of each other.

- Using [ljass]GroupEnumUnitsOfPlayer()[/ljass] and filtering units in the boolexpr.

So yeah, please discuss and give me your ideas. I will even post my system if you want to have a look.

We can also discuss the most efficient and practical way to do projectile on unit collisions as well.

Current ideas for that are:

- Using [ljass]GroupEnumUnitsInRange()[/ljass], which is basically the default way. This provides a pretty nice interface, but isn't great for high frequency use.

- Using [ljass]TriggerRegisterUnitInRange()[/ljass], which is a bit more advanced. This way is probably the most efficient, however it will probably require dynamic triggers for each projectile instance and will end up with a not so good interface when compared to the above option.

 

[kingkingyyk3]

Record the box of where projection is situated. When another projectile come in, just check for the box.

 

[Zwiebelchen]

Keep track of your missiles positions inside a 2-dimensional array that way, that you store the box the missile is currently in (as mentioned by kingking) as X and Y of the array and save the missile unit to the field value.

Now, when checking the missiles, you just need to get the missile X and Y, look up the array and check if there is already a missile stored to it. If so, you just need to kill both missiles.

 

[phyrex1an]

Just got this crazy idea:
Give permanent immolation to all projectiles, make it so it only targets other projectiles with very low damage. Projectile collision is now the same as takes damage. It might even work

 

[Trollvottel]

Since projectiles are mostly locust units i doubt they will take damage.

@Zwiebelchens method:

To make it faster you could divide the whole map into H*W rects. each projectile will now get the current rect it is in. then you just need to enum those units in the same rect (and, if the unit is at a border, the units at a neighbour rect).
If the rects are too big, it will consume power to pick all units in them.
If the rects are too small, you will often have to change the rects or to look if there is a unit in the next rect.
=> find the right size

 

[Romek]

Unit In Range triggering would be the best way, and it's the only way that doesn't involve doing somewhat complex checks at high frequency.

Phyrex1ans way might work, though if you're using triggers, you might as well use "Unit in Range", rather than complicating things.

 

[Trollvottel]

Unit In Range triggering would be the best way, and it's the only way that doesn't involve doing somewhat complex checks at high frequency.

Phyrex1ans way might work, though if you're using triggers, you might as well use "Unit in Range", rather than complicating things.

the problem is that you still would have to check 100 projectiles for each projectile if there are 100 projectiles in the map. if you check this for each projectile that would be 100*100 checks = 10000 checks. each tick.
but if you divide everything in, say 20 parts and say that in each rect there are 5 projectiles which dont hit the border, that would be 5 checks for each projectile, so all in all 5 checks * 100 = 500 checks. now even if you say you have 50% of the projectiles touching one border so you have to check a second rect for collisions, that would just add 5 checks * 50 = 250 checks. so in the end that would be 750 checks compared to 10000.

 

[Zwiebelchen]

You could also use the specific unit event: "UnitWithinRangeOfUnit" with dynamic triggers. This is probably the most efficient way to do it, as it doesn't involve Enumeration at all. I do not know wether it works with locust units, though.

 

[Azlier]

Since that UnitInRange trigger does distance checks every 0.1 seconds (such a low frequency is probably somewhat inaccurate) internally, is it really the most efficient method? Hmm.

 

[Darthfett]

I'm assuming you're giving the projectiles locust so that they may not be selected.

I'd say the easiest way to detect collisions is to "attach" an invulnerable unit without a model (but does not have locust) to each projectile, and add the Unit Enter Range event to the invisible dummy unit. Make sure to move it alongside the projectile, and whenever the dummy unit detects collision, explode the projectile.

The problem with immolation is that it requires your projectiles to be in range long enough for the immolation to take effect (I believe the spell runs on a 1/2 second or 1 second tick). You'd have to give immolation a high range, which could cause problems for lower/higher speed projectiles.

 

[Trollvottel]

I'm assuming you're giving the projectiles locust so that they may not be selected.

I'd say the easiest way to detect collisions is to "attach" an invulnerable unit without a model (but does not have locust) to each projectile, and add the Unit Enter Range event to the invisible dummy unit. Make sure to move it alongside the projectile, and whenever the dummy unit detects collision, explode the projectile.

The problem with immolation is that it requires your projectiles to be in range long enough for the immolation to take effect (I believe the spell runs on a 1/2 second or 1 second tick). You'd have to give immolation a high range, which could cause problems for lower/higher speed projectiles.

well you will see that the most unperformant thing about projectiles is not calculating their position but moving them :/and if you pick units you will always have to pick in a large radius since you dont know how big the collision of surrounding units is.

 

[Darthfett]

well you will see that the most unperformant thing about projectiles is not calculating their position but moving them :/and if you pick units you will always have to pick in a large radius since you dont know how big the collision of surrounding units is.

There's always having adding multiple events (based on the range of the units), and then checking to see if they're within the entering units' collision radius. There would be no need to pick units, but let the game's event engine do it.

 

[Zwiebelchen]

Since that UnitInRange trigger does distance checks every 0.1 seconds (such a low frequency is probably somewhat inaccurate) internally, is it really the most efficient method? Hmm.

Hmm, are you sure it works like that? I always thought the "Unit Comes Within Range of Unit" event was better than enumeration and instant :/ ... don't crush my hopes.

 

[Accname]

I'm assuming you're giving the projectiles locust so that they may not be selected.

you can add locust and remove it again to make the unit unselectable but still able to take damage, that way immolation does work.

The problem with immolation is that it requires your projectiles to be in range long enough for the immolation to take effect (I believe the spell runs on a 1/2 second or 1 second tick). You'd have to give immolation a high range, which could cause problems for lower/higher speed projectiles.

and the period of which the immolation damage is dealt can be set in the object editor. it can be anything you want.

I'd say the easiest way to detect collisions is to "attach" an invulnerable unit without a model (but does not have locust) to each projectile, and add the Unit Enter Range event to the invisible dummy unit. Make sure to move it alongside the projectile, and whenever the dummy unit detects collision, explode the projectile.

more over i think having 2 units for 1 projectile will result in even more lag.

 

[Azlier]

>Hmm, are you sure it works like that?

I'm going by Troll-Brain research here and so far he's pretty accurate.

 

[Kenny]

There are lots of interesting ideas here so far.

I was wondering though..

Does: [ljass]TriggerRegisterUnitInRange()[/ljass] detect locust units? Anyone actually know before I go off and test it?

I think I may resort to that if nothing else works efficiently enough for my needs (then again, that way might not be so efficient either).

Also, If it does work for locust units, then I could use that event for both projectile and unit collision, which might make a big difference.

*Hopes for [ljass]TriggerRegisterUnitInRange()[/ljass] to detect locust units*

Hmm.. It would be awesome if I had some type of Dynamic Trigger Support system that was up to date and approved.

Wait, that system destroys triggers anyway... Scratch that.

 

[Weep]

Hmm, are you sure it works like that? I always thought the "Unit Comes Within Range of Unit" event was better than enumeration and instant :/

Well, it's not instant. Moving a unit in and out of range without any delay does not trigger a UnitInRange event. EnterRegion, however, is instant. What about sliding a region around with each projectile?

(But then, if UnitInRange internally is a periodic test, for all I know, EnterRegion might internally test every time a unit is moved. :nuts: )

 

[Darthfett]

Well, it's not instant. Moving a unit in and out of range without any delay does not trigger a UnitInRange event.

There will be delay unless you move a unit and then move it again in the same thread without any delay. SetUnitX/Y should work fine. Unfortunately, I don't think it works with Locust.

My idea was to slide a unit with no model (effectively no additional graphical lag) alongside the regular locust units. I think it would be a lot more efficient than the O(n^2) method of comparing distance for every locust unit with every other locust unit.

Sliding a region alongside would still have problems with units that are of different collision size (as well as the fact that it's square in shape, but I suppose that's not a huge factor), and would require you to check the region every time you slide a unit (as opposed to the internal engine using a Unit Enters Range event).

 

[Weep]

There will be delay unless you move a unit and then move it again in the same thread without any delay.

The point was that it's not instant.

My idea was to slide a unit with no model (effectively no additional graphical lag) alongside the regular locust units.

Why do that? Add/remove Locust from the projectile unit so it'll still be unselectable (due to Locust glitch) and make it invulnerable and spell immune. It can then be area-enumed and will still be almost entirely excluded from unit interaction. [edit] This might be incorrect...

Sliding a region alongside would still have problems with units that are of different collision size

That could be a benefit...

and would require you to check the region every time you slide a unit (as opposed to the internal engine using a Unit Enters Range event).

[ljass]TriggerRegisterEnterRegion[/ljass]...

 

[Kenny]

[ljass]TriggerRegisterUnitInRange()[/ljass] actually works quite well for non-locust units.

Bit disappointed that it doesn't work on locust units though.

So I'm guessing that [ljass]TriggerRegisterEnterRegion()[/ljass] works for locust units?

Sliding a region around with a unit might take a bit of work though, as I don't think you can just move a region.

Would creating a rect, attaching the rect to a projectile, adding it to the region, then moving the rect around with the projectile work properly?

Only con I can think of is that the collision detection isn't circular, but rectangular.

Edit:

Actually that con wouldn't matter, as I am then checking if each projectile is within spherical range of the other.