Snippet GetNearestUnit

Dirac

22710180
The fastest, easiest and with more flexible way to retrieve the nearest unit from a point

JASS:
library GetNearestUnit /* v1.1.1

*/uses/*
*/  MergeSort           /*  thehelper.net/forums/showthread.php/168621-MergeSort
*/  LinkedListModule    /*  thehelper.net/forums/showthread.php/168775-LinkedListModule

***********************************************************************
*
*   function GetNearestUnit takes real x, real y, boolexpr filter returns unit
*   function GetFarthestUnit takes real x, real y, boolexpr filter returns unit
*
*   function GetNearestUnitEx takes real x, real y, real range, boolexpr filter, integer i returns unit
*   function GetFarthestUnitEx takes real x, real y, real range, boolexpr filter, integer i returns unit
*       -   The extra integer argument skips that many units in the
*       -   list of near units.
*       -   Ex: If takes "2" then it would return the second nearest
*       -   unit.
*
***********************************************************************
*
*   HOW TO USE:
*
*   function SomeFilter takes nothing returns boolean
*       return GetUnitTypeId(GetFilterUnit())=='hfoo'
*   endfunction
*
*   call GetNearestUnit(0,0,Filter(function SomeFilter)
*
*   -   In the example above the script would only pick the closest
*   -   footman from the point 0,0
*
**********************************************************************/

    globals
        //*********************************************************************
        //  Default circumference pick range for non extended functions.
        private constant real DEFAULT_RANGE = 2000
    endglobals

    private struct List extends array
        implement LinkedList
        
        unit unit
        real distance
        
        //! runtextmacro MERGE_SORT("sort","v1.distance>v2.distance")
        
        static method for takes real x, real y, real r, boolexpr c returns nothing
            local List node
            local unit e
            call GroupEnumUnitsInRange(bj_lastCreatedGroup,x,y,r,c)
            loop
                set e = FirstOfGroup(bj_lastCreatedGroup)
                exitwhen e==null
                set node = List.allocate()
                set node.unit = e
                set node.distance = (GetUnitX(e)-x)*(GetUnitX(e)-x)+(GetUnitY(e)-y)*(GetUnitY(e)-y)
                call base.insertNode(node)
                call GroupRemoveUnit(bj_lastCreatedGroup,e)
            endloop
            call sort(base)
            set e = null
        endmethod
        
    endstruct

    function GetNearestUnitEx takes real x, real y, real r, boolexpr c, integer i returns unit
        local List this = List.base
        call List.for(x,y,r,c)
        loop
            set this = this.next
            set i = i-1
            exitwhen i==0 or this.head
        endloop
        call List.base.clearNode()
        return this.unit
    endfunction
    
    function GetFarthestUnitEx takes real x, real y, real r, boolexpr c, integer i returns unit
        local List this = List.base
        call List.for(x,y,r,c)
        loop
            set this = this.prev
            set i = i-1
            exitwhen i==0 or this.head
        endloop
        call List.base.clearNode()
        return this.unit
    endfunction
    
    function GetNearestUnit takes real x, real y, boolexpr c returns unit
        return GetNearestUnitEx(x,y,DEFAULT_RANGE,c,1)
    endfunction
    
    function GetFarthestUnit takes real x, real y, boolexpr c returns unit
        return GetFarthestUnitEx(x,y,DEFAULT_RANGE,c,1)
    endfunction

endlibrary
 

Laiev

