Theory - What is faster?

01-23-2009, 10:55 AM

StRoNgFoE_2000

Assuming a tower defense, some towers cast spells. I'm trying to find the quickest and most efficient way of a simple scenario. Basically, I want a tower to find a nearby unit, and cast a spell on it when the cooldown is up. There are many ways of doing this, and each of these have their flaws. I'm hoping a map would never get to the worse case scenario, but it can, and at times, it will.

The Worst Case Scenario
Assume there are 400 towers on the map, 100 of these towers cast a spell every 8 seconds, and there are 100 creeps running to the goal. If the graphics lag of this many animated units isn't enough on older machines, (it serves no issue on newer ones), the script running it all has to be as efficient as possible.

There are several methods of doing so, I need to know the best one.

Method A - Detecting an Attack

The most common method practiced is to detect the attack of a tower, then order the tower to spell cast on the attacked unit. The tower's attack speed would be slightly offset from the cooldown (cooldown + .2). I think this could be a big problem, considering the worst case scenario. Assume all 400 towers have an attack cooldown of 1 second, are attacking at once, and there are 50 tower types and their 'triggers' responsible for the spell casting. That would equal a whopping 20,000 events fired and conditions checked each second. I'm assuming that would eat some resources, and does not seem like a very practical method in the end as the game progresses.

Method B - Timer Expiration

This method seems more practical and less resource intense, besides the fact it would involve creating lots of timers and groups, which in turn could cause even more lag than 20k events and conditions a second, but I doubt it. Ok, so how it would be done is, a tower is built, a timer is started offsetting the cooldown of the spell to be cast (cooldown + .2), and every timer expiration a group has to be created around the tower, pick a random enemy unit, and cast the spell on the randomly picked unit, then the usual cleanup. The only flaw I see of this method is the group creation, but they are only created at the expiration of each timer. If 100 out of the 400 towers are spell casting towers in the worst case scenario, all with cooldowns of 8 seconds, that's only 100 groups created over 8 seconds. But also, there's now 100 timers constantly running in the background along with all the other timers used in the map. Not sure if that's faster than the 20k event condition problem of Method A, but in theory it sounds like it.

Method C - UnitInRange Event

This method probably seems like the most impractical, it would probably have to use structs attached to triggers due to the nature of UnitInRange event. It would also probably be the most laggy, because there's a lot of units coming in range of a lot of towers. But generally, it would probably go something like: a tower is built, a trigger is created to know when a unit is in range of tower, attach some data to the trigger so when the event fires it can recover the tower, spell cast the TriggerUnit. Again, assuming the worst case scenario, 100 units are coming in range of 400 towers (assuming they didn't die), so now you have twice as many events fire and conditions checked as Method A, 40,000 a second! Also, theres now 400 structs created, 400 more triggers created, can you say goodbye RAM?

Edit: I realized my math is a little off here considering they aren't all gonna reach each tower at the same time, but you get the idea.

The Verdict?

Looking at the remaining events, I really can't think of a Method D, and all 3 of these methods seem impractical and laggy in the worst case scenario. Method B seems like it would be the fastest, that is, unless creating and destroying groups is 20x times as slow as event firing and condition checking. So all that remains is my question.

If I have to use method A-C, which one should I use and why? If there's a better method, then what? How can I optimize whatever method I am to use?

All I really need to know, is the fastest method for when a tower cooldown is up, it finds a nearby enemy unit, and casts a spell on it. So simple, but at the same time, so complex because of the worst case scenario.

01-23-2009, 12:17 PM	#2
Anitarf	You can accomplish method B without creating groups. Seems to me like it would be the cleanest one.

01-23-2009, 01:17 PM	#3
Captain Griffen	Method B + static group + GroupEnumUnitsInRange + condition (always returns false, does actions) + single timer looping/ForGrouping the towers.

01-23-2009, 07:56 PM	#4
Joker	Sry Off-Topic: What happens if you have the condition return true?

01-23-2009, 08:09 PM

Fireeye

