System PUI - Perfect Unit Indexing

Discussion in 'Systems and Snippets' started by Cohadar, Dec 1, 2007.

  1. Cohadar

    Cohadar master of fugue

    Ratings:
    +209 / 0 / -0
    New Version: 5.2

    Fixed a small "maybe-bug"
    Optimized recycling algorithm.

    @Builder Bob. (try 31/sec)
    And try not to die from laughter when you see the new algorithm
     
  2. 13lade619

    13lade619 is now a game developer :)

    Ratings:
    +399 / 0 / -0
    ..did you update with the new natives?..
     
  3. Cohadar

    Cohadar master of fugue

    Ratings:
    +209 / 0 / -0
    PUI is not affected by patch 1.23b
    (not using gamecache, not using H2I)

    My other systems that need 1.23b updating have already been updated.
     
  4. Builder Bob

    Builder Bob Live free or don't

    Ratings:
    +249 / 0 / -0
    Hmmm... It's slightly different, using two separate arrays for used and decaying indexes. It's much of the same apart from that. I find it hard to test how much more efficient it is. It doesn't handle 31/sec at all.

    Most, if not all proper unit indexing won't be affected by this. Still, I'm confused. Why don't you want to use linked lists when they can handle it better. (in my opinion at least)

    When using linked lists for the decaying indexes, the maximum decaying indexes you can possibly see at any time is 160. (32 per sec multiplied with 5 seconds decay time)

    Using linked lists when checking used indexes ensures you don't check units just created moments ago. This may or may not be beneficial, depending on the map.


    Is this implementation any better?
    JASS:
    library PUI initializer Init
    
    //==============================================================================
    globals    
        //-----------------------------------------------
        private constant real INDEX_DECAY_TIME = 5.  // seconds
        
        //-----------------------------------------------    
        private constant real PERIOD = 0.03125   // 32 fps
            
        //-----------------------------------------------
        private constant integer DECAY_TICKS = R2I(INDEX_DECAY_TIME/PERIOD)
        
        //-----------------------------------------------
        private integer Tick = 0
        private integer Decaying = 0
        
        private integer LastUsed = 0
        private integer LastDecaying = 0
        private integer array Next
        private integer array ReleaseTime
        
        private unit array Units
        private integer array Indexes
        private integer MaxIndex = 0
        private integer FreeIndex = 0
    endglobals
    
    private function DisplayListDetails takes nothing returns nothing
        call ClearTextMessages()
        call BJDebugMsg("Used/Free/Decaying: " + I2S(MaxIndex - FreeIndex) + "/" + I2S(FreeIndex) + "/" + I2S(Decaying))
    endfunction
    
    private function PeriodicRecycler takes nothing returns nothing
        local integer this
        local integer firstUsed
        set Tick = Tick + 1
        
        if LastUsed != 0 then
            set this = Next[LastUsed]
            call SetUnitUserData(Units[this], this)
            if GetUnitUserData(Units[this]) != this then
                set firstUsed = Next[this]
                
                set Units[this] = null
                set ReleaseTime[this] = Tick + DECAY_TICKS
                
                //begin decaying index
                if LastDecaying == 0 then
                    set LastDecaying = this
                    set Next[this] = this
                else
                    set Next[this] = Next[LastDecaying]
                    set Next[LastDecaying] = this
                    set LastDecaying = this
                endif
                
                //update links of used indexes
                if LastUsed == this then
                    set LastUsed = 0
                else
                    set Next[LastUsed] = firstUsed
                endif
                
    debug        set Decaying = Decaying + 1
            else
                set LastUsed = this
            endif
        endif
        
        if LastDecaying != 0 then
            set this = Next[LastDecaying]
            if Tick >= ReleaseTime[this] then
                
                //release index
                set Indexes[FreeIndex] = this
                set FreeIndex = FreeIndex + 1
                
                //update decaying links
                if LastDecaying == this then
                    set LastDecaying = 0
                else
                    set Next[LastDecaying] = Next[this]
                endif
                
    debug        set Decaying = Decaying - 1
            endif
        endif
        
    debug call DisplayListDetails()
    endfunction
    
    function GetUnitIndex takes unit whichUnit returns integer
        local integer index
        
        debug if whichUnit == null then
        debug   call BJDebugMsg("|c00FF0000ERROR: Index requested for null unit")
        debug   return 0
        debug endif
        
        set index = GetUnitUserData(whichUnit)
        
        if index == 0 then
            
            if FreeIndex == 0 then
                if MaxIndex == 8191 then
                    debug call BJDebugMsg("|c00FF0000WARNING: Unable to allocate more unit indexes")
                    return 0
                else
                    set MaxIndex = MaxIndex + 1
                    set index = MaxIndex
                endif
            else
                set FreeIndex = FreeIndex - 1
                set index = Indexes[FreeIndex]
            endif
            
            if LastUsed == 0 then
                set LastUsed = index
                set Next[index] = index
            else
                set Next[index] = Next[LastUsed]
                set Next[LastUsed] = index
                set LastUsed = index
            endif
            
            set Units[index] = whichUnit
            call SetUnitUserData(whichUnit, index)
            set index = GetUnitUserData(whichUnit)
            
            // this happens when requesting unit index for removed unit
            debug if index == 0 then
            debug     call BJDebugMsg("|c00FFCC00WARNING: Bad unit handle")
            debug endif
        endif
        
        return index
    endfunction
    
    //==============================================================================
    private function DisplayStats takes nothing returns nothing
        call BJDebugMsg("=============================================")    
        call BJDebugMsg("Biggest index ever = " + I2S(MaxIndex))    
        call BJDebugMsg("Indexes in use = " + I2S(MaxIndex - FreeIndex))
        debug call BJDebugMsg("Decaying indexes = " + I2S(Decaying))
        call BJDebugMsg("Released indexes = " + I2S(FreeIndex))
        call BJDebugMsg("=============================================")    
    endfunction
    
    //===========================================================================
    private function DisplaySelectedEnum takes nothing returns nothing
        call BJDebugMsg( "PUI(" + ( GetUnitName(GetEnumUnit()) + ( ") = " + I2S(GetUnitUserData(GetEnumUnit())) ) ) )
    endfunction
    
    //===========================================================================
    private function DisplaySelected takes nothing returns nothing
        local group g = CreateGroup()
        call SyncSelections()
        call GroupEnumUnitsSelected(g, Player(0), null)
        call ForGroup(g, function DisplaySelectedEnum)
        call DestroyGroup(g)
        set  g = null
    endfunction
    
    //==============================================================================
    private function Init takes nothing returns nothing
        local trigger trig
        
        call TimerStart(CreateTimer(), PERIOD, true, function PeriodicRecycler)
        
        debug set trig = CreateTrigger()
        debug call TriggerRegisterPlayerChatEvent( trig, Player(0), "-pui", true )
        debug call TriggerAddAction( trig, function DisplaySelected )      
        
        debug set trig = CreateTrigger()
        debug call TriggerRegisterPlayerChatEvent( trig, Player(0), "-puistats", true )
        debug call TriggerAddAction( trig, function DisplayStats )
    endfunction
    
    endlibrary
     
  5. waaaks!

    waaaks! Zinctified

    Ratings:
    +256 / 0 / -0
    I have a spell that uses unit indexing scripts, from AutoIndex to PUI, because I thought it would fix the problem, but it doesn't.

    My First Problem with the Impale System, I was using PUI_PROPERTIES in it, and for each cast of the spell, theres a chance that a unit will never come down. I tried to use AutoIndex and it fixed the problem.

    My Second Problem is, when I used AutoIndex in the system, and each time the system kills a hero, it never registers DONE[unitindex] to false, which makes the hero unaffected by the system anymore, because the system only works for heroes that has DONE[unitindex] set to false, while the system stucks to DONE[unitindex] = true. Now I reverted back to PUI (because I saw some of your post that PUI is made for spell making), but still the problem exists.

    I doubted about the hero thing, while in your PUI tutorial, you said that "Heroes are special because they are never removed from game so their properties never need to be destroyed (only created).", and the bug only exists on heroes killed by the system.

    JASS:
    library ImpaleSystem initializer init needs ABuff, GroupUtils, TimerUtils, PUI, xedamage, DamageBasic
    
    private struct impdata
        integer abil
        integer l
        integer order
    endstruct
    
    globals 
        private constant real FACT = 0.5                                //Structure damage factor
        private constant real TICK2 = 0.025                             //Timer per Tick
        private constant integer DUMMY_CASTER = 'e000'                  //Your Dummy Caster
        private constant integer FLY  = 'Amrf'                          //The Fly Height Enabler ability
        private group DUMMY_GROUP = CreateGroup()                       //Do not touch
        private integer array FALL
        private integer array ONCE
        private boolean array DONE
        private aBuffType impBuff
        private impdata impc
    endglobals
    
    private struct impaleToss
        unit cast
        unit targ
        real dmg
        damagetype dmgtype
        integer dspell
        integer splvl
        integer sporder
        
        static method impToss takes nothing returns nothing
            local timer tim = GetExpiredTimer()
            local impaleToss it = GetTimerData(tim)
            local real height = GetUnitFlyHeight(it.targ)
            local real v = 45
            local real d = height * 0.1
            local real f = v - d
            if height > 400.0 and ONCE[GetUnitIndex(it.targ)] == 0 then
                set FALL[GetUnitIndex(it.targ)] = 1
                set ONCE[GetUnitIndex(it.targ)] = 1
            endif
            if FALL[GetUnitIndex(it.targ)] == 0 then
                call SetUnitFlyHeight(it.targ,height+f,0.0)
                call SetUnitPathing(it.targ, false)
                call PauseUnit(it.targ,true)
            else //make unit fall
                call SetUnitFlyHeight(it.targ,height-f,0.0)
                call PauseUnit(it.targ,true)
                call SetUnitPathing(it.targ,false)
            endif
            if height <= 15 and ONCE[GetUnitIndex(it.targ)] == 1 then
                call ReleaseTimer(tim)
                call it.destroy()
            endif
            set tim = null
        endmethod
        
        private method onDestroy takes nothing returns nothing
            local xedamage xe = xedamage.create()
            set xe.dtype = .dmgtype
            set impc.abil = .dspell
            set impc.order = .sporder
            set impc.l = .splvl
            call ABuffApply(impBuff,.targ,.cast,0.5*.splvl,.splvl,0)
            call xe.damageTarget(.cast,.targ,0.5*.dmg)
            call SetUnitFlyHeight(.targ,0.0,0.0)
            call PauseUnit(.targ,false)
            call SetUnitPathing(.targ,true)
            call IssueLastOrder(.targ)
            call xe.destroy()
            set FALL[GetUnitIndex(.targ)] = 0
            set ONCE[GetUnitIndex(.targ)] = 0
            set DONE[GetUnitIndex(.targ)] = false
        endmethod
        
        static method create takes unit ccg, unit tcg, real dmg, damagetype dmgtype, integer dspell, integer splvl, integer sporder returns impaleToss
            local impaleToss it = impaleToss.allocate()
            local timer tim = NewTimer()
            set it.cast = ccg
            set it.targ = tcg
            set it.dmg = dmg
            set it.dspell = dspell
            set it.splvl = splvl
            set it.sporder = sporder
            set it.dmgtype = dmgtype
            call UnitAddAbility(it.targ,FLY)
            call UnitRemoveAbility(it.targ,FLY)
            call UnitShareVision(it.targ,GetOwningPlayer(ccg),true)
            call PauseUnit(it.targ,true)
            call SetUnitPathing(it.targ,false)
            call TimerStart(tim,TICK2,true,function impaleToss.impToss)
            call SetTimerData(tim,it)
            set tim = null
            return it
        endmethod
        
    endstruct
    
    struct impaleSystem
        public real isRadius = 150.0
        public real isOffset = 100.0
        public real isDamage = 100.0
        public string isSfxTarget = "Abilities\\Spells\\Undead\\Impale\\ImpaleHitTarget.mdl"
        public string isSfxPath1 = "Abilities\\Spells\\Undead\\Impale\\ImpaleMissTarget.mdl"
        public string isSfxPath2 = ""
        public boolean isAffectStructures = false
        public damagetype isDamageType = DTEARTH
        public integer isAbilityId = 0
        public integer isLevel = 0
        public integer isOrder = 0
        unit isCaster = null
        player isOwningPlayer = Player(15)
        real isCasterX = 0.0
        real isCasterY = 0.0
        real isTargetX = 0.0
        real isTargetY = 0.0
        real isRange = 600.0
        unit dum
        real rx
        real ry
        real wavetime
        real test
    
        static method ImpRun takes nothing returns nothing
            local impaleSystem this = GetTimerData(GetExpiredTimer())
            local group g = NewGroup()
            local unit u
            local real x = GetUnitX(.dum)
            local real y = GetUnitY(.dum)
            local real a = Atan2(.ry-y,.rx-x)
            local real px = x + .isOffset * Cos(a)
            local real py = y + .isOffset * Sin(a)
            local real dx = .rx - x
            local real dy = .ry - y
            local real dis = SquareRoot(dx*dx+dy*dy)
            local impaleToss it
            local xedamage xe = xedamage.create()
            local real r = .isRange
            local real o = .isOffset
            local real w = .wavetime
            local real attempts = r / o
            local real dur = attempts * w
            set .test = .test + .wavetime
            set xe.dtype = .isDamageType
            call GroupEnumUnitsInRange(g,x,y,.isRadius,null)
            call SetUnitX(.dum,px)
            call SetUnitY(.dum,py)
            loop
                set u = FirstOfGroup(g)
                exitwhen u == null
                if .isAffectStructures then
                    if IsUnitEnemy(u,.isOwningPlayer) and GetWidgetLife(u) > 0.405 and not IsUnitInGroup(u,DUMMY_GROUP) then
                        if IsUnitType(u, UNIT_TYPE_STRUCTURE) then
                            call xe.damageTarget(.isCaster,u,.isDamage*0.5)
                            call DestroyEffect(AddSpecialEffect(.isSfxTarget, GetUnitX(u), GetUnitY(u)))
                        endif
                        if not IsUnitType(u,UNIT_TYPE_STRUCTURE) then
                            if DONE[GetUnitIndex(u)] == false then
                                set DONE[GetUnitIndex(u)] = true
                                call xe.damageTarget(.isCaster,u,.isDamage*0.5)
                                if GetWidgetLife(u) > 0.405 then
                                    set it = impaleToss.create(.isCaster,u,.isDamage,.isDamageType,.isAbilityId,.isLevel,.isOrder)
                                    call DestroyEffect(AddSpecialEffect(.isSfxTarget, GetUnitX(u), GetUnitY(u)))
                                endif
                            endif
                        endif
                    endif
                else
                    if IsUnitEnemy(u,.isOwningPlayer) and GetWidgetLife(u) > 0.405 and not IsUnitType(u,UNIT_TYPE_STRUCTURE) and not IsUnitInGroup(u,DUMMY_GROUP) then
                        if GetWidgetLife(u) > 0.405 then
                            if DONE[GetUnitIndex(u)] == false then
                                set DONE[GetUnitIndex(u)] = true
                                set it = impaleToss.create(.isCaster,u,.isDamage,.isDamageType,.isAbilityId,.isLevel,.isOrder)
                                call xe.damageTarget(.isCaster,u,.isDamage*0.5)
                                call DestroyEffect(AddSpecialEffect(.isSfxTarget, GetUnitX(u), GetUnitY(u)))
                                call UnitShareVision(u,.isOwningPlayer,true)
                            endif
                        endif
                    endif
                endif
                //set DONE[GetUnitIndex(u)] == false
                call GroupAddUnit(DUMMY_GROUP,u)
                call GroupRemoveUnit(g,u)
            endloop
            call ReleaseGroup(g)
            if .test >= dur then
                call ReleaseTimer(GetExpiredTimer())
                call GroupClear(DUMMY_GROUP)
                call .destroy()
            else
                call DestroyEffect(AddSpecialEffect(.isSfxPath1,px,py))
                call DestroyEffect(AddSpecialEffect(.isSfxPath2,px,py))
            endif
            call xe.destroy()
            set u = null
        endmethod
        
        static method create takes unit cast, real tx, real ty, real range, real wavetime returns impaleSystem
            local impaleSystem is = impaleSystem.allocate()
            local timer t = NewTimer()
            local location loc = GetUnitLoc(cast)
            local real a
            set is.isCaster = cast
            set is.isOwningPlayer = GetOwningPlayer(cast)
            set is.isCasterX = GetLocationX(loc)
            set is.isCasterY = GetLocationY(loc)
            set is.isTargetX = tx
            set is.isTargetY = ty
            set is.isRange = range
            set is.wavetime = wavetime
            set a = Atan2(is.isTargetY-is.isCasterY,is.isTargetX-is.isCasterX)
            set is.dum = CreateUnit(is.isOwningPlayer,DUMMY_CASTER,is.isCasterX,is.isCasterY,0.0)
            call UnitAddAbility(is.dum,'Aloc')
            call UnitApplyTimedLife(is.dum,'BTLF',3.0)
            set is.rx = is.isCasterX + is.isRange * Cos(a)
            set is.ry = is.isCasterY + is.isRange * Sin(a)
            call TimerStart(t,wavetime,true,function impaleSystem.ImpRun)
            call SetTimerData(t,is)
            call RemoveLocation(loc)
            set loc = null
            set t = null
            return is
        endmethod
        
        private method onDestroy takes nothing returns nothing
            call KillUnit(.dum)
            set .dum = null
            set .test = 0
        endmethod
    endstruct
    
    private function impCreate takes aBuff eb returns nothing
        local unit dum
        set dum = CreateUnit(GetOwningPlayer(eb.caster),DUMMY_CASTER,GetUnitX(eb.caster),GetUnitY(eb.caster),0.0)
        call UnitApplyTimedLife(dum,'BTLF',3.0)
        call UnitAddAbility(dum,'Aloc')
        call UnitAddAbility(dum,impc.abil)
        call SetUnitAbilityLevel(dum,impc.abil,impc.l)
        call IssueTargetOrderById(dum,impc.order,eb.target.u)
        call UnitShareVision(eb.target.u,GetOwningPlayer(eb.caster),false)
        set dum = null
    endfunction
    
    private function init takes nothing returns nothing
        set impBuff = aBuffType.create()
        set impBuff.eventCreate = impCreate
        set impc = impdata.create()
    endfunction
    
    endlibrary
     
  6. Cohadar

    Cohadar master of fugue

    Ratings:
    +209 / 0 / -0
    ?
    It does, I used your testmap to test it.
    31 is an extreme case so indexes first rise like crazy to around 500 or something but then they stabilyze.
    Maybe you did not wait for it to stabilize and assumed it did not work?
    Try 30?

    @waaaks!
    Sorry mate, if you want spell help you need to ask in the proper forum.
    Your problem is that you did not read the PUI tutorial carefully.

    TIPS:
    0. Read PUI tutorail again.
    1. try making some simple spells first so you learn how to use PUI and then
    do complex stuff.
    2. Don't forget to call release instead of destroy on PUI structs.
    3. Hero structs need not be destroyed but you stil must create them at some point (on first cast preferably)
    And that only means when hero is the caster, not when it is a target.
    4. MUI spell that targets units with D.O.T effects if probably the most complex spell kind, you simply need more experience to make it right.
    (go kill some boars in the forest :D)
     
  7. Builder Bob

    Builder Bob Live free or don't

    Ratings:
    +249 / 0 / -0
    Whoa, that's just too strange. I can swear the counter went to insane proportions like used/free/decaying = 1000+/0/0 when I tested it yesterday.

    Now when I do the same again, I get mixed results. Some times it will stabilize as late as 800/5/800, other times it stabilizes right away at 180/5/180, so it definitely can handle the extreme case of 31/s.

    I don't know why I didn't get these results yesterday. It works. Sorry I said otherwise.
     
  8. Romek

    Romek Super Moderator Staff Member

    Ratings:
    +961 / 0 / -0
    I don't see any reasons for not using modules.
    And a textmacro like I suggested before.

    Also, another minor thing: 'integer pui_data' could be 'thistype pui_data'.
    So '.' syntax can be used directly without typecasting from integer.
    JASS:
    // Before:
    call SomeStruct(SomeStruct[GetTriggerUnit()]).release()
    
    // After:
    call SomeStruct[GetTriggerUnit()].release()


    Edit:
    Actually, the [] operator should just return thistype. :)
     
  9. Builder Bob

    Builder Bob Live free or don't

    Ratings:
    +249 / 0 / -0
    I agree with Romek.


    Another thing. I've always thought the struct textmacro to be more difficult in usage than it has to be.
    Unfortunately, this following code breaks backwards compatibility, so I'm sure you won't like it. I'll post it anyway.

    JASS:
    //===========================================================================
    //  Never create PUI structs directly.
    //  Initialize new instances in the optional method onCreate instead
    //
    //  Never destroy PUI structs directly.
    //  Use .release() instead, will call .destroy()
    //===========================================================================
    
    private struct OnCreateMethod
        method onCreate takes nothing returns nothing
        endmethod
    endstruct
    
    module PUI
        private delegate OnCreateMethod delegator
        private static unit     array pui_unit
        private static thistype array pui_data
        private static integer  array pui_id
        
        static method operator[] takes unit whichUnit returns thistype
            local integer pui = GetUnitIndex(whichUnit)
            local thistype this = .pui_data[pui]
            if .pui_unit[pui] != whichUnit then
                if this != 0 then
                    // recycled handle detected
                    call this.destroy()
                endif
                set this = thistype.allocate()
                set .pui_unit[pui] = whichUnit
                set .pui_data[pui] = this
                set .pui_id[integer(this)] = pui
                call this.onCreate()
            endif
            return this
        endmethod
        
        method release takes nothing returns nothing
            local integer pui = .pui_id[integer(this)]
            call .destroy()
            set .pui_data[pui] = 0
            set .pui_unit[pui] = null
        endmethod
        
    endmodule
    
    //! textmacro PUI
        implement PUI
    //! endtextmacro


    The idea is to let PUI create/destroy all struct instances itself, so the user does not have to worry about it ever. The user can get a unit's struct instance with local Data dat = Data[whichUnit], and pui will handle any instance recycling.

    .create(), .allocate() and .destroy() should never be used by the user. Instead the methods onCreate and onDestroy can be used to initialize and clear up members for each unit.
     
  10. Cohadar

    Cohadar master of fugue

    Ratings:
    +209 / 0 / -0
    After some testing:
    31 can clog the array if you "hit" the PUI with it right away. (once in 20 times)
    But if you first do 30 (even for a sec) and then 31 it stabilizes fast.
    32 as you surely tested is the absolute break point.
    All in all it now works as it was always supposed to.
    I would like to thank you once more for that.

    I decided some time ago I don't like modules and will never use them for anything.

    Reasons:
    * There is nothing you can do with modules that cannot be done with a textmacro
    * There are things that module cannot do but macro can, PUI_PROPERTIES for example.
    * They are just a stupid hack with no equivalent in any other programming language

    So call me a programming puritan but I don't like bizzare semantic constructs.
    Something also tells me modules will become obsolete really soon.
    (because Vex now has hashtables and can finally build some proper stuff)

    I will check for that when I do next version.


    No, writing MUI stells that have unit targets is hard, it has nothing to do with PUI,
    it would be of same difficulti no matter what indexing you use.
    Besides being able to manually create and attach structs is irreplaceable for spells with stacking effects:
    For example a shield buff with stacking duration time:
    JASS:
    
    local Data data = Data[GetSpellTargetUnit()];
    if data == 0 then
      set data = Data.create(GetSpellTargetUnit());
      Data[GetSpellTargetUnit()] = data
      set data.duration = 30.0
      // do some special stuff on init.
    else
      // struct already there, prolong the duration
      set data.duration += 30.0
      // do some extra stacking stuff
    endif

    You simply need that if sometimes.
    Btw I never release pui structs, recycler does it for me so I just don't bother.
     
  11. Builder Bob

    Builder Bob Live free or don't

    Ratings:
    +249 / 0 / -0
    You're welcome


    mhm... You might be right. That else would be hard to do otherwise.


    Likewise
     
  12. Jesus4Lyf

    Jesus4Lyf Good Idea™

    Ratings:
    +394 / 0 / -0
    Have to say, I'm starting work on a new AoS of some sort, and came across the need for unit indexing.

    Now, neither PUI nor AutoIndex do what I want, so I'm writing my own (to do what I thought PUI did, but turns out I was wrong). However, of course, I'm looking through both to learn the best way to do things.

    But I have to say, Cohadar, if I've understood this right, I'm a little disappointed.

    Current code:
    JASS:
    set tick = tick + 1
        
        // unit recycler
        if usedIndexCount > 0 then
            set checker = checker + 1
            if checker > usedIndexCount then
                set checker = 1
            endif
            if (GetUnitUserData(Unitz[checker]) == 0) then
                set decayIndexCount = decayIndexCount + 1
                set Decayz[decayIndexCount] = Indexz[checker]
                set TimeStampz[decayIndexCount] = tick
                set TimeEndz[decayIndexCount] = tick + DECAY_TICKS
                
                set Indexz[checker] = Indexz[usedIndexCount]
                set Unitz[checker] = Unitz[usedIndexCount]
                set usedIndexCount = usedIndexCount - 1
            endif
        endif
    
        // index recycler
        if decayIndexCount > 0 then
            set decayer = decayer + 1
            if decayer > decayIndexCount then
                set decayer = 1
            endif
            set TimeStampz[decayer] = tick
            if TimeEndz[decayer] <= TimeStampz[decayer] then
                set freeIndexCount = freeIndexCount + 1
                set Indexz[usedIndexCount+freeIndexCount] = Decayz[decayer]
    
                set Decayz[decayer] = Decayz[decayIndexCount]
                set TimeStampz[decayer] = TimeStampz[decayIndexCount]
                set TimeEndz[decayer] = TimeEndz[decayIndexCount]          
                set decayIndexCount = decayIndexCount - 1
            endif    
        endif
    Optimisation:
    JASS:
    set tick = tick + 1
        
        // unit recycler
        if usedIndexCount > 0 then
            set checker = checker + 1
            if checker > usedIndexCount then
                set checker = 1
            endif
            if (GetUnitUserData(Unitz[checker]) == 0) then
                set decayIndexCount = decayIndexCount + 1
                set Decayz[decayIndexCount] = Indexz[checker]
                //set TimeStampz[decayIndexCount] = tick
                set TimeEndz[decayIndexCount] = tick + DECAY_TICKS
                
                set Indexz[checker] = Indexz[usedIndexCount]
                set Unitz[checker] = Unitz[usedIndexCount]
                set usedIndexCount = usedIndexCount - 1
            endif
        endif
    
        // index recycler
        if decayIndexCount > 0 then
            set decayer = decayer + 1
            if decayer > decayIndexCount then
                set decayer = 1
            endif
            //set TimeStampz[decayer] = tick
            //if TimeEndz[decayer] <= TimeStampz[decayer] then
            if TimeEndz[decayer] <= tick then
                set freeIndexCount = freeIndexCount + 1
                set Indexz[usedIndexCount+freeIndexCount] = Decayz[decayer]
    
                set Decayz[decayer] = Decayz[decayIndexCount]
                //set TimeStampz[decayer] = TimeStampz[decayIndexCount]
                set TimeEndz[decayer] = TimeEndz[decayIndexCount]          
                set decayIndexCount = decayIndexCount - 1
            endif    
        endif

    Am I right? Did I miss something? =/
    Were you seriously storing the current tick in an array for no apparent reason before using it? >_<

    This can be optimised a lot further to reduce complexity. I intend to address this shortly, if I may...

    The theory is that you can attach to ticks by hashing over 8191, and then you just check if there's anything to decay for the current tick, since you can only start one index decaying per tick anyway. ;)

    So you store what you need to decay on what tick, else 0.

    Let me know if I'm not making sense to you.

    It should remove TimeEndz and decayer. :)

    Edit:
    Try this...

    I haven't tested this, but it should be what is (or nearly is) a fully optimised version of the index recycler.
    JASS:
    //==============================================================================
    globals    
        //-----------------------------------------------
        private constant real INDEX_DECAY_TIME = 5.  // seconds
        
        //-----------------------------------------------    
        private constant real PERIOD = 0.03125   // 32 fps
            
        //-----------------------------------------------
        private constant integer DECAY_TICKS = R2I(INDEX_DECAY_TIME/PERIOD)
        
        //-----------------------------------------------
        private integer array Indexz
        private unit    array Unitz
        
        private integer array Decayz
        //private integer array TimeStampz
        //private integer array TimeEndz
    
        private integer maxIndex = 0
        
        private integer usedIndexCount = 0
        private integer checker  = 0
        
        private integer freeIndexCount = 0
            
        //private integer decayIndexCount = 0
        private integer decaySlot  = DECAY_TICKS
        
        private integer tick = 0
    endglobals
    
    //==============================================================================
    private function PeriodicRecycler takes nothing returns boolean
        set tick = tick + 1
        // Below lines added:
        if tick > 8190 then
            set tick = 0
        endif
        // decaySlot is set to DECAY_TICKS on start, so it is always DECAY_TICKS ahead.
        set decaySlot = decaySlot + 1
        if decaySlot > 8190 then
            set decaySlot = 0
        endif
        
        // unit recycler
        if usedIndexCount > 0 then
            set checker = checker + 1
            if checker > usedIndexCount then
                set checker = 1
            endif
            if (GetUnitUserData(Unitz[checker]) == 0) then
                //set decayIndexCount = decayIndexCount + 1
                //set Decayz[decayIndexCount] = Indexz[checker]
                //set TimeStampz[decayIndexCount] = tick
                //set TimeEndz[decayIndexCount] = tick + DECAY_TICKS
                set Decayz[decaySlot] = Indexz[checker] // Added
                
                set Indexz[checker] = Indexz[usedIndexCount]
                set Unitz[checker] = Unitz[usedIndexCount]
                set usedIndexCount = usedIndexCount - 1
            endif
        endif
    
        // index recycler
        if Decayz[tick] > 0 then
            //set decayer = decayer + 1
            //if decayer > decayIndexCount then
            //    set decayer = 0
            //endif
            //set TimeStampz[decayer] = tick
            //if TimeEndz[decayer] <= TimeStampz[decayer] then
            //if TimeEndz[decayer] <= tick then // Added
                set freeIndexCount = freeIndexCount + 1
                //set Indexz[usedIndexCount+freeIndexCount] = Decayz[decayer]
                set Indexz[usedIndexCount+freeIndexCount] = Decayz[decaySlot] // Added
    
                //set Decayz[decayer] = Decayz[decayIndexCount]
                set Decayz[decaySlot] = 0 // Added
                //set TimeStampz[decayer] = TimeStampz[decayIndexCount]
                //set TimeEndz[decayer] = TimeEndz[decayIndexCount]          
                //set decayIndexCount = decayIndexCount - 1
            //endif    
        endif
            
        // for debugging 
        //if ModuloInteger(tick, 8) == 0 then
        //    call ClearTextMessages()
        //    call BJDebugMsg("Used/Free/Decaying: " + I2S(usedIndexCount) + "/" + I2S(freeIndexCount) + "/" + I2S(decayIndexCount))
        //endif
        
        return false
    endfunction
     
  13. Cohadar

    Cohadar master of fugue

    Ratings:
    +209 / 0 / -0
    That is because you want to reinvent the wheel.

    Yes, yes(the point of using systems), yes.

    Maybe I just like the warm and couzy feeling inside I get from knowing at exactly what time the unit index started decaying.

    Do yourself (and myself) a favor and read this.

    Especially the part about being reasonable...
     
  14. Jesus4Lyf

    Jesus4Lyf Good Idea™

    Ratings:
    +394 / 0 / -0
    I'll cut past the cheap comments.
    Was there something unreasonable about copy/pasting my code to change O(n) complexity to O(1) complexity (for timeouts) and save a few thousand variables?

    I found your code unreadable when I just glanced at it as well.
     
  15. Cohadar

    Cohadar master of fugue

    Ratings:
    +209 / 0 / -0
    Oh sorry did not look past your first code post because it was silly. (IMHO)

    To reply to the second one:
    You did not do any optimization there.
    Optimization is by definition improving of some aspect of a system without modifying the algorithm.

    You changed the algorithm so you would "save a few thousand variables" and you fucked the algorithm up.

    PUI recycles indexes 5 seconds after they decay.
    Your modification does so after 8192/32 = 256 seconds.
    What is worse it has no restrain of max index.

    By saving a couple of arrays in your "optimization" (it is just a 16KB of memory == nothing) you drastically increased memory usage in the whole map.

    Explanation:
    It is imperative that indexes always be as low as possible because of the way jass arrays allocate memory.

    16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192

    An empy jass array has 16 variables.
    When you try to use index above 16 but below 32 jass relocates the array in memory so it can extend it to 32.
    Same goes for all others.

    So basically if you have say an array that uses first 32 indexes and the try to use index 40 jass VM has to COPY the 32 indexes from one place to another in memory area that has 64 free places.

    The first couple of realocation 16->32, 32->64, 64->128 are ok, the rest are nightmare.

    The relocation lag above 1024 is equal to that of non-preloaded effect of first-cast spell. (1-2 sec)
    (That is why ABC has that big array init function for example)

    So yeah you "optimized" both memory usage and speed, good job. :D
     
  16. Jesus4Lyf

    Jesus4Lyf Good Idea™

    Ratings:
    +394 / 0 / -0
    JASS:
    //==============================================================================
    globals    
        //-----------------------------------------------
        private constant real INDEX_DECAY_TIME = 5.  // seconds
        
        //-----------------------------------------------    
        private constant real PERIOD = 0.03125   // 32 fps
            
        //-----------------------------------------------
        private constant integer DECAY_TICKS = R2I(INDEX_DECAY_TIME/PERIOD)
        
        //-----------------------------------------------
        private integer array Indexz
        private unit    array Unitz
        
        private integer array Decayz
        //private integer array TimeStampz
        //private integer array TimeEndz
    
        private integer maxIndex = 0
        
        private integer usedIndexCount = 0
        private integer checker  = 0
        
        private integer freeIndexCount = 0
            
        //private integer decayIndexCount = 0
        private integer decaySlot  = DECAY_TICKS
        
        private integer tick = 0
    endglobals
    
    //==============================================================================
    private function PeriodicRecycler takes nothing returns boolean
        set tick = tick + 1
        // Below lines added:
        if tick > DECAY_TICKS then
            set tick = 0
        endif
        // decaySlot is set to DECAY_TICKS on start, so it is always DECAY_TICKS ahead.
        set decaySlot = decaySlot + 1
        if decaySlot > DECAY_TICKS then
            set decaySlot = 0
        endif
        
        // unit recycler
        if usedIndexCount > 0 then
            set checker = checker + 1
            if checker > usedIndexCount then
                set checker = 1
            endif
            if (GetUnitUserData(Unitz[checker]) == 0) then
                //set decayIndexCount = decayIndexCount + 1
                //set Decayz[decayIndexCount] = Indexz[checker]
                //set TimeStampz[decayIndexCount] = tick
                //set TimeEndz[decayIndexCount] = tick + DECAY_TICKS
                set Decayz[decaySlot] = Indexz[checker] // Added
                
                set Indexz[checker] = Indexz[usedIndexCount]
                set Unitz[checker] = Unitz[usedIndexCount]
                set usedIndexCount = usedIndexCount - 1
            endif
        endif
    
        // index recycler
        if Decayz[tick] > 0 then
            //set decayer = decayer + 1
            //if decayer > decayIndexCount then
            //    set decayer = 0
            //endif
            //set TimeStampz[decayer] = tick
            //if TimeEndz[decayer] <= TimeStampz[decayer] then
            //if TimeEndz[decayer] <= tick then // Added
                set freeIndexCount = freeIndexCount + 1
                //set Indexz[usedIndexCount+freeIndexCount] = Decayz[decayer]
                set Indexz[usedIndexCount+freeIndexCount] = Decayz[tick] // Added
    
                //set Decayz[decayer] = Decayz[decayIndexCount]
                set Decayz[tick] = 0 // Added
                //set TimeStampz[decayer] = TimeStampz[decayIndexCount]
                //set TimeEndz[decayer] = TimeEndz[decayIndexCount]          
                //set decayIndexCount = decayIndexCount - 1
            //endif    
        endif
            
        // for debugging 
        //if ModuloInteger(tick, 8) == 0 then
        //    call ClearTextMessages()
        //    call BJDebugMsg("Used/Free/Decaying: " + I2S(usedIndexCount) + "/" + I2S(freeIndexCount) + "/" + I2S(decayIndexCount))
        //endif
        
        return false
    endfunction
    My bad, there was a mistake in the code. decaySlot in the index recycler should've been tick.

    Everything you said there works in favor of my opt. This recycles the indices on exactly 5 seconds (unless I made another error somewhere) as opposed to your checking method.

    I might have to investigate that array thing...

    PS. Thanks for the explanation.
     
  17. Cohadar

    Cohadar master of fugue

    Ratings:
    +209 / 0 / -0
    You are welcome.

    (not being malicious)
    Maybe you need to actually test the things you write?
    Compiling the code in your head does not work sometimes. :)
     
  18. Jesus4Lyf

    Jesus4Lyf Good Idea™

    Ratings:
    +394 / 0 / -0
    I should. But at the time I was just trying to write an example to help convey what I was saying...

    I'm not sure by your comments there if you've reconsidered the code. Have you seen why this is beneficial, yet?
     
  19. grim001_

    grim001_ New Member

    Ratings:
    +6 / 0 / -0
    Jesus4Lyfe, what in the world could you want from unit indexing that neither PUI nor AutoIndex does?
     
    • Like Like x 1
  20. Cohadar

    Cohadar master of fugue

    Ratings:
    +209 / 0 / -0
    No, and I don't plan to.
    I believe in "don't fix if it is not broken" phylosophy.
    PUI works as it should and it works well, I have no intention of wasting my time on maybe-improvements.

    2-3 hours of my life are simply more expensive than 2-3 nanoseconds of PUI efficiency.

    Go read that optimization wiki again.
     

Share This Page