• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

[Snippet] GetClosestWidget

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
Old.
GetClosestWidget is snippet that gives user a quick way to find nearest destructable (any), destructable (tree), item or unit.

There was already GetClosestUnit by DiscipleOfLife, although there are few possible improvements which haven't been added since user is inactive for 1,5 year. However, this snippet contains those.

Some of you probably are thinking about usefullness of finding closest destructables or item, but I have found it usefull in my map with heroes based on items manipulation or nature powers. Example of usage getting nearest tree is obviously DotA and hero Rooftrellen (Treant Protector).

Optionaly requires IsDestructableTree.
- Vesrion 1.0.0.0 Release
- Vesrion 1.0.1.0 Removed GetClosestNUnits function and fixed issue with Fixed GetClosestNUnitsInGroup() picking the same unit all the time
- Version 1.0.0.1 Removed GroupClear() in GetClosestUnit
- Version 2.0.0.0 Performence drop while using "NUnits" type functions highly reduced; snippet has been rewritten
Special thanks to Bribe, baassee and Troll-Brain.

Rewritten. Modularity, configurability and efficiency - sums up the update.
Note: treeOnly parameter (destructable module) cease to exist, reasoning: there is a filter argument already, thus if you want to seach for trees-only do it there.

JASS:
/*****************************************************************************
*
*    GetClosestWidget v3.0.1.3
*       by Bannar aka Spinnaker
*
*    Allows finding closest widget with ease.
*
******************************************************************************
*
*    Configurables:
*
*       Choose which modules should or should not be implemented.
*
*          constant boolean UNITS_MODULE
*          constant boolean GROUP_MODULE
*          constant boolean ITEMS_MODULE
*          constant boolean DESTS_MODULE
*
*       Define start and final distances for search iterations within generic GetClosest functions.
*       If final value is reached, enumeration is performed on whole map.
*
*          constant real START_DISTANCE
*          constant real FINAL_DISTANCE
*
******************************************************************************
*
*    Functions:
*
*       Units:
*        | function GetClosestUnit takes real x, real y, boolexpr filter returns unit
*        |    returns unit closest to coords(x, y)
*        | 
*        | function GetClosestUnitInRange takes real x, real y, real radius, boolexpr filter returns unit
*        |    returns unit closest to coords(x, y) within range radius
*        | 
*        | function GetClosestUnitInGroup takes real x, real y, group g returns unit
*        |    returns unit closest to coords(x, y) within group g
*
*
*       Group:
*        | function GetClosestNUnitsInRange takes real x, real y, real radius, integer n, group dest, boolexpr filter returns nothing
*        |    adds to group dest up to N units, closest to coords(x, y) within range radius
*        | 
*        |  function GetClosestNUnitsInGroup takes real x, real y, integer n, group source, group dest returns nothing
*        |    adds to group dest up to N units, closest to coords(x, y) within group source
*
*
*       Items:
*        | function GetClosestItem takes real x, real y, boolexpr filter returns item
*        |    returns item closest to coords(x, y)
*        | 
*        | function GetClosestItemInRange takes real x, real y, real radius, boolexpr filter returns item
*        |    returns item closest to coords(x, y) within range radius
*
*
*       Destructables:
*        | function GetClosestDestructable takes real x, real y, boolexpr filter returns destructable
*        |    returns destructable closest to coords(x, y)
*        | 
*        | function GetClosestDestructableInRange takes real x, real y, real radius, boolexpr filter returns destructable
*        |    returns destructable closest to coords(x, y) within range radius
*
*
*****************************************************************************/
library GetClosestWidget

    globals
        private constant boolean UNITS_MODULE   = true
        private constant boolean GROUP_MODULE   = true
        private constant boolean ITEMS_MODULE   = true
        private constant boolean DESTS_MODULE   = true

        private constant real    START_DISTANCE = 800
        private constant real    FINAL_DISTANCE = 3200
    endglobals

    globals
        private real distance
        private real coordX
        private real coordY
    endglobals

	private keyword GroupModule

    private function calcDistance takes real x, real y returns real
        local real dx = x - coordX
        local real dy = y - coordY
        return ( (dx*dx + dy*dy) / 10000 )
    endfunction

    private struct ClosestWidget extends array
		static if UNITS_MODULE then
			static unit unit
			static group group = CreateGroup()
		endif

		static if GROUP_MODULE then
			static if not UNITS_MODULE then
				static group group = CreateGroup()
			endif
			static integer count = 0
			static unit array sorted
			static real array vector

			implement GroupModule
		endif

		static if ITEMS_MODULE then
			static item item
			static rect area = Rect(0, 0, 0, 0)
		endif

		static if DESTS_MODULE then
			static destructable destructable
			static if not ITEMS_MODULE then
				static rect area = Rect(0, 0, 0, 0)
			endif
		endif
	endstruct

    private function Defaults takes real x, real y returns nothing
	    static if UNITS_MODULE then
            set ClosestWidget.unit = null
        endif
        static if ITEMS_MODULE then
            set ClosestWidget.item = null
        endif
        static if DESTS_MODULE then
            set ClosestWidget.destructable = null
        endif

        set distance = 100000
        set coordX = x
        set coordY = y
    endfunction

    static if UNITS_MODULE then
        //! runtextmacro DEFINE_GCW_UNIT_MODULE()
    endif
    static if GROUP_MODULE then
        //! runtextmacro DEFINE_GCW_GROUP_MODULE()
    endif
    static if ITEMS_MODULE then
        //! runtextmacro DEFINE_GCW_MODULE("Item", "item")
    endif
    static if DESTS_MODULE then
        //! runtextmacro DEFINE_GCW_MODULE("Destructable", "destructable")
    endif