Hey Listen!!
Please, do this:
JASS:
library GetNearestUnit /* v1.1.0

*/uses/*
*/  MergeSort           /*  thehelper.net/forums/showthread.php/168621-MergeSort
*/  LinkedListModule    /*  thehelper.net/forums/showthread.php/168775-LinkedListModule

***********************************************************************
*
*   function GetNearestUnit takes real x, real y, boolexpr filter returns unit
*   function GetFarthestUnit takes real x, real y, boolexpr filter returns unit
*
*   function GetNearestUnitEx takes real x, real y, real r, boolexpr filter, integer i returns unit
*   function GetFarthestUnitEx takes real x, real y, real r, boolexpr filter, integer i returns unit
*       -   The extra integer argument skips that many units in the
*       -   list of near units.
*       -   Ex: If takes "2" then it would return the second nearest
*       -   unit.
*       -   The extra real argument is the range to pick unit
*       -   return null if no unit is picked.
***********************************************************************
*
*   HOW TO USE:
*
*   function SomeFilter takes nothing returns boolean
*       return GetUnitTypeId(GetFilterUnit())=='hfoo'
*   endfunction
*
*   call GetNearestUnit(0,0,Filter(function SomeFilter)
*
*   -   In the example above the script would only pick the closest
*   -   footman from the point 0,0
*
**********************************************************************/

    globals
        //*********************************************************************
        //  Will not be used on Ex's functions
        private constant real DEFAULT_RANGE = 99999.
    endglobals

    private struct List extends array
        implement LinkedList
        
        unit unit
        real distance
        
        //! runtextmacro MERGE_SORT("sort","v1.distance>v2.distance")
        
        static method for takes real x, real y, real r, boolexpr c returns thistype
            local List this = List.createNode()
            local List node
            local unit e
            call GroupEnumUnitsInRange(bj_lastCreatedGroup,x,y,r,c)
            loop
                set e = FirstOfGroup(bj_lastCreatedGroup)
                exitwhen e==null
                set node = List.allocate()
                set node.unit = e
                set node.distance = (GetUnitX(e)-x)*(GetUnitX(e)-x)+(GetUnitY(e)-y)*(GetUnitY(e)-y)
                call this.insertNode(node)
                call GroupRemoveUnit(bj_lastCreatedGroup,e)
            endloop
            call sort(this)
            return this
        endmethod
        
    endstruct

    function GetNearestUnitEx takes real x, real y, real r, boolexpr c, integer i returns unit
        local List this = List.for(x,y,r,c)
        local unit e
        loop
            set this = this.next
            set i = i-1
            exitwhen i==0 or this.head
        endloop
        set e = this.unit
        call this.flushNode()
        return e
    endfunction
    
    function GetFarthestUnitEx takes real x, real y, real r, boolexpr c, integer i returns unit
        local List this = List.for(x,y,r,c)
        local unit e
        loop
            set this = this.prev
            set i = i-1
            exitwhen i==0 or this.head
        endloop
        set e = this.unit
        call this.flushNode()
        return e
    endfunction
    
    function GetNearestUnit takes real x, real y, boolexpr c returns unit
        local List this = List.for(x,y,DEFAULT_RANGE,c)
        local unit e = this.next.unit
        call this.flushNode()
        return e
    endfunction
    
    function GetFarthestUnit takes real x, real y, boolexpr c returns unit
        local List this = List.for(x,y,DEFAULT_RANGE,c)
        local unit e = this.prev.unit
        call this.flushNode()
        return e
    endfunction

endlibrary
 

Sgqvur

FullOfUltimateTruthsAndEt ernalPrinciples, i.e shi
Why would that be any faster than a function that inlines: the grouping, then iterates over every unit and calculates the distance and thus finds the closes/farthest unit? Function calls take time, and ones with arguments take even more time =), if speed is what you're aming for.
 

muzk

Member
Why not just:
JASS:
globals
    private constant real MAX_DIST_POW = 99999999
endglobals

function GetNearestUnit takes real x, real y,real r, boolexpr c returns unit
    local unit u
    local unit e
    local real du=MAX_DIST_POW
    local real de
    call GroupEnumUnitsInRange(bj_lastCreatedGroup,x,y,r,c)
    loop
        set e=FirstOfGroup(bj_lastCreatedGroup)
        exitwhen e==null
        set de=(GetUnitX(e)-x)*(GetUnitX(e)-x)+(GetUnitY(e)-y)*(GetUnitY(e)-y)
        if de<du then
            set u=e
            set du=d
        endif
        call GroupRemoveUnit(bj_lastCreatedGroup,e)
    endloop
    return u
endfunction
 

NoobImbaPro

You can change this now in User CP.
there should be another way to find the closest unit.
You don't save anything from "speed" of code.
GroupEnumUnitsInRange(bj_lastCreatedGroup,x,y,r,c) forces to get units from a certain area, which searches for all units and then puts them into a group and then you search for every unit of them to find the closest.

