[JASS] Order of units inside a group

[Wareditor]

You would imagine that when you create a group and add units to it, they will be enumerated (using the ForGroup function) in the order they were added. This is true in most cases but not in all as I have found.

I have a situation where by adding a unit to a group, it will not be added at the end of the stack but at a random place, even sometimes taking the first place. And it is really random, because it will be different each time the map is launched and it seems to have no pattern what so ever.

The code basically looks like that :

set v = FirstOfGroup(g)
call GroupAddUnit(g,u)
call BJDebugMsg(I2S(GetHandleId(v)))
call BJDebugMsg(I2S(GetHandleId(FirstOfGroup(g))))

This is will display two different ids in my case.

Nothing fancy is happening. I am just adding an unit to a group. It will even happen when there is only one unit in the group and I add another to it.

The really strange thing is that it seems to be only happening in this function. I guess it must be coming from another part of the function but I can't see how anything would have an impact on the group in such a way.

So this is why I came to you after long hours of searching for a solution by myself. Maybe someone has encountered something similar and have found a solution ?

 

[Jampion]

A unit group is a unordered collection and FirstOfGroup does have to return a specific unit. It just returns the unit that happens to be the first in the group, so it is most likely the fastest element to get. As a result it is good, if you want any unit from the group and can be used to quickly enumerate through all units in the group or to check if the group is empty.

As an unordered collection the unit group should only be used in a way, where the order of the elements is irrelevant.

If in any situation the order in which the elements are matters, you must use an ordered collection like an array or list for example.

 

[IcemanBo]

Want to attach your demo?

 

[Aniki]

groups seem to be doubly-linked lists. GroupAddUnit adds heroes at the head of the linked list (and also at the end of the heros part of the list), while non-hero units are added at the tail of the linked list.

globals
    group myg = CreateGroup() // starts empty
endglobals

...

call GroupAddUnit(myg, Paladin)
// myg = Paladin
call GroupAddUnit(myg, footman)
// myg = Paladin -> footman
call GroupAddUnit(myg, peasant)
// myg = Paladin -> footman -> peasant
call GroupAddUnit(myg, Archmage)
// myg = Paladin -> Archmage -> footman -> peasant
call GroupAddUnit(myg, Bloodmage)
// myg = Paladin -> Archmage -> Bloodmage -> footman -> peasant
call GroupAddUnit(myg, rifleman)
// myg = Paladin -> Archmage -> Bloodmage -> footman -> peasant -> rifleman

 

[Tasyen]

Made a test: it is like Aniki said: groups first list heroes, then list up non-heroes.
But in my test a new added hero took over the position of FirstOfGroup and pushed others back. (newest warcraft 3 version).
While a new added non-Hero always was displayed last.

call GroupAddUnit(myg, Archmage)
// myg = Paladin -> Archmage -> footman -> peasant
// myg = Archmage -> Paladin -> footman -> peasant

 

[Wareditor]

All the units added are of the same unit type though.

@IcemanBo Sadly I can't, it would be too complicated for me, there are too many systems involved.
I could maybe send you the map by private if you have the time.

 

[Aniki]

But in my test a new added hero took over the position of FirstOfGroup and pushed others back.

My heroes got reversed because of the way I was iterating/printing the group:

function print_myg takes nothing returns nothing
    local group g = CreateGroup()
    local unit u
    local string name
    local string names

    // I am iterating over myg using FirstOfGroup & GroupRemoveUnit.
    // I didn't want to lose the units in myg so I made a "copy" of the it (using the blizzard.j function GroupAddGroup).
    // The way the copy is done is by iterating over the source group (myg, using the ForGroup native)
    // and adding each unit to the destination group (g, using the GroupAddGroup native).
    // We get the reversed order because ForGroup iterates the units in-order, but GroupAddGroup adds them
    // to the head of the linked list.
    //
    // myg = Bloodmage, Archmage, Paladin
    // ForGroup iteration order = Bloodmage, Archmage, Paladin
    //
    // call GroupAddUnit(g, Bloodmage)
    // g = Bloodmage
    // call GroupAddUnit(g, Archmage)
    // g = Archmage, Bloodmage
    // call GroupAddUnit(g, Paladin)
    // g = Paladin, Archmage, Bloodmage
    //
    //
    call GroupAddGroup(myg, g)

    set names = ""
    loop
        set u = FirstOfGroup(g)
        exitwhen u == null
        call GroupRemoveUnit(g, u)

        set name = GetUnitName(u)
        if not IsUnitType(u, UNIT_TYPE_HERO) then
            set name = StringCase(name, /*upper:*/ false)
        endif

        set names = names + name + " -> "
    endloop
    set names = names + "nil"

    call BJDebugMsg(names)

    call DestroyGroup(g)
    set g = null
endfunction

All the units added are of the same unit type though.