//! textmacro DEFINE_GCW_UNIT_MODULE

    private function doEnumUnits takes unit u returns nothing
        local real dist = calcDistance(GetUnitX(u), GetUnitY(u))

        if ( dist < distance ) then
            set ClosestWidget.unit = u
            set distance = dist
        endif
    endfunction

    private function enumUnits takes nothing returns nothing
        call doEnumUnits(GetEnumUnit())
    endfunction

    function GetClosestUnit takes real x, real y, boolexpr filter returns unit
        local real r = START_DISTANCE
        local unit u
        call Defaults(x, y)

        loop
            if ( r > FINAL_DISTANCE ) then
                call GroupEnumUnitsInRect(ClosestWidget.group, GetWorldBounds(), filter)
                exitwhen true
            else
                call GroupEnumUnitsInRange(ClosestWidget.group, x, y, r, filter)
                exitwhen FirstOfGroup(ClosestWidget.group) != null
            endif
            set r = 2*r
        endloop

        loop
            set u = FirstOfGroup(ClosestWidget.group)
            exitwhen u == null
            call doEnumUnits(u)
            call GroupRemoveUnit(ClosestWidget.group, u)
        endloop

        return ClosestWidget.unit
    endfunction

    function GetClosestUnitInRange takes real x, real y, real radius, boolexpr filter returns unit
        local unit u
        call Defaults(x, y)

        if ( radius >= 0 ) then
            call GroupEnumUnitsInRange(ClosestWidget.group, x, y, radius, filter)
            loop
                set u = FirstOfGroup(ClosestWidget.group)
                exitwhen u == null
                call doEnumUnits(u)
                call GroupRemoveUnit(ClosestWidget.group, u)
            endloop
        endif

        return ClosestWidget.unit
    endfunction

    function GetClosestUnitInGroup takes real x, real y, group g returns unit
        call Defaults(x, y)
        call ForGroup(g, function enumUnits)
        return ClosestWidget.unit
    endfunction

//! endtextmacro

