1. The long-awaited results for Concept Art Contest #11 have finally been released!
    Dismiss Notice
  2. Join Texturing Contest #30 now in a legendary battle of mythological creatures!
    Dismiss Notice
  3. The Aftermath has been revealed for the 19th Terraining Contest! Be sure to check out the Results and see what came out of 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

Visualize: Dynamic Indexing

Discussion in 'Trigger (GUI) Editor Tutorials' started by PurgeandFire, Sep 27, 2013.

  1. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,419
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18


    Introduction
    [​IMG]
    Dynamic indexing is a technique used to ensure that your spell or code can be ran multiple times
    without any MUI issues. At first, it is incredibly daunting to look at. This tutorial aims to show
    it in a better light: de-complicating the complicated.

    Before we go into dynamic indexing, you should understand its purpose. The main reason is to achieve
    MUI, the goal that all non-failing spell-makers should hope to achieve.


    MUI
    MUI stands for Multiple Unit Instanceability. That is its only purpose: make a spell able to be
    cast by multiple units (without undesired behavior).

    What are these so-called MUI-issues that I speak of? Well, let's consider a simple timed spell that
    transfers health every 0.1 seconds.​

    [​IMG]

    Seems simple enough. You would start a timer when the spell starts to loop every 0.1 seconds.
    In the loop, you would damage the target for 2 hit points, and give 2 hit points to the caster:

    • Siphon Life Cast
      • Events
        • Unit - A unit Starts the effect of an ability
      • Conditions
        • (Ability being cast) Equal to Siphon Life
      • Actions
        • Set SL_Caster = (Triggering unit)
        • Set SL_Target = (Target unit of ability being cast)
        • Set SL_Counter = 0
        • Trigger - Turn on Siphon Life Loop <gen>

    • Siphon Life Loop
      • Events
        • Time - Every 0.10 seconds of game time
      • Conditions
      • Actions
        • Unit - Cause SL_Caster to damage SL_Target, dealing 2 damage of attack type Spells and damage type Normal
        • Unit - Set life of SL_Caster to ((Life of SL_Caster) + 2.00)
        • Set SL_Counter = (SL_Counter + 0.10)
        • If (All Conditions are True) then do (Then Actions) else do (Else actions)
          • If - Conditions
            • SL_Counter Greater than or equal to 3.00
          • Then - Actions
            • Trigger - Turn off (This trigger)
          • Else - Actions


    This would work (ignoring the fact that it doesn't check if the unit is dead and junk).​
    [​IMG]

    (The circle in the bottom right shows how much time has elapsed)

    But what do you think would happen when another caster comes in?​
    [​IMG]

    Now the original caster doesn't get any HP, and hogger only takes 2 damage per tick instead of 4
    (2 + 2). Why? Look at the trigger above. When the spell is cast, SL_Caster is set to the casting
    unit. Since variables can only point to one thing at a time, the original caster (green) is overwritten.
    Not only that, but the target is overwritten, and the counter is reset to 0.

    This illustrates why we need MUI. Without it, hogger doesn't experience as much pain as he should.​


    Dynamic Indexing
    There are many ways to achieve MUI. Dynamic indexing is just one way. It involves arrays and
    one index per spell cast.

    The first thing to do is to figure out what variables you need to store. In our case, we should store:
    • Caster:
      unit
    • Target:
      unit
    • Counter:
      real
    Why? Because those are the variables we use in the periodic loop. Only save what you need to access
    during the periodic. If you only need the data when the spell is first cast, you don't need to save it.

    Instead of making single variables, we will convert them into arrays:​
    [​IMG]
    Now, the goal of dynamic indexing is to have one index per spell cast. In the periodic trigger,
    you will loop through every active spell cast (known as an instance of a spell). An instance
    usually refers to one spell cast, and it will be associated with the index that is used. The first
    instance of a spell will have an index of 1, the second will have an index of 2. When we talk about
    multi-instanceability, we are basically saying that the spell should work with multiple-spell casts at
    the same time.

    For example, if you have 3 spell instances, this is how it will look:​
    [​IMG]
    As you loop through the instances, you'll have a different caster and target to deal with. Here is some pseudo code:
    • For each (SL_Loop_Integer) from 1 to 3, do (Actions)
      • Loop - Actions
        • Unit - Cause SL_Caster[SL_Loop_Integer] to damage SL_Target[SL_Loop_Integer], dealing 2 damage of attack type Spells and damage type Normal
        • Unit - Set life of SL_Caster[SL_Loop_Integer] to ((Life of SL_Caster[SL_Loop_Integer]) + 2.00)
        • Set SL_Counter[SL_Loop_Integer] = (SL_Counter[SL_Loop_Integer] + 0.10)

    Notice that each time the loop iterates, it refers to a new instance. When SL_Loop_Integer is 1,
    it will refer to the first instance (see picture above). When SL_Loop_Integer is 2, it will refer to the
    second instance. Same for the third.

    Now, that code is specific. It loops through only 3 instances. But what if we want 5? Or 10? Or just 1?
    The point of dynamic indexing is to make a general form that will work for all cases. How do we do that?
    Simple, we must make an integer variable to keep track of the instances:

    SL_Index (Name) - Integer (Type) - 0 (Initial Value)

    So how do we go about setting this up? Well, first we have to worry about allocation. Allocation is
    the process of getting a new index and assigning the variables we need to. Since we have an order of
    1, 2, 3, etc.. we just need to increment the index once each time a spell is cast.

    Consider the following scenario. The spell is cast by a dark ranger onto a hawk, a blood mage onto a pit lord,
    a firelord onto a skeleton, and a sea witch onto a clockwerk goblin:
    [​IMG]
    The above picture will show what it should look like on allocation. When the spell is cast by the
    dark ranger, the index should be 1. SL_Caster[1] should be the dark ranger. SL_Target[1] should be
    the hawk. SL_Counter[1] should be 0.0. So forth with the other indexes. Here is the trigger:
    • Siphon Life Cast
      • Events
        • Unit - A unit Starts the effect of an ability
      • Conditions
        • (Ability being cast) Equal to Siphon Life
      • Actions
        • Set SL_Index = SL_Index + 1
        • Set SL_Caster[SL_Index] = (Triggering unit)
        • Set SL_Target[SL_Index] = (Target unit of ability being cast)
        • Set SL_Counter[SL_Index] = 0
        • If (All Conditions are True) then do (Then Actions) else do (Else actions)
          • If - Conditions
            • SL_Index Equal to 1
          • Then - Actions
            • Trigger - Turn on Siphon Life Loop <gen>
          • Else - Actions

    This should work for it. SL_Index will increase by 1 for each instance, and the arrays will be set
    for that particular instance. For index 1, the caster will be the dark ranger, the target will be the
    hawk, and the counter will be 0. Same for the other instances, as shown in the picture above.

    How about the actual looping? It is the same as we did far above, but instead of looping up to 3,
    we just loop up to SL_Index. Why? If you think about it, SL_Index actually keeps track of the
    number of spell instances. When the first spell is cast, the index is set to 1. When the second is cast,
    the index is 2. When the fourth is cast, the index is 4. etc.

    As for the last lines, it turns on the periodic loop when the first instance is made. You may wonder why
    I don't turn it on initially–don't worry about it. That will be important later. Now we will move on to the looping.

    (This trigger should be initially off)
    • Siphon Life Loop
      • Events
        • Time - Every 0.10 seconds of game time
      • Conditions
      • Actions
        • For each (SL_Loop_Integer) from 1 to SL_Index, do (Actions)
          • Loop - Actions
            • Unit - Cause SL_Caster[SL_Loop_Integer] to damage SL_Target[SL_Loop_Integer], dealing 2 damage of attack type Spells and damage type Normal
            • Unit - Set life of SL_Caster[SL_Loop_Integer] to ((Life of SL_Caster[SL_Loop_Integer]) + 2.00)
            • Set SL_Counter[SL_Loop_Integer] = (SL_Counter[SL_Loop_Integer] + 0.10)
            • If (All Conditions are True) then do (Then Actions) else do (Else actions)
              • If - Conditions
                • SL_Counter[SL_Loop_Integer] Greater than or equal to 3.00
              • Then - Actions
              • Else - Actions


    Let's analyze the trigger. SL_Loop_Integer is just an integer variable used for looping, instead of
    (Integer A). It loops up to SL_Index, basically going through each instance up until the last one.
    SL_Caster[SL_Loop_Integer] will be the caster for that instance. Same for the other variables.
    That trigger will loop through the instance and perform the actions for every spell instance.

    You may be wondering why I left the "Then" actions empty. What do we do when the spell is over?
    We must deallocate the instance. Otherwise, the spell will keep running on the finished instance
    pointlessly. It will also ensure that SL_Index won't keep going up and up (max array index is 8191).
    So how do we do that? We overwrite the instance-to-delete with the last instance, and then we set
    the loop and SL_Index back 1 (so that it will run that instance). This is what it will look like:​
    [​IMG]
    As you can see, the blood mage finished his life-sucking (for now). So now the sea witch should take his
    spot. Our goal: get the sea witch to have index 2 (overwrite blood mage). Then reduce the index
    and iterator (SL_Loop_Index) by 1. This is how it will look:
    • Siphon Life Loop
      • Events
        • Time - Every 0.10 seconds of game time
      • Conditions
      • Actions
        • For each (SL_Loop_Integer) from 1 to SL_Index, do (Actions)
          • Loop - Actions
            • Unit - Cause SL_Caster[SL_Loop_Integer] to damage SL_Target[SL_Loop_Integer], dealing 2 damage of attack type Spells and damage type Normal
            • Unit - Set life of SL_Caster[SL_Loop_Integer] to ((Life of SL_Caster[SL_Loop_Integer]) + 2.00)
            • Set SL_Counter[SL_Loop_Integer] = (SL_Counter[SL_Loop_Integer] + 0.10)
            • If (All Conditions are True) then do (Then Actions) else do (Else actions)
              • If - Conditions
                • SL_Counter[SL_Loop_Integer] Greater than or equal to 3.00
              • Then - Actions
                • Set SL_Caster[SL_Loop_Integer] = SL_Caster[SL_Index]
                • Set SL_Target[SL_Loop_Integer] = SL_Target[SL_Index]
                • Set SL_Counter[SL_Loop_Integer] = SL_Counter[SL_Index]
                • Set SL_Index = (SL_Index - 1)
                • Set SL_Loop_Integer = (SL_Loop_Integer - 1)
              • Else - Actions

    Visually, this is how it would look overwriting the blood mage instance:​
    [​IMG]
    That takes care of that. But what about reducing the index and the loop integer? Why do we do that?
    Well, this is how it would look like right after we overwrite instance 2:
    [​IMG]
    Now that we've overwritten slot 2, we must reduce SL_Index because we don't need instance 4.
    SL_Index = SL_Index - 1, which is: 4 - 1 = 3. Here is what it will look like:​
    [​IMG]
    Now the problem is that instance 2 is over! The sea witch never got her turn! Thus, we must set
    SL_Loop_Integer back so that the sea witch's instance will run:​
    [​IMG]

    Finally, we've finished! The spell should work correctly. If you cast another spell, the index will take
    slot 4, which we have no issue with. Now the spell works, but there is one thing we can do for efficiency.
    If there are no active instances, we should turn off the trigger. Otherwise it will loop needlessly. Here
    are the final triggers:
    Code
    • Siphon Life Cast
      • Events
        • Unit - A unit Starts the effect of an ability
      • Conditions
        • (Ability being cast) Equal to Siphon Life
      • Actions
        • Set SL_Index = SL_Index + 1
        • Set SL_Caster[SL_Index] = (Triggering unit)
        • Set SL_Target[SL_Index] = (Target unit of ability being cast)
        • Set SL_Counter[SL_Index] = 0
        • If (All Conditions are True) then do (Then Actions) else do (Else actions)
          • If - Conditions
            • SL_Index Equal to 1
          • Then - Actions
            • Trigger - Turn on Siphon Life Loop <gen>
          • Else - Actions

    • Siphon Life Loop
      • Events
        • Time - Every 0.10 seconds of game time
      • Conditions
      • Actions
        • For each (SL_Loop_Integer) from 1 to SL_Index, do (Actions)
          • Loop - Actions
            • Unit - Cause SL_Caster[SL_Loop_Integer] to damage SL_Target[SL_Loop_Integer], dealing 2 damage of attack type Spells and damage type Normal
            • Unit - Set life of SL_Caster[SL_Loop_Integer] to ((Life of SL_Caster[SL_Loop_Integer]) + 2.00)
            • Set SL_Counter[SL_Loop_Integer] = (SL_Counter[SL_Loop_Integer] + 0.10)
            • If (All Conditions are True) then do (Then Actions) else do (Else actions)
              • If - Conditions
                • SL_Counter[SL_Loop_Integer] Greater than or equal to 3.00
              • Then - Actions
                • Set SL_Caster[SL_Loop_Integer] = SL_Caster[SL_Index]
                • Set SL_Target[SL_Loop_Integer] = SL_Target[SL_Index]
                • Set SL_Counter[SL_Loop_Integer] = SL_Counter[SL_Index]
                • Set SL_Index = (SL_Index - 1)
                • Set SL_Loop_Integer = (SL_Loop_Integer - 1)
                • If (All Conditions are True) then do (Then Actions) else do (Else actions)
                  • If - Conditions
                    • SL_Index Equal to 0
                  • Then - Actions
                    • Trigger - Turn off (This trigger)
                  • Else - Actions
              • Else - Actions

    Done!


    Comparison
    A lot of people ask how dynamic indexing compares to other methods. The important thing to
    remember that this is a matter of nanoseconds and can vary from situation to situation, but in general:
    • Allocation is often faster than saving all the items in a hashtable. (array set vs. hash set)
    • Iteration is faster than a hashtable/unit-group loop (array load vs. hash load)
    • Deallocation varies. Hashtables can sometimes be faster in deallocation since
      dynamic indexing deallocation is O(n).
    • Versus a struct linked list, allocation is faster. Iteration is relatively the same.
      Deallocation is almost always slower.
    Note that this is just a comparison of the methods, a lot of other factors can alter the speed.


    Credits
     

    Attached Files:

    Last edited: Sep 4, 2017
  2. chobibo

    chobibo

    Joined:
    Sep 24, 2005
    Messages:
    2,692
    Resources:
    0
    Resources:
    0
    Nice tutorial Purge, I was looking for one. Thank you very much.
     
    Last edited: Sep 27, 2013
  3. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,419
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    Yep, I just left that out because I didn't want to explain it at that point in the tutorial. :p No worries though, I have that check in the trigger later on.
     
  4. chobibo

    chobibo

    Joined:
    Sep 24, 2005
    Messages:
    2,692
    Resources:
    0
    Resources:
    0
    Oh sorry, my fault, I haven't finished reading the tutorial yet I commented. I apologize.
    EDIT:
    on general details:
    - So this indexing method also allows multiple spell instances for every unit, say for example, a footman can cast 5 indexed spells and not bug out.
    - I know this is not a tutorial about instancing, but since it is closely related, and that is what this method accomplishes, why not add a small section to explain instancing. I think it's relevant to the tutorial since people who start making spells stumble on the problem of instancing their spells.
    on the comparison:
    - considering the method proposed, is the de-allocation O(n) because of the data swaps involved with the operation? If that's the case then the said time complexity could also be said of the vjass implementation of linked lists, since it internally uses arrays. I think it should be O(1) since the iteration operation is essential for the trigger actions, and the thing to consider on de-allocation would only be the swapping.
     
    Last edited: Sep 27, 2013
  5. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,419
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    No problem. Anything that causes momentary confusion in a tutorial is worth considering, in my opinion. All comments are welcome.
     
  6. chobibo

    chobibo

    Joined:
    Sep 24, 2005
    Messages:
    2,692
    Resources:
    0
    Resources:
    0
    I've added comments on my previous post, I don't want to clutter the tutorial with my replies. :D
     
  7. pOke

    pOke

    Joined:
    Mar 24, 2013
    Messages:
    1,068
    Resources:
    1
    Maps:
    1
    Resources:
    1
    Great tutorial, wish it had been around when I first had tried to learn this method :p.
    2 quick questions--
    Any advantage to using a real counter instead of an integer?
    Is there a difference in decreasing the max index before the current index?
    • Set SL_Index = (SL_Index - 1)
    • Set SL_Loop_Integer = (SL_Loop_Integer - 1)

    • Set SL_Loop_Integer = (SL_Loop_Integer - 1)
    • Set SL_Index = (SL_Index - 1)


    Edit: Thanks for the response purge, and wow those pictures make this tut look spectacular.
     
    Last edited: Sep 28, 2013
  8. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,419
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    - Yes, 5 footman can cast the spell without bugging out. If you visualize the stack, it will always resolve itself, regardless of when you allocate/what instance you deallocate. Even if you deallocate the last instance (in which case, it is just setting itself = to itself), it will work.
    - Alright. I'll try to add some more info on instancing. I don't know how long it'll be though. The way I refer to "instances" of a spell is just one spell cast, and the index represents that particular instance.

    - Yes, it is O(n) because of the data swaps. If you have n pieces of data, then you must swap n-pieces of data in the deallocation. ex: you have 5 data vars: Caster, Target, Counter, Effect, Effect2

    You would need to do 5 swaps:
    Caster = Caster[max_index]
    Target = Target[max_index]
    ... etc.
    If you have 7, you have to do 7 swaps. So forth. This is all done so that you have a nice list of indexes:
    1 - 2 - 3 - 4 - 5..
    You'll never have an unordered list:
    1 - 4 - 7 - 8 - 2..

    However, with vJASS linked lists, you can have an unordered list, so we don't care about neatness. Linked lists just have pointers to the next and previous instance, so rather than looping through 1, 2, 3, 4, etc. we just go: next, next, next, next, next, 0 -> stop. Deallocation is just:
    Code (vJASS):
    set this.next.prev = this.prev
    set this.prev.next = this.next
    // unlinks the instance
    call this.deallocate() // free it to be used in allocation

    Its speed doesn't rely on how much data it has, so it is O(1).

    - Nah, you can use a real or an integer. It is up to you. I like reals because it is easier to compare. If you increment it by the timer's period each time, you would just check if it is over 3.00 (3 seconds). If you used an integer, you would have to check if the integer is over 30 (30 ticks * 0.1 = 3).

    - No difference. You can do it in whichever order you want because you are already done with the swapping. :) Just don't place that code before the swapping, otherwise it'll swap the wrong indexes.
     
  9. chobibo

    chobibo

    Joined:
    Sep 24, 2005
    Messages:
    2,692
    Resources:
    0
    Resources:
    0
    Oh yeah, I forgot that detail on linked lists. Thanks for the correction.
    Thanks for considering my suggestion, this would clear up a lot of questions for beginners.

    I've got no further questions, thanks for the tutorial, it's very useful.
     
  10. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,419
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    Updated to fix the images. Sorry for those who had to read the huge wall of text without any images. :( (sorry chobibo, pOke)

    @chobibo: Yeah that is a perfect spot to put more info on instances. I'll make that update soon.
     
  11. Nestharus

    Nestharus

    Joined:
    Jul 10, 2007
    Messages:
    6,149
    Resources:
    8
    Spells:
    3
    Tutorials:
    4
    JASS:
    1
    Resources:
    8
    make a tutorial on lists now

    regular and linked

    ;D
     
  12. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,419
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    Yeah lol, I was thinking of doing that. I'll keep it in mind for the future. :D

    edit: Added some follow-up info on "instances", in that area chobibo pointed out.
     
  13. edo494

    edo494

    Joined:
    Apr 16, 2012
    Messages:
    3,855
    Resources:
    5
    Spells:
    1
    JASS:
    4
    Resources:
    5
    shouldnt in this picture:

    picture
    [​IMG]


    Target[2] = Target[4] instead of caster?

    You dont want the poor Naga to drain life from herself do you
     
  14. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,419
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    sheet you're right.

    Thank you, I'll fix that. I was half watching a game when I made it so I must've not been paying attention.

    edit: Fixed! Thank you!
     
  15. jakeZinc

    jakeZinc

    Joined:
    Aug 13, 2013
    Messages:
    1,366
    Resources:
    20
    Spells:
    20
    Resources:
    20
    Hmmmmm... I thought this method is Indexed Arrays xD because dynamic indexing is from Hanky Template :(. I'm too confused about them
     
  16. PurgeandFire

    PurgeandFire

    Code Moderator

    Joined:
    Nov 11, 2006
    Messages:
    7,419
    Resources:
    18
    Icons:
    1
    Spells:
    4
    Tutorials:
    9
    JASS:
    4
    Resources:
    18
    It very well might be named that. I have no clue. I know the method, but I don't follow much of the GUI-business so I don't know its name.

    For all intents and purposes, you just need to know the technique. This is certainly different from hanky's method, but it performs a very similar task with a pretty similar method.
     
  17. Chaosy

    Chaosy

    Joined:
    Jun 9, 2011
    Messages:
    10,529
    Resources:
    17
    Maps:
    1
    Spells:
    10
    Tutorials:
    6
    Resources:
    17
    amazing looking tutorial!

    sadly this will increase the number of spells that use this method. Indexing is is just so fugly :(
     
  18. Xonok

    Xonok

    Joined:
    Mar 27, 2012
    Messages:
    3,043
    Resources:
    8
    Spells:
    3
    Tutorials:
    5
    Resources:
    8
    With a little bit more complication it is possible to do less swapping when allocating.
    Basically the way that structs are done behind the scenes.

    You have a data structure(some amount of arrays)
    The same indexes on arrays are always the same instance.

    However, your indexed array will actually only point to an integer(the object ID in data structure, aka instance)
    That way you only need to swap integers and not all the data behind them.

    This is all from the top of my head, so it might not be explained in the best way. However, I see no reason why it wouldn't work.
     
  19. chobibo

    chobibo

    Joined:
    Sep 24, 2005
    Messages:
    2,692
    Resources:
    0
    Resources:
    0
    You must be referring to a list and an instance allocator, Xonok.
     
  20. Xonok

    Xonok

    Joined:
    Mar 27, 2012
    Messages:
    3,043
    Resources:
    8
    Spells:
    3
    Tutorials:
    5
    Resources:
    8
    I'm not sure how it's called, but in any case the main advantage is that instance IDs are kept separate from data(less swapping)