It seems that if the units have the same type and are added one after the other (GroupAddUnit(myg, footman1), GroupAddUnit(myg, footman2)) they are ordered by their handle-id (GetHandleId) in increasing order. (don't quote me on this though =)).

 

[Wareditor]

No they are not ordered by their handle id nor by their time of creation. It's something else that nobody has figured out yet.

 

[Dr Super Good]

Either hash of their handle ID or internal ordering of a binary search tree. I doubt the test for units in a group has a O(n) (linear search) complexity, but more like O(log2(n)) (binary search) or O(1) (hash table lookup) complexity.

 

[TempMail]

I can only confirm that any unit with hero class, including illusions, calls different iterator whenever they're added to the group. Normal units follow slightly different algo.

Either hash of their handle ID or internal ordering of a binary search tree. I doubt the test for units in a group has a O(n) (linear search) complexity, but more like O(log2(n)) (binary search) or O(1) (hash table lookup) complexity.

it actually just compare each node's value with requested value, nothing else at all

 

[Wareditor]

@TempMail
So do you have any idea on how to predict or manipulate the order of units in a group ?

 

[Kaijyuu]

Use an array instead.

I didn't realize lookup for groups was O(n) complexity. Goddamn it Blizz from 17 years ago I suppose it's not a big deal these days since it's highly unlikely any group structure will have more than a few hundred elements. Still though, what were they thinking?

 

[Wareditor]

@Kaijyuu
I am not trying to find an alternative solution. I have a bunch of them. I want to understand how actual warcraft 3 group works. That's the only goal here - understand what we don't know.

 

[TempMail]

Well, it looks like a simple thing:
Adding a hero ID pushes him on the top of the list
Adding anything else - attached to the tail

grouping via GroupEnumUnitsInRange follows the same rules, heroes will always be on top of the list. Probably it made to provide hero-priority with some spells and UI, because most of ingame functions uses inner groups (linked lists of units) for its purpuses.

Order in grouping doesn't fit any kind of rule, but still when units move around, group order is changed, which means it most likely based on terrain cells iterator which is used to see who is belong to grouping AOE. Still, its not left-to-right and not anything else what I can distinct, so there are no way to predict exact order.

Iterator if you wanna test:

function B2S takes boolean b returns string
    if b then
        return "true"
    endif
    return "false"
endfunction

function ForGroupMy takes group g returns nothing
    local integer i=1
    local integer a=ConvertHandle(g)
    local integer b
    local integer c
    if a>0 then
        set a=a+0x24
        set b=RMem(a+0xC)
        if b>0 then
            loop
                set c=RMem(b+8)
                call BJDebugMsg(I2S(i)+" "+GetObjectName(RMem(c+0x30))+" h="+B2S(IsUnitIdType(RMem(c+0x30),UNIT_TYPE_HERO)))
                set b=RMem(b+4)
                exitwhen b < 1
               
                set i=i+1
            endloop
        else
            call BJDebugMsg("nothing in group")
        endif
    endif
   
endfunction

 

[Wareditor]

"Adding anything else - attached to the tail"
The whole point of this thread is that this is not true.

Actually @IcemanBo has found a very good lead.
Basically when there are handle ids to be recycled, the order of units in a group will be altered.

I am gonna attach the demo map he sent me.

In the first loop there are 2 last lines which create and remove a unit.
This creation does disturb the correct order.
If you disable the 2 actions, then the order will always be correct.

 

[TempMail]

So. It compares unit's ID with first (last? not sure) units in group list. If it match (same type), it compares unit's 1st half-handle

All handles in game are representation for address, which can be different for diff wc3 instances. So every object ingame has 2 4-byte values which represent him for game, binding his to specific handle as an address. It may be bullshit but Im saying that just to explain why I called it half-handle. Basically 2D array with X/Y for game purposes.

If newely added unit has lower 1st half-handle, then regroup is called, which arrange units strictly by Hero / non hero order, half-handle incrementing inside both "clans".

I can say its a-la when you select a group of various units, then adding one more unit into that. Game adds his pic next to other of his kind, sometimes breaking previous chain.

IIRC ingame heroes are always selected prior to normal units too

In my prev testing my half-handles only went higher and IDs were the same, thats why I had perfect implementation. Whenever half-handle gonna get lower for any reason groups will start shaking.

As well, whenever you add a unit to the group, you dont know which half-handle he has, so he may come at any place possible

So, conclusion:
Adding a hero (its just matter of the first letter, could even be an illusion) to a group with no heroes yet will 100% put him on the top
Adding non-hero to a group where at least 1 hero already exists will never put this unit on the top.

And yea, ForGroup going through units just like they're linked in the group.

 

[IcemanBo]

Sorry, could you explain half handle and 2D array idea again? I have problems to understand it. But I'm also not sure how your explanations could explain demo's behaviour. Or maybe just because I did not fully undersand it..

 

[TempMail]

just like I said,removing unit frees up his handle and halfhandles as well, so counter goes down, allowing to create a unit with lower halfhandle than previous one. Dont ask me on that, it's just unit creation being more than 1 handle in fact, if you check. Tons of objects are used in process, and even if handle ids itself kinda grow up, half-handle can still get lower value than previous one just because some inner (?) object got cleaned up.

Each object has 2 values in 0xC 0x10 offsets. They determine his real memory address. All info passed between players about actions uses this half-handles to explain who is got ordered, where, whom. We can imagine it as 2D array, where half-handles provides X/Y cell coordinates. 0xC == 0x1234, 0x10 == 0x8C8C, convert that with special func and you'll get proper address of the object with no collision possible. Thats how game manage all objects to keep it sync.

Anyway, case solved

 

[IcemanBo]

Where do you read the half handle from, and why do you call it half handle?