//! textmacro DEFINE_GCW_GROUP_MODULE

	private module GroupModule

		static method doSaveUnits takes unit u returns nothing
			set count = count + 1
			set sorted[count] = u
			set vector[count] = calcDistance(GetUnitX(u), GetUnitY(u))
		endmethod

		static method saveUnits takes nothing returns nothing
			call doSaveUnits(GetEnumUnit())
		endmethod

		static method sortUnits takes integer lo, integer hi returns nothing
			local integer i = lo
			local integer j = hi
			local real pivot = vector[(lo+hi)/2]

			loop
				loop
					exitwhen vector[i] >= pivot
					set i = i + 1
				endloop
				loop
					exitwhen vector[j] <= pivot
					set j = j - 1
				endloop

				exitwhen i > j

				set vector[0] = vector[i]
				set vector[i] = vector[j]
				set vector[j] = vector[0]

				set sorted[0] = sorted[i]
				set sorted[i] = sorted[j]
				set sorted[j] = sorted[0]

				set i = i + 1
				set j = j - 1
			endloop

			if ( lo < j ) then
				call sortUnits(lo, j)
			endif
			if ( hi > i ) then
				call sortUnits(i, hi)
			endif
		endmethod

		static method fillGroup takes integer n, group dest returns nothing
			loop
				exitwhen count <= 0 or sorted[count] == null
				if ( count <= n ) then
					call GroupAddUnit(dest, sorted[count])
				endif
				set sorted[count] = null
				set count = count - 1
			endloop
		endmethod

	endmodule

    function GetClosestNUnitsInRange takes real x, real y, real radius, integer n, group dest, boolexpr filter returns nothing
        local unit u
        call Defaults(x, y)

        if ( radius >= 0 )then
            call GroupEnumUnitsInRange(ClosestWidget.group, x, y, radius, filter)
            loop
                set u = FirstOfGroup(ClosestWidget.group)
                exitwhen u == null
                call ClosestWidget.doSaveUnits(u)
                call GroupRemoveUnit(ClosestWidget.group, u)
            endloop

            call ClosestWidget.sortUnits(1, ClosestWidget.count)
            call ClosestWidget.fillGroup(n, dest)
        endif
    endfunction

    function GetClosestNUnitsInGroup takes real x, real y, integer n, group source, group dest returns nothing
        local integer i = 0
        call Defaults(x, y)

        call ForGroup(source, function ClosestWidget.saveUnits)
        call ClosestWidget.sortUnits(1, ClosestWidget.count)
        call ClosestWidget.fillGroup(n, dest)
    endfunction

//! endtextmacro

//! textmacro DEFINE_GCW_MODULE takes NAME, TYPE

    private function enum$NAME$s takes nothing returns nothing
        local $TYPE$ temp = GetEnum$NAME$()
        local real dist = calcDistance(Get$NAME$X(temp), Get$NAME$Y(temp))

        if ( dist < distance ) then
            set ClosestWidget.$TYPE$ = temp
            set distance = dist
        endif

        set temp = null
    endfunction

    function GetClosest$NAME$ takes real x, real y, boolexpr filter returns $TYPE$
        local real r = START_DISTANCE
        call Defaults(x, y)

        loop
            if ( r > FINAL_DISTANCE ) then
                call Enum$NAME$sInRect(GetWorldBounds(), filter, function enum$NAME$s)
                exitwhen true
            else
                call SetRect(ClosestWidget.area, x-r, y-r, x+r, y+r)
                call Enum$NAME$sInRect(ClosestWidget.area, filter, function enum$NAME$s)
                exitwhen ClosestWidget.$TYPE$ != null
            endif
            set r = 2*r
        endloop

        return ClosestWidget.$TYPE$
    endfunction

    function GetClosest$NAME$InRange takes real x, real y, real radius, boolexpr filter returns $TYPE$
        call Defaults(x, y)

        if ( radius > 0 ) then
            call SetRect(ClosestWidget.area, x-radius, y-radius, x+radius, y+radius)
            call Enum$NAME$sInRect(ClosestWidget.area, filter, function enum$NAME$s)
        endif

        return ClosestWidget.$TYPE$
    endfunction

//! endtextmacro

endlibrary

Demo code:
JASS:
globals
	unit paladin = null
	group all = CreateGroup()
	group closest = CreateGroup()
endglobals

struct gcw_test extends array
    static method filter takes nothing returns boolean
        return GetFilterUnit() != paladin
    endmethod

    static method printU takes string prefix, unit u returns nothing
        call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, prefix + GetUnitName(u))
    endmethod

    static method printI takes string prefix, item i returns nothing
        call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, prefix + GetItemName(i))
    endmethod

    static method printD takes string prefix, destructable d returns nothing
        call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, prefix + GetDestructableName(d))
    endmethod

    static method call_test takes nothing returns boolean
        local real x = GetUnitX(paladin)
        local real y = GetUnitY(paladin)

        call GroupClear(closest)
        call ClearTextMessages()
        call GetClosestNUnitsInGroup(x, y, 1, all, closest)

        call printU("closest unit: ", GetClosestUnit(x, y, Filter(function thistype.filter)))
        call printU("closest unit within group: ", FirstOfGroup(closest))
        call printI("closest item: ", GetClosestItem(x, y, null))
        call printD("closest destructable: ", GetClosestDestructable(x, y, null))
        return false
    endmethod

    static method onInit takes nothing returns nothing
        local trigger t = CreateTrigger()
        call TriggerRegisterTimerEvent(t, 3, true)
        call TriggerAddCondition(t, function thistype.call_test)
        set t = null

        set paladin = CreateUnit(Player(0), 'Hpal', 0, 0, 0)
        call GroupEnumUnitsInRange(all, 0, 0, 5000, function thistype.filter)
    endmethod
