Group unit's ordering

[DracoL1ch]

Whenever you create a group out of units, they're always located the same way between each player. It required for many things, including FirstOfGroup native - it have to be synced value.

Basic ordering algoritm can be seen on normal unit selection, when you select bunch of units using mouse. Selected group's representation on the HUD is the same as the JASS group would looks like. The same way game handles all other groups ordering, at least to my knowledge.

1. Heroes (defined by ID's first letter) are always pushed on the top of the list.
2. Units with the same ID are always going in bunches, you can't have two units of the same typeID being spreaded inside the group listing, they're always nearby.
3. When 2 units have the same priority on placing, first cell will be taken by the one with lowest RefMini index.

Each object in game which has a handle also has 2 miniref indexes. One can imagine those indexes being an X/Y coordinates of 2D array, a-la "10D34" and "832D". Whole game working around those miniRefs, but there are no way for mapmaker to know those IDs or manipulate them. They aren't related to any handle ID and can be re-assigned when no longer used to another object, just like handle IDs, automatically.

In case if you have no leaks, dead units/objects (which got cleared from the memory) handles & miniRefs might be re-used and your groups will start to sharking because of their miniRef most likely will be lower than miniRef of unit created later.

In case if you leak each object's handle, game can't free minRefs either, leading in continuous increase of miniRef values. Therefore, in case if we don't speak about heroes, there are big chance that units added into a group will be ordered starting from the oldest one to newest one. I say a "chance" because there are instances you can't control, like abilities usage or buildings or anything else, plenty background process are happens each second.

Obviously, if you won't clean up your leaks, soon you'll get out of memory errors, so thats not the way to go.

Practical effect:

• Adding a hero into a group with no heroes or hero illusions will definitly put him into top cell. FirstOfGroup will always return this hero.
• Adding a second hero into the same group will force game to compare miniRefs, and you have no control over that.
• Adding a non-hero will never put him above any hero/illusion in group. All of non-heroes will stack next to each other in order of their miniRefs increasing.

None of unit's parameters even matter for the order they're inside the group. If first letter of his UnitTypeId is A-Z then he will be in first line, else - in second, everything else irrelevant.


Blizzard, pls give us:
native GetNthUnitFromGroup takes group g, integer n returns unit

so we can check each group's position manually. In case of bad N return null, as usual. Thats much better than slow-ass GroupPickRandomUnit. There are already a similar cycle inside GroupRemoveUnit, with a very small adjustments it can be turned into new native within 5 mins.

 

[Aniki]

Practical effect: ...

Another practical effect is that this enables one to detect "ghost" units returned by FirstOfGroup (see FirstOfGroup2).

Each object in game which has a handle also has 2 miniref indexes. One can imagine those indexes being an X/Y coordinates of 2D array, a-la "10D34" and "832D". Whole game working around those miniRefs, but there are no way for mapmaker to know those IDs or manipulate them. They aren't related to any handle ID and can be re-assigned when no longer used to another object, just like handle IDs, automatically.

Does anyone have an idea why Blizzard is using these 2 "minirefs" instead of pointers to "link up" game objects (or whatever these references are used for)? It helps with the networking side of the game or something? They take less memory than pointers?

Blizzard, pls give us:
native GetNthUnitFromGroup takes group g, integer n returns unit

Also, I think groups store the number of units that they have, which renders CountUnitsInGroup useless and inefficient (it calculates something that's already known).

 

[DracoL1ch]

Groups do store number of units, I told about it plenty times.
miniRefs used for every communication. Addresses impractical as they're differs, minirefs are static, plus its easier to read 2 4-bytes integers than trying to make a single 4-byte value unique

 

[Aniki]

Off-topic but...

I think you've mentioned this before (from some chat with leandrotp, or something), that the hashtables don't do any hashing, they simply linkup their keys/nodes into a linked list (which means that a hashtable lookup = 2 linear searches, 1 for the parent key, 1 for the child key, and thats not very fast?).

If the above is true, then "minirefs" are used to linkup a hashtable's nodes/keys, correct?

 

[Lizreu]

Off-topic but...

I think you've mentioned this before (from some chat with leandrotp, or something), that the hashtables don't do any hashing, they simply linkup their keys/nodes into a linked list (which means that a hashtable lookup = 2 linear searches, 1 for the parent key, 1 for the child key, and thats not very fast?).

If the above is true, then "minirefs" are used to linkup a hashtable's nodes/keys, correct?

That would be very dumb if they did that. Also, I think most benchmarks confirm that hashtables do not use linked lists for key lookup, otherwise we'd see very bad performance on large hashtables (and I don't think that's true)

What is very likely however, is that within each 'bucket' in the hashtables, i.e. keys that map to the same hash, there is a linked list to resolve hash collisions. That's a very common technique to resolve hash collisions in hashtables.

 

[DracoL1ch]

im not into hashtables, but wc3 has very poor realization of hashtables and Leandro told me it's not a hashtable as what you would expect when working with high-level programming language. So maybe you're right. But it's really not as solid as normal ht should be, thats all I can say. There are simple hashing method with high collision rate comparing to default