[Trigger] Why dynamic indexing is flawed and people should use linked list instead

[Maker]

This is aimed at GUI triggerers mostly, since in vjass we use linked lists mostly already. But in GUI, almost everyone uses dynamic indexing and I will show you why it is flawed.

Here are examples of dynamic and non dynamic indexing. They have similarities, both work like this.

Explanation on indexing systems When a spell is cast, the created instance is assinged a new index, always the last of the instance queue. Set MaxIndex = (MaxIndex + 1) Set Caster[MaxIndex] = (Triggering unit) A spell is cast, no other instances are active: Index 1 Instance 1 A spell is cast, while other instances are active: Index 1 2 ... MaxIndex Instance 1 2 ... MaxIndex The indexes are looped through in the periodic trigger For each (Integer CurrentIndex) from 1 to MaxIndex, do (Actions) ---- However, the deindexing differs. Non dynamic indexing When deindexing, a boolean is set to false to mark that the instance in inactive. Set Boolean[CurrentIndex] = false The loop checks each boolean before executing further actions if Boolean[CurrentIndex] == true then damage target move unit ... endif Here is what happens, an example of four instances running Index 1 2 3 4 Instance 1 2 3 4 Instance 2 expires for some reason, we mark it inactive, so basically it will not be run. Index 1 2 3 4 Instance 1 x 3 4 The max index is still 4, and the loop will go from 1 to 4, even though there are only three active instances. Dynamic indexing When deindexing, the last instance is reassigned to the current index that we want to destroy Set Caster[CurrentIndex] = Caster[MaxIndex] The max index is decreased by one since one instance is now destroyed. We also decrease current index so the instance that was assigned for last to current is looped through next Set MaxIndex = (MaxIndex - 1) Set CurrentIndex = (CurrentIndex - 1) Here is what happens, an example of four instances running Index 1 2 3 4 Instance 1 2 3 4 Instance 2 expires for some reason, we move instance from last index to the position of instance 2 and decrease the array size Index 1 2 3 Instance 1 4 3 Current index is 2 at this point. Then current index is set to current - 1, which is 1. When the loop finishes, the loop index is increased by one, that happens in the background in GUI and does not need an extra action. The instance 4 in index 2 is run during the next loop. There are some small issues with this, but nothing too major. The issue is that the order changes. The instances run in order, 1-2-3-4 - 1-2-3-4..., but when an instance expires, the order changes. 1-2-3-4 - 1-2-3-4 - 1-4-3... Instance 2 is destroyed, and at that point we see that instance 4 is run twice between two instance 3 runs. Imagine if projectile A and B are launched. Projectile C is launched 0.01 seconds after projectile A and B. They all have the same speed and trajectory. They are all flying and then projectile A hits a barrel and is destroyed, so is the barrel. Now projectile C is moved by the indexing to take the index of projectile A and is the next projectile to be moved. What happens is projectile C can now hit targets before projectile B, even though projectile C was created and lauched after projectile B. Did we just bend the laws of physics?

So you see that even dynamic indexing isn't perfect since it messed up the order of the instances.

An even better way is to use a linked list.

Here is what happens, an example of four instances running

Position in list	1	2	3	4
Instance ID	1	2	3	4

Instance 2 expires for some reason, we remove it from the list and link 1 and 3

Position in list	1	2	3
Instance ID	1	3	4

The order is the same. Sweet.

