Groups or Unit Arrays?

[WereElf]

At the moment I'm making one system, which uses unit groups, and FoG loops.

However, FoG doesn't work well if a unit from the group gets removed from the game while in the group.

Would it be better if I use Unit Array + a counter for my system instead?

Or perhaps there is an even better solution?

I could have an event, that detects when a unit leaves playable map area, and remove it from the Groups my system uses. Would that work?
And what if the unit is forced out of the playable map area trough "SetUnitX/Y", and is later returned to the map area?

 

[Anitarf]

There was a thread posted quite recently about this.

Arrays are definitely the better choice.

 

[WereElf]

Yeah, I've seen it, but I wasn't really sure what "linked lists" are until yesterday.
Just to make sure, is that how I should do it, or can you provide a better script?

globals
    integer last_freed
    integer array list_indexes
    integer max
    unit array unit_list
    integer array list_order
    integer array reverse_info
endglobals

function ListAddUnit takes unit u returns nothing
    local integer indx = last_freed
    if last_freed == 0 then
        set indx = max + 1
        set max = indx
    else
        set last_freed = list_indexes[last_freed]
    endif
    set list_indexes[indx] = -1
    set unit_list[indx] = u
    set list_order[0] = list_order[0] + 1
    set list_order[list_order[0]] = indx
    set reverse_info[indx] = list_order[0]
endfunction

function FreeIndex takes integer indx returns nothing
    if list_indexes[indx] == -1 then
        set list_indexes[indx] = last_freed
        set last_freed = indx
        set list_order[reverse_info[indx]] = list_order[list_order[0]]
        set list_order[0] = list_order[0] - 1
    endif
endfunction

function GroupLoop takes nothing returns nothing
    local integer i = 1
    loop
         exitwhen i > list_order[0]
         // do actions to unit unit_list[list_order[i]]
         set i = i + 1
    endloop
endfunction

I kind a just made this up, I'm not sure if this will even work

Perhaps I could just use a struct and save the struct's index into the list_order, and then it'd be simpler, but my question is if there is more efficient way, not "easier to define way".

 

[Anitarf]

Perhaps I could just use a struct and save the struct's index into the list_order, and then it'd be simpler, but my question is if there is more efficient way, not "easier to define way".

You're asking the wrong question. It should definitely be "how to make this simpler", not "how to make this more efficient". This is a fairly simple script and yet I am completely unable to follow your logic because it's so unreadable. Like, what are you trying to do here: set list_order[0] = list_order[1] + 1?

You should definitely use a struct, as far as I can tell what you're using now pretty much is the standard struct allocator code anyway.

 

[WereElf]

Sorry, that was supposed to be list_order[0] = list_order[0] + 1
Anyways... I "got" half of this script from Bribe, and it took me a while to understand how it works too. I added the other half just now, and I haven't really tested it (wrote it directly in Hive, not in the WE)
So the idea is:
1) Bribe's part:
- when you create an entry, and there are no "returned/free" indexes - it creates a new one (and sets the max to + 1)
- when an index is freed - it's saved as "last_freed"
- when another index is freed - the one freed before that is saved into the list of the new "last_freed"
- when an index is re-created - it takes the "last_freed" and loads the index freed before that, from the list (using "last_freed" as index).

(I admit its quite confusing, and I had to put it in the Editor and test it to understand what it actually does).

2) My part:
- I save the order in which indexes are given
- When a middle index is freed - I put the "last" index on its place.

Example would be the simplest way to explain things:
Bribe's part:
"create" gives 1, "create" gives 2, "create" gives 3, "create" gives 4, "create" gives 5.
"destroy 3" - 3 is saved as "last_freed", and "0" is saved in it.
"destroy 1" - 1 is saved as "last_freed", and "3" is saved in it.
"create" - returns 1, and loads "3" from it (and assigns that as the new "last_freed")
"create" - returns 3, and loads "0" from it (and assigns that as the new "last_freed")
"create" - since last freed is "0" - it just gives a new value = 6