endstruct
 
Last edited:

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
So basicaly you mean to get rid of resultGroup, in replacement we add additional parameter required by 'NUnits' functions, yeah?
If yes, would it be okey to clear the passed group first? or just add units into it?
JASS:
    function GetClosestNUnits takes real x, real y, integer n, boolexpr filter returns group
        call GroupEnumUnitsInRect(bj_lastCreatedGroup, bj_mapInitialPlayableArea, filter)
        call ResetData(x,y)
        call GroupClear(resultGroup)
        loop
            exitwhen 0 == n
            call ForGroup(bj_lastCreatedGroup, function EnumUnits)
            exitwhen closestUnit == null
            call GroupRemoveUnit(bj_lastCreatedGroup, closestUnit)
            call GroupAddUnit(resultGroup, closestUnit)
            set closestUnit = null
            set closestDistance = 100000
            set n = n - 1
        endloop
        return resultGroup
    endfunction

->>
JASS:
    function GetClosestNUnits takes real x, real y, integer n, group g, boolexpr filter returns group
        call GroupEnumUnitsInRect(bj_lastCreatedGroup, bj_mapInitialPlayableArea, filter)
        call ResetData(x,y)
        loop
            exitwhen 0 == n
            call ForGroup(bj_lastCreatedGroup, function EnumUnits)
            exitwhen closestUnit == null
            call GroupRemoveUnit(bj_lastCreatedGroup, closestUnit)
            call GroupAddUnit(g, closestUnit)
            set closestUnit = null
            set closestDistance = 100000
            set n = n - 1
        endloop
    endfunction
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
Adding units to it would be fine because the user should have cleared the group his/her self in such a case.

The reason I would really find it useful is if you wanted to acquire all the targets for a chain lightining type spell. To be fair, it's almost not worth even including GetClosestNUnits because the situations are limited. But it's your call.
 

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
I think it's reasonable thinking truely. If user wants group of units, he probably will need his own group anyways, plus yeah, it smoother and gives oportunity to use that group later.

~Removed the GetClosestNUnits
You are right once again Bribe, if user wants unit group without specific range, he can type enormous number anyways..
Heh, I was testing posibilities not to enumerate immidiately the entire map, and it ends with removing whole function.. thanks Bribe ;<

Fixed GetClosestNUnitsInGroup() function; it was picking all the time the same unit.
~Updated: Version 1.0.1.0
 
Level 22
Joined
Nov 14, 2008
Messages
3,256
Good work with this one!

Only thing I could spot right now was:

call GroupClear(bj_lastCreatedGroup)

No need to that when GroupEnumUnitsInRange clears the group before enumeration. I gues that GroupEnumUnitsInRect works the same (else my point here is useless).

In the GetClosestUnit, forgot to mention.

Also, is that module initializer really necessary? Can't you just initialize it in the globals block?
 

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
IIRC "Rect" returns null from the globals block.
Yup! I haven't been checking it for a long time but it's like creating a unit from global block - sucks :p

Are you 100% sure that clearing bj_lastCreatedGroup isn't necessary? In case I couldn't test in completely and wasn't sure about that fact. Everyone agrees that it isn't necessary?
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
While I don't see the point of most of the functions, I still think this is
pretty well done.

Getting the closest item, for example, could be used for an auotmatic
item-pickup system.

I'm going to approve this because I can't see any glaring thing that
keeps me from doing so.

The only thing is to change GetItem/DestructableX/Y to GetWidgetX/Y,
because they are faster functions, but for some reason GetUnitX/Y are
faster than GetWidgetX/Y according to benchmarks.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
I've just read the last function GetClosestNUnitsInGroup, but it can be obvioulsy improved.
You don't need a temp group such as bj_..., yes the only valid way to enum all units is ForGroup (in a not instant group) but you have to do it only one time (remember each unit enumerated with a ForGroup = new thread).
You can at least replace the ForGroup in the loop by a double linked list iteration, while the first ForGroup call will build this linked list.

And again it can still be improved, by sorting the ranges in numeric order.
 

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
~Updated to v2.0.0.0
Performence drop while using "NUnits" type functions highly reduced - ForGroup is executed only once per function call. Additionaly, snippet has been rewritten to take adventage of structs.

I'd like to thank Troll-Brain for forcing me to do that.

Uploaded the light version in additional to the full one.
Mostly, people are using such functions just for getting units - the rest of snippet would be total overkill for them - thats why I to leave the choice for user: if he needs manipulation of all the widgets, full version gonna be perfect for him, or the light one, if units handling is enough.