Triggers Example Spell Cast Events Player - Player 1 (Red) skips a cinematic sequence Conditions Actions -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Increase the instance count -------- -------- -------------------------------------------------- -------- Set Spell_Count = (Spell_Count + 1) -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Turn on the looping trigger if this is the first instance -------- -------- -------------------------------------------------- -------- If (All Conditions are True) then do (Then Actions) else do (Else Actions) If - Conditions Spell_Count Equal to 1 Then - Actions Trigger - Turn on Example Spell Loop <gen> Else - Actions -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- If there are no unused recycled integers, then increase max -------- -------- index count to get a guaranteed unique integer -------- -------- -------------------------------------------------- -------- If (All Conditions are True) then do (Then Actions) else do (Else Actions) If - Conditions Spell_RecycledSize Equal to 0 Then - Actions Set Spell_MaxIndex = (Spell_MaxIndex + 1) Set Temp_Spell_ID = Spell_MaxIndex Else - Actions Set Spell_RecycledSize = (Spell_RecycledSize - 1) Set Temp_Spell_ID = Spell_RecycledStack[Spell_RecycledSize] -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Link the node with other nodes -------- -------- -------------------------------------------------- -------- Set Spell_Next[Temp_Spell_ID] = 0 Set Spell_Next[Spell_Last] = Temp_Spell_ID Set Spell_Prev[Temp_Spell_ID] = Spell_Last -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Set new last created node -------- -------- -------------------------------------------------- -------- Set Spell_Last = Temp_Spell_ID -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- END OF INDEXING -------- -------- -------------------------------------------------- -------- -------- Set data for the new node -------- -------- -------------------------------------------------- -------- Unit - Create 1 Footman for Player 1 (Red) at (Random point in Region 000 <gen>) facing Default building facing degrees Set Spell_Data_Unit[Temp_Spell_ID] = (Last created unit) Set Spell_Data_Time[Temp_Spell_ID] = (Random real number between 1.00 and 5.00) -------- -------------------------------------------------- -------- Example Spell Loop Events Time - Every 0.03 seconds of game time Conditions Actions -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Set ID to be the starting node -------- -------- -------------------------------------------------- -------- Set Temp_Spell_ID = 0 -------- -------------------------------------------------- -------- For each (Integer TempInt) from 1 to Spell_Count, do (Actions) Loop - Actions -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Get next instance from the list -------- -------- -------------------------------------------------- -------- Set Temp_Spell_ID = Spell_Next[Temp_Spell_ID] -------- -------------------------------------------------- -------- -------- Reduces the timer value -------- Set Spell_Data_Time[Temp_Spell_ID] = (Spell_Data_Time[Temp_Spell_ID] - 0.03) -------- -------------------------------------------------- -------- If (All Conditions are True) then do (Then Actions) else do (Else Actions) If - Conditions Or - Any (Conditions) are true Conditions (Spell_Data_Unit[Temp_Spell_ID] is dead) Equal to True Spell_Data_Time[Temp_Spell_ID] Less than or equal to 0.00 Then - Actions -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Do whatever actions -------- -------- -------------------------------------------------- -------- Unit - Kill Spell_Data_Unit[Temp_Spell_ID] -------- -------------------------------------------------- -------- -------- INDEXING -------- -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Set new last created node if this is the last node -------- -------- -------------------------------------------------- -------- If (All Conditions are True) then do (Then Actions) else do (Else Actions) If - Conditions Spell_Last Equal to Temp_Spell_ID Then - Actions Set Spell_Last = Spell_Prev[Temp_Spell_ID] Else - Actions -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Release the spell ID to be used again -------- -------- -------------------------------------------------- -------- Set Spell_RecycledStack[Spell_RecycledSize] = Temp_Spell_ID Set Spell_RecycledSize = (Spell_RecycledSize + 1) -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Link the previous and next node -------- -------- -------------------------------------------------- -------- Set Spell_Next[Spell_Prev[Temp_Spell_ID]] = Spell_Next[Temp_Spell_ID] Set Spell_Prev[Spell_Next[Temp_Spell_ID]] = Spell_Prev[Temp_Spell_ID] -------- -------------------------------------------------- -------- -------- -------------------------------------------------- -------- -------- Decrease spell count and turn off the trigger -------- -------- -------------------------------------------------- -------- Set Spell_Count = (Spell_Count - 1) -------- -------------------------------------------------- -------- If (All Conditions are True) then do (Then Actions) else do (Else Actions) If - Conditions Spell_Count Equal to 0 Then - Actions Trigger - Turn off (This trigger) Else - Actions Else - Actions

There you have it.

 

[msongyboi]

Lol maker - everything I've done was basically copied off the linked lists that you do in your systems/spells. )

 

[GhostWolf]

There is never "best" when it comes to data structures. You have pluses, and you have minuses, and you need to decide what's more important to you.

In the case of a linked list, the minuses are obvious: it lacks random access. If this is fine for you, then go for it. If it isn't, don't.

 

[Almia]

Okay,I just got this idea or source quote from Nestharus.

Why use Linked List? Math operations of Blizzard are quite slow. In Linked Lists, Insertion, Deletion and Iteration doesn't use any of the operators, except for the Allocators and Deallocators.

But currently, let's just suggest GUI users to use Indexed Array or Dynamic Indexing, seriously because it was a lot of easier to code with IA or DI than Linked List.

 

[blit_40912]

<@maker--- non dynamic indexing>

is it bad to move the instance 4 to index 2 then reduce the counter??

like this way:
x> 5 2 6 3 4 these bullets are currently flying
6> 5 2 3 4 bullet no6 exploded
3> 5 2 4 bullet no3 and so fort
5> 2 4
2> 4
4> since counter is zero then turnoff trigger?

 

[Maker]

In the case of a linked list, the minuses are obvious: it lacks random access. If this is fine for you, then go for it. If it isn't, don't.

Exactly, but the point here is that for spells that just iterate through the list of the instances, a linked list is better than the dynamic indexing that almost everybody uses.

But currently, let's just suggest GUI users to use Indexed Array or Dynamic Indexing, seriously because it was a lot of easier to code with IA or DI than Linked List.

Did you read the whole explanation? Dynamic indexing can screw things up.

 

[mckill2009]

Current index is 2 at this point

I think you mean 4 is 2 at this point...

Instance 2 is destroyed, and at that point we see that instance 4 is run twice between two instance 3 runs.

Based on what I understand if 1-2-3-4, if 2 is destroyed the last index is now pointed to null coz its already in #2, so it will run 1-2-3 in the next loops, although the order is messed up but the # of running is still the same...

 

[Maker]

I think you mean 4 is 2 at this point...

No. Instance 2, which was at index 2 expires and instance 4 from index 4 is moved to index 2. The loop integer is still 2. The next loop runs index 2 again, which is instance 4.

Based on what I understand if 1-2-3-4, if 2 is destroyed the last index is now pointed to null coz its already in #2, so it will run 1-2-3 in the next loops, although the order is messed up but the # of running is still the same...

The instances run 1-2-3-4 -- 1-4-3. The order is messed up.

It will always loop indexes from 1 to max in order.

