[Trigger] Arraylists queues?

[ryanshowseason2]

I find that I am in need of using large arrays,and I was wondering if there are any scripts or tutorials for anything like array lists, good array handling or if possible queue implementations?

Any scripts ready made that are good for this sort of thing?

Just to explain the problem. I'm making a new kind of devour ability where the "stomach" is able to hold quite a few victims. However adding and removing units from the arrays used to keep track of the victims gets a bit complicated as there are then holes in the arrays. My goal was to make a centralized system where two arrays the first with the victims and the second with the unit swallowing would be used to apply damage but when units die I want to remove them.

Problems that arise are that arrays in the triggers are finite and not seemingly able to change size, then as well the wholes in the array are not preferable since they take up computation time to go through.

Any ideas? alternate solutions? General exclamations of WTF why are you doing it like that? Thanks for the input!

 

[Eleandor]

Problems that arise are that arrays in the triggers are finite and not seemingly able to change size, then as well the wholes in the array are not preferable since they take up computation time to go through.

The size is 8192... What are you doing that you need larger arrays? And holes don't take up computation time on arrays, Or at least per definition it shouldn't.

A basic technique to avoid holes in your array is an algorithm like:

array arr
integer last // defines the last used spot

Upon adding something to the array, you do this:
set last = last + 1
set arr[last] = the thing you need to add

Upon removing something, to avoid holes, you do this:
x = the index of the thing you need to remove from the array
set arr[x] = arr[last]
set arr[last] = null
set last = last - 1

 

[Dr Super Good]

The limate of 8192 values (0 to 8191) in 1 array is pleanty. I dought 8192 units will be swallowed at the same time so the limate should never sainly be achieved (wc3 will morlikly crash by the time there are 8192 units ingame let alone being handled by triggers).

Thanks to a system, you can easilly do what you want but it would need 2 accompaning integer arrays and would probably involve quite a bit of O(n).

What you do is you emulate an array using the 3 arrays. The inital refference to the array is where it starts or ends. When you add something to an array, you simply enlarge the array by 1 by adding at the largest unit and updating the previous references in the array chain to include the new one. To get values from it you loop throu the array until the value you want. When you remove a value, you get the last added value and get it to replace the removed value (updating all references while doing this) so that it shrinks by 1 value stored in total. The only problem I can see is the constantly changing values may make it hard to refference an array and thus a separate array would be needed to convert the variable array refference locations into something constant that a system can then use).

This simple table will give an example of the system and how the values are stored.
index - - - unit - - - int1 - - - int2
0 - unit1 - 2 - 44
2 - unit2 - 9 - 0
9 - unit3 - 32 - 2
32 - unit4 - 44 - 9
44 - unit5 - 0 - 32
The start and end values contain the index of an endpoint and the index of the next unit in the chain. The middle values of the chain contain a link to the next and previous value of the chain. Units are found via looping from one end point to the poisitoon or the other endpioint.
You can expand the array in both directions (eithor endpoint of the chain can be extended) and the indexes might not be in order (unit5 might be moved if a unit was removed from an another array to be index 1 althou it is still the end point of this array chain). When you add a unit to the chain you simply get the direction you want to extend from endpoint and update its references to the newly added part of the chain while making the newly added part of the chain a new endpoint. Removing is more complicated by involves you basically finding the section in the chain to remove via looping and then updating the references of the previous and next part of the chain to bypass that segment and then moving the lastly added part to any array to the empty index and updating all index refferences to it to its new location.

Although it looks messed up and doable with only 1 integer array with the data array, it needs both inorder to make sure the variable locations of each piece of data is kept under controle and so all references to it update.

It sounds complicated but is actually quite simple although not at all efficent. It does however allow you to fully use an array with no gaps with variable array sizes in it (like you want) in such a way that the limate of an actual array should never be reached while allowing for extreems (like 1 array containing 500 objects in it while 100 others only contain 1 at the same time).

However for efficency, I may have to recomend you store units in group objects, as they can be stored normally in an array (1 group per unit that can eat) and are variable in size (can store any number of units in them). Thus you purly loop throu every unit in the group every time period and damage them with damage from the consumer. This is probably a lot more efficent than the above method in both memory used and time taken to execute as it has to store less values and avoids excess O(n) opperations which involve a lot of comparisons and variable handeling.

 

[Eleandor]

(wc3 will morlikly crash by the time there are 8192 units ingame let alone being handled by triggers)

It won't as long as you have enough RAM free. Don't ask me why but I've had 32k units on a map once. It raised my memory usage by 300mb more or less. It will lag terribly, reducing your fps to below 1, but it won't crash

 

[Dr Super Good]

If 8192 units are on the map, the likly hood of a crash is a hell of a lot more than just if there were 819 units on the map (which is still too much). Units do not take up that much RAM but take up a hell of a lot of system recources comparitvly, especially if they are attacking and are ranged with a huge number of targets to choose from. Once the CPU load reaches max, people getting dropped from multiplayer is likly to occur (the slowest person going first). Also the increased stress on the WC3 engine ups the chance of minor bugs or errors occuring massivly, so a crash from one of them like a seldom seen pathing displacement bug might occur when creating a unit from a summon spell in an army.

Finally it is best to avoid exessive ammounts of units as it might result in the game going so slow, it may have well crashed (0.0001 FPS).

No map should ever use more than 800 active units, and thats with a push. A more reasonable number would be 200 active units for a fast paced map with a lot of action.

 

[Eleandor]

800 units is definitely not too much, most strategy games such as Azeroth wars run quite smooth with 100 units per player.

 

[Dr Super Good]

Yes but does it actually preform well? Last time I remembered, lag occured during large battles and units moved slowly due to pathing overload. Also remember that that map largly used object editor spells and no complex systems so the actual recource demands of it trigger wise are low.

 

[Eleandor]

Most of the lag is caused by area spells such as starfall or command aura, which affect a massive amount of nearby units. As long as those are avoided, the performance is good enough.