GetRandomSubGroupEnum bug

[xylign]

GetRandomSubGroup function in Blizzard.j has a subtle bug. The chance of picking multiple identical units can be different.

For instance, if we want to pick 2 random units from a group of 3 units: (a, b, c). Then we call GetRandomSubGroup in Blizzard.j, and it turns out like following:
The chance of getting (a, b) out of (a, b, c) is 4/9
The chance of getting (a, c) out of (a, b, c) is 2/9
The chance of getting (b, c) out of (a, b, c) is 1/3



Here's how I fixed this problem by overwriting blizzard.j function

function GetRandomSubGroupEnum takes nothing returns nothing
    if (bj_randomSubGroupWant > 0) then
        if (bj_randomSubGroupWant >= bj_randomSubGroupTotal) or (GetRandomReal(0,1) < bj_randomSubGroupChance) then
            // We either need every remaining unit, or the unit passed its chance check.
            call GroupAddUnit(bj_randomSubGroupGroup, GetEnumUnit())
            set bj_randomSubGroupWant = bj_randomSubGroupWant - 1
        endif
    endif
    set bj_randomSubGroupTotal = bj_randomSubGroupTotal - 1

    // Fixed by: xylign
    if (bj_randomSubGroupTotal > 0) then
      set bj_randomSubGroupChance = bj_randomSubGroupWant / I2R(bj_randomSubGroupTotal)
    endif

endfunction

In GetRandomSubGroupEnum function, when it goes through the group, it never changes the chance of picking subgroup units. However the size of remaining subgroup is decreasing each time it enums, which has caused the problem.

I wonder if anyone found that already but I've searched it and couldn't find any thread that mentioned it.

 

[Aniki]

Hehe... nice find, and a very nice fix! =)

We could also move everything inside the if (bj_randomSubGroupWant > 0) then, right?

function GetRandomSubGroupEnum takes nothing returns nothing
    if (bj_randomSubGroupWant > 0) then
        if (bj_randomSubGroupWant >= bj_randomSubGroupTotal) or (GetRandomReal(0,1) < bj_randomSubGroupChance) then
            // We either need every remaining unit, or the unit passed its chance check.
            call GroupAddUnit(bj_randomSubGroupGroup, GetEnumUnit())
            set bj_randomSubGroupWant = bj_randomSubGroupWant - 1
        endif

        set bj_randomSubGroupTotal = bj_randomSubGroupTotal - 1

        // Fixed by: xylign
        if (bj_randomSubGroupTotal > 0) then
          set bj_randomSubGroupChance = bj_randomSubGroupWant / I2R(bj_randomSubGroupTotal)
        endif
    endif
endfunction

 

[xylign]

Hehe... nice find, and a very nice fix! =)

We could also move everything inside the if (bj_randomSubGroupWant > 0) then, right?

function GetRandomSubGroupEnum takes nothing returns nothing
    if (bj_randomSubGroupWant > 0) then
        if (bj_randomSubGroupWant >= bj_randomSubGroupTotal) or (GetRandomReal(0,1) < bj_randomSubGroupChance) then
            // We either need every remaining unit, or the unit passed its chance check.
            call GroupAddUnit(bj_randomSubGroupGroup, GetEnumUnit())
            set bj_randomSubGroupWant = bj_randomSubGroupWant - 1
        endif

        set bj_randomSubGroupTotal = bj_randomSubGroupTotal - 1

        // Fixed by: xylign
        if (bj_randomSubGroupTotal > 0) then
          set bj_randomSubGroupChance = bj_randomSubGroupWant / I2R(bj_randomSubGroupTotal)
        endif
    endif
endfunction

I guess so, but here's my concern.
The line which decreases bj_randomSubGroupTotal was just outside of the if statement in the original blizzard.j. It might be there for a reason, or it might just be another mistake blizzard made decades ago. I would recommend perform some test to be safe.

 

[Wietlol]

Thats cool...
I was so kind to make a FirstOfGroup iterator function for it:

function GroupAddRandomUnits takes group destGroup, integer count, group sourceGroup returns group
    local group swap
    local unit FoG
    local integer remaining
    local real chance
    
    if count <=0 then
        return destGroup
    endif
    
    set swap = CreateGroup()
    set remaining = 0
    loop
        set FoG = FirstOfGroup(sourceGroup)
        exitwhen FoG == null
        call GroupRemoveUnit(sourceGroup, FoG)
        call GroupAddUnit(swap, FoG)
        set remaining = remaining +1
    endloop
    
    if remaining > 0 then
        loop
            set FoG = FirstOfGroup(swap)
            exitwhen FoG == null
            call GroupRemoveUnit(swap, FoG)
            call GroupAddUnit(sourceGroup, FoG)
            
            set chance = I2R(count) / remaining
            if count > 0 and (count >= remaining or GetRandomReal(0, 1) < chance) then
                call GroupAddUnit(destGroup, FoG)
                set count = count -1
            endif
            
            set remaining = remaining -1
        endloop
        
    endif
    call DestroyGroup(swap)
    
    return destGroup
endfunction

Simple use case:
local group randomUnits = GroupAddRandomUnits(CreateGroup(), 5, myGroup)

 

[Aniki]

I was so kind to make a FirstOfGroup iterator function for it:

Thanks, but it doesn't work =)...

 

[BPower]

Simple use case:
local group randomUnits = GroupAddRandomUnits(myGroup, 5, CreateGroup())

At first glance a bit confusing, as one could think myGroup is the target group.

GroupGetRandomUnits, GroupGetRandomUnitsFromGroup,.... i don't know.

Maybe GroupAddRandomUnits is a good function name and I just don't see it yet

 

[Wietlol]

I must say I didnt test it

At first, I was using whichGroup as first parameter, however because of some easy-to-understand reasons, I switched it over to sourceGroup... forgot to change the whichGroup to sourceGroup in the actual actions

I also kind of wonder how I missed the / (divide by) with the - (substract)
Anyway, editted it, should be working now

At first glance a bit confusing, as one could think myGroup is the target group.

GroupGetRandomUnits, GroupGetRandomUnitsFromGroup,.... i don't know.

Maybe GroupAddRandomUnits is a good function name and I just don't see it yet

Now that you mention it... yes having the first parameter the target group and the last the source group is actually better...

About the name... there is one thing that you should really keep in mind... with ALL my group functions actually.
Normal group functions like "GroupEnumUnitsBlaBlaBla" discards all the units it has and then adds the new units to that group...
My functions do not clear the group so the units are added to it.
Hence why I use "Add" instead of "Enum".
I also do not want to have super long function names... such as "GroupAddRandomNUnitsFromOtherGroupWithoutRemovingAlreadyExistingUnitsInTheTargetGroupHenceTheNameAddInsteadOfEnum".
Ok I might have gone a bit too far in that one.
I also wonder how you want to add random units to a group without loading them from a collection... and as far as vanilla JASS goes, the only unit collection is a group... so it is kind of straight forward to place "FromGroup" in it.

 

[WereElf]

Hmm... I'm kind a wondering, is this a good way to do it?:

loop
    set FoG = FirstOfGroup(g)
    exitwhen FoG == null
    set count = count + 1
    set uni[count] = FoG
    call GroupRemoveUnit(g, FoG)
endloop
loop
    exitwhen count == 0
    if amount < set_am
        set dice = GetRandomInt(1, count)
        GroupAddUnit(g, uni[dice])
        set uni[dice] = uni[count]
        set amount = amount + 1
    endif
    set uni[count] = null
    set count = count - 1
endloop

 

[Wietlol]

That is also good, however, you wont keep the group you initially had... so you can only do this for groups that you only want to use once.
It is also more recommended to also use the 0th index in the list... just for mainstream reasons

 

[Dr Super Good]

It is also more recommended to also use the 0th index in the list... just for mainstream reasons

It is because arrays are a pointer with an index offset. The pointer itself points towards the first element, and the index is then added to that pointer address to get other indices. The reasons why they do this could be debated, but most likely it is because it makes the most sense from a storage point of view. If index 1 was the first element it would mean the pointer would be pointing at memory belonging to another object.

 

[Wietlol]

I do have to add something to my previous post:
There is ofcourse one exception... for me at least.
When you want to keep 0 as an exception value.
Like if you do this: "set myArray = "blablabla"", and i would be null... 0 cause its an integer, then things get messed up.

But as long as you keep it clear when "total" is the length and when it is the last index, then it should be fine.

I also think that the storage point of view is kind of different in WC3... as arrays always have a size of 8192.
In a language where you have dynamically sized arrays and (most probably) have to define the size yourself, then it would make much more sense.