An A.I.D.S. like group enumeration and then a search through every single unit is faster. You save an extra search.

Although there is a graphs node solution with Dijkstra algorithm but I don't know if it's faster.
 

Dirac

22710180
there should be another way to find the closest unit.
You don't save anything from "speed" of code.
GroupEnumUnitsInRange(bj_lastCreatedGroup,x,y,r,c) forces to get units from a certain area, which searches for all units and then puts them into a group and then you search for every unit of them to find the closest.

An A.I.D.S. like group enumeration and then a search through every single unit is faster. You save an extra search.

Although there is a graphs node solution with Dijkstra algorithm but I don't know if it's faster.
I already conducted this using Nestharus's Unit List and it's by far slower.
The native is the best way to pick units.
 

Sgqvur

FullOfUltimateTruthsAndEt ernalPrinciples, i.e shi
>I already conducted this using Nestharus's Unit List and it's by far slower.
The native is the best way to pick units.

I agree.

> which searches for all units and then puts them into a group
How do you know that? You've seen the code?

Even if that's the case it is still native code (C++ probably) vs interpreted (Jass2 probably) =).
 

NoobImbaPro

You can change this now in User CP.
Yes i've seen it, but you may be right. the coding is in C, which is really faster than jass2.
The native takes all units in game and checks their range, if it's the range you've put or lower the unit goes in group. The first unit must be the closest one i think, check it.
 

muzk

Member
Why not just:
JASS:
globals
    private constant real MAX_DIST_POW = 99999999
endglobals

function GetNearestUnit takes real x, real y,real r, boolexpr c returns unit
    local unit u
    local unit e
    local real du=MAX_DIST_POW
    local real de
    call GroupEnumUnitsInRange(bj_lastCreatedGroup,x,y,r,c)
    loop
        set e=FirstOfGroup(bj_lastCreatedGroup)
        exitwhen e==null
        set de=(GetUnitX(e)-x)*(GetUnitX(e)-x)+(GetUnitY(e)-y)*(GetUnitY(e)-y)
        if de<du then
            set u=e
            set du=d
        endif
        call GroupRemoveUnit(bj_lastCreatedGroup,e)
    endloop
    return u
endfunction
?
 

Sgqvur

FullOfUltimateTruthsAndEt ernalPrinciples, i.e shi
@muzik
Yes this is basically the fastest way to do it (That I know of), although you are forgetting to null the e variable so it actually leaks [not a big deal though =)]

Well, actually the fastest way to do it, that I know of would be this:

JASS:
globals
    group G0 = CreateGroup()
    unit  U0 = null
    unit  U1 = null
    real  R0
    real  R1
    real  R2
    real  R3
endglobals

//! textmacro CLOSEST_UNIT takes x, y, range, filter, returns_unit
    set R0 = 9999999
    call GroupEnumUnitsInRange(G0, $x$, $y$, $range$, $filter$)

    loop
        set U0 = FirstOfGroup(G0)
        exitwhen U1 == null
        
        set R1 = $x$ - GetUnitX(U0)
        set R2 = $y$ - GetUnitY(U0)
        set R3 = R1 * R1 + R2 * R2

        if R0 > R3 then
            set R0 = R3
            set U1 = U0
        endif

        call GroupRemoveUnit(G0, U0)
    endloop
            
    set $returns_unit$ = U1
//! endtextmacro


I.e to inline even the call to the function =):

An example use might be:
JASS:
local unit u
//! runtextmacro CLOSEST_UNIT("GetUnitX(Hero[0]), "GetUnitY(Hero[0]", "RANGE", "null", "u")
call KillUnit(u) // actually kills Hero[0] because the filter is null =)
 

luorax

Invasion in Duskwood
@muzik
Yes this is basically the fastest way to do it (That I know of), although you are forgetting to null the e variable so it actually leaks [not a big deal though =)]
"u" leaks as well :p That's why using a global variable to return the nearest unit is better.
 

muzk