Ontopic: Captain Griffin is correct about the method, but i think there should be also a test if using the attack event is that bad or would it be acceptable.
I don't really know it, however method A or B with slight modifications are the way to go.

Offtopic: Then it will try to run a non existing action i guess, don't know what the worst scenario would be.
---Edit---
Ops, i'm somwhat out of my mind atm akolyt0r is right, i though about a trigger, nvm what i said...

01-23-2009, 08:34 PM

akolyt0r

Quote:

Originally Posted by Joker

Sry Off-Topic:

What happens if you have the condition return true?

the enumed units will be added to the group...nothing spectacular

01-23-2009, 09:22 PM

StRoNgFoE_2000

Ok, I kinda understand what to do, but my abilities are limited. I attempted my best though, this is what I came up with so far, it's going to need some revision. I don't understand how to make the condition return false and still work. Also, I cannot use a single timer because all spells have different cooldowns.

Anyway, this is what I've come up with so far. I have only used 2 of the total of 35 spell casting towers there are, so this struct is gonna get huge if it remains this way. Also, my method fails for the reason there is still a group being created for every instance of a spell being cast, but this is the only way I know how to do it.

JASS:

library TowerSource
    struct towerspell
        static timer   chainT
        static timer   faerieT
        static group   chainG
        static group   faerieG
        
        private static method onInit takes nothing returns nothing
            set towerspell.chainT   = CreateTimer()
            set towerspell.faerieT  = CreateTimer()
            set towerspell.chainG   = CreateGroup()
            set towerspell.faerieG  = CreateGroup()
            call TimerStart(towerspell.chainT, 4, true, function towerspell.chainstart)
            call TimerStart(towerspell.faerieT, 6, true, function towerspell.faeriestart)
        endmethod

    // All creeps have "Giant" tagged as a Unit Classification.
        static method filter takes nothing returns boolean
            return IsUnitType(GetFilterUnit(), UNIT_TYPE_GIANT) == true
        endmethod

    // Chain Lightning Towers
        static method chaincast takes nothing returns nothing
            local group g = CreateGroup()
            local unit  u = GetEnumUnit()
            local unit  t
            local real  x = GetUnitX(u)
            local real  y = GetUnitY(u)
            call GroupEnumUnitsInRange(g, x, y, 650, Condition(function towerspell.filter))
            set t = GroupPickRandomUnit(g) 
            call SetUnitState(u, UNIT_STATE_MANA, 1) 
            call IssueTargetOrder(u, "chainlightning", t)
            call DestroyGroup(g)
            set g = null
            set u = null
            set t = null
        endmethod
        static method chainstart takes nothing returns nothing
            call ForGroup(towerspell.chainG, function towerspell.chaincast)
        endmethod

    // Faerie Fire Towers
        static method faeriecast takes nothing returns nothing
            local group g = CreateGroup()
            local unit  u = GetEnumUnit()
            local unit  t
            local real  x = GetUnitX(u)
            local real  y = GetUnitY(u)
            call GroupEnumUnitsInRange(g, x, y, 650, Condition(function towerspell.filter))
            set t = GroupPickRandomUnit(g) 
            call SetUnitState(u, UNIT_STATE_MANA, 1) 
            call IssueTargetOrder(u, "faeriefire", t)
            call DestroyGroup(g)
            set g = null
            set u = null
            set t = null
        endmethod
        static method faeriestart takes nothing returns nothing
            call ForGroup(towerspell.faerieG, function towerspell.faeriecast)
        endmethod

    endstruct
endlibrary

// Separate triggers add the units to the groups.

// Chain Lightning
function ChainLightningCond takes nothing returns boolean
    return GetUnitTypeId(GetTriggerUnit()) == 'hC36' or GetUnitTypeId(GetTriggerUnit()) == 'h00B'
endfunction
function ChainLightningAdd takes nothing returns nothing
    local unit u = GetTriggerUnit()
    call GroupAddUnit(towerspell.chainG, u)
    set u = null