Test map attached. Units start in order P1-P2-P3-P4. Press ESC to kill P1 unit. P4 wins the race even if it started the last.

 

[mckill2009]

No. Instance 2, which was at index 2 expires and instance 4 from index 4 is moved to index 2. The loop integer is still 2. The next loop runs index 2 again, which is instance 4.

That's what I mean, 4 is 2 at this point, the max index which is 4 is moved to the current index which is 2 that is being destroyed...

The instances run 1-2-3-4 -- 1-4-3. The order is messed up.

It will always loop indexes from 1 to max in order.

Test map attached. Units start in order P1-P2-P3-P4. Press ESC to kill P1 unit. P4 wins the race even if it started the last.

I cant open a maps now, but based on my calculations, after the destruction of index 2, 3 indexes (instance & indexes is same to me) is running which is 1-4-3 (the last 4 is removed), so why should it be called twice?

sample:
1st loop: 1-2-3-4
2nd loop: 1-2-3-4

now we destroy #2
3rd loop: 1-4-3
4th loop: 1-4-3
and so on...

Im counting:
1 = runs 4x
2 = runs 2x
3 = runs 4x
4 = runs 4x

It does not run twice than the other but you're right #4 is the winner coz he's been promoted...

 

[deathismyfriend]

ive used counters when coding so u dont have to use linked lists. i rather indexed arrays.

 

[Maker]

It does not run twice than the other but you're right #4 is the winner coz he's been promoted...

Instance 4 runs twice between two instance 3 executions. That is the point. You can see that even from your example. It does not run twice twice during one iteration through the instances.

 

[DivineLight]

nice

 

[Daffa]

We can sticky this

 

[Nestharus]

We can sticky this

nice

amg, what have u done Maker >.<


Maker was kinda noob here... neither is better than the other /sigh

both have their owns pros and cons

 

[mckill2009]

He has a point Nes, internally, the last index runs first when say #1 is destroyed...but runs twice?, seems wrong to me...

 

[Spartipilo]

1 Deals Damage
2 Deals Damage
3 Deals Damage
4 Deals Damage

2 Is removed

1 Deals Damage
4 Deals Damage <----
3 Deals Damage

This is what maker means: Instance 4 runs twice before instance 3 runs twice.

 

[DivineLight]

so basically the instances 2 deals no damage?

 

[mckill2009]

The correct term is runs first, not runs twice, how can it runs twice if the size of the index has already been reduced?, 4 is already 2 that's why...

 

[Nestharus]

It doesn't matter if something runs before something else if the order doesn't matter... order only matters when otherwise it would destroy the behavior.

Would it destroy projectile systems? no
Would it destroy unit groups? no
Would it destroy player votes? no
Would it destroy a list of spell effects that you want to run in a specific order for cinema? yes

There are other ways besides list to maintain order

It doesn't matter if something runs twice before something else. #1 ran twice before anything else, so what's wrong with #4? -.-

 

[PurgeandFire]

It doesn't matter if something runs before something else if the order doesn't matter... order only matters when otherwise it would destroy the behavior.

Which is reaffirming that it can matter, justifying the creation of this thread.

However rare the case is, Maker's point is that the linked list is more likely to "cover all bases" whereas a stack would normally "suffice". Of course, the counterargument would be (as GhostWolf said) that it depends on what you're going for. A counterargument to that would be that it is more likely that order matters than it being necessary that order does not matter (which is actually subjective, but is still a valid point).

I don't think it is dramatic enough such that spells would have to change to linked lists, IMO. For many spells, order won't matter. Instead of requiring it, I think a tutorial/sample would be in order that explains when to use either case. That way, the user can determine which to use based on the trigger they are creating.

While it is flawed logically for spells and such, it won't make a difference in most cases so I think it is just something to keep in mind.

 

[Adiktuz]

It's just another way of doing it...

The correct term is runs first, not runs twice, how can it runs twice if the size of the index has already been reduced?

I agree...

 

[Maker]

If I had though this is something very dramatic, I would have uploaded it as a resource.

The correct term is runs first, not runs twice, how can it runs twice if the size of the index has already been reduced?, 4 is already 2 that's why...

It does not run twice during the same iteration through the list.

Loop starts
1
2
3
4
Loop ends

Time passes

Loop starts
1
2 is deleted, 4 indexed to index 2, 4 doesn't run yet
4
3
Loop ends

In loop 1, instance 3 runs, then instance 4 runs. In loop 2, instance 4 runs, then instance 3.

Therefore: 3-4--4-3. Instance 4 has ran two times in between two instance 3s. Two times == twice.

----

People seem to think that this does not matter gameplay wise, as players won't notice it. That a projecile that was launched 0.01 seconds after another can still hit an object before the other, doesn't matter. I can understand their point. I accept it.

I still see a logical flaw there, my views are not the universal truth so do what you want.

 

[DivineLight]

mybe not universal but some ppl in hive
I agree with you

 

[GhostWolf]

I'll just summarize my points from our very long discussion in the chat.

If you are looping over a group of objects and updating each one as you go, there is no difference whatsoever in what order you do it.

Supposing you have four projectiles sent from an equal distance towards some enemy, all at the same velocity. Which one should hit? it doesn't matter.

For every specific example where it seemingly matters, there are endless other examples where it doesn't.