Bribe, please change the thread title to: [Snippet] GetClosestWidget.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
Because of the cost of a function call in jass, a loop approach would be better than a recursive function call.

Also i think an extra parameter is needed for the GetClosestUnitInGroup function (and probably other ones), i don't really think someone want to get the nearest widget if it's completely far away the target.
I mean the user should precise a max range himself.

The local real "r" which defines a max range in some functions is also weird.
It could be at very least a constant instead, but i think a parameter is also better, just for the re-usability of the functions.

Also i'm not sure why the unique functions (which returns only one unit) have a filter argument while the N functions equivalents don't.

I don't get why you are using a loop for the GetClosestUnit, and even more why you are using a rect when the range is high enough, it's still innacurate.
I mean you should directly check for the highest range defined by the user, or if using this loop really improves the performance in case of many units in the whole map (that would make sense), the max range would still be up to the function user, as an argument.
 

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
Because of the cost of a function call in jass, a loop approach would be better than a recursive function call.
Lol, jass sucks.
Also i think an extra parameter is needed for the GetClosestUnitInGroup function (and probably other ones), i don't really think someone want to get the nearest widget if it's completely far away the target.
I mean the user should precise a max range himself.

Also i'm not sure why the unique functions (which returns only one unit) have a filter argument while the N functions equivalents don't.
I'm not sure about that - in case, if someone uses this function he probably already precised the group; he can use "InRange" function if he needs units in certain area.
And only the GetClosestNUnitsInGroup function doesn't own filter parameter - again, since he needs to pass source group parameter anyways, that group should have been filtered already. Filtering units is not the point of that function.

I mean, what would be the point of this function if filter and distance parameters were added? There is such function already and it's called GetClosestNUnitsInRange. The one, we are speaking about is for manipulation of already created group. For instance, how about random user who is performing timed spell effect with group set at the begining. During it's duration he needs to look for the nearest 2 targets from group previously created - thats what this function is for - he doesn't want to create new group, he just want to sort his one.
The local real "r" which defines a max range in some functions is also weird.
It could be at very least a constant instead, but i think a parameter is also better, just for the re-usability of the functions.

I don't get why you are using a loop for the GetClosestUnit, and even more why you are using a rect when the range is high enough, it's still innacurate.
I mean you should directly check for the highest range defined by the user, or if using this loop really improves the performance in case of many units in the whole map (that would make sense), the max range would still be up to the function user, as an argument.
That "r" real exists only in non specific functions, where users just wants the ClosestWidget. The local role is to reduce the performance drop, because in most cases searching immidiately whole map isn't nessecary. It can be converted to global tho, that might be ok.
 
Last edited:
Level 31
Joined
Jul 10, 2007
Messages
6,306
Try using iteration because function calls have so much overhead in Jass.

The sorting algorithm he used lends itself to recursion ; ).


Excellent resource, +rep : D.


edit
Actually, when I look at this more, this should be split up into different enum resources with GetClosestWidget using all of them. This isn't modular ; |.

edit
This should also be using first of group loops.. why oh why are you using ForGroup, lol.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
Nestharus said:
edit
This should also be using first of group loops.. why oh why are you using ForGroup, lol.

Because of ghost units, he could add a boolean argument i suppose, like in my resource UnitLL

Nestharus said:
Only in JASS is recursion slower than looping, lolz.

Are you 100 % sure ?, anyway the difference would be negligible. (at least with compiled languages)
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
However, this is what he said. I just randomly believe my college instructors when they say something.

What I've learned is most college instructors (at least in the US) would rather give you the answer rather than give you the correct answer.

For example Kindergarten-8th grade could be handled in 1-2 years. Too much of it is just fluff and unengagingly redundant
 

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
Hello,

Thanks for not burning this down into the depths of graveyard :>
Already updated GCW, but before I post update, few mentioned the ForGroup issue. Indeed its slower, however, there is a problem with "group" functions, example:
JASS:
    function GetNClosestUnitsInGroup takes real x, real y, integer n, group source, group dest returns nothing
        call default(x, y)
        // saveUnitEnum calls saveUnit(GetEnumUnit())
        // saveUnit(u) calculates distance from point(x, y) to coords of unit u
        call ForGroup(source, function saveUnitEnum)
        call sortUnits(1, count)
        loop
            exitwhen n <= 0 or sortedUnits[n] == null
            call GroupAddUnit(dest, sortedUnits[n])
            set sortedUnits[n] = null
            set n = n - 1
        endloop
        set count = 0
    endfunction