endfunction
function InitTrig_ChainLightning takes nothing returns nothing
    local integer i = 0
    set gg_trg_ChainLightning = CreateTrigger()
    loop
        exitwhen i > 5
        call TriggerRegisterPlayerUnitEvent(gg_trg_ChainLightning, Player(i), EVENT_PLAYER_UNIT_CONSTRUCT_FINISH, null)
        call TriggerRegisterPlayerUnitEvent(gg_trg_ChainLightning, Player(i), EVENT_PLAYER_UNIT_UPGRADE_FINISH, null)
        set i = i + 1
    endloop
    call TriggerAddCondition(gg_trg_ChainLightning, Condition(function ChainLightningCond))
    call TriggerAddAction(gg_trg_ChainLightning, function ChainLightningAdd)
endfunction

// Faerie Fire
function FaerieFireCond takes nothing returns boolean
    return GetUnitTypeId(GetTriggerUnit()) == 'o016' or GetUnitTypeId(GetTriggerUnit()) == 'oC26'
endfunction
function FaerieFire takes nothing returns nothing
    local unit u = GetTriggerUnit()
    call GroupAddUnit(towerspell.faerieG, u)
    set u = null
endfunction
function InitTrig_FaerieFire takes nothing returns nothing
    local integer i = 0
    set gg_trg_FaerieFire = CreateTrigger()
    loop
        exitwhen i > 5
        call TriggerRegisterPlayerUnitEvent(gg_trg_FaerieFire, Player(i), EVENT_PLAYER_UNIT_CONSTRUCT_FINISH, null)
        call TriggerRegisterPlayerUnitEvent(gg_trg_FaerieFire, Player(i), EVENT_PLAYER_UNIT_UPGRADE_FINISH, null)
        set i = i + 1
    endloop
    call TriggerAddCondition(gg_trg_FaerieFire, Condition(function FaerieFireCond))
    call TriggerAddAction(gg_trg_FaerieFire, function FaerieFire)
endfunction

I tested it out, seems to work so far. But like I said, this struct is gonna get huge if it remains this way, and I add all 35 towers. Also, I'm not 100% fond of all towers casting at the exact same time, but hey, speed over aesthetics wins.

01-23-2009, 10:31 PM

Blackroot

If you don't want them to all start at the same timer, add two reals 1 MAX_TIME and 1 CURRENT_TIME and set the timer to clock at something like 2Times/second. Every time it ticks subtract CURRENT_TIME by the amount of time it takes for each timer tick and if it's <= 0 run the spell and reset CURRENT_TIME to MAX_TIME.

If that makes since, I'm not at a computer where I can code.

[edit] you're creating/destroying a group in chaincast function, just reuse a global group.

01-23-2009, 11:22 PM

Anitarf

If your spells have long cooldowns compared to the time during which an enemy unit is in the range of the tower (for example, the cooldown is 10 seconds but the wave of creeps remains in range of the tower for 16 seconds), you're better off with one timer per tower since in the example mentioned above this guarantees you'll get two spells off per wave while otherwise you have a chance to only get one (for example, if the global timer for all the towers runs 8 seconds after the first creep in the wave comes in range). With a single timer per tower, you could have it wait the cooldown of the spell, then look for targets and if none are found, wait only a second before trying again, otherwise cast the spell and wait the whole cooldown again. Also, this way you avoid multiple towers always casting the spell at the same time which could look awkward.

You can avoid having to create groups by simply reusing the same static group stored in a global variable for your enums.

01-24-2009, 07:45 AM

#10

StRoNgFoE_2000

I've decided to take a similar yet different approach.

@Anitarf - I've decided to use your suggestion, 1 timer per tower. Not 100% sure if Vex's TimerUtils will hold out all game, considering the 408000 handle limit. Tower defenses create a ton of units, and I'm not sure if WC3 recycles the handle ID's once a handle is removed from the map. As for the cooldowns, I'm not too worried if the spell goes off or not, none of the spells I use have any cooldown above 8 seconds, as long players maze it shouldn't be an issue.

