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

[Darthfett]

The point was that it's not instant.

I've never heard of these tests before, but I was simply saying that I don't believe it has to be 'instant'. There will be around 0.03125 (or whatever the tick timer is) during which time the game engine should detect the units being in range of each other (assuming that they are only in range for 1 tick).

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.

I thought there was a glitch with the ALT button revealing these units' health bars. It would be a pain to have many on-screen, especially if the player has health bars set to be always shown.

That could be a benefit...

A benefit that it doesn't detect larger units (doing so would require more events as well as sliding multiple regions with the units).

[ljass]TriggerRegisterEnterRegion[/ljass]...

Whoops, I forgot that the GUI action creates a region and adds the rect to it to register these events. (I've had to tell so many people this that I forgot why ).

However, Kenny inadvertently brings up a good point. If you can use Enter Region/Range events with units that have locust added/removed, why not simply use the simple Enter Range events? It would require no extra dummy unit, along with no extra region sliding.

 

[Kenny]

Hmm... It seems that units that have had locust added and then removed still don't trigger the [ljass]TriggerRegisterUnitInRange()[/ljass] event. Weird.

Maybe I am just doing something wrong, lol.

I thought there was a glitch with the ALT button revealing these units' health bars. It would be a pain to have many on-screen, especially if the player has health bars set to be always shown.

I added and removed locust from the projectile, and held alt while they were moving and I saw no health bar and they couldn't be selected or anything, as if they were still locust units.

 

[Darthfett]

I added and removed locust from the projectile

How? Did you do it in this simple way, or did you do it by hiding the unit, removing locust, and unhiding the unit, as I believe is the correct way of doing so.

 

[Kenny]

Hiding it, adding and removing locust, and then showing it makes the unit completely selectable and everything. Would be the same if I just didn't add locust to begin with.

I thought there was some sort of in-between.

 

[Darthfett]

Hiding it, adding and removing locust, and then showing it makes the unit completely selectable and everything. Would be the same if I just didn't add locust to begin with.

Interesting, I thought there was still some glitch with doing that.

I thought there was some sort of in-between.

http://www.thehelper.net/forums/showpost.php?p=1144820&postcount=12

 

[Kenny]

I couldn't get that method to work properly, but no matter what else I tried, previously locust'ed units could not be detected by [ljass]TriggerRegisterUnitInRange()[/ljass].

However, using that method for unit collisions has drastically increased the performance of the system.

Previously with about 120 units my FPS was at about 16-18, now at around 210 units my FPS is about 18-20. So that is a massive boost there.

Only if it detected locust units properly... That would be awesome.

Edit:

Wow, with some of the 'extra' features disabled the system can run at around 230 units with above 20 FPS on my laptop (which isn't the best laptop out).

Just tested the system with the normal linked list iteration over the projectiles.

200 projectiles at 20 FPS with no projectile collision.

25 projectiles at 20 FPS with projectile collision.

 

[Weep]

Sadly, moving a rect does not update the region - removing the rect, then moving it, then re-adding it to the region is necessary. I don't know of a better way to implement that other than periodically handling every projectile. :thdown:

Attached anyway. I get about 70 FPS@800x600 (windowed mode) with about 220 projectiles if I move the camera to the corner so fewer projectiles are on-screen at a time, down from ~200 FPS with no projectiles. (Mind, even at what the game claims is ~100 FPS, the game is not smooth, with it freezing for a fraction of a second about thrice a second.) Framerate without collision and that many projectiles is ~180.

Projectiles only collide with one another.

constant function MISSILE_UNIT_TYPE takes nothing returns integer
    return 'h000'
endfunction

function Missiles_Collision takes nothing returns boolean
    local unit collidingunit = GetTriggerUnit()
    local integer id = GetHandleId(GetTriggeringTrigger())
    local unit missileunit = LoadUnitHandle(udg_TestHash, GetHandleId(GetTriggeringTrigger()), 0)
    
    if GetUnitTypeId(collidingunit) == MISSILE_UNIT_TYPE() and collidingunit != missileunit and IsUnitType(collidingunit, UNIT_TYPE_DEAD) == false then
        call KillUnit(collidingunit)
        call KillUnit(missileunit)
    endif
    
    set collidingunit = null
    set missileunit = null
    return false
endfunction

function Missiles_MissileDeath takes nothing returns boolean
    local integer id = GetHandleId(GetTriggerUnit())
    call DestroyTrigger(LoadTriggerHandle(udg_TestHash, id, 0))
    call RemoveRegion(LoadRegionHandle(udg_TestHash, id, 1))
    call RemoveRect(LoadRectHandle(udg_TestHash, id, 2))
    call FlushChildHashtable(udg_TestHash, id)
    return false
endfunction

function Missiles_MoveRect_Callback takes nothing returns nothing
    local unit missileunit = GetEnumUnit()
    local integer id = GetHandleId(missileunit)
    local region collisionregion = LoadRegionHandle(udg_TestHash, id, 1)
    local rect oldrect = LoadRectHandle(udg_TestHash, id, 2)
    call RegionClearRect(collisionregion, oldrect)
    call MoveRectTo(oldrect, GetUnitX(missileunit), GetUnitY(missileunit))
    call RegionAddRect(collisionregion, oldrect)
    set missileunit = null
    set collisionregion = null
    set oldrect = null
endfunction

function Missiles_MoveRect takes nothing returns nothing
    call ForGroup(udg_MissilesGroup, function Missiles_MoveRect_Callback)
endfunction

function Missiles_AddCollision takes nothing returns boolean
    local unit enteringunit = GetFilterUnit()
    local integer id = GetHandleId(enteringunit)
    local rect collisionrect = Rect(GetUnitX(enteringunit), GetUnitY(enteringunit), GetUnitX(enteringunit), GetUnitY(enteringunit))
    local region collisionregion = CreateRegion()
    local trigger collisiontrigger = CreateTrigger()
    call RegionAddRect(collisionregion, collisionrect)
    call SaveTriggerHandle(udg_TestHash, id, 0, collisiontrigger)
    call SaveRegionHandle(udg_TestHash, id, 1, collisionregion)
    call SaveRectHandle(udg_TestHash, id, 2, collisionrect)
    call SaveUnitHandle(udg_TestHash, GetHandleId(collisiontrigger), 0, enteringunit)
    call TriggerRegisterEnterRegion(collisiontrigger, collisionregion, null)
    call TriggerAddCondition(collisiontrigger, Condition(function Missiles_Collision))
    set enteringunit = null
    set collisionrect = null
    set collisionregion = null
    set collisiontrigger = null
    return false
endfunction

//===========================================================================
function InitTrig_Collide_Missiles takes nothing returns nothing
    local trigger deathtrigger = CreateTrigger()
    local region worldbounds = CreateRegion()
    set udg_TestHash = InitHashtable()
    
    call RegionAddRect(worldbounds, GetWorldBounds())
    call TriggerRegisterEnterRegion(CreateTrigger(), worldbounds, Condition(function Missiles_AddCollision))
    set worldbounds = null
    
    call TriggerRegisterAnyUnitEventBJ(deathtrigger, EVENT_PLAYER_UNIT_DEATH)
    call TriggerAddCondition(deathtrigger, Condition(function Missiles_MissileDeath))
    
    call TimerStart(CreateTimer(), 0.03, true, function Missiles_MoveRect)
endfunction

 

[Kenny]

Wow, thanks for the in depth explanation.

I definately think I will give this a try.

I think the FPS on our computers are very different, lol. Eighty is max for mine.

However, the good news is that with your method, my computer could handle around 60-75 projectiles with collision while having most in the centre of the screen.

I just wonder how it will go once added to my system.

Oh and one question:

How big is the rect that is made when you use:

Rect(GetUnitX(enteringunit), GetUnitY(enteringunit), GetUnitX(enteringunit), GetUnitY(enteringunit))

Does that even work properly?

 

[Weep]

However, the good news is that with your method, my computer could handle around 60-75 projectiles with collision while having most in the centre of the screen.

Well, that's good. The true test for a system like this, though, has to be measured by framerate without displaying the projectiles, since the graphics will make an even bigger hit on FPS unless your GPU is far better than your CPU.

By the way, it can definitely be optimized by stripping out the use of a hashtable (I was just being lazy ) and by cleaning the code.

How big is the rect that is made when you use:
Does that even work properly?

Well, it's supposed to be 0 by 0, and therefore only trigger with the target unit's collision size. It seems to work. Making it the size of the missile ([ljass]GetUnitX(missile) - diameter/2[/ljass], etc.) would perhaps be better.

BTW, I just tested, and it seems to be similarly efficient to GroupEnumUnitsInRange, but works for Locust units. Also, I'd swear just removing Locust from a unit rendered it area-enumable but not selectable, yet I'm failing to be able to area-enum them. Maybe I was confusing it with being attackable but unselectable. Sorry for the misinformation.

 

[Kenny]

Just finished implementing region collision detection.

I was surprised. The system could handle 100+ projectiles with collision enabled. Which is four times better than what it could do previous.

I had tested [ljass]GroupEnumUnitsInRange[/ljass] before with non-locust projectiles and it wasn't this good.

So I think I will stick with region collision detection, it seems to be the best way to do it currently.

Also, I am now thinking about getting rid of [ljass]TriggerRegisterUnitInRange[/ljass] for unit collision and just going with the same trigger + region detection for both units and projectiles.

I'm going to try and optimise this now and see how it goes. I wish I could +rep you like 100 times more Weep.

LOL! The current struct members for a projectile:

...
        // Public members:
        unit     caster           = null
        unit     target           = null
        player   owner            = null
        real     timedLife        = -1.00
        real     unitCollision    = DEFAULT_UNIT_COLL
        real     projCollision    = DEFAULT_PROJ_COLL
        boolean  pauseProj        = false
        boolean  collideable      = false
        boolean  enableHoming     = false
        
        // Readonly members:
        readonly unit   proj      = null
        readonly real   angle     = 0.00
        readonly real   pitch     = 0.00
        readonly vector pos       = 0
        readonly vector vel       = 0
        
        // Start and target coordinates:
        readonly real   startX    = 0.00
        readonly real   startY    = 0.00
        readonly real   startZ    = 0.00
        readonly real   targX     = 0.00
        readonly real   targY     = 0.00
        readonly real   targZ     = 0.00
        
        // Private members:
        private  trigger trig     = null
        private  effect  sfx      = null
        private  string  path     = ""
        private  boolean stop     = false
        private  boolean arcing   = false
        
        // Members for projectile collision:
        private region   projReg  = null
        private rect     projRect = null
        private trigger  projTrig = null
        
        // Members that handle speed changes:
        private  real    speed    = 0.00
        private  real    oriSpeed = 0.00
        private  real    oldSpeed = 0.00
        
        // Members needed for parabolic height changes:
        private  real    height   = 0.00
        private  real    maxDist  = 0.00
        private  real    distDone = 0.00
...

Time for some refining.

 

[Zwiebelchen]

I couldn't get that method to work properly, but no matter what else I tried, previously locust'ed units could not be detected by [ljass]TriggerRegisterUnitInRange()[/ljass].

However, using that method for unit collisions has drastically increased the performance of the system.

Hmm ... this is weird, if what Azlier said about [ljass]TriggerRegisterUnitInRange[/ljass] is true. Maybe it's true it does enumerations on its own internally, but for some reason, it seems to be still faster than using regular enumerations.
Weird, but then again, you do not know how exactly [ljass]TriggerRegisterUnitInRange[/ljass] really works. Maybe wc3 does some hashing in the background, that increases efficiency for this event over regular enumeration.


PS: Yes, it's clear that the Rect-method is way faster than all other ways, as EnterRect seems to be the only "real" event that fires instantly and thus isn't based on enumeration, but checked whenever a unit is moved.

 

[Kenny]

Yeah I am just really happy that [ljass]TriggerRegisterUnitInRange()[/ljass] wsa fast enough to give me an improvement, while still letting me keep a simple interface.

And [ljass]TriggerRegisterEnterRegion()[/ljass] works pretty damn well for projectile collisions. There are very rare cases where you would think two projectiles would collide, but they don't, but it is no big deal.

PS: Yes, it's clear that the Rect-method is way faster than all other ways, as EnterRect seems to be the only "real" event that fires instantly and thus isn't based on enumeration, but checked whenever a unit is moved.

Unfortunately [ljass]TriggerRegisterEnterRegion()[/ljass] didn't work very well for unit collision, so I had to stick to two separate triggers, one with each event per projectile.

But all in all, those events lead to a massive improvement in efficiency which is VERY noticeable in game.

 

[the Immortal]

Kd-trees? /lol


No, jokes aside, this should be the most optimal solution. Too bad it's a kinda overkill to write it in JASS (having to write a log(n)*n sort() for example, using almost no additional data structures, having that array limitation, etc, etc..). Plus, the first time I had to learn 'em and use 'em it took me like 4 hours.. just to make the tree structure and debug it. =P

 

[Viikuna]

Id probably make all projectiles to be owned by player neutral passive, use GroupEnumUnitsOfPlayer to get past locust ability and then just have some IsUnitInRange condition.

 

[Kenny]

@ Viikuna:

I actually tried that. With a decent amount of projectiles it is actually worse than just using a linked list and iterating through all instances. I could only handle around 20 or so units. The method I use now allows for over 100.

 

[Viikuna]

Ok. I think I gotta learn to read the whole thread before posting.

TriggerRegisterUnitInRange indeed sucks balls. I have used it and its delayed as hell.

But that region thingy is interesting. If its really instant its pretty damn cool way to do this stuff.

Since there aint round regions, you still gotta do some IsUnitInRange checks, if you want different collinsion sizes for your projectiles, or some vector math when dealing with 3d projectiles. ( But then again, you gotta do that with GroupEnum too, and that stuff is only done on collinsion anyways and not alla time. )

 

[TheDamien]

I think the best method is the spatial hashing suggested by kingkingyyk3 in the second post.

 

[SerraAvenger]

Calculate when the projectiles will meet? Works very great if they aren't accelerated (in x/y)

 

[Azlier]

gtfo wit u n ur intiligint solutonz.

I wish I knew how to calculate projectile stuff ahead of time like that.

 

[Zwiebelchen]

I wish I knew how to calculate projectile stuff ahead of time like that.

And of course, pre-made calculation would still require looping through all missiles. However, you'd only have to do that once per missile. Possibly, this is the best solution for (linear) projectile systems.

The maths for that is rather easy: All you have to do, is to get the fire angle and velocity, use tan(alpha)*velocity to get your dx and dy values and check intersection points of your current missile's linear function (y = dy/dx * x + n) with already existing missile's linear functions. If you have intersections (x = (n2 - n1) / (dy1/dx1-dy2/dx2) and y = dy1/dx1 * x + n1), you need to calculate (by using dx and dy) how many ticks it requires for those two missiles to reach that intersection point. If both require the same number of ticks, then both missiles will be destroyed after the calculated number of ticks.