1. Updated Resource Submission Rules: All model & skin resource submissions must now include an in-game screenshot. This is to help speed up the moderation process and to show how the model and/or texture looks like from the in-game camera.
    Dismiss Notice
  2. The 15th Mini-Mapping Contest came to an end. The Secrets of Warcraft 3 are soon to be revealed! Come and vote in the public poll for your favorite maps.
    Dismiss Notice
  3. The 12th incarnation of the Music Contest is LIVE! The theme is Synthwave. Knight Rider needs a song to listen to on his journey. You should definitely have some fun with this theme!
    Dismiss Notice
  4. Join other hivers in a friendly concept-art contest. The contestants have to create a genie coming out of its container. We wish you the best of luck!
    Dismiss Notice
  5. Check out the Staff job openings thread.
    Dismiss Notice
Dismiss Notice
60,000 passwords have been reset on July 8, 2019. If you cannot login, read this.

[System] MissileRecycler

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

  1. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    Here it is...

    It stays sorted and everything =o.


    Decide what you want to do.

    Code (vJASS):

    library Dummy /* v1.0.0.0
    *************************************************************************************
    *
    *   Allows one to create dummy units that are either at or are close
    *   to the angle specified.
    *
    *   Dummy recycling minimizes the number of dummy units on the map while supporting near
    *   instant SetUnitFacing.
    *
    *       Errors
    *       ----------------------------
    *
    *           Any error will result in the system disabling itself and an error message
    *
    *           ->  May not kill dummies
    *           ->  May not remove dummies
    *           ->  May not attempt to recycle non dummies
    *
    *************************************************************************************
    *
    *   Credits
    *
    *       Thanks to Vexorian for dummy.mdx
    *
    *************************************************************************************
    *
    *   */
    uses/*
    *
    *       */
    optional UnitIndexer     /*  hiveworkshop.com/forums/jass-functions-413/unit-indexer-172090/
    *
    ************************************************************************************
    *
    *   SETTINGS
    *
    */

    globals
        /*
        *   The unit id of dummy.mdx
        */

        private constant integer DUMMY_ID = 'h000'
       
        /*
        *   The space between angles for the recycler
        *
        *   Angles used are angles from 0 to 359 in intervals of ANGLE_SPACING
        *
        *   Higher spacing means less units but lower accuracy when creating the facing
        *
        */

        private constant integer ANGLE_SPACING = 15
       
        /*
        *   Max projectiles per angle
        *
        *   Max projectiles is 360/ANGLE_SPACING*MAX_PROJECTILES
        */

        private constant integer MAX_PROJECTILES = 16//125
       
        /*
        *   Maximum difference between queue sizes
        */

        private constant integer LOAD_BALANCE = 16
       
        /*
        *   How much to delay before recycling dummy
        */

        private constant real RECYCLE_DELAY = 2
    endglobals
    /*
    ************************************************************************************
    *
    *   struct Dummy extends array
    *
    *       Creators/Destructors
    *       ----------------------------
    *
    *           static method create takes real x, real y, real facingDeg returns Dummy
    *           method destroy takes nothing returns nothing
    *
    *       Fields
    *       ----------------------------
    *
    *           readonly unit unit
    *
    *       Operators
    *       ----------------------------
    *
    *           static method operator [] takes unit dummyUnit returns thistype
    *
    ************************************************************************************/

        private keyword Queue
       
        globals
            private unit array dummies
            private Queue dummyCount = 0
            private constant player DUMMY_OWNER = Player(15)
        endglobals
       
        function IsUnitDummy takes unit whichUnit returns boolean
            return dummies[GetUnitUserData(whichUnit)] == whichUnit
        endfunction
       
        private struct List extends array
            integer count
            thistype next
            thistype prev
           
            static method operator first takes nothing returns thistype
                return thistype(0).next
            endmethod
            static method operator last takes nothing returns thistype
                return thistype(0).prev
            endmethod
            method forward takes nothing returns boolean
                local thistype next = this.next
                local thistype prev = this.prev
                if (0 == next) then
                    set next = thistype(0).next
                    if (count - LOAD_BALANCE > next.count) then
                        set count = count - 1
                        set next.count = next.count + 1
                       
                        set this = next
                        set next = this.next
                       
                        if (count > next.count) then
                            set this.next = next.next
                            set this.next.prev = this
                           
                            set next.next = this
                            set this.prev = next
                           
                            set next.prev = prev
                            set prev.next = next
                        endif
                       
                        return true
                    endif
                elseif (count > next.count) then
                    set this.next = next.next
                    set this.next.prev = this
                   
                    set next.next = this
                    set this.prev = next
                   
                    set next.prev = prev
                    set prev.next = next
                endif
                return false
            endmethod
            method backward takes nothing returns boolean
                local thistype next = this.next
                local thistype prev = this.prev
                if (0 == prev) then
                    set prev = thistype(0).prev
                    if (count + LOAD_BALANCE < prev.count) then
                        set count = count + 1
                        set prev.count = prev.count - 1
                       
                        set this = prev
                        set prev = this.prev
                        if (count < prev.count) then
                            set this.prev = prev.prev
                            set this.prev.next = this
                           
                            set prev.prev = this
                            set this.next = prev
                           
                            set next.prev = prev
                            set prev.next = next
                        endif
                       
                        return true
                    endif
                elseif (count < prev.count) then
                    set this.prev = prev.prev
                    set this.prev.next = this
                   
                    set prev.prev = this
                    set this.next = prev
                   
                    set next.prev = prev
                    set prev.next = next
                endif
                return false
            endmethod
        endstruct
       
        private struct Queue extends array
            static timer time
           
            private real stamp
            thistype next
            thistype last
           
            private method backward takes nothing returns boolean
                return List(this).backward()
            endmethod
            private method forward takes nothing returns boolean
                return List(this).forward()
            endmethod
            private static method operator max takes nothing returns thistype
                return List.last
            endmethod
            private static method operator min takes nothing returns thistype
                return List.first
            endmethod
            private method operator count takes nothing returns integer
                return List(this).count
            endmethod
            private method operator count= takes integer count returns nothing
                set List(this).count = count
            endmethod
            static method add takes thistype dummy returns nothing
                local thistype this = thistype.min
                local thistype min
               
                set last.next = dummy
                set last = dummy
               
                call SetUnitFacing(dummies[dummy], (this - 1)*ANGLE_SPACING)
                set dummy.stamp = TimerGetElapsed(time) + RECYCLE_DELAY
               
                set count = count + 1
                if (forward()) then
                    set min = thistype.min
                    set dummy = this.next
                   
                    set min.last.next = dummy
                    set min.last = dummy
                    set next = dummy.next
                    set dummy.next = 0
                   
                    call SetUnitFacing(dummies[dummy], (min - 1)*ANGLE_SPACING)
                endif
            endmethod
            static method pop takes thistype angle returns integer
                local thistype this = angle/ANGLE_SPACING + 1
                local thistype dummy = next
                local thistype max
               
                if (0 == dummy or dummy.stamp < TimerGetElapsed(time)) then
                    return 0
                endif
               
                set next = dummy.next
               
                set count = count - 1
                if (backward()) then
                    set max = thistype.max
                    set angle = max.next
                   
                    set last.next = angle
                    set last = angle
                    set max.next = angle.next
                    set angle.next = 0
                   
                    call SetUnitFacing(dummies[angle], (max - 1)*ANGLE_SPACING)
                endif
               
                return dummy
            endmethod
        endstruct
       
        struct Dummy extends array
            debug private static boolean enabled = true
            debug private boolean allocated
           
            static method operator [] takes unit dummyUnit returns thistype
                debug if (not enabled) then
                    debug return 1/0
                debug endif
                return GetUnitUserData(dummyUnit)
            endmethod
            method operator unit takes nothing returns unit
                debug if (not enabled) then
                    debug set this = 1/0
                debug endif
                return dummies[this]
            endmethod
            private static method getClosestAngle takes integer angle returns integer
                set angle = angle - angle/360*360
                if (0 > angle) then
                    set angle = angle + 360
                endif
                return angle - (angle - angle/ANGLE_SPACING*ANGLE_SPACING)
            endmethod
            static method create takes real x, real y, real facingDeg returns Dummy
                local integer this
               
                debug if (not enabled) then
                    debug set this = 1/0
                debug endif
               
                set this = Queue.pop(getClosestAngle(R2I(facingDeg)))
                if (0 == this) then
                    set this = dummyCount + 1
                    set dummyCount = this
                    set dummies[this] = CreateUnit(DUMMY_OWNER, DUMMY_ID, x, y, facingDeg)
                    call SetUnitUserData(dummies[this], dummyCount)
                    call PauseUnit(dummies[this], true)
                else
                    call SetUnitX(dummies[this], x)
                    call SetUnitY(dummies[this], y)
                    call SetUnitFacing(dummies[this], facingDeg)
                endif
               
                debug set allocated = true
               
                return this
            endmethod
            method destroy takes nothing returns nothing
                debug if (not enabled) then
                    debug set this = 1/0
                debug endif
               
                debug if (0 == GetUnitTypeId(unit) or 0 == GetWidgetLife(unit) or not allocated) then
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 10, "DUMMY RECYCLER FATAL ERROR: ATTEMPTED TO RECYCLE INVALID DUMMY")
                    debug set enabled = false
                    debug set this = 1/0
                debug endif
               
                debug set allocated = false
               
                call Queue.add(this)
            endmethod
        endstruct
       
        /*
        *   Initialization
        */

        private module Init
            private static method onInit takes nothing returns nothing
                local unit dummy
                local integer blockAngle = 360/ANGLE_SPACING
                local integer angle = blockAngle*ANGLE_SPACING
                local List mz = 1
                local integer count = 0
               
                static if LIBRARY_UnitIndexer then
                    set UnitIndexer.enabled = false
                endif
               
                set Queue.time = CreateTimer()
                call TimerStart(Queue.time, 604800, false, null)
               
                set List(1).prev = 0
                set List(0).next = 1
                loop
                    set mz.next = mz + MAX_PROJECTILES
                    set count = MAX_PROJECTILES
                   
                    set dummyCount = dummyCount + 1
                    if (dummyCount == blockAngle) then
                        set dummyCount = dummyCount + 1
                        set blockAngle = blockAngle + ANGLE_SPACING
                    endif
                    set Queue(mz).next = dummyCount
                    loop
                        exitwhen 0 == count
                        set count = count - 1
                       
                        set dummyCount.next = dummyCount + 1
                        set dummy = CreateUnit(DUMMY_OWNER, DUMMY_ID, 0, 0, angle)
                        set dummies[dummyCount] = dummy
                        call SetUnitUserData(dummy, dummyCount)
                        call PauseUnit(dummy, true)
                       
                        set dummyCount = dummyCount + 1
                        if (dummyCount == blockAngle) then
                            set dummyCount = dummyCount + 1
                            set blockAngle = blockAngle + ANGLE_SPACING
                        endif
                    endloop
                    set dummyCount.next = 0
                    set Queue(mz).last = dummyCount
                   
                    set angle = angle - 1
                    exitwhen 0 == angle
                    set mz = mz + MAX_PROJECTILES
                    set mz.prev = mz - MAX_PROJECTILES
                endloop
                set List(0).prev = mz
                set mz.next = 0
               
                static if LIBRARY_UnitIndexer then
                    set UnitIndexer.enabled = true
                endif
               
                set dummy = null
            endmethod
        endmodule
        private struct Inits extends array
            implement Init
        endstruct
    endlibrary
     


    edit
    ok... this'll take some pondering to see which implementation gives better results... hm...


    Btw, I spent like 9.5 hours at this point on the above script ;o.

    edit
    still have logical errors, bleh
     
    Last edited: Mar 29, 2012
  2. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    I have a few comments/questions about your approach:

    - What is the purpose of having an owning player? I am interested if you have thought of something I haven't.

    - I like the idea of using SetUnitUserData as a reverse-lookup sort of deal. But at this point shouldn't UnitIndexer be the one generating the indices?

    - "R2I(angleR - angleR/360*360)" will be the same as R2I(angleR) because angleR is a real.
     
  3. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    If you shoot something like peasants as a wc3 missile, they will be colored using the owning player color. For example, peasants shot by a unit owned by player red will be red. This is just following wc3 standard behavior.

    No. The indexes used on dummies are typically, if not always, different from the indexes used by other units. Furthermore, generating using UnitIndexer = fired triggers. Also, many dummies will suck up the indexes that would otherwise be used by other units. By making dummies use their own indexes, you can have many dummies w/o causing UnitIndexer to lose its max index count ; ). The primary thing a dummy unit can be used for is retrieving a particle given a unit.

    That is.. correct ;p, my bad ;D.

    edit
    Also, my approach has slower creation/destruction times, but it will never end up creating a new unit unless you have run into the max projectiles. This means that overall, it is likeliest to use less units ^)^. However, your approach should work as it keeps the final counts of all of the queues equal. Then again, if one queue becomes empty, you end up creating/destroying units, which isn't good ;o. You have to remove the units because your queues don't remain balanced. This approach can keep any units that it makes. Because its queues are balanced, the necessity to create new units means that the map is using more projectiles than the limits allowed in the settings ;p.

    See, there are pros and cons to both approaches, which is why this makes it difficult to decide ; |.
     
  4. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Ok, so for the rare circumstance you actually need to change the player color, I recommend the user to change the owner manually. No reason to have it on for all missiles.

    You also need to use ModuloInteger, not the one line x - x / y * y, because Atan2 returns -PI to PI and ModuloInteger has negative-value protection which yours is lacking. So for half the time you will get accurate results, and the other half the time you will get errors.

    The way MissileRecycler works with dummies is that it creates a new unit when the queue responding to the desired facing angle is empty. You can't simply draw from an irrelevant queue.
     
  5. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    Yes, I know ; ). However, because your queues always keep w/e balances they have, you can't keep any unit you create or it'll result in unbalanced queues. That's the point I was making : ).

    Also, the modulo integer thing works just fine. -360--360*50/50 == -(360-360*50/50), which is modulo. You just get the negative answer, and I handle the negatives.

    I'll get rid of the set player color stuff ;p.
     
  6. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    But that's why I have overflow protection and remove the unit if the stack is full.

    If you are already handling the negative value, you might as well use the BJ cause inlining multi-line functions that work perfectly fine is a complete waste of time and space.
     
  7. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    The BJ will break it... angle != -angle.
     
  8. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    -180 degrees is the same as 180, so no, the BJ does not break it. In fact the modulo operator works exactly the same as the BJ in most languages I know of save for Python. I have tested it pretty extensively by spamming right-clicks from the unit's position to the position he was ordered to. New units are eventually created if I am clicking in the same spot all the time, and the debug messages print exactly what you'd expect.

    But I see what you're suggesting by balancing the trees now. For example if one queue is nearing depletion and the other queues are full, maybe it's time to shift units from a nearby angle and add a bit to its timestamp just in case.

    I like your thinking on it. A balanced stack of queues would be ideal and not just a flavor.
     
  9. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    90 degrees is not -90 degrees... the only time the degrees are the same is at 180, 0, and 360 >.>. 90 degrees points north and -90 points south. -90 degrees == 270 degrees.


    I'm still working on my algorithm for balancing, so don't copy the code or it won't work ;p.
     
  10. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Code (vJASS):

       function ModuloInteger takes integer dividend, integer divisor returns integer
           local integer modulus = dividend - (dividend / divisor) * divisor
           // If the dividend was negative, the above modulus calculation will
           // be negative, but within (-divisor..0).  We can add (divisor) to
           // shift this result into the desired range of (0..divisor).
           @if (modulus < 0) then
               set modulus = modulus + divisor
           endif@
           return modulus
       endfunction
     


    It doesn't do -angle, it does angle + 360. Like I said, the BJ doesn't break it. ModuloInteger is the perfect function for this. Look at what Anitarf did, for example, when ModuloInteger would have simplified it infinitely:

    Code (vJASS):

                loop
                    exitwhen face>0.0
                    set face=face+360.0
                endloop
                loop
                    exitwhen face<360.0
                    set face=face-360.0
                endloop
     
     
  11. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    oh doh, lolz, w/e ; P


    it's 6 am atm, I've been up all night (and the night before, and the night before, and the night before), so my brain is slightly fried atm ;D

    4th all nighter ftw, or is it #5? >.<

    edit
    Ok, I came up with an implementation idea that is even faster ^^ (my current implementation idea failed).


    #1: array of lists of nodes represented by value angle
    #2: array of lists of lists represented indexed by count list sizes

    count will always be in a range defined by how much smaller/bigger your counts can be. From here, you can update min/max pointers (pretty easy). Now you'll be able to retrieve any list while keeping everything sorted ; P. Yes, I'm still awake as I've been trying to figure out a good way to do this all night =O. Now that I've figured out how to do it, I'm going to bed ;D. I'll implement it when I get up ^_^.

    I really don't care who submits it, I just want a good dummy recycler.
     
    Last edited: Mar 29, 2012
  12. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Code (vJASS):

    library MissileRecycler initializer Init requires optional UnitIndexer /*

        MissileRecycler v 1.2.1.0
        =========================================================================
        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.
        Anitarf and Nestharus for coming up with the idea of having a balanced
            queue of units instead of just putting the dummies in any available
            queue. This was not my idea but it's a really good strategy.

        =========================================================================
        Requirements:
        -------------------------------------------------------------------------
        -   Updated JassHelper by Cohadar

        =========================================================================
        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.

        =========================================================================
        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 integer ANG_N = 16

        -   How many different angles are recognized by the system. You can'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 changing this be-
        cause at 16 resolution you will not be able to see the dummy unit turn
        (a higher ANG_N would be redundant, for example).

        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 lead to many of those dummy units never being
        used again.
            In general, I advise that the factor of ANG_N x ANG_STORAGE_MAX does
        not exceed 200. More than that is too much in my opinion.
            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.

        =========================================================================
        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 = 16             //# 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.
        endglobals

        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 group protect   = CreateGroup() //Used to prevent double frees.
            private integer array qlFill
            private integer array qlNext
            private integer array qlPrev //Used to keep the queues sorted.
        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
       
        private function TrySwap takes integer a, integer b, boolean forward returns nothing
            local integer prev
            local integer next
            if qlFill[a] > qlFill[b] and (not forward and a != qlPrev[ANG_N]) or (forward and b != qlNext[ANG_N]) then
                //Swap next/prev pointers for both nodes.
                set next = qlNext[b]
                set prev = qlPrev[a]
                set qlPrev[next] = a
                set qlNext[prev] = b
                set qlNext[a] = next
                set qlPrev[b] = prev
                set qlPrev[a] = b
                set qlNext[b] = a
                //Recursively swap until the list is balanced.
                if forward then
                    call TrySwap(a, next, true)
                else
                    call TrySwap(b, prev, false)
                endif
            endif
        endfunction
       
        //=======================================================================
        // 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
                //Lower the queue's position in the list if it's not already the
                //lowest.
                set qlFill[i] = qlFill[i] - 1
                call TrySwap(qlPrev[i], i, false)
                //Old unit will return as new
                set u = stack[this]
                call SetUnitFacing(u, facing)
                call GroupRemoveUnit(protect, u)
                debug call Print("Recycling")
            else
                debug call Print("Creating new")
                static if LIBRARY_UnitIndexer then
                    set UnitIndexer.enabled = false
                endif
                set u = CreateUnit(OWNER, DUMMY_ID, x, y, facing)
                static if LIBRARY_UnitIndexer then
                    set UnitIndexer.enabled = true
                endif
                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 not IsUnitInGroup(u, protect) then
                if this == 0 then
                    debug call Print("Stack is full - removing surplus unit")
                    call RemoveUnit(u)
                    return
                endif
                //Put the dummy in the least-filled queue.
                set i = qlNext[ANG_N]
                //Raise the queue's position in the list if it's not already the
                //highest.
                set qlFill[i] = qlFill[i] + 1
                call TrySwap(i, qlNext[i], true)
                //Get recycled dummy node instance.
                set recycle = queueLast[this]
                //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
                //Prevent double-free of this unit.
                call GroupAddUnit(protect, u)
                //Reset the dummy's properties.
                call SetUnitFacing(u, i * ANG_VAL + ANG_MID)
                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 else
                debug call BJDebugMsg("[MissileRecycler] Error: Attempt to recycle invalid unit.")
            endif
        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)
            static if LIBRARY_UnitIndexer then
                set UnitIndexer.enabled = false
            endif
            loop
                set i = i - 1
                set queueNext[i] = n
                set qlNext[i] = n
                set qlPrev[n] = i
                set qlFill[i] = ANG_STORAGE_MAX
                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 stack[n] = CreateUnit(OWNER, DUMMY_ID, x, y, angle)
                    call PauseUnit(stack[n], true)
                    set n = n + 1
                    exitwhen n == end
                endloop
                set queueNext[n - 1] = 0
                exitwhen i == 0
            endloop
            set qlPrev[0] = ANG_N
            static if LIBRARY_UnitIndexer then
                set UnitIndexer.enabled = true
            endif
            call TimerStart(gameTime, 1000000., false, null)
        endfunction

    endlibrary
     
     
    Last edited: Mar 29, 2012
  13. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    nop, not good. I came up with a better algorithm earlier, which is the array of stacks idea.

    array[total count of list] = first

    add the lists to the dif counts. From here, because the lists will always be close to each other w/ 0 holes, u can have min/max vars ; ).


    The algorithm you have up is like a bubble sort, lol... see, I realized that you had to do iterations earlier for most cases, hence why I changed it =o.

    If you need to do more than O(1) for the sorting, then the algorithm is no good : ).


    I'm still working on the new one, but it's still buggy
     
  14. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    I know it's bad though I like it more than when I had no balance.

    Too bad it's still bugging out for you. Your explanation of it makes sense though - but the array will often have holes I think. But it's smart to index by count and angle. Very good thinking.
     
  15. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    edit
    I added stuff to this post, so be sure to take a look at the new stuff ;p
    end edit

    If the allowed variance in the queues is >1, then it will have holes, you are correct. If it's 1, then it will never have holes (which is why I talked about benching SetUnitFacing).

    There is one other interesting thing... you can put the active counts into a list. If you have a variance of 16, then your list size will be a maze of 16. This will allow you to get the next active count = O.

    For this list, every value will be unique, meaning that the list will only ever at most swap 2 nodes. You won't have one node magically go up. The reason that the swapping doesn't work that way for my old implementation was because the values weren't unique, so you could have 125 125 125, then get 126 125 125 and have to move the 126 to the end ;o.

    So anyways, the list of counts will allow you to have holes, the array of lists referenced by count will allow you to retrieve the min/max stuff for recycling, and the array of queues referenced by the angle will allow you to retrieve a dummy given an angle.

    That is the final design >: O. Not bad if I do say so myself, pure O(1) operations ; ).


    If you want to code it all and save me the trouble of doing it, then let me know. I'm personally just not in the mood to work with dummy recyclers anymore after working on it so long yesterday and through half of today : |. Just make sure that it's good, and I will pound it into perfection as I will be needing it for the projectile system I'll be doing.

    Also, please use this for comments
    Code (vJASS):

    /*
    *  comment
    */

     


    Rather than this
    Code (vJASS):

    //comment
     


    The first one is easier to read. Also, your docs are very hard on my eyes. tbh, I started working on the dummy recycler w/o even reading through a lot of your stuff primarily because I didn't like your docs. You have a huge useless preface that I and other people using your resource don't care about.


    how does this help me use dummy recycling in any way???
    Code (vJASS):

        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.
     


    It doesn't, it's just useless information. Put that into the post so that people who want to just use the resource can have easy and direct access to the API. Keep the docs in the code uncluttered please ; ). Uncluttered docs are just so much easier to get through.

    This, as I'm sure you know, is unsafe and isn't really acceptable in public resources anymore
    //! 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


    The user will have to import the model from the map anyways, so might as well just keep it all in a map. Can also do a small Lua generation snippet if you want ;o.

    And really, all of your protection stuff in there... what I might do is write my own version with debug only protection that supports your API so that people can pick between whatever they want. You can also support my version's API ; |. I think that's the best scenario. Really, we're doing it two very dif ways and both have dif things we want our resources to do ;p. I like mine to be as optimal as possible and disable it and crash it if any errors occur. You want to just protect against all errors regardless w/o crashing it and so on so that the map can just limp its way through =p. They are just two different styles = ).


    So anyways, I think that that is the best approach at this point. Also, what you could do is write the resource and then I could modify it up a bit and we could have two versions on this thread, one with my style stuff and one with yours. They would both share the same API, that way a user could pick whichever one they wanted. They could also have dif style docs if you want to keep with your current doc style (I seriously can't handle that style).

    In fact, this might be a good solution for UnitIndexer as well. You want hook RemoveUnit right (even though it'll cut the speed down by quite a lot as it'll run through 3x rather than 2x). Yea, this might be a good approach to take for resources from now on. As long as they share the same APIs, no worries. If people prefer different style APIs, then as long as they all support all of the styles, it's all good ^_^.


    edit
    As for the projectile system debate, all current projectile systems, including the one I have up, are written incorrectly and should be terminated once I get a correctly designed projectile system up (hence the reason I started working on a DummyRecycler ^^). They all have very serious design flaws. The reason I rewrote all of my damage stuff was because my damage stuff, and all other damage stuff, had serious design flaws as well =O. Now look at damage, it's designed beautifully. It uses the same design (or possibly a better design) than top commercial games ;D. And yes, Purge's stuff was also written incorrectly.

    And btw, I know you may not like all of the rewrites, but very few people are willing to work with me on rewriting their code. Most people say good enough. This is the reason I do the rewrites, because good enough is not good enough for me ; ). For example, Dirac's damage stuff was good enough for most people, but to me it looked like absolute garbage. Purge's stuff seemed good enough for most people, but I didn't like his lib either. Dirac's projectile system seems good enough for most people, but to me it just looks like a heavyweight monster that's going for the world championship.. you obviously couldn't run 2D projectiles effectively on it... furthermore, it isn't very flexible at all >.<. You get what you get with it. This means that if you wanted 2D projectiles, u'd need a 2D projectile resource. If you wanted 3D, then you'd need a whole separate resource... and it just goes on and on... this is why I try to make it so that my own resources are highly flexible. It means that #1, you can easily extend off of them to add your own functionality to them. #2, you don't have to add band-aids to get your own functionality in (resulting in a jumble of unmanageable spaghetti code). I do realize that most of my older resources, like Unit Indexer and Unit Event, are like this, but I have been getting away from the business of spaghetti code ever since vex fixed his optimizer ; ). Also, if you notice, I continue to change my doc styles and comment styles with the goal of making them as easy to read as possible ^_^.

    So anyways, back on topic... getting a good dummy recycler with O(1). Two flavors, one version with safety always on (your style) and one version that disables itself and crashes thread with debug only safety (my style) ^_^. We are obviously never going to agree on the safety styles, which is why two versions are necessary. You'll likely never use my style and I'll never use your style, so just have two versions to support both styles ;o. Also, a function API + struct API. I personally like the API I did better, and I'm sure that you like your API more, so support both. Furthermore, you are still missing some functions in your API, like IsUnitDummy and what not ; ). Also, I personally like to pass in the unit index of the unit whereas you like to pass in the unit. In my code, I'm always working with indexes, not units, so it's just easier for me to pass in an index. In the resource itself, I'm always working with indexes, so it's easier to take an index. Passing in the unit handle just results in more GetUnitUserData calls and more array reads in order to convert the index back into a unit to be passed into the function. To support both styles, you'd have wrapper functions that take units but call the other functions that take indexes ; ). This makes everyone happy.
     
    Last edited: Mar 30, 2012
  16. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Yes I was going to say it sounds like a fun project for me to work on, would be a bit retarded if we both worked on it at the same time.
     
  17. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    Just don't forget the two styles ; ). I know most users won't care about them, but the more advanced users will care ;o. For example, some users prefer safety on at all times and others prefer debug only with thread crashing. The thread crashing helps users figure out where the error occurred (so that the map doesn't continue spamming error messages).

    What I'm expecting to happen is that we'll keep passing the resource back and forth between us until we get something that we both like ^)^. I know for one that I don't think you should have any groups in this ; ).
     
  18. Bribe

    Bribe

    Joined:
    Sep 26, 2009
    Messages:
    7,946
    Resources:
    25
    Maps:
    3
    Spells:
    10
    Tutorials:
    3
    JASS:
    9
    Resources:
    25
    Well I don't recommend turning off the safety but I can make it easier to find where the safeties are in case the user wants to manually disable them.
     
  19. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    I went ahead and submitted my resource since I think that it's unfair for you to take all of my work. The only thing I took from you in that resource was the idea to return a dummy based on the inputted angle. I took 0 of your code and 0 of any of your other ideas. For you, you'd be taking my designs, my ideas, my research, etc, etc ; |. It just seems unfair considering I put like 22 hours of work into all of that. The main work was not the coding but coming up with the design... Notice that I went through several different designs before coming to the one that is being used in the resource I submitted.

    Designing a good way to implement an idea typically takes much more work than coming up with that idea.


    Because you are personally involved with these resources, another moderator is needed to decide which resource to keep and which to not keep. Obviously, I believe that yours should be graveyarded and mine should be kept, and you can just go cry in a corner if you are against that. Taking someone else's work is just not cool.
     
    Last edited: Mar 31, 2012
  20. Phtes

    Phtes

    Joined:
    Aug 24, 2010
    Messages:
    1
    Resources:
    0
    Resources:
    0

    I am sort of at ends on how to post on something as horrendous as this post. It has been quite some time since I have done WC3 modding but I still avidly discuss coding with Nestharus.

    His resolve to never use another person's library is not something that should remotely be looked down upon. In coding it is always a competition to see who can create a better version of a resource. This is applicable to any real world scenario as well.

    None of the resources Nestharus has written was code written by someone else. In the case of this resource he saw it as an idea that he could use to create his OWN version. As it turns out almost this entire thread is him explaining his methods to you with you trying to take them and implement them as your own ideas.

    Nestharus has no reason to credit you for the same reason that when I write my own Age Verification scripts I do not credit the 900 others that have been made. It was my code not theirs. It is his own unique code not yours.

    From reading this thread it is clear he has a right to submit his own resource since it is all his own code and it is actually you who is trying to use his resource inside of your own flawed one.