This is because, without further calculations (time of impact, if you want further info, search for it online), you can't guarantee any order will result in a globally-correct solution.
It even goes beyond "does A collide with B first or does C collides with B first". What about chain reactions? What happens if you decided that A collides with B, but that made B collide with D. You didn't even anticipate this collision before hand, simply because B and D happened to not even be close to each other.

Guaranteeing global correctness in anything beyond the most basic simulations is actually quite impossible on computers, and thus approximations are made. If you look closely, this can be seen in every game in existence.

Since you are not going to make any realistic physics simulation in WC3, it just ends up not mattering at all.

However, in this specific case where you are most likely to keep adding and removing objects as you iterate over them, I would still use a linked list, simply because it fits the job better - this is practically what linked lists were made for.
It's just that the reason is code design, rather than solving order problems.

 

[Adiktuz]

In loop 1, instance 3 runs, then instance 4 runs. In loop 2, instance 4 runs, then instance 3.

Therefore: 3-4--4-3. Instance 4 has ran two times in between two instance 3s. Two times == twice.

-> of course because you already looped the list, twice too... we were thinking like, it runs twice in a single loop???

if there is a visible time difference between running each instance in one loop, then yes it can be a problem... but since in wc3, iteration between the indexes happens almost instantly, it doesn't really matter that much...

 

[Vinz]

Hmm.. Maybe a pretty necro-bump but I wanted to add something.

A solution for this would be looping from CurrentIndex to MaxIndex and replace the higher instance with the lower.

For example;

[1][2][3][4][5]

2 expires.
Instead of replacing 2 with 5..
Loop from 3 to 4 and replace 2 with 3, 3 with 4, then simple remove the last index. That way, we don't bend the laws of.. physics.

 

[Maker]

^That would be a solution...but the complexity of reindexing all instances can be theoretically too taxing compared to say, using a linked list.

 

[Vinz]

Trigger

• Loop
  • Events
    • Time - Every 0.03 seconds of game time
  • Conditions
  • Actions
    • For each (Integer TempIndex) from 1 to SW_Index, do (Actions)
      • Loop - Actions
        • Set TempPoint = (Position of SW_Target[TempIndex])
        • Set SW_Distance[TempIndex] = (SW_Distance[TempIndex] + SW_Speed[TempIndex])
        • Set OffsetLoc = (TempPoint offset by SW_Speed[TempIndex] towards SW_Angle[TempIndex] degrees)
        • Unit - Move SW_Target[TempIndex] instantly to OffsetLoc
        • Custom script: call RemoveLocation(udg_OffsetLoc)
        • Custom script: call RemoveLocation(udg_TempPoint)
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
            • SW_Distance[TempIndex] Greater than or equal to 250.00
          • Then - Actions
            • Set TempIndex = (TempIndex + 1)
            • For each (Integer TempInteger) from TempIndex to SW_Index, do (Actions)
              • Loop - Actions
                • Set TempInt = (TempInteger - 1)
                • Set SW_Angle[TempInt] = SW_Angle[TempInteger]
                • Set SW_Caster[TempInt] = SW_Caster[TempInteger]
                • Set SW_Distance[TempInt] = SW_Distance[TempInteger]
                • Custom script: call DestroyEffect(udg_SW_Effect[udg_TempInt])
                • Set SW_Effect[TempInt] = SW_Effect[TempInteger]
                • Set SW_Target[TempInt] = SW_Target[TempInteger]
            • Custom script: set udg_SW_Caster[udg_SW_Index] = null
            • Custom script: set udg_SW_Target[udg_SW_Index] = null
            • Set SW_Index = (SW_Index - 1)
            • Set TempIndex = (TempIndex - 2)
            • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
              • If - Conditions
                • SW_Index Equal to 0
              • Then - Actions
                • Trigger - Turn off (This trigger)
              • Else - Actions
          • Else - Actions

I don't really see why it is taxing.. It added only two lines of code.

 

[Xonok]

• Strong Will Loop
  • Events
    • Time - Every 0.03 seconds of game time
  • Conditions
  • Actions
    • For each (Integer TempIndex) from 1 to SW_Index, do (Actions)
      • Loop - Actions
        • Set TempPoint = (Position of SW_Target[TempIndex])
        • Set SW_Distance[TempIndex] = (SW_Distance[TempIndex] + SW_Speed[TempIndex])
        • Set OffsetLoc = (TempPoint offset by SW_Speed[TempIndex] towards SW_Angle[TempIndex] degrees)
        • Unit - Move SW_Target[TempIndex] instantly to OffsetLoc
        • Custom script: call RemoveLocation(udg_OffsetLoc)
        • Custom script: call RemoveLocation(udg_TempPoint)
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
            • SW_Distance[TempIndex] Greater than or equal to 250.00
          • Then - Actions
            • Set TempIndex = (TempIndex + 1)
            • For each (Integer TempInteger) from TempIndex to SW_Index, do (Actions)
              • Loop - Actions
                • Set TempInt = (TempInteger - 1)
                • Set SW_Angle[TempInt] = SW_Angle[TempInteger]
                • Set SW_Caster[TempInt] = SW_Caster[TempInteger]
                • Set SW_Distance[TempInt] = SW_Distance[TempInteger]
                • Custom script: call DestroyEffect(udg_SW_Effect[udg_TempInt])
                • Set SW_Effect[TempInt] = SW_Effect[TempInteger]
                • Set SW_Target[TempInt] = SW_Target[TempInteger]
            • Set SW_Index = (SW_Index - 1)
            • Set TempIndex = (TempIndex - 2)
            • Custom script: set udg_SW_Caster[udg_SW_Index] = null
            • Custom script: set udg_SW_Target[udg_SW_Index] = null
            • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
              • If - Conditions
                • SW_Index Equal to 0
              • Then - Actions
                • Trigger - Turn off (This trigger)
              • Else - Actions
          • Else - Actions

