• Listen to a special audio message from Bill Roper to the Hive Workshop community (Bill is a former Vice President of Blizzard Entertainment, Producer, Designer, Musician, Voice Actor) 🔗Click here to hear his message!
  • Read Evilhog's interview with Gregory Alper, the original composer of the music for WarCraft: Orcs & Humans 🔗Click here to read the full interview.
  • Vote for the theme of Hive's HD Modeling Contest #7! Click here to vote! - Please only vote if you plan on participating❗️

UnitGroups x UnitIndexer?

Status
Not open for further replies.
Level 15
Joined
Nov 30, 2007
Messages
1,202
Are Unit Groups slower then a unit indexer? Could one replace every single unit group with a UnitIndexer struct?

call group[SOME_CONSTANT].add(u)
call group[SOME_CONSTANT].remove(u)

I wonder how looping through the index would look, seeing as I can't make a double linked list, I can't do this. But I figure there is a reason for this not being out there? ^^
 
Level 24
Joined
Aug 1, 2013
Messages
4,658
Groups are slower than arrays.
However, using FirstOfGroup instead of ForGroup will improve your scripts good enough.
You can iterate 3000 units in a blink of an eye.

Also you will need a group to enumerate units in range for example.

When you have an array instead, you can use it but they are much harder to use.
 
Level 24
Joined
Aug 1, 2013
Messages
4,658
Because you cannot create dynamic arrays.

You can use one array that will be made through a struct.
Then you limit yourself to X instances and Y size of each group.
X * Y <= 8191

That wouldnt be hard to make... even without using a struct.
The other problem is that you still need GroupEnumUnits etc.
Just for the sake of being like that.

But yea, if you just want to have a library for all units in the map, and do not want anything more... people have actually made it.
That is called a unit indexer.
Every unit has it's own id, every unit can be stored in an array under that id. (Ussually done in the indexer already.)
It is not a big deal to split those up in 16 groups... however that will mean that you limit your map's units to 512 units per player.
Some maps may not like that limit.
Other maps are completely fine.
Remember that buildings are also indexed. (I hope.)
 
Yes, there are some scripts that do that, e.g.:
http://www.hiveworkshop.com/forums/graveyard-418/snippet-unitll-209540/

You can't say which is better, though--it depends on what it is used for. Usually you'll have three main choices: (1) use a unit array (2) use a linked list (3) use a unit group.

(1) is pretty standard. You just need an integer to keep track of the size, and then insertion is O(1) on the back (O(N) anywhere else if you want to preserve order). However, removal is O(N) assuming you don't want gaps--so if you want to remove a particular unit from the array, this isn't that good of an option. Clearing is O(N) if you really want to set all the members to point to null, but it is O(1) if you just reduce the size down to 0 (and when you iterate, you would only loop up to size). You waste memory that way though.

(2) Linked lists are nice in the sense that insertion is O(1) and removing a particular unit is O(1). It is slightly slower/more memory than the array method, but it has its perks.

(3) Groups... well you already know about groups. The difference is the enumeration. If you're just trying to store units (e.g. you're only using GroupAddUnit and GroupRemoveUnit) then option (1) or (2) is usually sufficient. However, groups can still win over in some cases--such as when you need to maintain multiple "groups" or "lists". Due to the 8191 limit, using a linked list or an array can easily become complicated if you need to support many individual "groups". With unit groups, you can simply make a group array. With option (1) or (2), it is less trivial since you need to partition the array accordingly and keep track of extra stuff.

Therefore, (1) and (2) are good options when you need something fast, reliable, and with a limited amount of "groups". For everything else, you're most likely better off using groups. Still, these are just general guidelines. They may not be concrete--and I may not have thought of all the cases.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
I have a related question about this (hope this does not count as thread hijacking):

I use linked lists for almost everything involving iteration. Is there any situation where it would be faster to iterate through a group? I am talking about stuff like missile systems or physics simulations here.

Yep, instant GroupEnum + FirstOfGroup / GroupRemoveUnit loop.
In short, when you don"t need to keep units stored and loop through them only one time.
 
Status
Not open for further replies.
Top