[vJASS] FindUnits

[Michael Peppers]

A small snippet I made a long time ago to find a nearest/furthest unit that I cleaned up a bunch recently, it might be too simple as a submission or may not be as good as the current alternative but I'd like to hear your opinion on this:

library FindUnits
//* ============================================================================= *
//* by Michael Peppers (v1.2 11/01/2022)                                          *
//*                                                                               *
//* To find units in a given area.                                                *
//*                                                                               *
//* 4 functions avaiable:                                                         *
//* ----------------------------------------------------------------------------- *
//* 1.0:                                                                          *
//* FindNearestUnit(real srcX, real srcY, real range, UnitSearchCond condition)   *
//* FindFarthestUnit(real srcX, real srcY, real range, UnitSearchCond condition)  *
//* ----------------------------------------------------------------------------- *
//* 1.2:                                                                          *
//* FindAnyNearestUnit(real srcX, real srcY, real range)                          *
//* FindAnyFarthestUnit(real srcX, real srcY, real range)                         *
//* ----------------------------------------------------------------------------- *
//*                                                                               *
//* 1.0 needs three real values and a condition: X, Y and range are the reals,    *
//* where X and Y are the point defining the center of the unit search            *
//* and range... well, is the range of the area in which we do the search.        *
//* The condition is used for... conditions, such as checking if a unit is alive, *
//* is owned by a particular player etc., the condition has to be a function and  *
//* can be private. 1.2 finds units without conditions. They return a unit value. *
//* ============================================================================= *

//Quick examples on how to use it:
//
// 1) With conditions:
//
//condition: unit we search for is alive and is a peasant
//private function Cond takes unit u returns boolean
//return (GetUnitTypeId(u) == 'hpea') and (GetUnitState(u, UNIT_STATE_LIFE) > 0.405)
//endfunction
//
//call IssueTargetOrder(Pig, "attack", FindNearestUnit(GetUnitX(Pig), GetUnitY(Pig), 1000, Cond))
//
// 2) Without conditions:
//
//call IssueTargetOrder(Pig, "attack", FindAnyNearestUnit(GetUnitX(Pig), GetUnitY(Pig), 1000))

public function interface UnitSearchCond takes unit u returns boolean

globals
    private UnitSearchCond func
    private unit Unit
    private real Dist
    private real unitX
    private real unitY
    private group ENUM = CreateGroup()
    private boolean nearest
endglobals

private function AnyUnitSearch takes nothing returns boolean
local real dx = unitX - GetUnitX(GetFilterUnit())
local real dy = unitY - GetUnitY(GetFilterUnit())
local real dist = (dx * dx + dy * dy)
if nearest then
    if (Dist < 0) or (dist < Dist) then
        set Unit = GetFilterUnit()
        set Dist = dist
    endif
else
    if (Dist < 0) or (dist > Dist) then
        set Unit = GetFilterUnit()
        set Dist = dist
    endif
endif
return false
endfunction

private function UnitSearch takes nothing returns boolean
local real dx
local real dy
local real dist
if func != 0 then
    if func.evaluate(GetFilterUnit()) == true then
        set dx = unitX - GetUnitX(GetFilterUnit())
        set dy = unitY - GetUnitY(GetFilterUnit())
        set dist = (dx * dx + dy * dy)
        if nearest then
            if (Dist < 0) or (dist < Dist) then
                set Unit = GetFilterUnit()
                set Dist = dist
            endif
        else
            if (Dist < 0) or (dist > Dist) then
                set Unit = GetFilterUnit()
                set Dist = dist
            endif
        endif
    endif
endif
return false
endfunction

function FindNearestUnit takes real srcX, real srcY, real range, UnitSearchCond condition returns unit
    set unitX = srcX
    set unitY = srcY
    set Dist = -1
    set Unit = null
    set nearest = true
    set func = condition
    call GroupEnumUnitsInRange(ENUM, unitX, unitY, range, Condition(function UnitSearch))
return Unit
endfunction

function FindFarthestUnit takes real srcX, real srcY, real range, UnitSearchCond condition returns unit
    set unitX = srcX
    set unitY = srcY
    set Dist = -1
    set Unit = null
    set nearest = false
    set func = condition
    call GroupEnumUnitsInRange(ENUM, unitX, unitY, range, Condition(function UnitSearch))
return Unit
endfunction