I don't really see why it is taxing.. It added only two lines of code.

How many lines of code something takes to make doesn't show much about how much power it takes.

The reason it is taxing is that there could potentially be hundreds or thousands on indexes.

 

[deathismyfriend]

this is why it is taxing.

• For each (Integer TempInteger) from TempIndex to SW_Index, do (Actions)
  • Loop - Actions
    • Set TempInt = (TempInteger - 1)
    • Set SW_Angle[TempInt] = SW_Angle[TempInteger]
    • Set SW_Caster[TempInt] = SW_Caster[TempInteger]
    • Set SW_Distance[TempInt] = SW_Distance[TempInteger]
    • Custom script: call DestroyEffect(udg_SW_Effect[udg_TempInt])
    • Set SW_Effect[TempInt] = SW_Effect[TempInteger]
    • Set SW_Target[TempInt] = SW_Target[TempInteger]

You are moving all indexes in this case which is a huge amount of code if there is a lot of indexes to go through. You can easily hit the op-limit this way.

 

[Vinz]

Okay lol thought it was a good idea >.<

 

[deathismyfriend]

Okay lol thought it was a good idea >.<

It's ok everyone makes mistakes. Just like everyone all you need to do is learn from those mistakes.

 

[Maker]

Yeah, imagine if there were 1000 instances and the first one expires. You would reindex 999 instances with your method, where as with a linked list for example you would only relink 1 instance with another. If you were working as a programmer an suggested such a solution, you would find yourself unemployed in no time.

 

[muzzel]

How is that a flaw. Relying on the order of dynamically indexed objects is extremely bad design.
Its a general concept: if you are abusing something for a purpose its not meant to be used for, dont expect it to work reliably.

 

[Dr Super Good]

I could swear people already did use a linked list for dynamic indexing as that is how you can add/remove instances with O(1) efficiency while recycling the index.

 

[SA Dashie]