My part:
Imagine that the same actions are done:
1 is saved as 1; 2 is saved as 2.... 5 is saved as 5.
When a loop is done - it will go from 1 to 5, and will act normally.
Okay... so when 3 is freed, the setup will become like this:
[1] = 1; [2] = 2; [3] = 5; [4] = 4; ([5] = 5, but the loop is from 1 to 4, so [5] isn't used)
Then 1 is freed too, and the order looks like this:
[1] = 4; [2] = 2; [3] = 5; ([4] and [5] still have values, but they aren't used, cuz the loop is from 1 to 3)
Then we re-assign 1 and 3, and the list starts looking like this:
[1] = 4; [2] = 2; [3] = 5; [4] = 1; [5] = 3

Hope you understood it with the example

EDIT: Perhaps I could GREATLY simplify that....

globals
    indx = -1
    unit_list array
endglobals

function ListAddUnit takes unit u returns nothing
    set indx = indx + 1
    set unit_list[indx] = u
endfunction

function ListRemoveUnit takes index i returns nothing
    set unit_list[i] = unit_list[indx]
    set indx = indx - 1
endfunction

I have no idea why did I think of the hellishly confusing way before thinking of this simple, but efficient way xP

 

[Anitarf]

You don't have to explain Bribe's part of the code, like I said, that's standard struct allocator code, I understand that part. You could just replace that with a struct and have essentially the same thing, only considerably more readable.

I now also get what your part of the code was trying to do, that's a classic array approach to maintaining a list of active instances, I just didn't recognise it because I thought you were trying to use a linked list approach, not an array.

It can be simplified to what you wrote in your last post, but then the moment you start storing additional values in your arrays beside the unit, those values must all be transcribed whenever you remove a unit from the list, which would not be needed with the additional "struct" layer between the array and the data.

With a true linked list approach, you wouldn't have this problem because you would never need to transcribe a unit to a different index. The units would stay where they are and only the links between them would get rearranged so that they would skip any unit that got removed from the list:

struct listed
    unit u

    readonly thistype next
    readonly thistype prev
    static method operator first takes nothing returns thistype
        return thistype(0).next
    endmethod
    static method operator last takes nothing returns thistype
        return thistype(0).prev
    endmethod

    method ListAdd takes nothing returns nothing
        // we can add extra safety checks here to make sure this is not yet listed
        set thistype(0).next.prev = this
        set this.next = thistype(0).next
        set this.prev = thistype(0)
        set thistype(0).next = this
    endmethod

    method listRemove takes nothing returns nothing
        // we can add extra safety checks here to make sure this is already listed
        set this.next.prev = this.prev
        set this.prev.next = this.next
    endmethod

    static method loop takes nothing returns nothing
        local thistype this = thistype.first
        loop
            exitwhen this==0
            // do stuff
            set this = this.next
        endloop
    endmethod
endstruct

You can write this code every time you need a list of all instances, or you could just implement a module to do that instead of you. If you're doing standard periodic updates, then you can use a different module that also handles the timer and looping.

 

[WereElf]

Okay, I looked at this, and I didn't really undestand it.
I think I got some idea what it does, but I'm curious what's this "thistype(0)".
I tried to test it, but then I figured I don't know how

Would it be something like:

function testFunc takes nothing returns nothing
    local group g = CreateGroup()
    local unit u
    local listed l = listed.create()
    call GroupEnumUnitsInRect(g, bj_mapInitialPlayableArea, null)
    loop
        set u = FirstOfGroup(g)
        exitwhen u == null
        set l.u = u
        call l.AddList()
        call GroupRemoveUnit(g, u)
    endloop
    call l.listRemove()
    call l.loop()
    call DestroyGroup(g)
    set g = null
endfunction

 

[Anitarf]

thistype(0) is a typecasting operation, it typecasts the integer 0 into a "listed" struct instance ("thistype" is a generic replacement keyword for the type of the struct it is written in, it was designed to be used with modules but you can use it anywhere in a struct). Since the index 0 never gets used when allocating structs, it's a handy place to store the first and last nodes of a list. Alternatively, we could store them in dedicated static members but then we'd need a bunch of extra ifs inside the listAdd and listRemove methods.

In your example, you need to create a struct instance for each unit.

function PeriodicUpdate
    call listed.loop()
endfunction

function Init takes nothing returns nothing
    local group g = CreateGroup()
    local unit u
    local listed l
    call GroupEnumUnitsInRect(g, bj_mapInitialPlayableArea, null)
    loop
        set u = FirstOfGroup(g)
        exitwhen u == null

        set l = listed.create()
        set l.u = u
        call l.listAdd()

        call GroupRemoveUnit(g, u)
    endloop

    call DestroyGroup(g)
    set g = null
    set u = null

    call TimerStart( NewTimer(), 1.0, true, function PeriodicUpdate )
endfunction

 

[WereElf]

Ah, I see, now it makes sense (kind a, would need to re-check the script when I'm not so tired).
Anyways... since a list needs to be created every time before using the listAdd, why isn't listAdd just replaced with a static "create" method?

EDIT: Okay, I understant it now

 

[Anitarf]

You could just add the code from listAdd to the create method (and the code from listRemove to the destroy method), however, sometimes, you might want to create an instance without immediately adding it to the update list. Even when you always want all instances to be on the list, it's better to put list code into separate methods and call those methods from create/destroy, just to make the code more readable.

 

[WereElf]

I kind a re-made my sliding library to use this linked list method.
Is that any good?

library Sliding requires Destructables

    globals
        constant real Tick = 0.06
        private timer NormalTimer = CreateTimer()
        private boolean NormalRuning = false
        private timer ToUnitTimer = CreateTimer()
        private boolean ToUnitRuning = false
        private timer ToCoordinatesTimer = CreateTimer()
        private boolean ToCoordinatesRuning = false
    endglobals

    private struct Normal
        unit u
        real ang
        real distance
        real time
        boolean rough

        readonly thistype next
        readonly thistype prev
        static method operator first takes nothing returns thistype
            return thistype(0).next
        endmethod
        static method operator last takes nothing returns thistype
            return thistype(0).prev
        endmethod

        static method create takes unit u, real ang, real speed, real time, boolean rough returns thistype
            local thistype this = thistype.allocate()
            set thistype(0).next.prev = this
            set this.next = thistype(0).next
            set this.prev = thistype(0)
            set thistype(0).next = this
            set this.u = u
            set this.ang = ang*bj_DEGTORAD
            set this.distance = speed*Tick
            set this.time = time
            set this.rough = rough
            return this
        endmethod

        method onDestroy takes nothing returns nothing
            if this.first == this.last then
                set NormalRuning = false
                call PauseTimer(NormalTimer)
            endif
            set this.next.prev = this.prev
            set this.prev.next = this.next
        endmethod

        static method slide takes nothing returns nothing
            local thistype this = thistype.first
            local real x
            local real y
            loop
                exitwhen this == 0
                set x = GetUnitX(this.u) + this.distance*Cos(this.ang)
                set y = GetUnitY(this.u) + this.distance*Sin(this.ang)
                if this.rough then
                    if IsUnitType(this.u , UNIT_TYPE_GROUND) then
                        call DestroyEffect(AddSpecialEffect("Abilities\\Spells\\Human\\FlakCannons\\FlakTarget.mdl",x,y))
                        call EnumDestructablesInCircle( x, y, 150, function KillTrees)
                    endif
                    call SetUnitPosition( this.u , x , y )
                else
                    call SetUnitX(this.u, x)
                    call SetUnitY(this.u, y)
                endif
                set this.time = this.time - Tick
                if this.time <= 0 then
                    call Normal.destroy(this)
                endif
                set this = this.next
            endloop
        endmethod
    endstruct

    private function NormalLoop takes nothing returns nothing
        call Normal.slide()
    endfunction

    function Slide takes unit u, real ang, real time, real speed, boolean s_type returns nothing
        local Normal list = Normal.create(u, ang, speed, time, s_type)
        if not NormalRuning then
            set NormalRuning = true
            call TimerStart(NormalTimer, Tick, true, function NormalLoop)
        endif
    endfunction

    private struct ToUnit
        unit u
        unit t
        real distance
        real end
        trigger tr

        readonly thistype next
        readonly thistype prev
        static method operator first takes nothing returns thistype
            return thistype(0).next
        endmethod
        static method operator last takes nothing returns thistype
            return thistype(0).prev
        endmethod

        static method create takes unit u, unit t, real speed, real end, trigger tr returns thistype
            local thistype this = thistype.allocate()
            set thistype(0).next.prev = this
            set this.next = thistype(0).next
            set this.prev = thistype(0)
            set thistype(0).next = this
            set this.u = u
            set this.t = t
            set this.distance = speed*Tick
            set this.end = end
            set this.tr = tr
            return this
        endmethod

        method onDestroy takes nothing returns nothing
            if this.first == this.last then
                set ToUnitRuning = false
                call PauseTimer(ToUnitTimer)
            endif
            set this.next.prev = this.prev
            set this.prev.next = this.next
        endmethod

        static method slide takes nothing returns nothing
            local thistype this = thistype.first
            local real x
            local real y
            local real xt
            local real yt
            local real h
            local real w
            local real a
            local integer id
            loop
                exitwhen this == 0
                set x = GetUnitX(this.u)
                set y = GetUnitY(this.u)
                set xt = GetUnitX(this.t)
                set yt = GetUnitY(this.t)
                set a = Atan2(yt - y, xt - x)
                set x = x + this.distance*Cos(a)
                set y = y + this.distance*Sin(a)
                set h = yt - y
                set w = xt - x
                call SetUnitX(this.u, x)
                call SetUnitY(this.u, y)
                if this.tr != null then
                    set id = GetHandleId(this.tr)
                    call SaveUnitHandle(udg_Table, id, 'unit', this.u)
                    call SaveUnitHandle(udg_Table, id, 'targ', this.t)
                    call SaveReal(udg_Table, id, 'dist', SquareRoot(h*h+w*w))
                    call TriggerEvaluate(this.tr)
                    call FlushChildHashtable(udg_Table, id)
                endif
                if h*h + w*w <= this.end*this.end or IsUnitDeadBJ(this.u) or IsUnitDeadBJ(this.t) then
                    call ToUnit.destroy(this)
                endif
                set this = this.next
            endloop
        endmethod
    endstruct

    function ToUnitLoop takes nothing returns nothing
        call ToUnit.slide()
    endfunction

    function SlideToUnit takes unit u, unit d, real speed, real end, trigger tr returns nothing
        local ToUnit list = ToUnit.create(u, d, speed, end, tr)
        if not ToUnitRuning then
            set ToUnitRuning = true
            call TimerStart(ToUnitTimer, Tick, true, function ToUnitLoop)
        endif
    endfunction
    
    private struct ToCoordinates
        unit u
        real x
        real y
        real distance
        trigger tr

        readonly thistype next
        readonly thistype prev
        static method operator first takes nothing returns thistype
            return thistype(0).next
        endmethod
        static method operator last takes nothing returns thistype
            return thistype(0).prev
        endmethod

        static method create takes unit u, real x, real y, real speed, trigger tr returns thistype
            local thistype this = thistype.allocate()
            set thistype(0).next.prev = this
            set this.next = thistype(0).next
            set this.prev = thistype(0)
            set thistype(0).next = this
            set this.u = u
            set this.x = x
            set this.y = y
            set this.distance = speed*Tick
            set this.tr = tr
            return this
        endmethod

        method onDestroy takes nothing returns nothing
            if this.first == this.last then
                set ToCoordinatesRuning = false
                call PauseTimer(ToCoordinatesTimer)
            endif
            set this.next.prev = this.prev
            set this.prev.next = this.next
        endmethod

        static method slide takes nothing returns nothing
            local thistype this = thistype.first
            local real x
            local real y
            local real a
            local integer id
            loop
                exitwhen this == 0
                set x = GetUnitX(this.u)
                set y = GetUnitY(this.u)
                set a = Atan2(this.y - y, this.x -x)
                if IsUnitDeadBJ(this.u) then
                    call ToCoordinates.destroy(this)
                elseif (this.x - x)*(this.x - x) + (this.y - y)*(this.y - y) >= this.distance*this.distance then
                    call SetUnitX(this.u, x + Cos(a)*this.distance)
                    call SetUnitY(this.u, y + Sin(a)*this.distance)
                    if this.tr != null then
                        set id = GetHandleId(this.tr)
                        call SaveUnitHandle(udg_Table, id, 'unit', this.u)
                        call SaveReal(udg_Table, id, 'desx', this.x)
                        call SaveReal(udg_Table, id, 'desy', this.y)
                        call TriggerEvaluate(this.tr)
                        call FlushChildHashtable(udg_Table, id)
                    endif
                else
                    call SetUnitX(this.u, this.x)
                    call SetUnitY(this.u, this.y)
                    if this.tr != null then
                        set id = GetHandleId(this.tr)
                        call SaveUnitHandle(udg_Table, id, 'unit', this.u)
                        call SaveReal(udg_Table, id, 'desx', this.x)
                        call SaveReal(udg_Table, id, 'desy', this.y)
                        call TriggerEvaluate(this.tr)
                        call FlushChildHashtable(udg_Table, id)
                    endif
                    call ToCoordinates.destroy(this)
                endif
                set this = this.next
            endloop
        endmethod
    endstruct

    function ToCoordinatesLoop takes nothing returns nothing
        call ToCoordinates.slide()
    endfunction

    function SlideTo takes unit u, real x, real y, real speed, trigger tr returns nothing
        local ToCoordinates list = ToCoordinates.create(u, x, y, speed, tr)
        if not ToCoordinatesRuning then
            set ToCoordinatesRuning = true
            call TimerStart(ToCoordinatesTimer, Tick, true, function ToCoordinatesLoop)
        endif
    endfunction

endlibrary

(Do have in mind, that this library is only for my needs, I'm not really planing to make it into a public resource)
Is there a way to call the loop every time the timer expires, without having to make an extra function to call the loop?

 

[Anitarf]

call TimerStart(NormalTimer, Tick, true, function Normal.slide) This doesn't work?

You could save yourself a lot of work if you just used an existing periodic loop module.