1. The long-awaited results for Concept Art Contest #11 have finally been released!
    Dismiss Notice
  2. The mythological era has spawned some interesting characters around. Check them out and be sure to vote for them in the 30th Poll of the Texturing Contest.
    Dismiss Notice
  3. The 20th iteration of the Terraining Contest is upon us! Join and create exquisite Water Structures for it.
    Dismiss Notice
  4. Hivers united and created a bunch of 2v2 melee maps. Vote for the best in our Melee Mapping Contest #4 - Poll!
    Dismiss Notice
  5. Check out the Staff job openings thread.
    Dismiss Notice

[System] MissileRecycler

Discussion in 'JASS Resources' started by Bribe, Oct 27, 2011.

  1. BPower

    BPower

    Joined:
    Mar 18, 2012
    Messages:
    1,745
    Resources:
    21
    Spells:
    15
    Tutorials:
    1
    JASS:
    5
    Resources:
    21
    Nice idea to use ExecuteFunc(). I never used it, but according to teh Jass Helper Manual
    RecycleMissileDelayed_private.execute() would be even better. :p
     
  2. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    If you like having duplicated code, go for it ;)

    I am well past the point where that degree of efficiency matters. I really like ExecuteFunc as it saves from having to create a trigger, actions, etc. and ExecuteFunc also doesn't require code to be above the calling function. It's probably my favorite native in JASS because of it.

    Many of my GUIJASS resources would be impossible were it not for ExecuteFunc, as I'd have to resort to converting the entire trigger to JASS otherwise:

    http://www.hiveworkshop.com/forums/...dexer-1-2-0-2-a-197329/?prev=status=a&u=Bribe
     
  3. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Updated - implemented changes proposed by BPower so the need to delay missile restocking is gone. I also changed the RemoveUnit call to a UnitApplyTimedLife.
     
  4. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Ok, current WIP. Highlights:
    - Uses UnitUserData instead of a unitgroup for double-free protection.
    - Now easily works with any Unit Indexer, including my GUI system thanks to the new UnitIndexerGUI library
    - No longer needs a loop to find which angle to index a dummy to.
    - Still doesn't balance the angle queues but I really don't want this resource to be 3x as long just for that one minor, situational benefit. Allocation and deallocation are extremely fast this way, and it hardly needs any variables.


    Code (vJASS):

    library MissileRecycler initializer PreInit requires optional UnitIndexer, optional UnitDex, optional UnitIndexerGUI /*

        MissileRecycler v 1.4.0.1
        =========================================================================
        Credits:
        -------------------------------------------------------------------------
        Written by Bribe
        Vexorian, Anitarf and iNfraNe for the dummy.mdx model file
        Nestharus for the Queue data structure and for finding that paused units
            consume very few CPU resources.

    =========================================================================
        Introduction:
        -------------------------------------------------------------------------
        Recycling dummy units is important because the CreateUnit call is one of,
        if not the, most processor-intensive native in the entire game. Creating
        just a couple dozen dummy units in a single thread causes a visible frame
        glitch for that instant. The overhead is even higher if you are using a
        Unit Indexing library in the map which causes some extra evaluations per
        new unit.

        There are also reports of removed units leaving a little trail of RAM
        surplus in their wake. I have not been able to reproduce this so I don't
        know if this is still a factor in 1.26.

        I was motivated to create this system because removed units might be un-
        safe in very large numbers and CreateUnit is a very heavy process.

        The thing that makes this system different than others is the fact that
        it considers the facing angle of the dummies being recycled, which I have
        never seen another system even attempt. Considering the facing angle is
        important because it takes almost 1 second for the unit to turn around,
        which looks especially weird if you are creating a unit-trail or if you
        are shooting arrow-shaped objects as projectiles. For fireball effects or
        effects that generally don't depend on facing angle, this system would be
        a bit wasteful.

        Worst case scenario, it will take 0.09 seconds for the projectile to turn
        to the angle you need. This is 1/8 of the normal worst case scenario if
        you weren't recycling dummies considering facing. On average, it takes
        roughly 0.045 seconds to turn to the angle you need (which is not even
        noticable). However, I have made this completely configurable and you are
        able to change the values to whatever needs you have.

        =========================================================================
        Calibration Guide:
        -------------------------------------------------------------------------
        The thing that surprised me the most about this system was, no matter how
        complex it turned out, it became very configurable. So I should let you
        know what the constants do so you know if/how much you want to modify.
       
        constant real DEATH_TIME = 2.0 //seconds

        - Should not be less than the maximum time a death animation needs to play.
        Should not be lower than .73 to ensure enough time to turn.
        Should not be too high otherwise the dummies will take too long to recycle.

        constant integer ANG_N = 8

        -   How many different angles are recognized by the system. Don't do
        360 different angles because then you're going to have thousands of dummy
        units stored and that's ridiculous, the game lags enough at 1000 units.
        Increasing ANG_N increases realism but decreases the chance that a dummy
        unit will be available to be recycled. I don't recommend making this any
        lower, and the max I'd recommend would be 16.

        constant integer ANG_STORAGE_MAX = 12

        -   How many dummy units are stored per angle. This limit is important
        because you might have a spike at one point in the game where many units
        are created, which could result in too high of a dummy population.
            In general, I advise that the product of ANG_N x ANG_STORAGE_MAX does
        not exceed 100 or 200. More than that is excessive, but you can
        hypothetically have it up to 8190 if Warcraft 3's memory management
        were better.
       
            Preloads ANG_N x ANG_STORAGE_MAX dummy units. Preloading dummies is
        useful as it dumps a lot of CreateUnit calls in initialization where you
        won't see a frame glitch. In the 1.4 update, preloading is done 0 seconds
        into the game to ensure any Indexers have already initialized.

        private function ToggleIndexer takes boolean flag returns nothing
        -   Put what you need in here to disable/enable any indexer in your
        map. if flag is true, enable indexer. If false, disable.

        =========================================================================
        API Guide:
        -------------------------------------------------------------------------
        You obviously need some functions so you can get a recycled dummy unit or
        recycle it. Therefore I provide these:

        function GetRecycledMissile
            takes real x, real y, real z, real facing
                returns unit

            Returns a new dummy unit that acts as a projectile missile. The args
            are simply the last three arguments you'd use for a CreateUnit call,
            with the addition of a z parameter to represent the flying height -
            it isn't the absolute z but relative to the ground because it uses
            SetUnitFlyHeight on that value directly.

        function RecycleMissile
            takes unit u
                returns nothing

            When you are done with that dummy unit, recycle it via this function.
            This function is pretty intelligent and resets that unit's animation
            and its facing angle so you don't have to.
    */

        //=======================================================================
        // Save the map, then delete the exclaimation mark in the following line.
        // Make sure that you don't have an object in your map with the rawcode
        // 'dumi' and also configure the model path (war3mapImported\dummy.mdl)
        // to the dummy.mdx model created by Vexorian.
        //! external ObjectMerger w3u ewsp dumi unam "Missile Dummy" ubui "" uhom 1 ucol 0.01 umvt "None" umvr 1.00 utar "" uspa "" umdl "war3mapImported\dummy.mdl" umxr 0.00 umxp 0.00 ushr 0 uerd 0.00 udtm 0.00 ucbs 0.00 uble 0.00 uabi "Aloc,Amrf"

        //Thanks to Vexorian that Optimizer 5.0 no longer kills natives
        native UnitAlive takes unit id returns boolean

        globals
            //-------------------------------------------------------------------
            // You must configure the dummy unit with the one created from the
            // ObjectMerger statement above.
            //
            private constant integer DUMMY_ID = 'dumi'      //The rawcode of the dummy unit.
            private          player  OWNER    = Player(15)  //The owner of the dummy unit.

            private constant integer ANG_N = 8              //# of indexed angles. Higher value increases realism but decreases recycle frequency.
            private constant integer ANG_STORAGE_MAX = 12   //Max dummies per indexed angle. I recommend lowering this if you increase ANG_N.

            private constant real DEATH_TIME = 2. //Allow the special effect on
            //the unit to complete its "death" animation in this timeframe. Must
            //be higher than 0.74 seconds to allow the unit time to turn. This
            //number should not be lower than the maximum death-animation time of
            //your missile-units' effect attachments, just to be safe.

            //If you are mixing vJass with GUI (I'll be the last to judge)
        endglobals

        private function ToggleIndexer takes boolean flag returns nothing
            static if LIBRARY_UnitIndexer then
                set UnitIndexer.enabled = flag
            elseif LIBRARY_UnitIndexerGUI then
                set udg_UnitIndexerEnabled = flag
            elseif LIBRARY_UnitDex then
                set UnitDex.Enabled = flag
            endif
        endfunction

        globals
            private constant integer ANG_VAL = 360 / ANG_N //Generate angle value from ANG_N.
            private constant integer ANG_MID = ANG_VAL / 2 //The middle value of angle value.

            //Misc vars
            private unit array stack       //Recycled dummy units.
            private real array timeStamp   //Prevents early recycling of units.
            private integer array queueNext
            private integer array queueLast
            private integer recycle = 0
            private timer gameTime  = CreateTimer() //Used for visual continuity.
            private integer array queueStack
            private integer queueStackN = 0 //Used to avoid searching the queues.
        endglobals

        static if DEBUG_MODE then
            private function Print takes string s returns nothing
                //Un-comment this next line if you want to know how the system works:
                //call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 999, "[MissileRecycler] " + s)
            endfunction
        endif

        //=======================================================================
        // Get a recycled dummy missile unit. If there are no recycled dummies
        // that are already facing the angle you need, it creates a new dummy for
        // you.
        //
        function GetRecycledMissile takes real x, real y, real z, real facing returns unit
            local integer i = ModuloInteger(R2I(facing), 360) / ANG_VAL
            local integer this = queueNext[i]
            local unit u
            if this != 0 and TimerGetElapsed(gameTime) >= timeStamp[this] then
                //Dequeue this
                set queueNext[i] = queueNext[this]
                if queueNext[i] == 0 then
                    set queueLast[i] = i
                endif
                //Recycle this index
                set queueLast[this] = recycle
                set recycle = this
                //Add queue index to available stack
                set queueStack[queueStackN] = i
                set queueStackN = queueStackN + 1
                //Old unit will return as new
                set u = stack[this]
                call SetUnitFacing(u, facing)
                call SetUnitUserData(u, 0)
                //Reset the dummy's properties.
                call SetUnitVertexColor(u, 255, 255, 255, 255)
                call SetUnitAnimationByIndex(u, 90)
                call SetUnitScale(u, 1, 0, 0)
                //call PauseUnit(u, false) -- you can disable "resets" that you don't need to worry about.
                debug call Print("Recycling")
            else
                debug call Print("Creating new")
                call ToggleIndexer(false)
                set u = CreateUnit(OWNER, DUMMY_ID, x, y, facing)
                call ToggleIndexer(true)
                call PauseUnit(u, true)
            endif
            call SetUnitX(u, x)
            call SetUnitY(u, y)
            call SetUnitFlyHeight(u, z, 0)
            set bj_lastCreatedUnit = u
            set u = null
            return bj_lastCreatedUnit
        endfunction

        //=======================================================================
        // You should recycle the dummy missile unit when its job is done.
        //
        function RecycleMissile takes unit u returns nothing
            local integer i
            local integer this = recycle
            if GetUnitTypeId(u) == DUMMY_ID and UnitAlive(u) and GetUnitUserData(u) != -1 then
                if queueStackN == 0 then
                    debug call Print("Stack is full - removing surplus unit")
                    call UnitApplyTimedLife(u, 'BTLF', DEATH_TIME)
                    return
                endif
                //Recycle this
                set recycle = queueLast[this]
                //Index the dummy unit to an available facing angle.
                //Get the last vacant angle index.
                set queueStackN = queueStackN - 1
                set i = queueStack[queueStackN]
                //Enqueue this
                set queueNext[queueLast[i]] = this
                set queueLast[i] = this
                set queueNext[this] = 0
                //Allow a time barrier for the effect to destroy/turn to complete.
                set timeStamp[this] = TimerGetElapsed(gameTime) + DEATH_TIME
                set stack[this] = u
                call SetUnitFacing(u, i * ANG_VAL + ANG_MID)
                //Prevent double-free of this unit.
                call SetUnitUserData(u, -1)
            debug else
                debug call BJDebugMsg("[MissileRecycler] Error: Attempt to recycle invalid unit.")
            endif
        endfunction

        //=======================================================================
        // I didn't need this function after all
        //
        function RecycleMissileDelayed takes unit u, real r returns nothing
            call RecycleMissile(u)
        endfunction

        //=======================================================================
        // Map the dummy units to their facing angles (map below is if ANG_N is
        // 4 and ANG_STORAGE_MAX is 3).
        //
        // angle[0] (0)   -  [4] [5] [6]
        // angle[1] (90)  -  [7] [8] [9]
        // angle[2] (180) - [10][11][12]
        // angle[3] (270) - [13][14][15]
        //
        private function Init takes nothing returns nothing
            local integer end
            local integer i = ANG_N
            local integer n = i
            local integer angle
            local real x = GetRectMaxX(bj_mapInitialPlayableArea)
            local real y = GetRectMaxY(bj_mapInitialPlayableArea)
            local unit u
            call ToggleIndexer(false)
            loop
                set i = i - 1
                set queueNext[i] = n
                set angle = i * ANG_VAL + ANG_MID
                set end = n + ANG_STORAGE_MAX
                set queueLast[i] = end - 1
                loop
                    set queueNext[n] = n + 1
                    set u = CreateUnit(OWNER, DUMMY_ID, x, y, angle)
                    set stack[n] = u
                    call PauseUnit(u, true)
                    call SetUnitUserData(u, -1)
                    set n = n + 1
                    exitwhen n == end
                endloop
                set queueNext[n - 1] = 0
                exitwhen i == 0
            endloop
            call ToggleIndexer(true)
            call TimerStart(gameTime, 1000000., false, null)
            set u = null
        endfunction

        private function PreInit takes nothing returns nothing
            static if LIBRARY_UnitIndexerGUI then
                call OnUnitIndexerInitialized(function Init)
            else
                call Init()
            endif
        endfunction

    endlibrary
     
     
    Last edited: Aug 10, 2015
  5. Flux

    Flux

    Joined:
    Feb 6, 2014
    Messages:
    2,333
    Resources:
    28
    Maps:
    1
    Spells:
    19
    Tutorials:
    2
    JASS:
    6
    Resources:
    28
    Just some suggestions:
    - Allow GetRecycleUnit (can't think of a function name) with no angle parameter (for non-moving/facing dummy units). I think it is best if it would return the unit facing with greatest number in the stack. For example, most dummies with 0 facing angle were unused, then return a unit from that group.
    - Add an AddRecycleTimer(unit, time) which it will recycle the dummy after a certain time.
     
  6. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    1) just use any dummy recycling for that
    2) just set the constant DEATH_TIME if you think you need more than 2 seconds. edit: if you're talking about for a projectile- which this is for- you recycle the missile at the end of the journey. a timed recycler is unneeded for that.
     
  7. Flux

    Flux

    Joined:
    Feb 6, 2014
    Messages:
    2,333
    Resources:
    28
    Maps:
    1
    Spells:
    19
    Tutorials:
    2
    JASS:
    6
    Resources:
    28
    Oh, its just that using another system when you already used this one is kind of redundant. What dummy recycling do you mean? Is it in THW?
     
  8. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Well there is at least one dummy recycler in the approved Jass resources. watermelon wrote it I think.

    Really the main reason this exists is for dummies that need to have a certain facing angle.
     
  9. Flux

    Flux

    Joined:
    Feb 6, 2014
    Messages:
    2,333
    Resources:
    28
    Maps:
    1
    Spells:
    19
    Tutorials:
    2
    JASS:
    6
    Resources:
    28
    How about Nestharus' Dummy?
     
  10. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Dummy works in the same way. What do you need the dummy for, by the way. A timed special effect?
     
  11. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    Mine does this in O(1) : p, but as Bribe pointed out, it's like 3x longer, lol...



    See, there's actually a trick to keeping everything balanced. At the start, you have an equal number of dummies for each angle. When you get one, you then get something like this

    -1, 0

    where -1 means that there are some angles that have 1 less dummy in them than other angles. If you take another one out, then you get this

    -2, 0

    At this point, the thing is not balanced, so you take a dummy from one of the things in 0 to get this again

    -1, 0

    Suppose you put a dummy back. It would always end up going into a negative queue. What happens if you have this then?

    0, 1

    This would be after all dummies are back, plus a few extra. Well, that is nothing more than this

    -1, 0

    Where the 0 just has fewer angles than the -1 now.

    The point I'm making is that you will only have at most two different angle counts if you do it right.

    Suppose that every collection of units for an angle is a doubly linked list. You can organize these lists in two ways. The first way is by angle. This will allow you to retrieve a unit closest to a desired facing. The second way is by count. Every count can be a doubly linked lists of those doubly linked lists that store units.

    array[count] -> list of angles -> list of units

    You take a unit out from a linked list. The count goes down by 1, moving it down to a lower rank. If the lower rank is 2 away from the highest rank, or vice versa, then take one out of the lowest/highest thing, whichever is appropriate.


    The algorithm is pretty simple and just makes sense to use. I don't mind if anyone uses the above algorithm for their things. It's a good algorithm : ). Just be sure to credit me for the algorithm and we're cool ^_-.

    Currently, only my dummy recycling makes use of that algorithm, but I'd like to see more libraries use it. Maybe someone will even find a way to improve it, like someone found a way to expand on the idea I had for allocation to reduce code generation further =).


    Also, hint hint on organizing by count. I don't remember how I originally implemented this thing, but you could do a low and high list and sometimes swap them. There are plenty of other ways you can implement it too. This is where you can get creative and really show off your skills. I don't think I implemented this part well either when I did it all those years ago. I'd do it well now though >: (, but I'd have to think about how I'd want to implement this.
     
    Last edited: Aug 26, 2015
  12. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Nes - thank you for reminding me that I hadn't updated the original post with the O(1) RecycleMissile method and getting rid of the unit group. I have now updated it.

    I'll take a look into what you said about balancing the queues.
     
  13. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    There's one other cool thing. Uhm, I figured out my own way to remove need of timers. I don't know if this is your way or not : o.

    Do priority queues for the units, where priority is based on difference between unit facing and target facing. If first unit in queue isn't target facing, or queue is empty, create a new unit : ).

    Priority queue could be implemented with a linked heap, a linked list, or something.

    Don't know if you're already doing this? : o

    You could also just assume the oldest unit, that being the first, will always have the smallest delta. This isn't always the case, so you may be allocating extra units, but it'll be fast : ). I'd prob go with this approach.
     
  14. Flux

    Flux

    Joined:
    Feb 6, 2014
    Messages:
    2,333
    Resources:
    28
    Maps:
    1
    Spells:
    19
    Tutorials:
    2
    JASS:
    6
    Resources:
    28
    Yes. A fire timed special effect. Facing angle doesn't really matter using a fire sfx so that is where my suggestion came from.
     
  15. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
  16. Flux

    Flux

    Joined:
    Feb 6, 2014
    Messages:
    2,333
    Resources:
    28
    Maps:
    1
    Spells:
    19
    Tutorials:
    2
    JASS:
    6
    Resources:
    28
    One last thing, what if I want the missile to have vision at certain circumstances. It belongs to Player(15) so adding a sight ability won't help.
     
  17. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    I think if u just set the player owner to an ally it will grant vision
     
  18. Flux

    Flux

    Joined:
    Feb 6, 2014
    Messages:
    2,333
    Resources:
    28
    Maps:
    1
    Spells:
    19
    Tutorials:
    2
    JASS:
    6
    Resources:
    28
    Ok then. So, I didn't need the sight ability afterall if the 'dumi' has a sight initially. And I will set the owner to the player directly instead to an ally. Then before recycling, I will give it back to Player(15). Thanks again Bribe ;)
     
  19. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    Attached is balancing picture

    [​IMG]
     

    Attached Files:

  20. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,773
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    I see, I see, so high and low are not a sorted list keeping track of everything in between, they are just 2 scalar pointers to the relevant angles. Pretty freaking awesome! Thanks for illustrating it, this makes it so much less imposing than it was before