Ok here is another system that I made up (or atleast I don't remember seeing anywhere).
Instead of re-indexing all the variables only a couple do. That would be an Integer to keep track of what index it is and a boolean to see if there is room to put in new variables.

Here's an example I made.

• Spell Cast Example
  • Events
    • Unit - A unit Begins casting an ability
  • Conditions
  • Actions
    • Set Spell_MaxIndex = (Spell_MaxIndex + 1)
    • For each (Integer Temp_LoopInt) from 1 to 9001, do (Actions)
      • Loop - Actions
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
            • Spell_IndexTaken[Temp_LoopInt] Equal to False
          • Then - Actions
            • -------- -- --------
            • -------- Variable Set Examples --------
            • Set Spell_CasterSpeed[Temp_LoopIn] = (Current movement speed of (Triggering unit))
            • Set Spell_TargetSpeed[Temp_LoopInt] = (Current movement speed of (Target unit of ability being cast))
            • Set Spell_CastUnit[Temp_LoopInt] = (Triggering unit)
            • Set Spell_CastUnit[Temp_LoopInt] = (Target unit of ability being cast)
            • -------- -- --------
            • -------- -- --------
            • Set Spell_IndexTaken[Temp_LoopInt] = True
            • Set Spell_Index[Spell_MaxIndex] = Temp_LoopInt
            • Custom script: exitwhen true
          • Else - Actions
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • Spell_MaxIndex Equal to 1
      • Then - Actions
        • Trigger - Turn on Periodic Example <gen>
      • Else - Actions

• Periodic Example
  • Events
    • Time - Every 0.03 seconds of game time
  • Conditions
  • Actions
    • For each (Integer Temp_LoopInt) from 1 to Spell_MaxIndex, do (Actions)
      • Loop - Actions
        • Set Temp_LoopIndex = Spell_Index[Temp_LoopInt]
        • -------- -- --------
        • -------- Example Actions --------
        • Set Spell_CasterSpeed[Temp_LoopIndex] = (Spell_CasterSpeed[Temp_LoopIndex] x 1.20)
        • Unit - Set Spell_CastUnit[Temp_LoopIndex] movement speed to Spell_CasterSpeed[Temp_LoopIndex]
        • Set Spell_TargetSpeed[Temp_LoopIndex] = (Spell_TargetSpeed[Temp_LoopIndex] x 0.80)
        • Unit - Set Spell_TargetUnit[Temp_LoopIndex] movement speed to Spell_TargetSpeed[Temp_LoopIndex]
        • -------- --- --------
        • -------- -- --------
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
            • (Number of units in (Units in (Playable map area))) Equal to 10
          • Then - Actions
            • Set Spell_TimerInt[Temp_LoopIndex] = 0
            • Set Spell_IndexTaken[Temp_LoopIndex] = False
            • Set Spell_Index[Temp_LoopIndex] = Spell_Index[Spell_MaxIndex]
            • Set Spell_MaxIndex = (Spell_MaxIndex - 1)
          • Else - Actions
            • Set Spell_TimerInt[Temp_LoopIndex] = (Spell_TimerInt[Temp_LoopIndex] + 1)
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • Spell_MaxIndex Equal to 0
      • Then - Actions
        • Trigger - Turn off Periodic Example <gen>
      • Else - Actions

I'm not always awesome at explaining what I've done, so hit me with any questions. If you want.

 

[deathismyfriend]

u shouldn't loop from 1 to 9001 every time. That will definitely hit the op-limit.
The op-limit isn't a specific number for a loop.
The limit (according to PipeDream) is 300,000 byte code operations.

umm why do you have this ?

• Set Spell_TargetUnit[Temp_LoopIndex] = Spell_TargetUnit[Temp_LoopIndex]

This is inefficient because you aren't reducing the index when the things get de-indexed and because of that huge loop in the cast trigger.

 

[SA Dashie]

Within the commented code is just an example of how it could be used.
Ill fix that now.

The thing about my system is that it only indexes and de-indexes one variable instead of all the variables required for it. This could become useful for spells and systems that require alot of variables.

Also with that loop that I am using, it loops through to check if there isn't a space that is used, then it exits the loop(this part would look more logical in jass/vjass/etc)..

 

[deathismyfriend]

ik how it works but think about looping through 1000 indexes every time just to see if a space available ?

Also if it uses a key to store unused indexes then you should use an array of viable indexes to be used like I used in my ping quest system. I did it that way so I didn't have to loop through everything to check for an available index.
I'm not sure what it would be called as that is the only thing i could think of doing and I'm not sure what data structure it would be called.

 

[Spartipilo]

Using a Hashtable would be a lot better than looping through 1000 indexes

 

[Almia]

Using a Hashtable would be a lot better than looping through 1000 indexes

IF Hashtables was faster.

 

[deathismyfriend]

IF Hashtables was faster.

when looping through 1k indexes hashtables would be faster.

 

[Dr Super Good]

The thing about my system is that it only indexes and de-indexes one variable instead of all the variables required for it. This could become useful for spells and systems that require alot of variables.

Also with that loop that I am using, it loops through to check if there isn't a space that is used, then it exits the loop(this part would look more logical in jass/vjass/etc)..

Since index fragmentation is not a problem, you need to keep a collection of free index numbers which you pop from on demand and add to when an index is no longer needed. Array fragmentation is no concern as JASS never down-sizes arrays anyway so as long as you avoid allocating new index numbers the arrays will not be increased in size.

One possible implementation would be to use a stack for holding the non-used index numbers. This uses two variables, the backing array which is an integer array that holds the index numbers that are not in use and the other is the stack pointer, an integer that holds the top of stack index. Once an index is finished being used you push it to the top of the stack and you pop from the stack when new index numbers are needed. Only if the stack is empty do you allocate a new index number.

However I am guessing all this conversation is about iterating through active index numbers for systems like script enhanced abilities. For this there are possible solutions.

1. Data relocation. Since the order of iteration does not mater you can view the entire data structure as a form of stack. You push new instances onto the top of the stack. When removing indexes from the middle of the stack you can then copy the top of stack over the removed index and decrease the stack size.

Advantages of this method...
Saves on variables, it has recycling variables built into it.
Iterator friendly, only ever touching instances that exist.

Disadvantages of this method...
No way to discern individual instances from the collection efficiently. You cannot couple an instance else-where.
Copies all instance data on instance destruction. This can be costly for complex instances with a lot of variables. Cost is only issue with short instance life cycle or if instances are stupidly complicated.

I strongly support using this type of indexer when possible as it is simple and efficient. If you need static index numbers for instances, do not need to iterate or plan to allocate and deallocate complex objects multiple times a function this is a bad choice.

2. Multi-purpose linked list. Index recycling can be performed using a linked list as a stack of sorts. If this list only uses non-allocated index numbers you can multiplex the use of the arrays with a separate linked list for allocated index objects which can be used to form a linked list of all allocated index numbers. This link list can be iterated through highly efficiently to get all active instances.

Advantages of this method...
Allocates static index numbers to instances. Suitable for reference by other systems.
Supports efficient iteration, allocation and de-allocation of instances (only during iteration).

Disadvantages of this method...
Requires extra variables, at least 3 (2 integers for list head pointers and 1 integer array for next element pointer).
De-allocation only efficient if done in the iterator, otherwise you will need a linear search or separate array for doubly-linked list which reduces array efficiency.

This method extends 1 to a full index allocator system while retaining the ability to efficiently iterate through active index numbers. Integration of both allocated and de-allocated lists allows highly optimized code and saves on variables. However using such a system when 1 will suffice is pointless since 1 is simpler and probably better performing. Only go as far as to use this if you really need static index numbers for instances and need to iterate through all active instances.

 

[SA Dashie]

Since index fragmentation is not a problem, you need to keep a collection of free index numbers which you pop from on demand and add to when an index is no longer needed. Array fragmentation is no concern as JASS never down-sizes arrays anyway so as long as you avoid allocating new index numbers the arrays will not be increased in size.

One possible implementation would be to use a stack for holding the non-used index numbers. This uses two variables, the backing array which is an integer array that holds the index numbers that are not in use and the other is the stack pointer, an integer that holds the top of stack index. Once an index is finished being used you push it to the top of the stack and you pop from the stack when new index numbers are needed. Only if the stack is empty do you allocate a new index number.

Thanks for the idea.
Here is my attempt for implementation.

This code shows an example of recycling unused index spacing, by collecting index numbers when they are finished with use.

Spell Cast

• Spell Cast Example
  • Events
    • Unit - A unit Begins casting an ability
  • Conditions
  • Actions
    • Set Spell_MaxInUse = (Spell_MaxInUse + 1)
    • -------- -- --------
    • -------- Check for latest unused Index space --------
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • Spell_MaxIndexUnused Greater than 0
      • Then - Actions
        • -------- If index find unused space it gets filled in --------
        • Set TempInt = Spell_IndexUnused[1]
        • Set Spell_IndexUnused[1] = Spell_IndexUnused[Spell_MaxIndexUnused]
        • Set Spell_MaxIndexUnused = (Spell_MaxIndexUnused - 1)
      • Else - Actions
        • -------- Pushes the index up if any preused arn't found --------
        • Set TempInt = Spell_MaxInUse
    • Set Spell_Index[Spell_MaxInUse] = TempInt
    • -------- -- --------
    • -------- Turn on Periodic if not currently activated --------
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • Spell_MaxInUse Equal to 1
      • Then - Actions
        • Trigger - Turn on Periodic Example <gen>
      • Else - Actions
    • -------- -- --------
    • -------- Variable Set Examples --------
    • Set Spell_CastUnit[TempInt] = (Triggering unit)
    • Set Spell_TargetUnit[TempInt] = (Target unit of ability being cast)
    • Set Spell_CasterSpeed[TempInt] = (Current movement speed of Spell_CastUnit[TempInt])
    • Set Spell_TargetSpeed[TempInt] = (Current movement speed of Spell_TargetUnit[TempInt])
    • -------- -- --------

Periodic

• Periodic Example
  • Events
    • Time - Every 0.03 seconds of game time
  • Conditions
  • Actions
    • For each (Integer Temp_LoopInt) from 1 to Spell_MaxInUse, do (Actions)
      • Loop - Actions
        • Set Temp_LoopIndex = Spell_Index[Temp_LoopInt]
        • -------- -- --------
        • -------- Example Actions --------
        • Set Spell_CasterSpeed[Temp_LoopIndex] = (Spell_CasterSpeed[Temp_LoopIndex] x 1.20)
        • Unit - Set Spell_CastUnit[Temp_LoopIndex] movement speed to Spell_CasterSpeed[Temp_LoopIndex]
        • Set Spell_TargetSpeed[Temp_LoopIndex] = (Spell_TargetSpeed[Temp_LoopIndex] x 0.80)
        • Unit - Set Spell_TargetUnit[Temp_LoopIndex] movement speed to Spell_TargetSpeed[Temp_LoopIndex]
        • -------- --- --------
        • -------- -- --------
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
            • Spell_TimerInt[Temp_LoopIndex] Equal to 10
          • Then - Actions
            • -------- This caches the index space for recycling --------
            • Set Spell_MaxIndexUnused = (Spell_MaxIndexUnused + 1)
            • Set Spell_IndexUnused[Spell_MaxIndexUnused] = Spell_Index[Temp_LoopIndex]
            • -------- -- --------
            • -------- Resets the timer --------
            • Set Spell_TimerInt[Temp_LoopIndex] = 0
            • -------- Pushes down the max index to this one --------
            • Set Spell_Index[Temp_LoopIndex] = Spell_Index[Spell_MaxInUse]
            • -------- This tells that this spell is no longer in index --------
            • Set Spell_MaxInUse = (Spell_MaxInUse - 1)
            • -------- This pushes down the loop so that the previously pushed down index can run --------
            • Set Temp_LoopInt = (Temp_LoopInt - 1)
          • Else - Actions
            • -------- Increases till the spell expires --------
            • Set Spell_TimerInt[Temp_LoopIndex] = (Spell_TimerInt[Temp_LoopIndex] + 1)
    • -------- Turns off this periodic trigger if no longer in use --------
    • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
      • If - Conditions
        • Spell_MaxInUse Equal to 0
      • Then - Actions
        • Trigger - Turn off Periodic Example <gen>
      • Else - Actions

 

[deathismyfriend]

this leaks a unit group every time it's used.

• (Number of units in (Units in (Playable map area))) Equal to 10

these should be switched and the variable should be used for efficiency and speed.

• Set Spell_CasterSpeed[Temp_LoopInt] = (Current movement speed of (Triggering unit))
• Set Spell_TargetSpeed[Temp_LoopInt] = (Current movement speed of (Target unit of ability being cast))
• Set Spell_CastUnit[Temp_LoopInt] = (Triggering unit)
• Set Spell_CastUnit[Temp_LoopInt] = (Target unit of ability being cast)

I'm not sure why you use the ITE in the cast trigger to check for a usable index. If there isn't a usable index then that means that you are using all indexes. ITE shouldn't be needed.

With this it would be simpler to use indexed arrays. I don't see a speed or efficiency boost unless I'm missing something ?

 

[SA Dashie]

^This is what I get for trying to code in GUI.

this leaks a unit group every time it's used.

• (Number of units in (Units in (Playable map area))) Equal to 10

Gah haven't done anything like this in GUI for about a year or so(to used to vJass >.<).

Idk why I used "(Number of units in (Units in (Playable map area)))" it's meant to be "Spell_TimerInt[Temp_LoopIndex]"

these should be switched and the variable should be used for efficiency and speed.

• Set Spell_CasterSpeed[Temp_LoopInt] = (Current movement speed of (Triggering unit))
• Set Spell_TargetSpeed[Temp_LoopInt] = (Current movement speed of (Target unit of ability being cast))
• Set Spell_CastUnit[Temp_LoopInt] = (Triggering unit)
• Set Spell_CastUnit[Temp_LoopInt] = (Target unit of ability being cast)

For this I would usually use local variables if I where using vJass, so idk if using a global array is faster than directly using functions like "Triggering Unit".

I'm not sure why you use the ITE in the cast trigger to check for a usable index. If there isn't a usable index then that means that you are using all indexes. ITE shouldn't be needed.

This checks whether or not there is an index that can be recycled and is no longer in use. If there isn't an index that can be recycled then it is given a "+1" to the Index.

Once the periodic function is finished for the spell(the spell finishes) that index gets stored to be over written and recycled for the next use again.

Not sure how else to explain it..

With this it would be simpler to use indexed arrays. I don't see a speed or efficiency boost unless I'm missing something ?

The example here that I made isn't really a great one. I kind of see what you mean.

Although this kind of system may not be considered so fast for alot of cases. It could be used for spells and systems that need alot of recycling and have alot of variables. The point in this system is it can miss a mass use of variable moving.

Thank you, I'll fix the triggers above. (can't currently give out more rep to you)

 