ForGroup allows us to keep source group without any changes, while using FirstOfGroup would require:
JASS:
    function GetClosestNUnitsInGroup takes real x, real y, integer n, group source, group dest returns nothing
        local group temp = CreateGroup()
        local unit u
        call default(x, y)

        loop
            set u = FirstOfGroup(source)
            exitwhen u == null
            call saveUnit(u)
            call GroupRemoveUnit(source, u)
            call GroupAddUnit(temp, u)
        endloop

        call sortUnits(1, count)

        loop
            exitwhen n <= 0 or sortedUnits[n] == null
            call GroupAddUnit(dest, sortedUnits[n])
            set sortedUnits[n] = null
            set n = n - 1
        endloop

        loop
            set u = FirstOfGroup(temp)
            exitwhen u == null
            call GroupRemoveUnit(temp, u)
            call GroupAddUnit(source, u)
        endloop

        call DestroyGroup(temp)
        set temp = null
        set count = 0
    endfunction
I've performed simple test via:
JASS:
function FilterExample takes nothing returns boolean
    return GetFilterUnit() != udg_u
endfunction

function CallTest takes nothing returns boolean
    local group test1 = CreateGroup()
    local group g = CreateGroup()
    local group test2 = CreateGroup()
    local integer sw = 0
    local real array time

    call GroupEnumUnitsInRange(test1, 0, 0, 5000, function FilterExample)
    call GroupEnumUnitsInRange(test2, 0, 0, 5000, function FilterExample)
    call ClearTextMessages()

    set sw = StopWatchCreate()
    call GetClosestNUnitsInGroup(GetUnitX(udg_u), GetUnitY(udg_u), 1, test1, g)
    set time[0] = StopWatchTicks(sw)
    call StopWatchDestroy(sw)

    set g = CreateGroup()
    set sw = StopWatchCreate()
    call GetNClosestUnitsInGroup(GetUnitX(udg_u), GetUnitY(udg_u), 1, test2, g)
    set time[1] = StopWatchTicks(sw)
    call StopWatchDestroy(sw)
   
    call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, "enum: " + R2S(time[0]) + " forgroup: "+ R2S(time[1]))
    if (time[0] > time[1]) then
        set time[2] = 100 - (time[1]/time[0] * 100)
        call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, "Method #2 is " + R2S(time[2]) + "% faster than Method #1\n")
    else
        set time[2] = 100 - (time[0]/time[1] * 100)
        call DisplayTextToPlayer(GetLocalPlayer(), 0, 0, "Method #1 is " + R2S(time[2]) + "% faster than Method #2\n")
    endif

    return false
endfunction

//===========================================================================
function InitTrig_Test takes nothing returns nothing
    local trigger t = CreateTrigger()
    set udg_u = gg_unit_Hpal_0008 // hero from attached test map
    call MeleeStartingVisibility()
    call FogEnableOff()
    call FogMaskEnableOff()
    call TriggerRegisterTimerEvent(t, 3, true)
    call TriggerAddCondition(t, Filter(function CallTest))
    set t = null
endfunction
What shows that overhead of additionals adding/removing is enough to make method #2 waster by about ~22%.

Have I missed smthing? Is any other method to iterate through group without changing the actual source? GroupEnum with filter?? Dont think it will be faster tho.

Thanks in advance.
 
GroupEnum will clear the group. ForGroup is the best way (IMO) to iterate through a group and preserve it. ForGroup is considered 'slow' because it runs on a separate thread and requires passing globals. However, it is usually more elegant than 2-3 loops. Think of it as a matter of computational complexity: ForGroup is O(N) whereas FirstOfGroup (with preservation) is O(2*N). Even if in some cases FirstOfGroup may be faster, we generally lean towards the lower complexity, as a general rule of thumb (which is why we recommend hashtables over linked list searches, where applicable, even if the lists tend to be low in size).

FirstOfGroup is great when you don't need the group to be preserved, but IMO it is excessive when you need to maintain the group.
 

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
@Purge, thank you for replay, although you havent had to explain me the difference between ForGroup and FirstOfGroup ;>