Anyway, I've decided to use structs all the way, this way I really don't need global variables, at least not yet, I might need some for when a tower is removed or upgraded, because the current destroy method isn't firing. For some reason it's not seeing a null when I remove the tower from the map. Here's what I have, it works perfectly, but the struct isn't being destroyed when data.u is removed from the map. I'll debug it a bit more after I post this.

JASS:

// The master struct, I can use any spells with this bad boy because of
// the arguments taken by the create method.

library TowerSpells requires TimerUtils
struct towerspell
    timer    t = null
    unit     u = null
    unit     z = null
    group    g = null
    boolexpr b = null
    real     r
    real     x
    real     y
    string   s
    private static method unitenemy takes nothing returns boolean
        return IsUnitType(GetFilterUnit(), UNIT_TYPE_GIANT) == true
    endmethod
    static method create takes string castorder, real range returns towerspell
        local towerspell data = towerspell.allocate()
        set data.s = castorder
        set data.r = range
        set data.t = NewTimer()
        set data.g = CreateGroup()
        set data.u = GetTriggerUnit()
        set data.x = GetUnitX(data.u)
        set data.y = GetUnitY(data.u)
        set data.b = Condition(function towerspell.unitenemy)
        return data
    endmethod
    static method spellcast takes nothing returns nothing
        local timer   t = GetExpiredTimer()
        local towerspell data = GetTimerData(t)
        if data.u != null then
            call GroupEnumUnitsInRange(data.g, data.x, data.y, data.r, data.b)
            if CountUnitsInGroup(data.g) > 0 then
                set data.z = GroupPickRandomUnit(data.g) 
                call SetUnitState(data.u, UNIT_STATE_MANA, 1) 
                call IssueTargetOrder(data.u, data.s, data.z)
                call GroupClear(data.g)
            endif
        else

//--------------------------------------------------

// isolated the issue here, even if the tower is removed, the debug
// message isn't showing, so I'm assuming the data isn't destroyed.

            call BJDebugMsg("Unit is missing, destroying data!")
            call data.destroy()

//--------------------------------------------------
        endif
        set t = null
    endmethod
    method onDestroy takes nothing returns nothing
        call ReleaseTimer(.t)
        call DestroyGroup(.g)
        call DestroyBoolExpr(.b)
    endmethod   
endstruct
endlibrary

JASS:

// An example trigger of using the struct, again, chain lightning tower.

function ChainLightningCond takes nothing returns boolean
    return GetUnitTypeId(GetTriggerUnit()) == 'hC36' or GetUnitTypeId(GetTriggerUnit()) == 'h00B'
endfunction
function ChainLightningAdd takes nothing returns nothing
    local towerspell data = towerspell.create("chainlightning", 650)
    call SetTimerData(data.t, data)
    call TimerStart(data.t, 4, true, function towerspell.spellcast)
endfunction
function InitTrig_ChainLightning takes nothing returns nothing
    local integer i = 0
    set gg_trg_ChainLightning = CreateTrigger()
    loop
        exitwhen i > 5
        call TriggerRegisterPlayerUnitEvent(gg_trg_ChainLightning, Player(i), EVENT_PLAYER_UNIT_UPGRADE_FINISH, null)
        call TriggerRegisterPlayerUnitEvent(gg_trg_ChainLightning, Player(i), EVENT_PLAYER_UNIT_CONSTRUCT_FINISH, null)
        set i = i + 1
    endloop
    call TriggerAddCondition(gg_trg_ChainLightning, Condition(function ChainLightningCond))
    call TriggerAddAction(gg_trg_ChainLightning, function ChainLightningAdd)
endfunction

01-24-2009, 07:56 AM

#11

Blackroot

You are insane if you think you will exceed 408,000 handles ever.

To recycle a handle

Code:

local unit u
call RemoveUnit(u)
set u = null