function FindAnyNearestUnit takes real srcX, real srcY, real range returns unit
    set unitX = srcX
    set unitY = srcY
    set Dist = -1
    set Unit = null
    set nearest = true
    call GroupEnumUnitsInRange(ENUM, unitX, unitY, range, Condition(function AnyUnitSearch))
return Unit
endfunction

function FindAnyFarthestUnit takes real srcX, real srcY, real range returns unit
    set unitX = srcX
    set unitY = srcY
    set Dist = -1
    set Unit = null
    set nearest = false
    call GroupEnumUnitsInRange(ENUM, unitX, unitY, range, Condition(function AnyUnitSearch))
return Unit
endfunction

endlibrary

Comparing it to the closest alternative that's present here on the Hive (GetClosestWidget):

Pros:

• More efficient as it uses a bunch less globals, the group used for the actual calculation never gets populated and it avoids any unnecessary calculations (like dividing the distance by 10000)
• Can search for the farthest unit in range if anybody ever needs to do that

Cons:

• Limited to just single units (although I have similar snippets around for Destructible and Tree searches, the latter of which used PitzerMike's version of IsDestructableTree)

 

[Elprede]

Your algorithm for finding nearest unit is not more efficient than the one used in GetClosestWidget if the range is high enough. GetClosestWidget gradually increases the distance detected to the desired target distance. That way, not all units are enumerated and filtered at once or need to be if the unit is found in a short range.

 

[Michael Peppers]

Your algorithm for finding nearest unit is not more efficient than the one used in GetClosestWidget if the range is high enough. GetClosestWidget gradually increases the distance detected to the desired target distance. That way, not all units are enumerated and filtered at once or need to be if the unit is found in a short range.

That's (partially) true and it's something I didn't catch at first about GetClosestWidget but it depends on a whole lot of factors, first if you pass a range below or equal 800 to my script then mine is more efficient by design, second, if the nearest/farthest unit is in a distance higher than 800 from the starting search point my script is yet again more efficient, as GetClosestWidget in that case would make multiple searches instead of just one, which is bad.

Even in the cases when the unit search is in a Range above 800 and the unit one has to find is below that number the performance difference is pretty much debatable as GetClosestWidget populates a group variable and then removes units from it, I don't exactly know how much overhead is added by doing something like that and it might not be such a big deal, but still, I feel like populating a group for such a search is unnecessary and could be easily avoided.

In short, I guess in some cases GetClosestWidget would be more efficient but I find there's a bunch of unnecessary overhead that's present in that script that overall makes it less efficient than mine in execution in a lot of other cases and hampers its increased efficiency in the cases where it would be better anyway. The idea of saving performance by doing more searches starting on lower ranges and then ramping it up is neat but it has flaws in itself and is brought down by other design choices that were made in that same script.

 

[Bribe]

Mi Michael,

The resource you linked to, [Snippet] GetClosestWidget, has some methods I'd recommend borrowing from. If your algorithm is better, his will still benchmark much faster than yours becuase of the overhead of the threads created by vJass's Function Interfaces and WarCraft 3's "Filter" callbacks.

FirstOfGroup loops will always be significantly faster than passing the Filter to GroupEnumUnits. With one of the later WarCraft 3 patches, there is even a "GroupGetUnitAt" native (name might be slightly different) which removes the overhead of removing the units from the group during the loop.

Lastly (nitpicking here), while there might be a case for "local" declaration at the top of a function or a "return" statement at the bottom of a function to be un-indented or mildly-indented, the if/else statements should get indented like anything else within the function.

 

[Michael Peppers]

Mi Michael,

The resource you linked to, [Snippet] GetClosestWidget, has some methods I'd recommend borrowing from. If your algorithm is better, his will still benchmark much faster than yours becuase of the overhead of the threads created by vJass's Function Interfaces and WarCraft 3's "Filter" callbacks.

FirstOfGroup loops will always be significantly faster than passing the Filter to GroupEnumUnits. With one of the later WarCraft 3 patches, there is even a "GroupGetUnitAt" native (name might be slightly different) which removes the overhead of removing the units from the group during the loop.

I'll look into that whole aspect better, although GetClosestWidget's Unit functions use plenty of GroupEnumUnits in a similar way too.

 

[Bribe]

Upon further evaluation, the function interfaces have a minimal performance impact if the user doesn't have need of that API. Approved.