I was asking for advice due to Nestharus' "why oh why you use ForGroup (...)" and this stopped me from posting update today. Was thinking: meaby I've missed something? Meaby there is a better way?
Anyways, additional clarification doesn't hurt.
Indeed, in "range" functions, FirstOfGroup is a choice of ours, however, I couldnt bare using FoG in "group" cases. Whatmore, benchmark pretty much ensured me that in those functions, ForGroup prevails.
 

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
Okey, so the next question: what do you think about dividing script into modules as mentioned earlier? Honestly, splitting this to GetClosestUnit/Destructable/Item libraries that require GetClosestWidget does not please me. Here is an update, and proposed "modularity" (unit part has been omited).
JASS:
library GetClosestWidget

    globals
        private constant boolean UNITS_MODULE = true
        private constant boolean ITEMS_MODULE = true
        private constant boolean DESTS_MODULE = true

        private constant real START_DISTANCE  = 800
        private constant real FINAL_DISTANCE  = 3200
    endglobals

    /**
        Begining of internal script
    */

    globals
        private unit array sorted
        private real array vector
        private integer count = 0

        private real distance = 0
        private real coordX = 0
        private real coordY = 0

        private unit closestUnit = null
        private rect rectangle = null
    endglobals

    private module ClosestWidgetInit
        private static method onInit takes nothing returns nothing
            set rectangle = Rect(0, 0, 0, 0)
        endmethod
    endmodule

    struct ClosestWidget extends array
        implement ClosestWidgetInit
    endstruct

    private keyword closestDestructable
    private keyword closestItem

    private function default takes real x, real y returns nothing
        static if DESTS_MODULE then
            set closestDestructable = null
        endif
        static if ITEMS_MODULE then
            set closestItem = null
        endif
        set closestUnit = null

        set distance = 100000
        set coordX = x
        set coordY = y
    endfunction

    private function calcDistance takes real x, real y returns real
        local real dx = x - coordX
        local real dy = y - coordY
        return ( (dx*dx + dy*dy) / 10000 )
    endfunction

    private function cbEnumUnits takes unit u returns nothing
        local real dist = calcDistance(GetUnitX(u), GetUnitY(u))
        if ( dist < distance ) then
            set closestUnit = u
            set distance = dist
        endif
    endfunction

    private function enumUnits takes nothing returns nothing
        call cbEnumUnits(GetEnumUnit())
    endfunction

    private function cbSaveUnits takes unit u returns nothing
        set count = count + 1
        set sorted[count] = u
        set vector[count] = calcDistance(GetUnitX(u), GetUnitY(u))
    endfunction

    private function saveUnits takes nothing returns nothing
        call cbSaveUnits(GetEnumUnit())
    endfunction

    private function sortUnits takes integer lo, integer hi returns nothing
        local integer i = lo
        local integer j = hi
        local real pivot = vector[(lo+hi)/2]
        loop
            loop
                exitwhen vector[i] >= pivot
                set i = i + 1
            endloop
            loop
                exitwhen vector[j] <= pivot
                set j = j - 1
            endloop

            exitwhen i > j
            // use index 0 as temp variable
            set vector[0] = vector[i]
            set vector[i] = vector[j]
            set vector[j] = vector[0]

            // set unit array accordingly
            set sorted[0] = sorted[i]
            set sorted[i] = sorted[j]
            set sorted[j] = sorted[0]
            set i = i + 1
            set j = j - 1
        endloop

        if ( lo < j ) then
            call sortUnits(lo, j)
        endif
        if ( hi > i ) then
            call sortUnits(i, hi)
        endif
    endfunction

    function GetClosestUnit takes real x, real y, boolexpr filter returns unit
        local real r = START_DISTANCE
        local unit u
        call default(x, y)

        loop
            if ( r > FINAL_DISTANCE ) then
                call GroupEnumUnitsInRect(bj_lastCreatedGroup, bj_mapInitialPlayableArea, filter)
                exitwhen true
            else
                call GroupEnumUnitsInRange(bj_lastCreatedGroup, x, y, r, filter)
                exitwhen FirstOfGroup(bj_lastCreatedGroup) != null
            endif
            set r = 2*r
        endloop

        loop
            set u = FirstOfGroup(bj_lastCreatedGroup)
            exitwhen u == null
            call cbEnumUnits(u)
            call GroupRemoveUnit(bj_lastCreatedGroup, u)
        endloop

        return closestUnit
    endfunction

    function GetClosestUnitInRange takes real x, real y, real radius, boolexpr filter returns unit
        local unit u
        call default(x, y)

        if ( radius >= 0 ) then
            call GroupEnumUnitsInRange(bj_lastCreatedGroup, x, y, radius, filter)
            loop
                set u = FirstOfGroup(bj_lastCreatedGroup)
                exitwhen u == null
                call cbEnumUnits(u)
                call GroupRemoveUnit(bj_lastCreatedGroup, u)
            endloop
            set u = null
        endif

        return closestUnit
    endfunction

    function GetClosestUnitInGroup takes real x, real y, group g returns unit
        call default(x, y)
        call ForGroup(g, function enumUnits)
        return closestUnit
    endfunction

    function GetClosestNUnitsInRange takes real x, real y, real radius, integer n, group dest, boolexpr filter returns nothing
        local unit u
        call default(x, y)
        set count = 0

        if ( radius >= 0 )then
            call GroupEnumUnitsInRange(bj_lastCreatedGroup, x, y, radius, filter)
            loop
                set u = FirstOfGroup(bj_lastCreatedGroup)
                exitwhen u == null
                call cbSaveUnits(u)
                call GroupRemoveUnit(bj_lastCreatedGroup, u)
            endloop

            set u = null
            call sortUnits(1, count)

            loop
                exitwhen n <= 0 or sorted[n] == null
                call GroupAddUnit(dest, sorted[n])
                set sorted[n] = null
                set n = n - 1
            endloop
        endif
    endfunction

    function GetClosestNUnitsInGroup takes real x, real y, integer n, group source, group dest returns nothing
        call default(x, y)
        set count = 0

        call ForGroup(source, function saveUnits)
        call sortUnits(1, count)

        loop
            exitwhen n <= 0 or sorted[n] == null
            call GroupAddUnit(dest, sorted[n])
            set sorted[n] = null
            set n = n - 1
        endloop
    endfunction

    static if ITEMS_MODULE then
        //! runtextmacro DEFINE_GCW_MODULE("Item", "item")
    endif
    static if DESTS_MODULE then
        //! runtextmacro DEFINE_GCW_MODULE("Destructable", "destructable")
    endif