I don't remember if RemoveUnit recycles the handle or setting the variable to null does, either way one of the two recycles them. Note that a dead unit's handle will not recycle by default (Someone confirm/deny this, I'm not 100%)

To iterate on the handle thing, I once had a trigger set up to count the handles in skibi's td. It ended up not even exceeding 5000 towards the end. I see no logical way to create 408,000 handles even over months of playing the same map.

The reason destroy isin't firing is because a dead unit is not equal to null. Check it's HP (GetWidgetLife(tower) < .405) or remove the unit when it's destroyed.

01-24-2009, 10:26 AM

#12

Anitarf

Quote:

Originally Posted by Blackroot

The handle adress gets recycled automatically once the handle stored there is removed and there are no more references (variables set) to that adress. So neither of those two recycles the handle, they just make it recyclable.

After units finish decaying (or when they die, if they don't leave a corpse), they are removed automatically. As long as you null all your variables pointing to that unit the unit's handle adress will get recycled.

If you're worried about handle count inflation, you can always use the red TimerUtils flavour (although then you must worry about maximum number of timers running at once), but with a high enough array size you can use the blue flavour quite safely, if you're confident about your coding then even using blue TimerUtils with an array size of 8190 is safe.

01-24-2009, 11:45 AM

#13

StRoNgFoE_2000

Finally I think it's perfect, working flawlessly. The struct is being destroyed if the tower is removed, or if it's upgraded into a new tower.

JASS:

library TowerSpells requires TimerUtils
struct spelltarget
    timer    t = null
    unit     u = null
    unit     z = null
    group    g = null
    boolexpr b = null
    real     r
    real     x
    real     y
    string   s
    integer  i
    integer  d
    private static method unitenemy takes nothing returns boolean
        return IsUnitType(GetFilterUnit(), UNIT_TYPE_GIANT) == true
    endmethod
    static method create takes string castorder, real range returns spelltarget
        local spelltarget data = spelltarget.allocate()
        set data.s = castorder
        set data.r = range
        set data.t = NewTimer()
        set data.g = CreateGroup()
        set data.u = GetTriggerUnit()
        set data.x = GetUnitX(data.u)
        set data.y = GetUnitY(data.u)
        set data.i = GetUnitTypeId(data.u)
        set data.b = Condition(function spelltarget.unitenemy)
        return data
    endmethod
    static method spellcast takes nothing returns nothing
        local timer   t = GetExpiredTimer()
        local spelltarget data = GetTimerData(t)
        set data.d = GetUnitTypeId(data.u)
        if GetWidgetLife(data.u) > .405 and data.i == data.d then
            call GroupEnumUnitsInRange(data.g, data.x, data.y, data.r, data.b)
            if CountUnitsInGroup(data.g) > 0 then
                set data.z = GroupPickRandomUnit(data.g) 
                call SetUnitState(data.u, UNIT_STATE_MANA, 1) 
                call IssueTargetOrder(data.u, data.s, data.z)
                call GroupClear(data.g)
            endif
        else
            call data.destroy()
        endif
        set t = null
    endmethod
    method onDestroy takes nothing returns nothing
        call ReleaseTimer(.t)
        call DestroyGroup(.g)
        call DestroyBoolExpr(.b)
    endmethod
endstruct
endlibrary

The method of checking the HP worked, as well as my secret weapon of checking the tower's unit type ID when the struct is created, then comparing it with the tower's ID after every timer end. That way, if it's ever upgraded into a new tower, it will destroy the struct as well. Thank you all for all your help and suggestions, they have definitely aided me in a much cleaner spell target system over unit attacking events.

The only remaining question I have is, why compare the unit's HP to .405 rather than just 0?

01-24-2009, 12:06 PM

#14

Troll-Brain

The only remaining question I have is, why compare the unit's HP to .405 rather than just 0?

If an unit have 0.405 hp or less, then the unit is dead. But personnaly i use IsUnitType(u,UNIT_TYPE_DEAD).

This is good to know for a damage system or in general when you need to make damages, but quite useless here.
Maybe for speed freak, but i dunno if it is really revelent, i prefer to choice the safest solution.

01-24-2009, 12:20 PM

#15

akolyt0r

Quote:

Originally Posted by Troll-Brain

i think ...units which die have 0.405 hp during there dying animation ...