Member
Oh yeah, I forgot about "u" leak, using a global may solve it.
Not necesary null "e", because loop condition is exitwhen e==null, so e is null when loop ends.
 

Dirac

22710180
I just went all full retard when i realize there was no need for that local, or a globals to replace it. The List.unit array's value isn't lost when the list is flushed, mild brain blackout I had there.

Update v1.1.1
-Improved Code efficiency

I'm sticking with mergesort because I really would like to be able to know the 2nd, 3rd or any unit in the list.
The speed difference is so minimal it's not even worth the debate
 

Sgqvur

FullOfUltimateTruthsAndEt ernalPrinciples, i.e shi
>I'm sticking with mergesort because I really would like to be able to know the 2nd, 3rd or any unit in the list.

If you don't mind can you give me an example where based on the distance the 2nd, 3rd, etc. unit is actually needed?


>The speed difference is so minimal it's not even worth the debate
=) Well... I did a little benchmark 1000 calls for all and the results were (same arguments were passed for all cases of course):

Dirac's: time = 0.872
muzk's: time = 0.178
inlined: time = 0.134 (inlined using textmacro and only two calls to the GetUnitX/Y natives)

So no offense but yours is actually 5 to 6 times slower, but you are probably right it's not worth the debate =).
 

Dirac

22710180
If you don't mind can you give me an example where based on the distance the 2nd, 3rd, etc. unit is actually needed?
Use your imagination, maybe an ability that deals decaying AoE damage to nearby units, starting by 300 to the closest, 270 for the second, 240 for the third and so on.
 

luorax

Invasion in Duskwood
An instant casted Chain Lightning which jumps thorugh each unit, from the closest to the farthest.
 
General chit-chat
Help Users
  • No one is chatting at the moment.
  • C Cherry.Grove:
    My boyfriend is super into Bethesda modding so I'm probably going to join him in that for a bit, then move on to making mobile/browser games.
  • C Cherry.Grove:
    I mostly just want to look at my old projects because I know I posted uploads on here somewhere.
  • C Cherry.Grove:
    My one game was basically Among Us but you sabotaged an entire medieval city simulated drastically inefficiently with dynamic NPCs :S
  • C Cherry.Grove:
    of course I never finished it x D
  • jonas jonas:
    xD
  • jonas jonas:
    I think you can still run the original game, just there's a chance your map won't work with the newer patches
  • jonas jonas:
    what development framework have you been looking at for mobile development?
  • jonas jonas:
    I'm currently creating (as a hobby) a space invaders like game for mobile using Xamarin, after starting a few larger projects that I also may not have finished :rolleyes::p
  • The Helper The Helper:
    Awesome! you should look at the Atari VCS platform it does not have a huge user base but the one it has is super active at around 11k and they have no games in there store
  • The Helper The Helper:
    basically it is linux
  • The Helper The Helper:
    OMG it is BanLord as Blackveiled on the forum
  • The Helper The Helper:
    what is up buddy
  • jonas jonas:
    thanks for the tip, that sounds cool. Never heard about the VCS before but seems like it should be a good match
  • tom_mai78101 tom_mai78101:
    The winter vacation left a toll on me. I missed staying up late and sleeping in late.
  • C Cherry.Grove:
    i haven't looked into it yet
  • C Cherry.Grove:
    If I could use something Python compatible it would save me some learning
  • C Cherry.Grove:
    But Unity might be easiest
  • C Cherry.Grove:
    looking at old posts here makes me happy. Makes me be all like "wow I was pretty smart in 2009"
  • C Cherry.Grove:
    mostly failing at life through adulthood really demotivated me for a while
  • C Cherry.Grove:
    ....what I don't get is why the fuck they would force us to permanently convert to a version of the game everyone fucking hated : \
  • C Cherry.Grove:
    Raid Shadow Legends texture pack smh
  • jonas jonas:
    Most people fail at life throughout their adulthood. Sometimes we get to learn from it. Usually it just feels like crap.
    +1
  • The Helper The Helper:
    What does not kill you makes you stronger is what they say
  • C Cherry.Grove:
    for real! :cool:

    Staff online

    Members online

    Affiliates

    Hive Workshop NUON Dome
    Top