[deathismyfriend]

For this I would usually use local variables if I where using vJass, so idk if using a global array is faster than directly using functions like "Triggering Unit".

calling a function is slower than using a global variable. I'm not sure by how much.

This checks whether or not there is an index that can be recycled and is no longer in use. If there isn't an index that can be recycled then it is given a "+1" to the Index.

Once the periodic function is finished for the spell(the spell finishes) that index gets stored to be over written and recycled for the next use again.

Not sure how else to explain it..

problem is that if it is given a +1 then it is using an index that has already been used. It will then break that other index.

When an indexed gets recycled it should be re-indexed into the array that stores all of the unused indexes immediately.

The example here that I made isn't really a great one. I kind of see what you mean.

Although this kind of system may not be considered so fast for alot of cases. It could be used for spells and systems that need alot of recycling and have alot of variables. The point in this system is it can miss a mass use of variable moving.

Thank you, I'll fix the triggers above. (can't currently give out more rep to you)

It can be used in a system for something that uses a lot off variables or something that needs this kind of indexing. I used something like this in my ping quest system. It's in my sig you should take a look at it. It's all in Jass except for config.

 

[SA Dashie]

It should work, just as you said it should. Although I should actually test it out sometime to make sure it is functioning 100%.

problem is that if it is given a +1 then it is using an index that has already been used. It will then break that other index.