//! textmacro DEFINE_GCW_MODULE takes NAME, TYPE
    globals
        private $TYPE$ closest$NAME$ = null
    endglobals

    private function enum$NAME$s takes nothing returns nothing
        local $TYPE$ temp = GetEnum$NAME$()
        local real dist = calcDistance(Get$NAME$X(temp), Get$NAME$Y(temp))

        if ( dist < distance ) then
            set closest$NAME$ = temp
            set distance = dist
        endif

        set temp = null
    endfunction

    function GetClosest$NAME$ takes real x, real y, boolexpr filter returns $TYPE$
        local real r = START_DISTANCE
        call default(x, y)

        loop
            if ( r > FINAL_DISTANCE ) then
                call Enum$NAME$sInRect(bj_mapInitialPlayableArea, filter, function enum$NAME$s)
                exitwhen true
            else
                call SetRect(rectangle, x-r, y-r, x+r, y+r)
                call Enum$NAME$sInRect(rectangle, filter, function enum$NAME$s)
                exitwhen closest$NAME$ != null
            endif
            set r = 2*r
        endloop

        return closest$NAME$
    endfunction

    function GetClosest$NAME$InRange takes real x, real y, real radius, boolexpr filter returns $TYPE$
        call default(x, y)
        if ( radius > 0 ) then
            call SetRect(rectangle, x-radius, y-radius, x+radius, y+radius)
            call Enum$NAME$sInRect(rectangle, filter, function enum$NAME$s)
        endif
        return closest$NAME$
    endfunction
//! endtextmacro

endlibrary
Same api, less code, better readability, FoG, and no fucking q, v (...) variables. The only important thing to mention: lack of "treeOnly" parameter in "destructable"-ish version of api - reasoning: those functions already require filter, thus if user does not want any dests beside trees, he will probably do that via filter.
 

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
Yes, you're free and safe to use it, if it fits ur needs. With last update, only the method and efficiency has changed, not the API (except for "trees"), thus compatability is kept.

Also, now you have more control under what should/shouldn't be included (modularity), and additional globals used in generic GetClosest methods to minimise lag issues if those are present.
 
Level 11
Joined
Oct 11, 2012
Messages
711
It is already on the JASS section so it is approved... anything that needs approval is on the submissions section

Yes, you're free and safe to use it, if it fits ur needs. With last update, only the method and efficiency has changed, not the API (except for "trees"), thus compatability is kept.

Also, now you have more control under what should/shouldn't be included (modularity), and additional globals used in generic GetClosest methods to minimise lag issues if those are present.

Thanks for both of you and especially Bannar for making this resource. :)
 
Top