[Snippet] GetClosestUnit(s)

Level 9
Joined
Mar 25, 2005
Messages
252

GetClosestUnit(s) v1.3.1
finds the unit, or group of units closest to a point faster than any existing alternative

v1.3.1
  • removed unnecessary GroupClear calls
v1.3
  • GetClosestUnit function is now smart
  • GetClosestUnitAlt: a new function that resembles the old and simple GetClosestUnit function (since it can be faster than the smart version in some rare cases)
  • GetClosestUnit and GetClosestUnitInRange now use ForGroup() instead of And() making them a lot faster
v1.2b
  • apparently boolexprs created with And() leak every time they are created, these leaks have now been removed from GCU
v1.2
  • added a description and comments
  • replaced bj_globals with own private globals (again from HINDYhat's request)
v1.1
  • fixed a few bugs in GetClosestUnit(s)InGroup and also replaced a few global groups with local ones (thx HINDYhat)
  • changed library name from GetClosestUnit to GCU
JASS:
//==============================================================================
//---DiscipleOfLife's-----------------------------------------------------------

//          GCU // GetClosestUnit(s) v1.3.1

//------------------------------------------------------------------------------
//
//  This library contains the following functions, each of which return the
//  unit that is closest to given coordinates and passes a specified filter:
//
//  - GetClosestUnit(x, y, filter)
//  - GetClosestUnitAlt(x, y, filter)
//  - GetClosestUnitInRange(x, y, radius, filter)
//  - GetClosestUnitInGroup(x, y, g)
//
//  Included are also the following functions, each of which return a
//  group consisting of the units closest to given coordinates that
//  pass a specified filter:
//
//  - GetClosestUnits(x, y, n, filter)
//  - GetClosestUnitsInRange(x, y, radius, n, filter)
//  - GetClosestUnitsInGroup(x, y, g, n)
//
//  Important:
//
//  - flying heights and the height of the ground aren't taken into account,
//    only the distance in 2D
//
//  - these functions can't be used in the boolexpr's passed to them
//
//  - all of the functions in this library go through many units to find the
//    closest one, meaning that the functions' performance is highly dependant
//    on the amount of units they have to go through
//
//------------------------------------------------------------------------------
library GCU
    
    globals
        private unit CurrentPick
        private real CenterX
        private real CenterY
        private real CurrentDistance
        private group AnyGroup = CreateGroup()
    endglobals
    
    private function Enum takes nothing returns nothing
        local unit u = GetEnumUnit()
        local real dx = GetUnitX(u) - CenterX
        local real dy = GetUnitY(u) - CenterY
        local real d = (dx*dx + dy*dy) / 10000.
        if d < CurrentDistance then
            set CurrentDistance = d
            set CurrentPick = u
        endif
        set u = null
    endfunction
    
    //==========================================================================
    // Finds the unit that is closest to (x, y) from all units on the map that
    // pass the filter and do not have the locust ability.
    //
    function GetClosestUnit takes real x, real y, boolexpr filter returns unit
        local real r = 800.
        loop
            call GroupEnumUnitsInRange(AnyGroup, x, y, r, filter)
            exitwhen FirstOfGroup(AnyGroup) != null
            if r >= 3200. then
                call GroupEnumUnitsInRect(AnyGroup, bj_mapInitialPlayableArea, filter)
                exitwhen true
            endif
            set r = 2.00 * r
        endloop
        set CurrentPick = null
        set CenterX = x
        set CenterY = y
        set CurrentDistance = 100000
        call ForGroup(AnyGroup, function Enum)
        return CurrentPick
    endfunction
    
    //==========================================================================
    // Does the same as above. Faster when there are no units that pass the
    // filter in a 3200 radius, but at other times slower, and most likely a
    // lot slower. How much faster is somewhat directly proportional to the
    // amount of units that do not pass the filter inside that 3200 radius.
    //
    function GetClosestUnitAlt takes real x, real y, boolexpr filter returns unit
        set CurrentPick = null
        set CenterX = x
        set CenterY = y
        set CurrentDistance = 100000
        call GroupEnumUnitsInRect(AnyGroup, bj_mapInitialPlayableArea, filter)
        call ForGroup(AnyGroup, function Enum)
        return CurrentPick
    endfunction
    
    
    //==========================================================================
    // Finds the unit that is closest to (x, y) from all units in the specified
    // radius, that pass the filter and do not have the locust ability.
    //
    function GetClosestUnitInRange takes real x, real y, real radius, boolexpr filter returns unit
        set CurrentPick = null
        set CenterX = x
        set CenterY = y
        set CurrentDistance = 100000
        call GroupEnumUnitsInRange(AnyGroup, x, y, radius, filter)
        call ForGroup(AnyGroup, function Enum)
        return CurrentPick
    endfunction
    
    //==========================================================================
    // Finds the unit that is closest to (x, y) from whichGroup. Unlike the
    // other versions this one considers locusted units also.
    //
    function GetClosestUnitInGroup takes real x, real y, group whichGroup returns unit
        set CurrentPick = null
        set CenterX = x
        set CenterY = y
        set CurrentDistance = 100000
        call ForGroup(whichGroup, function Enum)
        return CurrentPick
    endfunction
    
    //==========================================================================
    // The following three functions do the same as the preceding ones, with  //
    // the exception that they return groups consisting of the n closest      //
    // units instead of the closest unit                                      //
    //==========================================================================
    
    globals
        private group ResultGroup
    endglobals
    
    function GetClosestUnits takes real x, real y, integer n, boolexpr filter returns group
        call GroupEnumUnitsInRect(AnyGroup, bj_mapInitialPlayableArea, filter)
        set ResultGroup = CreateGroup()
        set CenterX = x
        set CenterY = y
        loop
            exitwhen n == 0
            set CurrentPick = null
            set CurrentDistance = 100000
            call ForGroup(AnyGroup, function Enum)
            exitwhen CurrentPick == null
            call GroupRemoveUnit(AnyGroup, CurrentPick)
            call GroupAddUnit(ResultGroup, CurrentPick)
            set n = n - 1
        endloop
        return ResultGroup
    endfunction
    
    function GetClosestUnitsInRange takes real x, real y, real radius, integer n, boolexpr filter returns group
        call GroupEnumUnitsInRange(AnyGroup, x, y, radius, filter)
        set ResultGroup = CreateGroup()
        set CenterX = x
        set CenterY = y
        loop
            exitwhen n == 0
            set CurrentPick = null
            set CurrentDistance = 100000
            call ForGroup(AnyGroup, function Enum)
            exitwhen CurrentPick == null
            call GroupRemoveUnit(AnyGroup, CurrentPick)
            call GroupAddUnit(ResultGroup, CurrentPick)
            set n = n - 1
        endloop
        return ResultGroup
    endfunction
    
    private function AnyGroupAddGroupEnum takes nothing returns nothing
        call GroupAddUnit(AnyGroup, GetEnumUnit())
    endfunction
    
    function GetClosestUnitsInGroup takes real x, real y, group whichGroup, integer n returns group
        call GroupClear(AnyGroup)
        call ForGroup(whichGroup, function AnyGroupAddGroupEnum)
        set ResultGroup = CreateGroup()
        set CenterX = x
        set CenterY = y
        loop
            exitwhen n == 0
            set CurrentPick = null
            set CurrentDistance = 100000
            call ForGroup(AnyGroup, function Enum)
            exitwhen CurrentPick == null
            call GroupRemoveUnit(AnyGroup, CurrentPick)
            call GroupAddUnit(ResultGroup, CurrentPick)
            set n = n - 1
        endloop
        return ResultGroup
    endfunction
    
endlibrary // End of GetClosestUnit
//==============================================================================a
The code above requires JassHelper to work, whereas the code below doesn't
JASS:
//==============================================================================
//---DiscipleOfLife's-----------------------------------------------------------

//          GCU // GetClosestUnit(s) v1.3.1 without vJass

//------------------------------------------------------------------------------
//
//                Contents:
//
//  This library contains the following functions, each of which return the
//  unit that is closest to given coordinates and passes a specified filter:
//
//  - GetClosestUnit(x, y, filter)
//  - GetClosestUnitAlt(x, y, filter)
//  - GetClosestUnitInRange(x, y, radius, filter)
//  - GetClosestUnitInGroup(x, y, g)
//
//  Included are also the following functions, each of which return a
//  group consisting of the units closest to given coordinates that
//  pass a specified filter:
//
//  - GetClosestUnits(x, y, n, filter)
//  - GetClosestUnitsInRange(x, y, radius, n, filter)
//  - GetClosestUnitsInGroup(x, y, g, n)
//
//                  Notes:
//
//  - flying heights  and the  height of  the  ground  aren't  taken  into
//    account, only the distance in 2D
//
//  - these functions can't be used in the boolexpr's passed to them
//
//  - all of the functions in this library go through many units  to  find
//    the closest one, meaning that the functions'  performance is  highly
//    dependant on the amount of units they have to go through
//
//    - this without vJass version is as efficient as the vJass version
//
//                Implementing Instructions:
//
//  - either  paste this system  into  your map's  header  or  inside  any
//    trigger  that  has been  converted  to  custom text, that  has  been
//    created before any other triggers  in which you wish  to  use  these
//    functions!
//
//  - press  Ctrl+B to open  the variable  editor and create the following
//    variables leaving their initial values to the default ones
//
//              Type        Name
//              Unit        GCU_CurrentPick
//              Real        GCU_CurrentX
//              Real        GCU_CurrentY
//              Real        GCU_CurrentDistance
//              Unit Group  GCU_AnyGroup
//              Unit Group  GCU_ResultingGroup
//
//       - congrats, you are done!
//
//------------------------------------------------------------------------------
    
    function GCU_Enum takes nothing returns nothing
        local unit u = GetEnumUnit()
        local real dx = GetUnitX(u) - udg_GCU_CurrentX
        local real dy = GetUnitY(u) - udg_GCU_CurrentY
        local real d = (dx*dx + dy*dy) / 10000.
        if d < udg_GCU_CurrentDistance then
            set udg_GCU_CurrentDistance = d
            set udg_GCU_CurrentPick = u
        endif
        set u = null
    endfunction
    
    //==========================================================================
    // Finds the unit that is closest to (x, y) from all units on the map that
    // pass the filter and do not have the locust ability.
    //
    function GetClosestUnit takes real x, real y, boolexpr filter returns unit
        local real r = 800.
        loop
            call GroupEnumUnitsInRange(udg_GCU_AnyGroup, x, y, r, filter)
            exitwhen FirstOfGroup(udg_GCU_AnyGroup) != null
            if r >= 3200. then
                call GroupEnumUnitsInRect(udg_GCU_AnyGroup, bj_mapInitialPlayableArea, filter)
                exitwhen true
            endif
            set r = 2.00 * r
        endloop
        set udg_GCU_CurrentPick = null
        set udg_GCU_CurrentX = x
        set udg_GCU_CurrentY = y
        set udg_GCU_CurrentDistance = 100000
        call ForGroup(udg_GCU_AnyGroup, function GCU_Enum)
        return udg_GCU_CurrentPick
    endfunction
    
    //==========================================================================
    // Does the same as above. Faster when there are no units that pass the
    // filter in a 3200 radius, but at other times slower, and most likely a
    // lot slower. How much faster is somewhat directly proportional to the
    // amount of units that do not pass the filter inside that 3200 radius.
    //
    function GetClosestUnitAlt takes real x, real y, boolexpr filter returns unit
        set udg_GCU_CurrentPick = null
        set udg_GCU_CurrentX = x
        set udg_GCU_CurrentY = y
        set udg_GCU_CurrentDistance = 100000
        call GroupEnumUnitsInRect(udg_GCU_AnyGroup, bj_mapInitialPlayableArea, filter)
        call ForGroup(udg_GCU_AnyGroup, function GCU_Enum)
        return udg_GCU_CurrentPick
    endfunction
    
    
    //==========================================================================
    // Finds the unit that is closest to (x, y) from all units in the specified
    // radius, that pass the filter and do not have the locust ability.
    //
    function GetClosestUnitInRange takes real x, real y, real radius, boolexpr filter returns unit
        set udg_GCU_CurrentPick = null
        set udg_GCU_CurrentX = x
        set udg_GCU_CurrentY = y
        set udg_GCU_CurrentDistance = 100000
        call GroupEnumUnitsInRange(udg_GCU_AnyGroup, x, y, radius, filter)
        call ForGroup(udg_GCU_AnyGroup, function GCU_Enum)
        return udg_GCU_CurrentPick
    endfunction
    
    //==========================================================================
    // Finds the unit that is closest to (x, y) from whichGroup. Unlike the
    // other versions this one considers locusted units also.
    //
    function GetClosestUnitInGroup takes real x, real y, group whichGroup returns unit
        set udg_GCU_CurrentPick = null
        set udg_GCU_CurrentX = x
        set udg_GCU_CurrentY = y
        set udg_GCU_CurrentDistance = 100000
        call ForGroup(whichGroup, function GCU_Enum)
        return udg_GCU_CurrentPick
    endfunction
    
    //==========================================================================
    // The following three functions do the same as the preceding ones, with  //
    // the exception that they return groups consisting of the n closest      //
    // units instead of the closest unit                                      //
    //==========================================================================
    
    function GetClosestUnits takes real x, real y, integer n, boolexpr filter returns group
        call GroupEnumUnitsInRect(udg_GCU_AnyGroup, bj_mapInitialPlayableArea, filter)
        set udg_GCU_ResultingGroup = CreateGroup()
        set udg_GCU_CurrentX = x
        set udg_GCU_CurrentY = y
        loop
            exitwhen n == 0
            set udg_GCU_CurrentPick = null
            set udg_GCU_CurrentDistance = 100000
            call ForGroup(udg_GCU_AnyGroup, function GCU_Enum)
            exitwhen udg_GCU_CurrentPick == null
            call GroupRemoveUnit(udg_GCU_AnyGroup, udg_GCU_CurrentPick)
            call GroupAddUnit(udg_GCU_ResultingGroup, udg_GCU_CurrentPick)
            set n = n - 1
        endloop
        return udg_GCU_ResultingGroup
    endfunction
    
    function GetClosestUnitsInRange takes real x, real y, real radius, integer n, boolexpr filter returns group
        call GroupEnumUnitsInRange(udg_GCU_AnyGroup, x, y, radius, filter)
        set udg_GCU_ResultingGroup = CreateGroup()
        set udg_GCU_CurrentX = x
        set udg_GCU_CurrentY = y
        loop
            exitwhen n == 0
            set udg_GCU_CurrentPick = null
            set udg_GCU_CurrentDistance = 100000
            call ForGroup(udg_GCU_AnyGroup, function GCU_Enum)
            exitwhen udg_GCU_CurrentPick == null
            call GroupRemoveUnit(udg_GCU_AnyGroup, udg_GCU_CurrentPick)
            call GroupAddUnit(udg_GCU_ResultingGroup, udg_GCU_CurrentPick)
            set n = n - 1
        endloop
        return udg_GCU_ResultingGroup
    endfunction
    
    function GCU_AnyGroupAddGroupEnum takes nothing returns nothing
        call GroupAddUnit(udg_GCU_AnyGroup, GetEnumUnit())
    endfunction
    
    function GetClosestUnitsInGroup takes real x, real y, group whichGroup, integer n returns group
        call GroupClear(udg_GCU_AnyGroup)
        call ForGroup(whichGroup, function GCU_AnyGroupAddGroupEnum)
        set udg_GCU_ResultingGroup = CreateGroup()
        set udg_GCU_CurrentX = x
        set udg_GCU_CurrentY = y
        loop
            exitwhen n == 0
            set udg_GCU_CurrentPick = null
            set udg_GCU_CurrentDistance = 100000
            call ForGroup(udg_GCU_AnyGroup, function GCU_Enum)
            exitwhen udg_GCU_CurrentPick == null
            call GroupRemoveUnit(udg_GCU_AnyGroup, udg_GCU_CurrentPick)
            call GroupAddUnit(udg_GCU_ResultingGroup, udg_GCU_CurrentPick)
            set n = n - 1
        endloop
        return udg_GCU_ResultingGroup
    endfunction
    
           // End of GetClosestUnit
//==============================================================================
 
Last edited:
Level 40
Joined
Dec 14, 2005
Messages
10,532
Basically, if you give them a radius and coordinates, it finds the unit closest to the coordinates matching certain conditions (including being in that radius), although some assume radius is infinite.

I'll give these the standard checkup once I return from vacation, Monday night or Tuesday afternoon.
 
Level 9
Joined
Mar 25, 2005
Messages
252
Found a bug. In the GetClosestUnitInGroup function:
JASS:
call ForGroup( bj_groupAddGroupDest, function Enum2)
Should be:
JASS:
call ForGroup( whichGroup, function Enum2)

Other than that, why are you using global groups everywhere?

Damn I feel stupid right now. Fixed that bug now and removed 2 unneccessary globals uses. Thx & +rep.
Right now the bj_groupRemoveGroupDest global is used because it is returned in the functions it is in. The G global is just an empty group that is never filled with anything since the filter I use with it returns always false. (Using a null group instead doesn't work.)
In GetClosestUnitsInGroup I use bj_groupAddGroupDest because the GroupAddGroupEnum function fills it automaticly.

Now I have actually tested all of them -.-... I thought I had but seems like I skipped the Group versions :(. Pls forgive me.
 
Level 20
Joined
Apr 22, 2007
Messages
1,960
I understand the use of bj_groupAddGroupDest, but I don't understand the use of bj_groupRemoveGroupDest... You should use a local to avoid double frees or just randomness with globals.

Maybe you should add some documentation (mostly considering locusted units and enums) or something about each function : some people don't understand very easily. Extra documentation is always nice.

If you fix those two issues, I think this is good for approval. Might ask another mod though first.
 
Level 9
Joined
Mar 25, 2005
Messages
252
Maybe you should add some documentation (mostly considering locusted units and enums) or something about each function : some people don't understand very easily. Extra documentation is always nice.
Updated to 1.2 which now includes documentation.

I understand the use of bj_groupAddGroupDest, but I don't understand the use of bj_groupRemoveGroupDest... You should use a local to avoid double frees or just randomness with globals.

bj_groupRemoveGroupDest, which I know replaced with a private global 'resultingGroup' in v1.2, is a global because if it was local I would have to null it, but I cant null and return it at the same time.[jass=Example failure]function A takes nothing returns group
local group g = CreateGroup()
// ...actions...
set g = null
return g // == return null
endfunction[/code]


The new version uses 'G' instead of bj_groupAddGroupDest, so there shouldn't be any possible conflicts regarding bj_globals anymore.
 
Level 20
Joined
Apr 22, 2007
Messages
1,960
Why would you have to null it...? If the user is calling that function, then the local is being passed to another use, so the nulling falls in the hands of the user (like it always should). Really, use of a global group here is completely unnecessary, but I'll try to get a second opinion to strengthen my cause.
 
Level 13
Joined
Nov 22, 2006
Messages
1,260
FirstOfGroup gets the first unit in that group, the first unit added to that group. This code gets the closest unit measured from a certain point, so the distance is main here.

JASS:
local group g = CreateGroup()
local unit u = .....
local unit v = .....
local unit z = .....
local unit f
call GroupAddUnit(g, u)
call GroupAddUnit(g, v)
call GroupAddUnit(g, z)

set f = FirstOfGroup(g)


FirstOfGroup will return the "u" unit in this case, get it?

The only thing I'm wondering is in what order do GroupEnums add units.......if somebody finds out, maybe that could be used somehow?
 
Level 20
Joined
Apr 22, 2007
Messages
1,960
Can't test right now, but that would be a quick way to test.
JASS:
function filter takes nothing returns boolean
    call BJDebugMsg(R2S(GetUnitY(GetFilterUnit())))
    return true
endfunction

function test takes nothing returns nothing
    local real y=0.
    local group g=CreateGroup()
    loop
        exitwhen y>=750.
        call CreateUnit(Player(0),'hpea',0.,y,0.)
        set y=y+75.
    endloop
    call GroupEnumUnitsInRange(g,0.,0.,750.,Filter(function filter))
    call DestroyGroup(g)
    set g=null
endfunction
 
Level 9
Joined
Mar 25, 2005
Messages
252
Some spacings wouldn't kill you, otherwise, nice job.

ty

When I posted this there were tabs but no empty lines. Now it has empty lines but no tabs lol. I use Notepad++, perhaps the Hive doesnt like it. I'll see if I can get a prettier version posted here :).

EDIT: I just replaced all tabs with 4 spaces. Shows correctly atleast on my comp now.
 
Last edited:
Level 9
Joined
Mar 25, 2005
Messages
252
Untill you do that you can use the freshly coded "without vJass" version.

I haven't tested if it works in game. I only renamed the global variables to use udg_GCU prefix, as well as removed all private keywords and the library so I highly doubt that it wouldn't work :).

EDIT: About efficiency which you were wondering:

The no-vJass version is almost identical to the vJass version. The only difference that affects performance is that the vJass version uses a precomputed boolexpr while the no-vJass version doesn't. This difference shouldn't be anything to worry about.
 
Level 7
Joined
Mar 12, 2006
Messages
407
sorry for digging this out but i would like to know if i can use this as a very frequent event lets say like every second
how much would that influence the overall performance ? may it cause lagg along with other functions ?
I dont know much about jass so i cant really guess it myself
 
Level 9
Joined
Mar 25, 2005
Messages
252
Only once per second shouldn't be a problem at all, unless you have several hundreds of units that need to be searched through to find the closest one. Generally it is best to use the function that goes through the least amount of units possible, for example GetClosestUnitInRange instead of GetClosestUnit whenever the range limit doesn't bother you.

EDIT:
New version 1.3 is now up. Its GetClosestUnit most often avoids going through all units on the map unlike the old one, thus the new one should be a lot faster on maps with a lot of units in it.
 
Last edited:
Level 9
Joined
Mar 25, 2005
Messages
252
The normal version requires you to have jasshelper whereas the vJassless doesn't, but on the other hand when importing the vJassless version you have to create a few global variables with the Trigger Editor's variable editor.

The current versions of both of the systems (1.3.1) are identical when it comes to performance and functionality, except that the normal version is in a library called GCU and thus can be required by other libraries.
 
Level 12
Joined
Aug 20, 2007
Messages
866
Damn, I made my own version of this using 3D, and just getclosestofgroup, as it seemed to be the most generic + efficient way to use the function for each situation

I didn't even think about using ForGroup() :ugly:

I think you might want to add in a 3D version too, just incase your working with projectiles and the such
 
Level 13
Joined
Nov 22, 2006
Messages
1,260
I think you might want to add in a 3D version too, just incase your working with projectiles and the such

Nobody cares for the third dimension in wc3 because there are many algorithms and calculations when working in 3D plus it's very possible that you'll never get it right...... it's just not worth it and it doesn't make much difference.

But you can post your 3D version if you know how to make it :)
 
Level 12
Joined
Aug 20, 2007
Messages
866
For a 3-D GetClosestUnit, all you need to do is add another real parameter for the Z, and incorporate the Z calculations for the pythagorean theroem, instead of x*x + y*y = d*d, it becomes x*x + y*y + z*z = d*d

Ok, I will post a 3D version, for this specific case, it is much more simple than using any crazy algorithms
 
Level 11
Joined
May 21, 2009
Messages
997
Hello, i have a very "stupid" question. But there is something in vJass i always wondered. How do you use this ? I know how to copy library, but do you call the library's name when you wanna use it ? sorry for noobish question ;/
 
Hello, i have a very "stupid" question. But there is something in vJass i always wondered. How do you use this ? I know how to copy library, but do you call the library's name when you wanna use it ? sorry for noobish question ;/

You call it with vJass / Custom Scripts:
JASS:
call LIBRARYNAME_FUNCTION(PARAMETERS)

for exmaple:
JASS:
local group g = GetClosestUnitsInRange(0., 0., 285, 25, null)
 
Level 15
Joined
Oct 18, 2008
Messages
1,588
God... Could some1 help me? :D I want to use this trigger for my map, but I have 2+1 problems:
1. I want it not to check plyar 11's and 12's units.
2. I don't really know how to implement it in my exceptionally complex trigger system...

and the +1:IDK Jass... There isn't any script language which is a little similar to it... I understand 60-70% of it but some functins are weird xD And I don't really know how to make the sorting thing I said ;)
 
Top