Actually the way my system should be working is that if all indexes are being used then an extra index is used/added that hasn't been used before will be used. That would be the max indexes in use +1.
It doesn't overwrite any indexes that are currently being used.
Guess I wasn't sure how to explain it properly?

When an indexed gets recycled it should be re-indexed into the array that stores all of the unused indexes immediately.

This is don't under the periodic trigger when the spell(/system) has finished.


__

Oh yes btw this thing, also when a new spell is used it uses the lowest index index as the one being used, then pushes down the latest one to the bottom. After taking the max unused ones down.

 

[Cokemonkey11]

This is the silliest thread I've seen in a long time.

When you use the dynamic indexing method, you're effectively giving the game a promise: "I expect my code to run on TIMER_CLOCK frames per second, and I don't care about what happens in less than a frame, because the performance is worth it."

If you need an accuracy fidelity of up to 1ms, then use a timer clock of 1ms.

Remember also that no matter what order the stack is in, if the projectiles fire within the same frame with the same target distance and velocity, they will hit at the same time, because we have defined time as having a fidelity of TIMER_CLOCK.

To tell people they should use linked lists instead of dynamic indexing is absurd. One incurs better performance for actions on all object, and one incurs worse. Teach people about both concepts and they will make the correct choice for themselves in an ad-hoc manner. Only an idiot would say mergesort is strictly better than quicksort.

If you're worried about things changing order beyond the scope of a single clock cycle, then you're programming your system incorrectly. Decrement the loop index after deletion.

---

Deathchef, I haven't read your version because talking about performance improvements in GUI is silly.

---

Lastly, please, someone close this thread. The title and original post are not only incorrect from a standpoint of high level game design, but also incorrect in regards to the performance of warcraft 3 using JASS. It's also quite embarrassing for the otherwise high achievers who argued for the proposition.

 

[SA Dashie]

---

Deathchef, I haven't read your version because talking about performance improvements in GUI is silly.

---

Not necessarily constricted to GUI lolz.
I can easily convert what I have done into vJass, I just did it in GUI for user friendly readability sakes.

I just did this cause I enjoyed making such a system that could become useful, no matter how little use you claim it has.